Matematika | Logika » Logic and Proofs

Source: http://www.doksinet MATH 1130 1 Discrete Structures Chapter I – Logic and Proofs Propositions A proposition is a statement that is either true (T) or false (F), but or both. Examples Propositions: 1. I am a man 2. I am taller than 170 cm 3. You are studying in Baptist U 4. 1 + 1 = 3 Not propositions: 1. How are you? 2. Go to catch the dog 3. I like this colour Negation of a Proposition Let p be a proposition. The statement “It is not the case that p” is another proposition, called the negation of p. The negation of p is denoted by ¬p and read “not p”. Example P: ¬p : “It is a sunny day.” “It is not the case that it is a sunny day.”, or simply “It is not a sunny day” Truth Table A truth table displays the relationships between the truth values of propositions. Truth tables are especially valuable in the determination of the truth values of propositions constructed from simpler propositions. Reference: K.H Rosen, Discrete Mathematics and Its

Applications, 5th Edition, McGraw-Hill, 2003 Daricks Chan Source: http://www.doksinet MATH 1130 2 Discrete Structures Example The truth table for the negation of a proposition p ¬p T F F T Logic Operators (Connectives) Conjunction Let p and q be propositions. The proposition “p and q”, denoted by p ∧ q , is the proposition that is true when both p and q are true and is false otherwise. The proposition p ∧ q is called the conjunction of p and q. The truth table for the conjunction of p and q p q p∧q T T T T F F F T F F F F Disjunction Let p and q be propositions. The proposition “p or q”, denoted by p ∨ q , is the proposition that is false when p and q are both false and true otherwise. The proposition p ∨ q is called the disjunction of p and q. The truth table for the disjunction of p and q p q p∨q T T T T F T F T T F F F Reference: K.H Rosen, Discrete Mathematics and Its Applications, 5th Edition, McGraw-Hill, 2003

Daricks Chan Source: http://www.doksinet MATH 1130 3 Exclusive Or Let p and q be propositions. Discrete Structures The exclusive or of p and q, denoted by p ⊕ q , is the proposition that is true when exactly one of p and q is true and is false otherwise. The truth table for the exclusive or of p and q p q p⊕q T T F T F T F T T F F F Conditional Propositions Implication Let p and q be propositions. The implication p q is the proposition that is false when p is true and q is false and true otherwise. In this implication, p is called the hypothesis and q is called the conclusion. The truth table for the implication p q Remarks: I) II) p q pq T T T T F F F T T F F T Equivalent expressions of implication 1. if p, then q 2. p is sufficient for q 3. p implies q 4. p only if q 5. q is necessary for p Related Implications q p is called the converse of p q 1. 2. ¬q ¬p is called the contrapositive of p q Reference: K.H Rosen, Discrete

Mathematics and Its Applications, 5th Edition, McGraw-Hill, 2003 Daricks Chan Source: http://www.doksinet MATH 1130 4 Biconditional Let p and q be propositions. Discrete Structures The biconditional p ↔ q is the proposition that is true when p and q In this biconditional, p is necessary and sufficient have the same truth values and is false otherwise. for q, or p if and only if q. The truth table for the biconditional p ↔ q p q p↔q T T T T F F F T F F F T Translating English Sentences Example He will not be charged (c) if he is handsome (h) or he is muscular (m). ⇓ (h ∨ m ) ¬c h m h∨m ¬c c T T T F F T T T T T T F T F T F F T T F T T T F F T T F F T F T T T T F F F F T F T F F F T T F Bit String A bit string is a sequence of zero or more bits. The length of a bit string is the number of bits in the string. Example 0100100111 is a 10-bit string. Reference: K.H Rosen, Discrete Mathematics and

Its Applications, 5th Edition, McGraw-Hill, 2003 Daricks Chan Source: http://www.doksinet MATH 1130 5 Discrete Structures Bitwise OR, bitwise AND and bitwise XOR We define the bitwise OR, bitwise AND and bitwise XOR of two strings of the same length to be the strings that have as their bits the OR, AND and XOR of the corresponding bits in the two strings, respectively. Example 01 1011 0110 11 0001 1101 11 1011 1111 01 0001 0100 10 1010 1011 bitwise OR bitwise AND bitwise XOR Logical equivalence Tautology, Contradiction and Contingency A compound proposition that is always true, no matter what the truth values of the propositions that occur in it, is called a tautology. A compound proposition that is always false is called a contradiction. Finally, a proposition that is neither a tautology nor a contradiction is called a contingency. Truth table of examples of a tautology and a contradiction p ¬p p ∨ ¬p p ∧ ¬p T F T F F T T F Logically Equivalent The

