Software Engineering Body of Knowledge (v3) (2014) (811503), страница 73
Текст из файла (страница 73)
However, the range is asingle element {8}. This qualifies as an exampleof a function even if all the x-values are mappedto the same y-value. Here, each x-value is distinctand hence the function is well behaved. RelationB may be represented by the equation y = 8.The characteristic of a function may be verifiedusing a vertical line test, which is stated below:Given the graph of a relation, if one can drawa vertical line that crosses the graph in more thanone place, then the relation is not a function.Figure 14.7. Vertical Line Test for FunctionIn this example, both lines L1 and L2 cut thegraph for the relation thrice. This signifies thatfor the same x-value, there are three differenty-values for each of case. Thus, the relation is nota function.Mathematical Foundations 14-52. Basic Logic[1*, c1]2.1. Propositional LogicA proposition is a statement that is either trueor false, but not both.
Let’s consider declarativesentences for which it is meaningful to assigneither of the two status values: true or false. Someexamples of propositions are given below.1.The sun is a star2.Elephants are mammals.3.2 + 3 = 5.However, a + 3 = b is not a proposition, as it isneither true nor false. It depends on the values ofthe variables a and b.The Law of Excluded Middle: For every proposition p, either p is true or p is false.The Law of Contradiction: For every proposition p, it is not the case that p is both true and false.Propositional logic is the area of logic thatdeals with propositions.
A truth table displaysthe relationships between the truth values ofpropositions.A Boolean variable is one whose value is eithertrue or false. Computer bit operations correspondto logical operations of Boolean variables.The basic logical operators including negation(¬ p), conjunction (p ∧ q), disjunction (p ∨ q),exclusive or (p ⊕ q), and implication (p → q) areto be studied. Compound propositions may beformed using various logical operators.A compound proposition that is always true is atautology. A compound proposition that is alwaysfalse is a contradiction. A compound propositionthat is neither a tautology nor a contradiction is acontingency.Compound propositions that always have thesame truth value are called logically equivalent(denoted by ≡).
Some of the common equivalences are:Identity laws:p ∧ T ≡ pp∨F≡pDomination laws:p ∨ T ≡ Tp∧F≡FIdempotent laws:p ∨ p ≡ pp∧p≡pDouble negation law:¬ (¬ p) ≡ pCommutative laws:p ∨ q ≡ q ∨ p p ∧ q ≡ q ∧ pAssociative laws:(p ∨ q) ∨ r ≡ p ∨ (q ∨ r)(p ∧ q) ∧ r ≡ p ∧ (q ∧ r)Distributive laws:p ∨ (q ∧ r) ≡ (p ∨ q) ∧ (p ∨ r)p ∧ (q ∨ r) ≡ (p ∧ q) ∨ (p ∧ r)De Morgan’s laws:¬ (p ∧ q) ≡ ¬ p ∨ ¬ q¬ (p ∨ q) ≡ ¬ p ∧ ¬ q2.2. Predicate LogicA predicate is a verb phrase template thatdescribes a property of objects or a relationshipamong objects represented by the variables. Forexample, in the sentence, The flower is red, thetemplate is red is a predicate. It describes theproperty of a flower. The same predicate may beused in other sentences too.Predicates are often given a name, e.g., “Red”or simply “R” can be used to represent the predicate is red. Assuming R as the name for the predicate is red, sentences that assert an object is of thecolor red can be represented as R(x), where x represents an arbitrary object.
R(x) reads as x is red.Quantifiers allow statements about entire collections of objects rather than having to enumerate the objects by name.The Universal quantifier ∀x asserts that a sentence is true for all values of variable x.For example, ∀x Tiger(x) → Mammal(x)means all tigers are mammals.The Existential quantifier ∃x asserts that a sentence is true for at least one value of variable x.For example, ∃x Tiger(x) → Man-eater(x) meansthere exists at least one tiger that is a man-eater.Thus, while universal quantification usesimplication, the existential quantification naturally uses conjunction.14-6 SWEBOK® Guide V3.0A variable x that is introduced into a logicalexpression by a quantifier is bound to the closestenclosing quantifier.A variable is said to be a free variable if it is notbound to a quantifier.Similarly, in a block-structured programminglanguage, a variable in a logical expression refersto the closest quantifier within whose scope itappears.For example, in ∃x (Cat(x) ∧ ∀x (Black(x))), xin Black(x) is universally quantified.
The expression implies that cats exist and everything isblack.Propositional logic falls short in representingmany assertions that are used in computer science and mathematics. It also fails to compareequivalence and some other types of relationshipbetween propositions.For example, the assertion a is greater than1 is not a proposition because one cannot inferwhether it is true or false without knowing thevalue of a. Thus, propositional logic cannot dealwith such sentences. However, such assertionsappear quite often in mathematics and we wantto infer on those assertions. Also, the patterninvolved in the following two logical equivalences cannot be captured by propositionallogic: “Not all men are smokers” and “Some mendon’t smoke.” Each of these two propositionsis treated independently in propositional logic.There is no mechanism in propositional logic tofind out whether or not the two are equivalent toone another. Hence, in propositional logic, eachequivalent proposition is treated individuallyrather than dealing with a general formula thatcovers all equivalences collectively.Predicate logic is supposed to be a more powerful logic that addresses these issues.
In a sense,predicate logic (also known as first-order logicor predicate calculus) is an extension of propositional logic to formulas involving terms andpredicates.3. Proof Techniques[1*, c1]A proof is an argument that rigorously establishesthe truth of a statement. Proofs can themselves berepresented formally as discrete structures.Statements used in a proof include axiomsand postulates that are essentially the underlyingassumptions about mathematical structures, thehypotheses of the theorem to be proved, and previously proved theorems.A theorem is a statement that can be shown tobe true.A lemma is a simple theorem used in the proofof other theorems.A corollary is a proposition that can be established directly from a theorem that has beenproved.A conjecture is a statement whose truth valueis unknown.When a conjecture’s proof is found, the conjecture becomes a theorem.
Many times conjecturesare shown to be false and, hence, are not theorems.3.1. Methods of Proving TheoremsDirect Proof. Direct proof is a technique to establish that the implication p → q is true by showingthat q must be true when p is true.For example, to show that if n is odd then n2−1is even, suppose n is odd, i.e., n = 2k + 1 for someinteger k:∴ n2 = (2k + 1)2 = 4k2 + 4k + 1.As the first two terms of the Right Hand Side(RHS) are even numbers irrespective of the valueof k, the Left Hand Side (LHS) (i.e., n2) is an oddnumber. Therefore, n2−1 is even.Proof by Contradiction. A proposition p is trueby contradiction if proved based on the truth ofthe implication ¬ p → q where q is a contradiction.For example, to show that the sum of 2x + 1and 2y − 1 is even, assume that the sum of 2x + 1and 2y − 1is odd.
In other words, 2(x + y), whichis a multiple of 2, is odd. This is a contradiction.Hence, the sum of 2x + 1 and 2y − 1 is even.An inference rule is a pattern establishing thatif a set of premises are all true, then it can bededuced that a certain conclusion statement istrue. The reference rules of addition, simplification, and conjunction need to be studied.Proof by Induction. Proof by induction is donein two phases.
First, the proposition is established to be true for a base case—typically for theMathematical Foundations 14-7positive integer 1. In the second phase, it is established that if the proposition holds for an arbitrarypositive integer k, then it must also hold for thenext greater integer, k + 1. In other words, proofby induction is based on the rule of inference thattells us that the truth of an infinite sequence ofpropositions P(n), ∀n ∈ [1 … ∞] is establishedif P(1) is true, and secondly, ∀k ∈ [2 ... n] if P(k)→ P(k + 1).It may be noted here that, for a proof by mathematical induction, it is not assumed that P(k) istrue for all positive integers k.
Proving a theorem or proposition only requires us to establishthat if it is assumed P(k) is true for any arbitrarypositive integer k, then P(k + 1) is also true. Thecorrectness of mathematical induction as a validproof technique is beyond discussion of the current text. Let us prove the following propositionusing induction.Proposition: The sum of the first n positive oddintegers P(n) is n2.Basis Step: The proposition is true for n = 1 asP(1) = 12 = 1.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
