Chapter 1 The Foundations Logic and Proofs.pdf

8/29/2024 Chapter Summary Chapter 1 Propositional Logic (1.1-1.3) The Language of Propositions Applications...

8/29/2024 Chapter Summary Chapter 1 Propositional Logic (1.1-1.3) The Language of Propositions Applications Logical Equivalences The Foundations: Logic and Predicate Logic (1.4) Proofs The Language of Quantifiers Logical Equivalences Proofs (1.6-1.7) Rules of Inference Cao Fall 2024 Proof Methods 1 2 Propositional Logic Summary The Language of Propositions Connectives Truth Values Truth Tables Propositional Logic Applications Translating English Sentences System Specifications Section 1.1 Logic Puzzles Logic Circuits Logical Equivalences Important Equivalences Showing Equivalence Satisfiability 3 4  8/29/2024 Section Summary Propositions Propositions A proposition is a declarative sentence that is either true or false. Are these propositions? Connectives a) The Moon is made of green cheese. Negation b) Trenton is the capital of New Jersey. Conjunction c) Toronto is the capital of Canada. d) 1+0=1 Disjunction e) 0+0=2 Implication; contrapositive, inverse, converse f) Sit down! Biconditional g) What time is it? Truth Tables h) x+1=2 i) x+y=z 5 6 5 6 Propositional Logic Compound Propositions: Negation Constructing Propositions The negation of a proposition p is denoted by Propositional Variables: p, q, r, s, … p and has this truth table: The proposition that is always true is denoted by T and the proposition that is always false is denoted by F. p p Compound Propositions - constructed from logical T F connectives and other propositions F T Negation Conjunction ∧ Example: If p denotes “The earth is round.”, then p denotes Disjunction ∨ “It is not the case that the earth is round,” or more simply “The Implication → earth is not round.” Biconditional 7 8 7 8  8/29/2024 Conjunction Disjunction The conjunction of propositions p and q is The disjunction of propositions p and q is denoted by p ∧ q and has this truth table: denoted by p ∨ q and has this truth table: p q p∧q p q p∨q T T T T T T T F F T F T F T F F T T F F F F F F Example: If p denotes “I am at home.” and q denotes “It is Example: If p denotes “I am at home.” and q denotes “It is raining.” then p ∧ q denotes raining.” then p ∨ q denotes “I am at home and it is raining.” 9 “I am at home or it is raining.” 10 9 10 The Connective Or in English Implication In English “or” has two distinct meanings. If p and q are propositions, then p → q is a conditional statement or implication which is read as “if p, then q” and has “Inclusive Or” - In the sentence “Students who have taken CS202 or Math120 may take this class,” we assume that students need to have taken one of the this truth table: prerequisites, but may have taken both. This is the meaning of disjunction. For p ∨ q to be true, either one or both of p and q must be true. p q p→q “Exclusive Or” - When reading the sentence “Soup or salad comes with this T T T entrée,” we do not expect to be able to get both soup and salad. This is the meaning of Exclusive Or (Xor). In p ⊕ q , one of p and q must be true, but not T F F both. The truth table for ⊕ is: F T T p q p⊕q F F T T T F Example: If p denotes “I am at home.” and q denotes “It is T F T raining.” then p → q denotes “If I am at home then it is raining.” F T T In p → q, p is the hypothesis (antecedent or premise) and q is the F F F conclusion (or consequence). 11 12 11 12  8/29/2024 Understanding Implication 1 Understanding Implication 2 In p → q there does not need to be any connection One way to view the logical conditional is to between the antecedent or the consequent. The think of an obligation or contract. “meaning” of p → q depends only on the truth values of p and q. “If I am elected, then I will lower taxes.” These implications are perfectly fine, but would not be “If you get 100% on the final, then you will get an A.” used in ordinary English. If the politician is elected and does not lower “If the moon is made of green cheese, then I have more taxes, then the voters can say that he or she has money than Bill Gates. ” broken the campaign pledge. Something similar “If the moon is made of green cheese then I’m on welfare.” holds for the professor. This corresponds to the “If 1 + 1 = 3, then your grandma wears combat boots.” case where p is true and q is false. 13 14 13 14 Different Ways of Expressing p → q Converse, Contrapositive, and Inverse if p, then q p implies q From p → q we can form new conditional statements. q→p is the converse of p → q if p, q p only if q q → p is the contrapositive of p → q q unless p q when p p → q is the inverse of p → q q if p Example: Find the converse, inverse, and contrapositive of “It is raining is a sufficient condition for me not going q whenever p p is sufficient for q to town.” q follows from p q is necessary for p Solution: converse: If I do not go to town, then it is raining. a necessary condition for p is q inverse: If it is not raining, then I will go to town. a sufficient condition for q is p contrapositive: If I go to town, then it is not raining. 15 16 15 16  8/29/2024 Biconditional Expressing the Biconditional If p and q are propositions, then we can form the biconditional Some alternative ways “p if and only if q” is proposition p q, read as “p if and only if q.” The biconditional p q denotes the proposition with this truth table: expressed in English: p q p q p is necessary and sufficient for q T T T if p then q, and conversely T F F p if q F T F F F T If p denotes “I am at home.” and q denotes “It is raining.” then p q denotes “I am at home if and only if it is raining.” 17 18 17 18 Truth Tables For Compound Example Truth Table Propositions Construction of a truth table: Construct a truth table for p ∨ q → r Rows p q r r p∨q p∨q→ r Need a row for every possible combination of values for T T T F T F the atomic propositions. T T F T T T Columns T F T F T F Need a column for the compound proposition (usually at T F F T T T far right) F T T F T F F T F T T T Need a column for the truth value of each expression that occurs in the compound proposition as it is built up. F F T F F T This includes the atomic propositions F F F T F T 19 20 19 20  8/29/2024 Equivalent Propositions Problem Two propositions are equivalent if they always How many rows are there in a truth table with n have the same truth value. propositional variables? Example: Show using a truth table that the Solution: 2n conditional is equivalent to the contrapositive. Note that this means that with n propositional Solution: variables, we can construct 2n distinct (that is, p q p q p→q q→ p not equivalent) propositions. T T F F T T T F F T F F F T T F T T F F T T T T 21 22 21 22 Precedence of Logical Operators Operator Precedence ∧ 1 2 Applications of ∨ → 3 4 Propositional Logic 5 Section 1.2 p ∨ q → r is equivalent to (p ∨ q) → r If the intended meaning is p ∨(q → r) then parentheses must be used. 23 24 23 24  8/29/2024 Section Summary Translating English Sentences Translating English to Propositional Logic Steps to convert an English sentence to a statement in propositional logic System Specifications Identify atomic propositions and represent using Logic Puzzles propositional variables. Determine appropriate logical connectives Logic Circuits “If I go to school or to the gym, I will not go shopping.” p: I go to school If p or q then not r. q: I go to the gym r: I will go shopping  p  q  r 25 26 25 26 Example System Specifications Problem: Translate the following sentence into System and Software engineers take requirements in propositional logic: English and express them in a precise specification language based on logic. “You can access the Internet from campus only if you are a computer science major or you are not a Example: Express in propositional logic: freshman.” “The automated reply cannot be sent when the file system is full” 27 28 27 28  8/29/2024 Consistent System Specifications Logic Puzzles Definition: A list of propositions is consistent if it is possible to An island has two kinds of inhabitants, knights, who always tell the truth, and assign truth values to the proposition variables so that each knaves, who always lie. proposition is true. You go to the island and meet A and B. Exercise: Are these specifications consistent? A says “B is a knight.” “The diagnostic message is stored in the buffer or it is retransmitted.” B says “The two of us are of opposite types.” “The diagnostic message is not stored in the buffer.” Example: What are the types of A and B? “If the diagnostic message is stored in the buffer, then it is retransmitted.” 29 30 29 30 Section Summary Tautologies, Contradictions, and Contingencies. Logical Equivalence Propositional Equivalences Important Logical Equivalences Showing Logical Equivalence (Proof) Propositional Satisfiability Section 1.3 32 31 32  8/29/2024 Tautologies, Contradictions, and Logically Equivalent Contingencies p p p∨ p p∧ p Two compound propositions p and q are logically equivalent if p q is a tautology. T F T F We write this as p⇔q or as p≡q where p and q are compound F T T F propositions. A tautology is a proposition which is always true. Two compound propositions p and q are equivalent if and only if the columns in a truth table giving their truth values agree. Example: p ∨ p This truth table shows that p ∨ q is equivalent to p → q. A contradiction is a proposition which is always false. p q p p∨q p→q T T F T T Example: p ∧ p T F F F F A contingency is a proposition which is neither a F T T T T tautology nor a contradiction, such as p 33 F F T T T 34 33 34 De Morgan’s Laws Key Logical Equivalences 1   p  q   p  q Augustus De Morgan Identity Laws: p  T  p, pF  p 1806-1871   p  q   p  q Domination Laws: p T  T, pF  F Use this truth table to show that De Morgan’s Second Law holds. Idempotent laws: p  p  p, p p  p p q p q (p ∨ q) (p ∨ q) p∧ q T T F F T F F T F F T T F F Double Negation Law:   p   p F T T F T F F F F T T F T T Negation Laws: p  p  T , p  p  F 35 36 35 36  8/29/2024 Key Logical Equivalences 2 More Logical Equivalences* Commutative Laws: p  q  q  p, p  q  q  p TABLE 7 Logical Equivalences Involving Conditional Statements. TABLE 8 Logical Equivalences Associative Laws:  p  q  r  p   q  r  p q  p  q p q  q p Involving Biconditional Statements.  p  q  r  p   q  r  p  q  p q p  q   p q   q p p  q  p  q p  q    p q  Distributive Laws:  p   q  r    p  q   p  r    p q   p  q p  q   p  q    p  q    p  q   p  q  p   q  r    p  q   p  r   p q   p r   p  q  r   p r    q r    p  q r * Provided for exams Absorption Laws: p   p  q  p p   p  q  p  p q   p r   p  q  r   p r    q r    p  q r 37 38 37 38 Constructing New Logical Equivalences Equivalence Proofs 1 We can show that two expressions are logically Example: Show that  p   p  q    equivalent by developing a series of logically equivalent is logically equivalent to p  q statements. Solution: To prove that A ≡ B we produce a series of equivalences beginning with A and ending with B. A  A1  An  B Keep in mind that whenever a proposition (represented by a propositional variable) occurs in the equivalences listed earlier, it may be replaced by an arbitrarily complex compound proposition. 39 40 39 40  8/29/2024 Equivalence Proofs 2 Propositional Satisfiability Example: Show that  p  q   p  q  A compound proposition is satisfiable if there is is a tautology. an assignment of truth values to its variables Solution: that make it true. When no such assignments exist, the compound proposition is unsatisfiable. A compound proposition is unsatisfiable if and only if its negation is a tautology. 41 42 41 42 Propositional Satisfiability Example: Determine the satisfiability of the following compound propositions:  p   q    q  r    r   p  Solution: Predicates and Quantifiers  p  q  r    p   q  r  Solution: Section 1.4  p   q    q   r    r  p    p  q  r     p   q   r  Solution 43 43 44  8/29/2024 Section Summary Propositional Logic Not Enough Predicates If we have: Variables “All men are mortal.” Quantifiers “Socrates is a man.” Universal Quantifier Does it follow that “Socrates is mortal?” Existential Quantifier Negating Quantifiers Can’t be represented in propositional logic. Need a language that talks about objects, their De Morgan’s Laws for Quantifiers properties, and their relations. Translating English to Logic Later we’ll see how to draw inferences. 46 45 46 Introducing Predicate Logic Propositional Functions Predicate logic uses the following new features: Propositional functions become propositions (and have truth values) when their variables are each replaced by a value from Variables: x, y, z the domain (or bound by a quantifier, as we will see later). Predicates: P(x), M(x) The statement P(x) is said to be the value of the propositional function P at x. Quantifiers (to be covered in a few slides): For example, let P(x) denote “x > 0” and the domain be the integers. Then: Propositional functions are a generalization of P(-3) F propositions. P(0) F They contain variables and a predicate, e.g., P(x) P(3) T Variables can be replaced by elements from their Often the domain is denoted by U. So in this example U is the domain. integers. 47 48 47 48  8/29/2024 Examples of Propositional Functions Compound Expressions Let “x + y = z” be denoted by R(x, y, z) and U (for all three Connectives from propositional logic carry over to predicate logic. variables) be the integers. Find these truth values: If P(x) denotes “x 0,” find these truth values: R(2,-1,5) Solution: F P(3) ∨ P(-1) Solution: T R(3,4,7) P(3) ∧ P(-1) Solution: F Solution: T P(3) → P(-1) Solution: F R(x, 3, z) Solution: Not a Proposition P(3) → P(-1) Solution: T Now let “x - y = z” be denoted by Q(x, y, z), with U as the Expressions with variables are not propositions and therefore do integers. Find these truth values: not have truth values. For example, Q(2,-1,3) Solution: P(3) ∧ P(y) T Q(3,4,7) P(x) → P(y) Solution: F Q(x, 3, z) When used with quantifiers (to be introduced next), these Solution: Not a Proposition expressions (propositional functions) become propositions. 49 50 49 50 Quantifiers Universal Quantifier We need quantifiers to express the meaning of English words x P(x) is read as “For all x, P(x)” or “For every x, P(x)” including all and some: “All men are Mortal.” Examples: “Some cats do not have fur.” 1) If P(x) denotes “x 0” and U is the integers, then x The two most important quantifiers are: P(x) is False. Universal Quantifier, “For all,” symbol:  2) If P(x) denotes “x 0” and U is the positive integers, Existential Quantifier, “There exists,” symbol:  then x P(x) is True. We write as in x P(x) and x P(x). 3) If P(x) denotes “x is even” and U is the integers, then  x P(x) asserts P(x) is true for every x in the domain. x P(x) is False. x P(x) asserts P(x) is true for some x in the domain. The quantifiers are said to bind the variable x in these expressions. 51 52 51 52  8/29/2024 Existential Quantifier Thinking about Quantifiers x P(x) is read as “For some x, P(x)”, or as “There When the domain of discourse is finite, we can think of quantification as looping through the elements of the domain. is an x such that P(x),” or “For at least one x, P(x).” To evaluate x P(x), loop through all x in the domain. Examples: If at every step P(x) is true, then x P(x) is true. 1. If P(x) denotes “x 0” and U is the integers, then x If at a step P(x) is false, then x P(x) is false and the loop terminates. P(x) is true. It is also true if U is the positive integers. To evaluate x P(x), loop through all x in the domain. 2. If P(x) denotes “x 0” and U is the positive integers, If at some step, P(x) is true, then x P(x) is true and the loop terminates. then x P(x) is False. If the loop ends without finding an x for which P(x) is true, then x P(x) is false. 3. If P(x) denotes “x is even” and U is the integers, then x P(x) is True. Even if the domains are infinite, we can still think of the quantifiers this fashion, but the loops will not terminate in some cases. 53 54 53 54 Properties of Quantifiers Precedence of Quantifiers The truth value of x P x and  x P x depend on both The quantifiers  and  have higher precedence than all the propositional function P x and on the domain U. the logical operators. Examples: For example,x P(x)∨ Q(x) means (x P(x))∨ Q(x) 1. If U is the positive integers and P(x) is the statement “x 2”, x (P(x)∨ Q(x)) means something different. then x P x is T ,  x P x is F. Unfortunately, often people writex P(x)∨ Q(x) when 2. If U is the negative integers and P(x) is the statement “x 2”, they mean x (P(x) ∨ Q(x)). then x P x is T ,  x P x is T. 3. If U consists of 3, 4, and 5, and P(x) is the statement “x 2”, then both x P x and x P x are true. But if P(x) is the statement “x 2”, then both x P x and x P x are false. 55 56 55 56  8/29/2024 Translating from English to Logic Translating from English to Logic 2 Example 1: Translate the following sentence into Example 2: Translate the following sentence into predicate logic: “Every student in this class has taken a predicate logic: “Some student in this class has taken a course in Java.” course in Java.” Solution: Solution: 57 58 57 58 Thinking about Quantifiers as Equivalences in Predicate Logic Conjunctions and Disjunctions Statements involving predicates and quantifiers If the domain is finite, a universally quantified proposition is are logically equivalent if and only if they have equivalent to a conjunction of propositions without quantifiers and an existentially quantified proposition is the same truth value equivalent to a disjunction of propositions without quantifiers. for every predicate substituted into these If U consists of the integers 1,2, and 3: statements and for every domain of discourse used for the variables xP  x   P 1  P  2   P  3 in the expressions. xP  x   P 1  P  2   P  3 The notation S ≡T indicates that S and T are logically equivalent. Even if the domains are infinite, you can still think of the quantifiers in this fashion, but the equivalent expressions Example: x S(x) ≡x S(x) without quantifiers will be infinitely long. 59 60 59 60  8/29/2024 Negating Quantified Expressions 1 Negating Quantified Expressions 2 Considerx J(x) Now Consider  x J(x) “Every student in your class has taken a course in Java.” “There is a student in this class who has taken a course in Java.” Here J(x) is “x has taken a course in Java” and Where J(x) is “x has taken a course in Java.” the domain is students in your class. Negating the original statement gives “It is not the Negating the original statement gives “It is not the case case that there is a student in this class who has that every student in your class has taken Java.” This implies that “There is a student in your class who has not taken Java.” This implies that “Every student in this taken Java.” class has not taken Java” Symbolically x J(x) and x J(x) are equivalent Symbolically  x J(x) and x J(x) are equivalent 61 62 61 62 De Morgan’s Laws for Quantifiers Translation from English to Logic The rules for negating quantifiers are: Examples: TABLE 2 De Morgan’s Laws for Quantifiers. 1. “Some student in this class has visited Mexico.” Negation Equivalent Statement When Is Negation True? When False? Solution: xP  x x P  x  For every x, P(x) is false. There is x for which P(x) is true. xP  x x  P  x  There is an x for which P (x) is false. P(x) is true for every x. The reasoning in the table shows that: 2. “Every student in this class has visited Canada or xP  x   xP  x  Mexico.” Solution: xP  x   xP  x  These are important. You will use these. 63 64 63 64  8/29/2024 Translation from English to Logic System Specification Example Examples: Find the negations of the followings: Predicate logic is used for specifying properties that systems must satisfy. For example, translate into predicate logic: 1. “There is an honest politician.” “Every mail message larger than one megabyte will be compressed.” “If a user is active, at least one network link will be available.” Decide on predicates and domains (left implicit here) for the variables: Let L(m, y) be “Mail message m is larger than y megabytes.” Let C(m) denote “Mail message m will be compressed.” 2. “All Americans eat cheeseburgers.” Let A(u) represent “User u is active.” Let S(n, x) represent “Network link n is state x. Now we have: 65 66 65 66 Nested Quantifiers Nested quantifiers are often necessary to express the meaning of sentences in English as well as important concepts in computer science and mathematics. Nested Quantifiers Example: “Every real number has an inverse” is x y(x + y = 0) Section 1.4 where the domains of x and y are the real numbers. We can also think of nested propositional functions: x y(x + y = 0) can be viewed as x Q(x) where Q(x) is y P(x, y) where P(x, y) is (x + y = 0) 67 68  8/29/2024 Thinking of Nested Quantification Order of Quantifiers Nested Loops Examples: To see if xyP x,y is true, loop through the values of x : At each step, loop through the values for y. 1. Let P(x,y) be the statement “x + y = y + x.” Assume If for some pair of x andy, P x,y is false, then x yP x,y is false and both that U is the real numbers. Then x yP(x,y) and the outer and inner loop terminate. y xP(x,y) have the same truth value. x y P x,y is true if the outer loop ends after stepping through each x. To see if x yP x,y is true, loop through the values of x: 2. Let Q(x,y) be the statement “x + y = 0.” Assume that U At each step, loop through the values for y. is the real numbers. Then x yQ(x,y) is true, but The inner loop ends when a pair x and y is found such that P x, y is true. If no y is found such that P x, y is true the outer loop terminates as x y xQ(x,y) is false. yP x,y has been shown to be false. x y P x,y is true if the outer loop ends after stepping through each x. If the domains of the variables are infinite, then this process can not actually be carried out. 69 70 Questions on Order of Quantifiers 1 Questions on Order of Quantifiers 2 Example 1: Let U be the real numbers, Example 2: Let U be the real numbers, Define P(x,y) : x · y = 0 Define P(x,y) : x / y = 1 What is the truth value of the following: What is the truth value of the following: 1.  x yP( x, y ) 1.  x yP( x, y ) Answer:False Answer:False 2.  x yP( x, y ) 2.  x yP( x, y ) Answer:True Answer:False 3.  x yP( x, y ) 3.  x yP( x, y ) Answer:True Answer:False 4.  x yP( x, y ) 4.  x yP( x, y ) Answer:True Answer:True 71 72  8/29/2024 Quantifications of Two Variables Statement When True? When False xyP  x, y  P(x,y) is true for every There is a pair x, y for pair x,y. which P(x,y) is false. yxP  x, y  Rules of Inference xyP  x, y  For every x there is a y There is an x such that for which P(x,y) is true. P(x,y) is false for every y. There is an x for which For every x there is a y Section 1.6 xyP  x, y  P(x,y) is true for every y. for which P(x,y) is false. xyP  x, y  There is a pair x, y for P(x,y) is false for every which P(x,y) is true. pair x,y yxP  x, y  74 73 74 Section Summary 1 Revisiting the Socrates Example Valid Arguments We have the two premises: Inference Rules for Propositional Logic “All men are mortal.” Using Rules of Inference to Build Arguments “Socrates is a man.” Rules of Inference for Quantified Statements And the conclusion: Building Arguments for Quantified Statements “Socrates is mortal.” How do we get the conclusion from the premises? 75 76 75 76  8/29/2024 The Argument Valid Arguments We can express the premises (above the line) We will show how to construct valid arguments and the conclusion (below the line) in predicate in two stages; first for propositional logic and logic as an argument: then for predicate logic. The rules of inference are the essential building block in the x  Man  x Mortal  x   construction of valid arguments. Man  Socrates  1. Propositional Logic  Mortal  Socrates  Inference Rules We will see shortly that this is a valid argument. 2. Predicate Logic Inference rules for propositional logic plus additional inference rules to handle variables and quantifiers. 77 78 77 78 Rules of Inference for Propositional Arguments in Propositional Logic Logic: Modus Ponens An argument in propositional logic is a sequence of propositions. All but the final proposition are called premises. The last Corresponding Tautology: statement is the conclusion. The argument is valid if the premises imply the conclusion. An argument form is an argument that is valid no matter what Example: propositions are substituted into its propositional variables. Let p be “Texas is snowing.” If the premises are p1 ,p2, …, pn and the conclusion is q then Let q be “Texans will lose power.” (p1 ∧ p2 ∧ … ∧ pn ) → q is a tautology. “If Texas is snowing, then Texans will lose power.” Inference rules are all argument simple argument forms that will be used to construct more complex argument forms. “Texas is snowing.” “Therefore , Texans will lose power.” 79 80 79 80  8/29/2024 Modus Tollens Hypothetical Syllogism Corresponding Tautology: pq Corresponding Tautology: qr  p q   q r   p r  pr Example: Example: Let p be “it is snowing.” Let p be “it snows.” Let q be “I will study discrete math.” Let q be “I will study discrete math.” “If it is snowing, then I will study discrete math.” Let r be “I will get an A.” “I will not study discrete math.” “If it snows, then I will study discrete math.” “Therefore , it is not snowing.” “If I study discrete math, I will get an A.” 81 “Therefore , If it snows, I will get an A.” 82 81 82 Disjunctive Syllogism Addition pq Corresponding Tautology: Corresponding Tautology: p p p  p  q  p   p  q   q  pq q Example: Example: Let p be “I will study discrete math.” Let p be “I will study discrete math.” Let q be “I will study English literature.” Let q be “I will visit Las Vegas.” “I will study discrete math or I will study English “I will study discrete math.” literature.” “Therefore, I will study discrete math or I will visit “I will not study discrete math.” Las Vegas.” “Therefore , I will study English literature.” 83 84 83 84  8/29/2024 Simplification Conjunction pq Corresponding Tautology: p Corresponding Tautology: p  p  q p q  p   q  p  q  pq Example: Example: Let p be “I will study discrete math.” Let p be “I will study discrete math.” Let q be “I will study English literature.” Let q be “I will study English literature.” “I will study discrete math and English literature” “I will study discrete math.” “Therefore, I will study discrete math.” “I will study English literature.” “Therefore, I will study discrete math and I will study English literature.” 85 86 85 86 Resolution Resolution Corresponding Tautology: Decide satisfiability or validity by resolution rule. Considering a set of clauses, use resolution rule to prove it is   p  r    p  q    q  r  unsatisfiable: Example: Let p be “I will study discrete math.” Let q be “I will study databases.” Let r be “I will study English literature.” 5) 𝑞 𝑎 ∨ 𝑟 𝑎 , from 1) and 2) “I will study discrete math or I will study databases.” 6) 𝑞 𝑎 , from 2) and 4) “I will not study discrete math or I will study English literature.” 7) 𝑞 𝑎 , from 3) and 5) “Therefore, I will study databases or I will study English from 6) and 7), we get an empty clause, or a contradictory. literature.” 87 88 87 88  8/29/2024 Using the Rules of Inference to Build Valid Arguments Valid Arguments A valid argument is a sequence of statements. Each statement is Example 1: From the single proposition either a premise or follows from previous statements by rules of inference. The last statement is called conclusion. p   p q A valid argument takes the following form: Show that q is a conclusion. S1 Solution: S2... Sn C 89 90 89 90 Valid Arguments Valid Arguments Example 2: Show that the premises “It is not sunny this Example 2: 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.” p : “It is sunny this afternoon.” r : “We will go swimming.” t : “We will be home by sunset.” q : “It is colder than yesterday.” s : “We will take a canoe trip.” 91 92 91 92  8/29/2024 Valid Arguments Fallacies Example 3: Show that the premises 𝑝 ∧ 𝑞 ∨ 𝑟 and Is the following argument valid? 𝑟 → 𝑠 imply 𝑝 ∨ 𝑠 If you do every problem in this book, then you Solution: will learn discrete mathematics. Distributive Law: You learned discrete mathematics. Logical Equivalence for →: Therefore, you did every problem in this book. Resolution: Fallacy of affirming the conclusion 93 94 93 94 Fallacies Handling Quantified Statements Is the following argument valid? Valid arguments for quantified statements are a If you do every problem in this book, then you sequence of statements. Each statement is either will learn discrete mathematics. a premise or follows from previous statements by rules of inference which include: You did not do every problem in this book. 1. Rules of Inference for Propositional Logic Therefore, you did not learn discrete 2. Rules of Inference for Quantified Statements mathematics. Fallacy of denying the hypothesis 95 96 95 96  8/29/2024 Universal Instantiation (UI) Universal Generalization (UG) xP  x P  c for an arbitrary c  P  c xP  x  Example: Used often implicitly in Mathematical Proofs. Our domain consists of all dogs and Fido is a dog. “All dogs are cuddly.” “Therefore, Fido is cuddly.” 97 98 97 98 Existential Instantiation (EI) Existential Generalization (EG) xP  x P  c  for some element c  P  c  for some element c xP  x  Example: Example: “There is someone who got an A in the course.” “Michelle got an A in the class.” “Let’s call her a and say that a got an A” “Therefore, someone got an A in the class.” 99 10 0 99 100  8/29/2024 Using Rules of Inference Universal Modus Ponens Example 1: Using the rules of inference, construct a valid argument to show that Universal Modus Ponens combines universal “John Smith has two legs” instantiation and modus ponens into one rule. is a consequence of the premises: “Every man has two legs.” “John Smith is a man.” Solution: Let M(x) denote “x is a man” and L(x) “x has two legs” and let John x  P  x  Q  x   Smith be a member of the domain. Valid Argument: P  a  , where a is a particular element in the domain  Q  a This rule is used in the Socrates example. 10 10 1 2 101 102 Returning to the Socrates Example Using Rules of Inference x  Man  x Mortal  x  Example 2: Use the rules of inference to construct a valid argument showing that the conclusion Man  Socrates  “Someone who passed the first exam has not read the book.”  Mortal  Socrates  follows from the premises “A student in this class has not read the book.” “Everyone in this class passed the first exam.” 1. ∀𝑥 𝑀𝑎𝑛 𝑥 → 𝑀𝑜𝑟𝑡𝑎𝑙 𝑥 , Premise Solution: Let C(x) denote “x is in this class,” B(x) denote “x has read the book,” and P(x) denote “x passed the first exam.” 2. 𝑀𝑎𝑛 𝑆𝑜𝑐𝑟𝑎𝑡𝑒𝑠 → 𝑀𝑜𝑟𝑡𝑎𝑙 𝑆𝑜𝑐𝑟𝑎𝑡𝑒𝑠 , UI from 1 First, we translate the premises and conclusion into symbolic form. 3. 𝑀𝑎𝑛 𝑆𝑜𝑐𝑟𝑎𝑡𝑒𝑠 , Premise x  C  x    B  x   4. 𝑀𝑜𝑟𝑡𝑎𝑙 𝑆𝑜𝑐𝑟𝑎𝑡𝑒𝑠 , Modus Pones from 2 and 3 x  C  x  P  x   x  P  x   B  x  10 10 3 4 103 104  8/29/2024 Using Rules of Inference Valid Argument: x  C  x  B  x  x  C  x  P  x   x  P  x  B  x  Introduction to Proofs Section 1.7 10 5 105 106 Section Summary 2 Proofs of Mathematical Statements Mathematical Proofs A proof is a valid argument that establishes the truth of a statement. Forms of Theorems In math, CS, and other disciplines, informal proofs which are generally shorter, are generally used. Direct Proofs More than one rule of inference are often used in a step. Steps may be skipped. Indirect Proofs The rules of inference used are not explicitly stated. Easier to understand and to explain to people. Proof of the Contrapositive But it is also easier to introduce errors. Proofs have many practical applications: Proof by Contradiction verification that computer programs are correct establishing that operating systems are secure enabling programs to make inferences in artificial intelligence showing that system specifications are consistent 108 107 108  8/29/2024 Definitions Forms of Theorems A theorem is a statement that can be shown to be true using: Many theorems assert that a property holds for all elements in a definitions domain, such as the integers, the real numbers, or some of the discrete structures that we will study in this class. other theorems axioms (statements which are given as true) Often the universal quantifier (needed for a precise statement of rules of inference a theorem) is omitted by standard mathematical convention. A lemma is a ‘helping theorem’ or a result which is needed to For example, the statement: prove a theorem. “If x > y, where x and y are positive real numbers, then x2 > y2 ” A corollary is a result which follows directly from a theorem. Less important theorems are sometimes called propositions. really means A conjecture is a statement that is being proposed to be true. “For all positive real numbers x and y, if x > y, then x2 > y2.” Once a proof of a conjecture is found, it becomes a theorem. It may turn out to be false. 109 110 109 110 Proving Theorems Proving Conditional Statements: p → q Many theorems have the form: x  P  x  Q  x   Trivial Proof: If we know q is true, then p → q is true as well. To where c is an arbitrary element of the “If it is raining then 1=1.” domain, P  c Q  c Vacuous Proof: If we know p is false then By universal generalization (UG) the truth of the p → q is true as well. original formula follows. “If I am both rich and poor then 2 + 2 = 5.” So, we must prove something of the form: p q [ Even though these examples seem silly, both trivial and vacuous proofs are often used in mathematical induction, as we will see in Chapter 5) ] 111 112 111 112  8/29/2024 Background: Even and Odd Integers Proving Conditional Statements: p → q Definition: The integer n is even if there exists an Direct Proof: Assume that p is true. Use rules of inference, axioms, and logical equivalences to show that q must also be true. integer k such that n = 2k, and n is odd if there Example: Give a direct proof of the theorem “If n is an odd integer, exists an integer k, such that n = 2k + 1. Note then n2 is odd.” that every integer is either even or odd and no Solution: integer is both even and odd. We will need this basic fact about the integers in some of the example proofs to follow. We will learn more about the integers in Chapter 4. (marks the end of the proof. Sometimes QED is used instead.) 113 114 113 114 Proving Conditional Statements: p → q Proving Conditional Statements: p → q Definition: The real number r is rational if there exist integers p Proof by Contraposition: Assume q and show p is true also. and q where q≠0 such that r = p/q This is sometimes called an indirect proof method. If we give a Example: Prove that the sum of two rational numbers is rational. direct proof of q → p then we have a proof of p → q. Solution: Why does this work? Example: Prove that if n is an integer and 3n + 2 is odd, then n is odd. Solution: 115 116 115 116  8/29/2024 Proving Conditional Statements: p → q Proving Conditional Statements: p → q Exercise: Use proof by contraposition to prove that for Proof by Contradiction: To prove q, assume q and derive an integer n, if n2 is odd, then n is odd. a contradiction r, such that q → r is true, which means q →F, then it follows that the contrapositive T→q also holds. Solution: How can we find such r? Example: Prove that if you pick 22 days from the calendar, at least 4 must fall on the same day of the week. Solution: Assume that no more than 3 of the 22 days fall on the same day of the week. Because there are 7 days of the week, we could only have picked 21 days. This contradicts the assumption that we have picked 22 days. 117 118 117 118 Proving Conditional Statements: p → q Proving Conditional Statements: p → q Example: Use a proof by contradiction to give a proof Exercise: Prove by contradiction of the theorem “If 3n + 2 is that 2 is irrational. odd, then n is odd.”. Solution: Solution: 119 120 119 120  8/29/2024 What is wrong with this? What is wrong with this? “Proof” that 1 = 2 Show that 𝑛 is an even integer whenever 𝑛 is an even integer. Step Reason 1. a  b Premise Proof: Suppose that 𝑛 is even. Then 𝑛 2𝑘 for some 2. a =a  b 2 Multiply both sides of 1 by a integer 𝑘. Let 𝑛 2𝑙 for some integer 𝑙. This shows 3. a  b =a  b  b 2 2 2 Subtract b 2 from both sides of  2 that 𝑛 is even. 4.  a  b a  b =b  a  b Algebra on  3 5. a  b  b Divide both sides by a  b Solution: 6. 2b  b Replace a by b in  5 because a  b 7. 2  1 Divide both sides of  6 by b Solution: 121 122 121 122 Section Summary Proof by Cases Existence Proofs Proof Methods and Strategy Constructive Nonconstructive Disproof by Counterexample Section 1.8 Uniqueness Proofs Proof Strategies Proving Universally Quantified Assertions 123 124 123 124  8/29/2024 Proof by Cases Proof by Cases To prove a conditional statement of the form: Example: Prove that if n is an integer, then 𝑛 𝑛.  p1  p2    pn  q Proof: We can split the proof into three cases: 1 𝑛 0 Use the tautology  p1  p2    pn  q   2 𝑛 1  p1 q    p2 q      pn q   Each of the implications pi q is a case. 3 𝑛 1 125 126 125 126 Proof by Cases Existence Proofs Example: Show that if x and y are integers and both x∙y and x+y Proof of theorems of the form xP  x . are even, then both x and y are even. Constructive existence proof: Proof: Use a proof by contraposition. Suppose x and y are not Find an explicit value of c, for which P(c) is true. both even. Then, one or both are odd. Without loss of generality, Then xP  x  is true by Existential Generalization (EG). assume that x is odd. Then x 2m 1 for some integer m. Example: Show that there is a positive integer that can be written Case 1: y is even. Then y 2n for some integer n, so as the sum of cubes of positive integers in two different ways: x y 2m 1 2n 2 m n 1 is odd. Proof: 1729 is such a number since Case 2: y is odd. Then y 2n + 1 for some integer n, so x∙y 2m 1 2n 1 2 2m ∙ n m n 1 is odd. 1729 = 103 + 93 = 123 + 13 We only cover the case where x is odd because the case where y is odd is similar. The use phrase without loss of generality WLO