propositions p and q are called logically equivalent if p ↔ q is a tautology. The notation p ⇔ q denotes that p and q are logically equivalent. Reference: K.H Rosen, Discrete Mathematics and Its Applications, 5th Edition, McGraw-Hill, 2003 Daricks Chan Source: http://www.doksinet MATH 1130 6 Discrete Structures Example The following truth table shows that the compound propositions ¬( p ∨ q ) and ¬p ∧ ¬q are logically equivalent. p q p∨q ¬( p ∨ q ) ¬p ¬q ¬p ∧ ¬q T T T F F F F T F T F F T F F T T F T F F F F F T T T T Exercise Complete the following truth table to show that ¬p ∨ q and p q are logically equivalent. p q T T T F F T F F ¬p ¬p ∨ q pq Logical Equivalences Equivalence p∧T ⇔ p p∨F⇔ p p∨T ⇔T p∧F ⇔ F p∧ p⇔ p p∨ p ⇔ p Name Identity laws Domination laws Idempotent laws ¬(¬p ) ⇔ p p∨q ⇔ q∨ p Double negative law p∧q ⇔ q∧ p Commutative laws ( p ∨ q

) ∨ r ⇔ p ∨ (q ∨ r ) ( p ∧ q ) ∧ r ⇔ p ∧ (q ∧ r ) p ∨ (q ∧ r ) ⇔ ( p ∨ q ) ∧ ( p ∨ r ) p ∧ (q ∨ r ) ⇔ ( p ∧ q ) ∨ ( p ∧ r ) ¬( p ∧ q ) ⇔ ¬p ∨ ¬q ¬( p ∨ q ) ⇔ ¬p ∧ ¬q Associative laws Distributive laws De Morgan’s laws Reference: K.H Rosen, Discrete Mathematics and Its Applications, 5th Edition, McGraw-Hill, 2003 Daricks Chan Source: http://www.doksinet MATH 1130 7 Discrete Structures p ∨ ¬p ⇔ T p ∧ ¬p ⇔ F p q ⇔ ¬p ∨ q Predicates and Quantifiers Predicates In statements involving variables, there are two parts – the variable (is the subject of the statement) and predicate (refers to a property that the subject can have). Example In the statement: “ x > 3 ” (x is greater than 3) “x” is the variable and “is greater than 3” is the predicate. Let P ( x ) denote the statement “ x > 3 ”. The value of P (4 ) is true and the value of P (2 ) is false. Universe of Discourse Many

mathematical statements assert that a property is true for all values of a variable in a particular domain, called the universe of discourse. Universal Quantification and Universal Quantifier The universal quantification of P ( x ) is the proposition: “ P ( x ) is true for all values of x in the universe of discourse”, and is denoted by ∀x P ( x ) for all (every) x P ( x ) . Here, ∀ is called the universal quantifier. Existential Quantification and Existential Quantifier The existential quantification of P( x ) is the proposition: “There exists an element x in the universe of discourse such that P ( x ) is true”, and is denoted by ∃x P ( x ) for some x P ( x ) . Here, ∃ is called existential quantifier. Statement ∀x P ( x ) ∃x P( x ) When True? P ( x ) is true for every x. There is an x for which P ( x ) is true. When False? There is an x for which P ( x ) is false. P ( x ) is false for every x. Reference: K.H Rosen, Discrete Mathematics and Its

Applications, 5th Edition, McGraw-Hill, 2003 Daricks Chan Source: http://www.doksinet MATH 1130 8 Discrete Structures Examples Translating logical statements into English I) ∀x (C ( x ) ∨ ∃y (C ( y ) ∧ F ( x, y ))) where C (x ) is “x has a computer”, F ( x, y ) is “x and y are friends”, and the universe of discourse for both x and y is the set of all students in this class. Every student in your school has a computer or has a friend who has a computer. II) ∃x∀y∀z (((F ( x, y ) ∧ F ( x, z ) ∧ ( y ≠ z )) ¬F ( y, z ))) where F (a, b ) means a and b are friends and the universe of discourse for x, y and z is the set of all students in your school. There is a student none of whose friends are also friends with each other. Translating sentences into logical expressions III) Some student in this class has visited Mexico. Let M ( x ) be the statement “x has visited Mexico”. ∃xM ( x ) , the universe of discourse for x is the set of all the

students in this class. IV) Every student in this class has visited either Canada or Mexico. Let M ( x ) be the statement “x has visited Mexico” and C (x ) be the statement “x has visited Canada”. ∀x(C ( x ) ∨ M ( x )) , the universe of discourse for x is the set of all the students in this class. V) If somebody is female and is a parent, then this person is someone’s mother Let F (x ) be the statement “x is female”, P(x ) be the statement “x is a parent”, and M ( x, y ) be the statement “x is the mother of y”. ∀x((F ( x ) ∧ P ( x )) ∃yM ( x, y )) , the universe of discourse for x and y is the set of all people. Reference: K.H Rosen, Discrete Mathematics and Its Applications, 5th Edition, McGraw-Hill, 2003 Daricks Chan Source: http://www.doksinet MATH 1130 9 Discrete Structures VI) lim f ( x ) = L (For every real number ε > 0 , there exists a real number δ > 0 such that x a f ( x ) − L < ε whenever 0 < x − a < δ .

∀ε∃δ∀x(0 < x − a < δ f ( x ) − L < ε ) , the universe of discourse for ε and δ is the set of positive real numbers, and that of x is the set of real numbers, and a is a real constant. Negations The negation of a universal quantification is an existential quantification. ¬∀xP( x ) ⇔ ∃x¬P ( x ) The negation of an existential quantification is a universal quantification. ¬∃xQ(x ) ⇔ ∀x¬Q( x ) Method of Proofs Theorems A theorem is a statement that can be shown to be true. Proofs We demonstrate that a theorem is true with a sequence of statements that form an argument, called a proof. Axioms and Postulates Statements used in a proof include axioms and postulates, which are the underlying assumptions about mathematical structures, the hypotheses of the theorem to be proved, and previously proved theorems. Lemmas A lemma is a simple theorem used in the proof of other theorems. Corollaries A corollary is a proposition that can be established

directly from a theorem that has been proved. Conjectures A conjecture is a statement whose truth value is unknown. Reference: K.H Rosen, Discrete Mathematics and Its Applications, 5th Edition, McGraw-Hill, 2003 Daricks Chan Source: http://www.doksinet MATH 1130 Remark: 10 Discrete Structures When a proof of a conjecture is found, the conjecture becomes a theorem. Many times conjectures are shown to be false, so they are not theorems. Rules of inference The rules of inference, which are the means used to draw conclusions from other assertions, tie together the steps of a proof. Rule of Inference Tautology Name p ∴p∨q p ( p ∨ q) Addition p∧q ∴p p∧q p Simplification p q ∴p∧q (( p ) ∧ (q )) ( p ∧ q ) Conjunction p pq ∴q ( p ∧ ( p q )) q Modus ponens ¬q pq ∴ ¬p (¬q ∧ ( p q )) ¬p Modus tollens pq qr ∴pr (( p q ) ∧ (q r )) ( p r ) Hypothetical syllogism p∨q ¬p ∴q (( p ∨ q ) ∧ ¬p ) q Disjunctive

syllogism Reference: K.H Rosen, Discrete Mathematics and Its Applications, 5th Edition, McGraw-Hill, 2003 Daricks Chan Source: http://www.doksinet MATH 1130 11 Discrete Structures Examples I) Show that the hypotheses “It is not sunny this afternoon and it is colder than yesterday”, “We will go swimming only if it is sunny”, “If we do not go swimming, then we will take a canoe trip”, and “If we take a canoe trip, then we will be home by sunset” lead to the conclusion “We will be home by sunset”. Let p: q: r: s: t: It is sunny this afternoon It is colder than yesterday We will go swimming We will take a canoe trip We will be home by sunset Hypotheses “It is not sunny this afternoon and it is colder than yesterday” “We will go swimming only if it is sunny” “If we do not go swimming, then we will take a canoe trip” “If we take a canoe trip, then we will be home by sunset” Conclusion “We will be home by sunset” Step 1. ¬p ∧ q ¬p ∧ q

rp ¬r s st t Reason Hypothesis 2. ¬p Simplification using Step 1 3. rp Hypothesis 4. ¬r Modus tollens using Steps 2 and 3 5. ¬r s Hypothesis 6. s Modus ponens using Steps 4 and 5 7. st Hypothesis 8. t Modus ponens using Steps 6 and 7 Reference: K.H Rosen, Discrete Mathematics and Its Applications, 5th Edition, McGraw-Hill, 2003 Daricks Chan Source: http://www.doksinet MATH 1130 II) 12 Discrete Structures Show that the hypotheses “If you send me an email message, then I will finish writing the program”, “If you do not send me an email message, then I will go to sleep early”, and “If I go to sleep early, then I will wake up feeling refreshed” lead to the conclusion “If I do not finish writing the program, then I will wake up feeling refreshed”. Let p: q: r: s: You send me an email message I will finish writing the program I will go to sleep early I will wake up feeling refreshed Hypotheses “If you send me an email message, then I

will finish writing the program” “If you do not send me an email message, then I will go to sleep early” pq ¬p r “If I go to sleep early, then I will wake up feeling refreshed” rs Conclusion “If I do not finish writing the program, then I will wake up feeling refreshed” ¬q s Step 1. pq Reason Hypothesis 2. ¬q ¬p Contrapositive of Step 1 3. ¬p r Hypothesis 4. ¬q r Hypothetical syllogism using Steps 2 and 3 5. 6. rs ¬q s Hypothesis Hypothetical syllogism using Steps 4 and 5 Fallacies Some common forms of incorrect reasoning are called fallacies. I) Fallacy of affirming the conclusion ((F T ) ∧ T ) F (( p q ) ∧ q ) p is False Reference: K.H Rosen, Discrete Mathematics and Its Applications, 5th Edition, McGraw-Hill, 2003 Daricks Chan Source: http://www.doksinet MATH 1130 13 Discrete Structures Example p: it is an apple q: it is red. It is red but it may not be an apple. II) Fallacy of denying the hypothesis ((F T )

∧ T ) F (( p q ) ∧ ¬p ) ¬q is False Example p: it is an apple q: it is red. It is not an apple but it may be red. III) Circular reasoning (F F) F ( p p) p is False Example p: it is an apple “If it is an apple, then it is an apple” is always true, even though it is not an apple. Rules of Inference for quantified statements U is the universal of discourse Rule of Inference Name ∀xP( x ) ∴ P(c ) if c ∈ U Universal instantiation P(c ) for an arbitrary c ∈ U ∴ ∀xP( x ) Universal generalization ∃xP( x ) ∴ P(c ) for some element c ∈ U Existential instantiation P(c ) for some element c ∈ U ∴ ∃xP( x ) Existential generalization Reference: K.H Rosen, Discrete Mathematics and Its Applications, 5th Edition, McGraw-Hill, 2003 Daricks Chan Source: http://www.doksinet MATH 1130 14 Discrete Structures Methods of Proving Theorems Direct Proof A proof that the implication p q is true that proceeds by showing that q must be true when

p is true. Example Show that if n is odd, then n 2 is odd. Suppose n is odd. Ie n = 2k + 1 for some integer k n 2 = (2k + 1) = 4k 2 + 4k + 1 = 4k (k + 1) + 1 , 2 is an odd number. Indirect Proof A proof that the implication p q is true that proceeds by showing that p must be false when q is false. Example Show that if n 2 is odd, then n is odd. Suppose n is even. Ie n = 2k for some integer k n 2 = (2k ) = 4k 2 , is an even number. 2 Vacuous Proof A proof that the implication p q is the based on the fact that p is false. Example Show that if 3 > 5 , then 5 > 9 . Since “ 3 > 5 ” is false, the statement “if 3 > 5 , then 5 > 9 ” is true. Reference: K.H Rosen, Discrete Mathematics and Its Applications, 5th Edition, McGraw-Hill, 2003 Daricks Chan Source: http://www.doksinet MATH 1130 15 Discrete Structures Trivial Proof A proof that the implication p q is true based on the fact that q is true. Example Show that if 5 > 3 , then 9 > 5 . Since

“ 9 > 5 ” is always true, the statement “if 5 > 3 , then 9 > 5 ” is true. Proof by Contradiction A proof that a proposition p is true based on the truth of the implication ¬p q where q is a contradiction Example Show that the sum of 2m + 1 and 2n − 1 is even. Assume the sum of 2m + 1 and 2n − 1 is odd. 2(m + n ) , a multiple of 2, is odd. This is a contradiction. Proof by Cases A proof of an implication where the hypothesis is a disjunction of propositions that shows that each hypothesis separately implies the conclusion Example Show that if n > 3 or n < −2 , then n 2 − n − 6 > 0 . Case 1 Case 2 Suppose n > 3 . n 2 − n − 6 = (n − 3)(n + 2) > (3 − 3)(3 + 2) = 0 Suppose n < −2 . n 2 > 4 n 2 − n − 6 > 4 − (− 2) − 6 = 0 Therefore, if n > 3 or n < −2 , then n 2 − n − 6 > 0 . Existence Proofs A proof of a proposition of the form ∃xP(x ) is called an existence proof. Constructive Existence

Proofs An existence proof of ∃xP(x ) given by finding an element a such that P (a ) is true is called a constructive existence proof. Reference: K.H Rosen, Discrete Mathematics and Its Applications, 5th Edition, McGraw-Hill, 2003 Daricks Chan Source: http://www.doksinet MATH 1130 16 Discrete Structures Example Show that there exists an irrational number between any two rational numbers. Let α and β be two rational numbers. With loss of generality, we may assume α < β . Let ε = β − α . Clearly, ε is also a rational number and β −α ε 1 =1> > 0⇒α < +α < β . ε 2 2 Nonconstructive Existence Proofs An existence proof of ∃xP(x ) given by not finding an element a such that P (a ) is true is called a nonconstructive existence proof. Example Show that for every positive integer n there is a prime greater than n. Let n be a positive integer. To show there is a prime greater than n, we may consider the integer n!+1 . One possibility is that

n!+1 is already prime Otherwise, n!+1 is divisible by a prime number. Clearly, n!+1 is not divisible by any number less than or equal to n Thus, the prime factor of n!+1 is greater than n. Counterexample Suppose a statement of the form ∀xP( x ) is false. We find an element a such that P (a ) is false I.e ∃x¬P ( x ) is true The element a for which P (a ) is false is called a counterexample Example Show that “ 3n + 1 is odd for all integers n” is false. For n = 3 , 3(3) + 1 = 10 is even. Therefore, “ 3n + 1 is odd for all integers n” is false Reference: K.H Rosen, Discrete Mathematics and Its Applications, 5th Edition, McGraw-Hill, 2003 Daricks Chan Source: http://www.doksinet MATH 1130 17 Discrete Structures Mathematical Induction To use prove that a statement is true for all natural numbers n by mathematical induction, we have the following three steps: 1. 2. 3. To prove the statement is true for the first (few) case(s). To assume the statement is true for n ≤

k for some k. With the induction hypothesis in step 2, to prove the statement is true for n = k + 1 . Example I) Euler’s Formula If G is a connected plane graph, then v + f = ε + 2 where v, f and e are the numbers of vertices, faces and edges of G respectively. The formula can be shown by induction on the number of faces of G. If f = 1 , then edge of G is a cut edge (a bridge) of G and so G is a tree. In this case, v = ε + 1 , and so the theorem holds We may suppose that the theorem holds for all connected plane graphs with f ≤ k , and consider a connected plane graph G having k + 1 faces. Since G has more than one face, there should be an edge e in G that is separating two faces. By taking away e from G, we may obtain G − e with v(G − e ) = v(G ) , f (G − e ) = f (G ) − 1 and ε (G − e ) = ε (G ) − 1 . Then v(G − e ) + f (G − e ) = ε (G − e ) + 2 , and so v(G ) + f (G ) = ε (G ) + 2 . IIa) Four Colour Theorem Any map can be coloured using no more than

4 colours. Remark: Any map can be represented by a simple connected plane graph. Reference: K.H Rosen, Discrete Mathematics and Its Applications, 5th Edition, McGraw-Hill, 2003 Daricks Chan Source: http://www.doksinet MATH 1130 18 Discrete Structures IIb) Five Colour Theorem This theorem can be proved by induction on the number of vertices of G. If v ≤ 5 , the theorem holds. Suppose the theorem holds for all graphs of v ≤ k and consider a graph G of k + 1 vertices. From Euler’s formula, we may deduce that the minimum degree of G (any plane graph), δ (G ) , is less than or equal to 5. Choose a vertex u in G of the minimum degree In the case d (u ) ≤ 4 , G − u is a graph of k vertices. By the induction hypothesis, G − u can be coloured with five colours, and so we may add u back and put on u a colour which is not on the adjacent vertices of u. In the case d (u ) = 5 , there should be two adjacent vertices, s and t, of u which are not adjacent. It is because the

5-complete graph is not planar Then we may merge s and t to form G − u | s ,t of k − 1 vertices. Clearly, G − u | s ,t is 5-colourable by the induction hypothesis, and the any colourings on G − u | s ,t are also valid on G − u with s and t of the same colour. Thus, on any colourings of G − u , there are at most four colours on the adjacent vertices of u in G. Then we may put on u the a colour other than those on its adjacent vertices Reference: K.H Rosen, Discrete Mathematics and Its Applications, 5th Edition, McGraw-Hill, 2003 Daricks Chan