Foundations: Logic & Proofs PDF

The Foundations: Logic & Proofs Chapter 1, Part I: Propositional Logic With Question/Answer Animations  Chapter Summary Propositional Logic The Language of Propositions Applications Logical Equivalences Predicate Logic The Lan...

The Foundations: Logic & Proofs Chapter 1, Part I: Propositional Logic With Question/Answer Animations  Chapter Summary Propositional Logic The Language of Propositions Applications Logical Equivalences Predicate Logic The Language of Quantifiers Logical Equivalences Nested Quantifiers Proofs Rules of Inference Proof Methods Proof Strategy  Propositional Logic Summary The Language of Propositions Connectives Truth Values Truth Tables Applications Translating English Sentences System Specifications Logic Puzzles Logic Circuits Logical Equivalences Important Equivalences Showing Equivalence Satisfiability Propositional Logic Section 1.1  Section Summary Propositions Connectives Negation Conjunction Disjunction Implication; contrapositive, inverse, converse Biconditional Truth Tables  Propositions A proposition is a declarative sentence that is either true or false. e.g., a) The Moon is made of green cheese. b) Trenton is the capital of New Jersey. c) Toronto is the capital of Canada. d) 1+0=1 e) 0+0=2 Examples that are not propositions. f) Sit down! g) What time is it? h) x+1=2 i) x+y=z  Propositions A proposition is a declarative sentence that is either true or false. Examples of propositions: Examples that are not propositions. The Moon is made of green cheese. Sit down! Trenton is the capital of New Jersey. What time is it? Toronto is the capital of Canada. x + 1 = 2 1 + 0 = 1 x + y = z 0 + 0 = 2 7  Propositional Logic Constructing Propositions Propositional Variables: p, q, r, s, … The proposition that is always true is denoted by T & the proposition that is always false is denoted by F. Compound Propositions; constructed from logical connectives & other propositions Negation ¬ Conjunction ∧ Disjunction ∨ Implication → Biconditional ↔  Compound Propositions: Negation The negation of a proposition p is denoted by ¬p & has this truth table: p ¬p T F F T e.g., If p denotes “The earth is round.”, then ¬p denotes “It is not the case that the earth is round,” or more simply “The earth is not round.”  Conjunction The conjunction of propositions p & q is denoted by p ∧ q & has this truth table: p q p∧q T T T T F F F T F F F F e.g., If p denotes “I am at home.” & q denotes “It is raining.” then p ∧q denotes “I am at home & it is raining.”  Disjunction The disjunction of propositions p & q is denoted by p ∨q & has this truth table: p q p ∨q T T T T F T F T T F F F e.g., If p denotes “I am at home.” & q denotes “It is raining.” then p ∨q denotes “I am at home or it is raining.”  The Connective Or in English In English “or” has 2 distinct meanings. “Inclusive Or” - In the sentence “Students who have taken CS202 or Math120 may take this class,” we assume that students need to have taken 1 of the prerequisites, but may have taken both. This is the meaning of disjunction. For p ∨q to be true, either 1 or both of p & q must be true. “Exclusive Or” - When reading the sentence “Soup or salad comes with this entrée,” we do not expect to be able to get both soup & salad. This is the meaning of Exclusive Or (Xor). In p ⊕ q , 1 of p & q must be true, but not both. The truth table for ⊕ is: p q p ⊕q T T F T F T F T T F F F  Implication If p & q are propositions, then p →q is a conditional statement or implication which is read as “if p, then q ” & has this truth table: p q p →q T T T T F F F T T F F T e.g., If p denotes “I am at home.” & q denotes “It is raining.” then p →q denotes “If I am at home then it is raining.” In p →q , p is the hypothesis (antecedent or premise) & q is the conclusion (or consequence).  Understanding Implication In p →q there does not need to be any connection between the antecedent or the consequent. The “meaning” of p →q depends only on the truth values of p & q. These implications are perfectly fine, but would not be used in ordinary English. “If the moon is made of green cheese, then I have more money than Bill Gates. ” “If the moon is made of green cheese then I’m on welfare.” “If 1 + 1 = 3, then your grandma wears combat boots.”  Understanding Implication (cont) One way to view the logical conditional is to think of an obligation or contract. “If I am elected, then I will lower taxes.” “If you get 100% on the final, then you will get an A.” If the politician is elected & does not lower taxes, then the voters can say that he or she has broken the campaign pledge. Something similar holds for the professor. This corresponds to the case where p is true & q is false.  Different Ways of Expressing p →q if p, then q p implies q if p, q p only if q q unless ¬p q when p q if p q whenever p p is sufficient for q q follows from p q is necessary for p a necessary condition for p is q a sufficient condition for q is p  Converse, Contrapositive, & Inverse From p →q we can form new conditional statements. q →p is the converse of p →q ¬q → ¬ p is the contrapositive of p →q ¬p→¬q is the inverse of p →q e.g., Find the converse, inverse, & contrapositive of “It raining is a sufficient condition for my not going to town.” Solution: converse: If I do not go to town, then it is raining. inverse: If it is not raining, then I will go to town. contrapositive: If I go to town, then it is not raining.  Biconditional If p & q are propositions, then we can form the biconditional proposition p ↔q , read as “p if & only if q.” The biconditional p ↔q denotes the proposition with this truth table: p q p ↔q T T T T F F F T F F F T If p denotes “I am at home.” & q denotes “It is raining.” then p ↔q denotes “I am at home if & only if it is raining.”  Expressing the Biconditional Some alternative ways “p if & only if q” is expressed in English: p is necessary & sufficient for q if p then q , & conversely p iff q  Truth Tables For Compound Propositions Construction of a truth table: Rows Need a row for every possible combination of values for the atomic propositions. Columns Need a column for the compound proposition (usually at far right) Need a column for the truth value of each expression that occurs in the compound proposition as it is built up. This includes the atomic propositions  Example Truth Table Construct a truth table for p q r r p q p q→ r T T T F T F T T F T T T T F T F T F T F F T T T F T T F T F F T F T T T F F T F F T F F F T F T  q →p is the converse of p →q Equivalent Propositions ¬q → ¬ p is the contrapositive of p →q ¬ p → ¬ q is the inverse of p →q Two propositions are equivalent if they always have the same truth value. e.g., Show using a truth table that the conditional is equivalent to the contrapositive. Solution: p q ¬p ¬q p →q ¬q → ¬ p T T F F T T T F F T F F F T T F T T F F T T T T  Using a Truth Table to Show Non-Equivalence e.g., Show using truth tables that neither the converse nor inverse of an implication are not equivalent to the implication. Solution: p q ¬p ¬q p →q ¬ p →¬ q q→p T T F F T T T T F F T F T T F T T F T F F F F T T T T T q →p is the converse of p →q ¬q → ¬ p is the contrapositive of p →q ¬ p → ¬ q is the inverse of p →q  Problem How many rows are there in a truth table with n propositional variables? Solution: 2n We will see how to do this in Chapter 6. Note that this means that with n propositional variables, we can construct 2n distinct (i.e., not equivalent) propositions. Precedence of Logical Operators Operator Precedence 1 2 3 4 5 p q r is equivalent to (p q) ( r) If the intended meaning is p (q r) then parentheses must be used. Applications of Propositional Logic Section 1.2  Applications of Propositional Logic: Summary Translating English to Propositional Logic System Specifications Boolean Searching Logic Puzzles Logic Circuits AI Diagnosis Method (Optional)  Translating English Sentences Steps to convert an English sentence to a statement in propositional logic Identify atomic propositions & represent using propositional variables. Determine appropriate logical connectives “If I go to Makkah or to Riyadh, I will not go shopping.” p: I go to Makkah q: I go to the Riyadh. r: I will go shopping. If p or q then not r.  Example Problem: Translate the following sentence into propositional logic: “You can access the Internet from campus only if you are a computer science major or you are not a freshman.” 1 Solution: Let a, c, & f represent respectively “You can access the internet from campus,” “You are a computer science major,” & “You are a freshman.” a→ (c ∨ ¬ f )  System Specifications System & Software engineers take requirements in English & express them in a precise specification language based on logic. e.g., Express in propositional logic: “The automated reply cannot be sent when the file system is full” Solution: 1 possible solution: Let p denote “The automated reply can be sent” & q denote “The file system is full.” q→ ¬ p  Consistent System Specifications Definition: A list of propositions is consistent if there is at least one possible way to assign truth values to the proposition variables so that all propositions are true. Exercise: Are these specifications consistent? “The diagnostic message is stored in the buffer, or it is retransmitted.” p q P ∨∨ q ¬p p→ ¬q “The diagnostic message is not stored in the buffer.” q “If the diagnostic message is stored in the buffer, then it is retransmitted.” T T T F T F T F T F F T Solution: Let p denote “The diagnostic message is stored in the buffer.” F T T T T F Let q denote “The diagnostic message is retransmitted” F F F T T T The specification can be written as: p ∨ q, ¬p, p → q. When p is false, & q is true all 3 statements are true. So the specification is consistent. What if “The diagnostic message is not retransmitted” is added. Solution: Now we are adding ¬q & there is no satisfying assignment. So the specification is not consistent.  Logic Circuits (Studied in depth in Chapter 12) Electronic circuits; each input/output signal can be viewed as a 0 or 1. 0 represents False 1 represents True Complicated circuits are constructed from 3 basic circuits called gates. The inverter (NOT gate)takes an input bit & produces the negation of that bit. The OR gate takes 2 input bits & produces the value equivalent to the disjunction of the 2 bits. The & gate takes 2 input bits & produces the value equivalent to the conjunction of the 2 bits. e.g., Write each of these statements in the form “if p, then q” in English. a) I will remember to send you the address only if you send me an e-mail message. b) To be a citizen of this country, it is sufficient that you were born in the United States. c) If you keep your textbook, it will be a useful reference in your future courses.  Write these propositions using p, q, & r & logical connectives (including negations). a) Berries are ripe along the trail, but grizzly bears have not been seen in the area. b) Grizzly bears have not been seen in the area & hiking on the trail is safe, but berries are ripe along the trail. c) If berries are ripe along the trail, hiking is safe if & only if grizzly bears have not been seen in the area. d) It is not safe to hike on the trail, but grizzly bears have not been seen in the area & the berries along the trail are ripe. e) For hiking on the trail to be safe, it is necessary but not sufficient that berries not be ripe along the trail & for grizzly bears not to have Propositional Equivalences Section 1.3  Section Summary Tautologies, Contradictions, & Contingencies. Logical Equivalence Important Logical Equivalences Showing Logical Equivalence Normal Forms (optional, covered in exercises in text) Disjunctive Normal Form Conjunctive Normal Form Propositional Satisfiability Sudoku Example  Tautologies, Contradictions, & Contingencies A tautology is a proposition which is always true. e.g., p ∨¬p A contradiction is a proposition which is always false. e.g., p ∧¬p A contingency is a proposition which is neither a tautology nor a contradiction, e.g., p P ¬p p ∨∨¬p p ∧∧¬p T F T F F T T F  Logically Equivalent Two compound propositions p & q are logically equivalent if p↔q is a tautology. We write this as p q or as p≡q where p & q are compound propositions. Two compound propositions p & q are equivalent if & only if the columns in a truth table giving their truth values agree. This truth table shows that ¬p ∨ q is equivalent to p → q. p q ¬p ¬p ∨∨ q p→ q T T F T T T F F F F F T T T T F F T T T q →p is the converse of p →q ¬q → ¬ p is the contrapositive of p →q ¬ p → ¬ q is the inverse of p →q  De Morgan’s Laws Augustus De Morgan 1806-1871 This truth table shows that De Morgan’s Second Law holds. p q ¬p ¬q (p∨ ∨q) ¬(p∨ ∨q) ¬p∧ ∧¬q T T F F T F F T F F T T F F F T T F T F F F F T T F T T  Key Logical Equivalences Identity Laws: Domination Laws: Idempotent laws: Double Negation Law: Negation Laws:  Key Logical Equivalences (cont) Commutative Laws: Associative Laws: Distributive Laws: Absorption Laws: More Logical Equivalences  Constructing New Logical Equivalences We can show that two expressions are logically equivalent by developing a series of logically equivalent statements. To prove that we produce a series of equivalences beginning with A & ending with 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.  Equivalence Proofs e.g., Show that is logically equivalent to Solution:  Equivalence Proofs e.g., Show that is a tautology. Solution:  Propositional Satisfiability A compound proposition is satisfiable if there is at least one assignment of truth values to its variables that make it true. When no such assignments exist, the compound proposition is unsatisfiable. A compound proposition is unsatisfiable if & only if its negation is a tautology.  Questions on Propositional Satisfiability e.g., Determine the satisfiability of the following compound propositions: Solution: Satisfiable. Assign T to p, q, & r. Solution: Satisfiable. Assign T to p & F to q. Solution: Not satisfiable. Check each possible assignment of truth values to the propositional variables & none will make the proposition The Foundations: Logic and Proofs Chapter 1, Part II: Predicate Logic With Question/Answer Animations  Summary Predicate Logic (First-Order Logic (FOL), Predicate Calculus) The Language of Quantifiers Logical Equivalences Nested Quantifiers Translation from Predicate Logic to English Translation from English to Predicate Logic Predicates and Quantifiers Section 1.4  Section Summary Predicates Variables Quantifiers Universal Quantifier Existential Quantifier Negating Quantifiers De Morgan’s Laws for Quantifiers Translating English to Logic Logic Programming (optional)  Propositional Logic Not Enough If we have: “All men are mortal.” “Socrates is a man.” Does it follow that “Socrates is mortal?” Can’t be represented in propositional logic. Need a language that talks about objects, their properties, and their relations. Later we’ll see how to draw inferences.  Introducing Predicate Logic Predicate logic uses the following new features: Variables: x, y, z Predicates: P(x), M(x) Quantifiers (to be covered in a few slides): Propositional functions are a generalization of propositions. They contain variables and a predicate, e.g., P(x) Variables can be replaced by elements from their domain.  Propositional Functions Propositional functions become propositions (and have truth values) when their variables are each replaced by a value from the domain (or bound by a quantifier, as we will see later). The statement P(x) is said to be the value of the propositional function P at x. For example, let P(x) denote “x > 0” and the domain be the integers. Then: P(-3) is false. P(0) is false. P(3) is true.  Examples of Propositional Functions Let “x + y = z” be denoted by R(x, y, z) and U (for all three variables) be the integers. Find these truth values: R(2,-1,5) Solution: F R(3,4,7) Solution: T R(x, 3, z) Solution: Not a Proposition Now let “x - y = z” be denoted by Q(x, y, z), with U as the integers. Find these truth values: Q(2,-1,3) Solution: T Q(3,4,7) Solution: F  Compound Expressions Connectives from propositional logic carry over to predicate logic. If P(x) denotes “x > 0,” find these truth values: P(3) ∨ P(-1) Solution: T P(3) ∧ P(-1) Solution: F P(3) → P(-1) Solution: F P(3) → ¬P(-1) Solution: T Expressions with variables are not propositions and therefore do not have truth values. For example, P(3) ∧ P(y)  Quantifiers Charles Peirce (1839-1914) We need quantifiers to express the meaning of English words including all and some: “All men are Mortal.” “Some cats do not have fur.” The two most important quantifiers are: Universal Quantifier, “For all,” symbol: Existential Quantifier, “There exists,” symbol: We write as in x P(x) and x P(x). x P(x) asserts P(x) is true for every x in the domain. 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.  Universal Quantifier x P(x) is read as “For all x, P(x)” or “For every x, P(x)” Examples: 1) If P(x) denotes “x > 0” and U is the integers, then x P(x) is false. 2) If P(x) denotes “x > 0” and U is the positive integers, then x P(x) is true. 3) If P(x) denotes “x is even” and U is the integers, then x P(x) is false.  Existential Quantifier x P(x) is read as “For some x, P(x)”, or as “There is an x such that P(x),” or “For at least one x, P(x).” Examples: 1. If P(x) denotes “x > 0” and U is the integers, then x P(x) is true. It is also true if U is the positive integers. 2. If P(x) denotes “x < 0” and U is the positive integers, then x P(x) is false. 3. If P(x) denotes “x is even” and U is the integers, then xP(x) is true.  Thinking about Quantifiers When the domain of discourse is finite, we can think of quantification as looping through the elements of the domain. To evaluate x P(x) loop through all x in the domain. If at every step P(x) is true, then x P(x) is true. If at a step P(x) is false, then x P(x) is false and the loop terminates. To evaluate x P(x) loop through all x in the domain. If at some step, P(x) is true, then x P(x) is true and the loop terminates. If the loop ends without finding an x for which P(x) is true, then x P(x) is false. Even if the domains are infinite, we can still think of the quantifiers this fashion, but the loops will not terminate in some cases.  Properties of Quantifiers The truth value of x P(x) and x P(x) depend on both the propositional function P(x) and on the domain U. Examples: 1. If U is the positive integers and P(x) is the statement “x < 2”, then x P(x) is true, but x P(x) is false. 2. If U is the negative integers and P(x) is the statement “x < 2”, then both x P(x) and x P(x) are true. 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.  Precedence of Quantifiers The quantifiers and have higher precedence than all the logical operators. For example, x P(x) ∨ Q(x) means ( x P(x))∨ Q(x) x (P(x) ∨ Q(x)) means something different. Unfortunately, often people write x P(x) ∨ Q(x) when they mean x (P(x) ∨ Q(x)).  Translating from English to Logic Example 1: Translate the following sentence into predicate logic: “Every student in this class has taken a course in Java.” Solution: First decide on the domain U. Solution 1: If U is all students in this class, define a propositional function J(x) denoting “x has taken a course in Java” and translate as x J(x). Solution 2: But if U is all people, also define a propositional function S(x) denoting “x is a student in this class” and translate as x (S(x)→ J(x)). x (S(x) ∧ J(x)) is not correct. What does it mean?  Translating from English to Logic Example 2: Translate the following sentence into predicate logic: “Some student in this class has taken a course in Java.” Solution: First decide on the domain U. Solution 1: If U is all students in this class, translate as x J(x) Solution 2: But if U is all people, then translate as x (S(x) ∧ J(x)) x (S(x)→ J(x)) is not correct. What does it mean?  Returning to the Socrates Example Introduce the propositional functions Man(x) denoting “x is a man” and Mortal(x) denoting “x is mortal.” Specify the domain as all people. The two premises are: The conclusion is: Later we will show how to prove that the conclusion follows from the premises.  Equivalences in Predicate Logic Statements involving predicates and quantifiers are logically equivalent if and only if they have the same truth value for every predicate substituted into these statements and for every domain of discourse used for the variables in the expressions. The notation S ≡T indicates that S and T are logically equivalent. Example: x ¬¬S(x) ≡ x S(x)  Thinking about Quantifiers as Conjunctions and Disjunctions If the domain is finite, a universally quantified proposition is equivalent to a conjunction of propositions without quantifiers and an existentially quantified proposition is equivalent to a disjunction of propositions without quantifiers. If U consists of the integers 1,2, and 3: Even if the domains are infinite, you can still think of the quantifiers in Using the five circles, as seen below, we make the following statement: “Some circles are shaded.” What would the negation of this statement be? “Some circles are not shaded.” No! Because this statement is also true!  Negating Quantified Expressions Consider x J(x) “Every student in your class has taken a course in Java.” Here J(x) is “x has taken a course in Java” and the domain is students in your class. Negating the original statement gives “It is not the case that every student in your class has taken Java.” This implies that “There is a student in your class who has not taken Java.” Symbolically ¬ x J(x) and x ¬J(x) are equivalent Now Consider x J(x) “There is a student in this class who has taken a course in Java.” Where J(x) is “x has taken a course in Java.” Negating the original statement gives “It is not the case that there is a student in this class who has taken Java.” This implies that “Every student in this  De Morgan’s Laws for Quantifiers The rules for negating quantifiers are: The reasoning in the table shows that: These are important. You will use these.  Translation from English to Logic Examples: 1. “Some student in this class has visited Mexico.” Solution: Let M(x) denote “x has visited Mexico” and S(x) denote “x is a student in this class,” and U be all people. x (S(x) ∧ M(x)) 2. “Every student in this class has visited Canada or Mexico.” Solution: Add C(x) denoting “x has visited Canada.” x (S(x)→ (M(x)∨C(x)))  Some Fun with Translating from English into Logical Expressions U = {fleegles, snurds, thingamabobs} F(x): x is a fleegle S(x): x is a snurd T(x): x is a thingamabob Translate “Everything is a fleegle” Solution: x F(x) “Nothing is a snurd.” Solution: ¬ x S(x) What is this equivalent to? Solution: x ¬ S(x)  Translation (cont) U = {fleegles, snurds, thingamabobs} F(x): x is a fleegle S(x): x is a snurd T(x): x is a thingamabob “Some fleegles are thingamabobs.” Solution: x (F(x) ∧ T(x)) “No snurd is a thingamabob.” Solution: ¬ x (S(x) ∧ T(x)) What is this equivalent to? Solution: x (¬S(x) ∨ ¬T(x))  Lewis Carroll Example Charles Lutwidge Dodgson (AKA Lewis Caroll) (1832-1898) The first two are called premises and the third is called the conclusion. 1. “All lions are fierce.” 2. “Some lions do not drink coffee.” 3. “Some fierce creatures do not drink coffee.” Here is one way to translate these statements to predicate logic. Let P(x), Q(x), and R(x) be the propositional functions “x is a lion,” “x is fierce,” and “x drinks coffee,” respectively. 4. x (P(x)→ Q(x)) 5. x (P(x) ∧ ¬R(x)) 6. x (Q(x) ∧ ¬R(x)) Later we will see how to prove that the conclusion follows from the premises. Nested Quantifiers Section 1.5  Section Summary Nested Quantifiers Order of Quantifiers Translating from Nested Quantifiers into English Translating Mathematical Statements into Statements involving Nested Quantifiers. Translated English Sentences into Logical Expressions. Negating Nested Quantifiers.  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. Example: “Every real number has an additive inverse” is x y(x + y = 0) 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)  Thinking of Nested Quantification Nested Loops To see if x yP (x,y) is true, loop through the values of x : At each step, loop through the values for y. If for some pair of x andy, P(x,y) is false, then x yP(x,y) is false and both the outer and inner loop terminate. 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: At each step, loop through the values for y. 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 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.  Order of Quantifiers Examples: 1. Let P(x,y) be the statement “x + y = y + x.” Assume that U is the real numbers. Then x yP(x,y) and y xP(x,y) have the same truth value. 2. Let Q(x,y) be the statement “x + y = 0.” Assume that U is the real numbers. Then x yQ(x,y) is true, but y xQ(x,y) is false.  Questions on Order of Quantifiers 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 (where y=0) Answer: False 3. x y P(x,y) 3. x y P(x,y) Answer: True (where x=0) Answer: False 4. x y P(x,y) 4. x y P(x,y) Answer: True (both x,y=0) Answer: True  Quantifications of Two Variables Statement When True? When False P(x,y) is true for every pair There is a pair x, y for x,y. which P(x,y) is false. For every x there is a y for There is an x such that 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 for P(x,y) is true for every y. which P(x,y) is false. There is a pair x, y for P(x,y) is false for every which P(x,y) is true. pair x,y  Translating Nested Quantifiers into English Example 1: Translate the statement x (C(x )∨ y (C(y ) ∧ F(x, y))) where C(x) is “x has a computer,” and F(x,y) is “x and y are friends,” and the domain for both x and y consists of all students in your school. Solution: Every student in your school has a computer or has a friend who has a computer. Example 2: Translate the statement x y z ((F(x, y)∧ F(x,z) ∧ (y ≠z))→¬F(y,z)) Solution: There is a student none of whose friends are also friends with each other. There is a student in your school (x), such that, for any other two students (y,z), if (x) is a friend to (y and z) and (y,z) are distinct student, then (y,z ) are not friends.  Translating Mathematical Statements into Predicate Logic Example : Translate “The sum of two positive integers is always positive” into a logical expression. Solution: 1. Rewrite the statement to make the implied quantifiers and domains explicit: “For every two integers, if these integers are both positive, then the sum of these integers is positive.” 2. Introduce the variables x and y, and specify the domain, to obtain: “For all positive integers x and y, x + y is positive.” 3. The result is: x y ((x > 0)∧ (y > 0)→ (x + y > 0)) where the domain of both variables consists of all integers  Questions on Translation from English Choose the obvious predicates and express in predicate logic. Example 1: “Brothers are siblings.” Solution: x y (B(x,y) → S(x,y)) Example 2: “Siblinghood is symmetric.” Solution: x y (S(x,y) → S(y,x)) Example 3: “Everybody loves somebody.” Solution: x y L(x,y) Example 4: “There is someone who is loved by everyone.” Solution: y x L(x,y) Example 5: “There is someone who loves someone.”  Negating Nested Quantifiers Example 1: Recall the logical expression developed in the previous: w a f (P(w,f ) ∧ Q(f,a)) Part 1: Use quantifiers to express the statement that “There does not exist a woman who has taken a flight on every airline in the world.” Solution: ¬ w a f (P(w,f ) ∧ Q(f,a)) Part 2: Now use De Morgan’s Laws to move the negation as far inwards as possible. Solution: 1. ¬ w a f (P(w,f ) ∧ Q(f,a)) 2. w¬ a f (P(w,f ) ∧ Q(f,a)) by De Morgan’s for 3. w a¬ f (P(w,f ) ∧ Q(f,a)) by De Morgan’s for 4. w a f ¬ (P(w,f ) ∧ Q(f,a)) by De Morgan’s for The Foundations: Logic & Proofs Chapter 1, Part III: Proofs With Question/Answer Animations  Summary Valid Arguments & Rules of Inference Proof Methods Proof Strategies Rules of Inference Section 1.6  Section Summary Valid Arguments Inference Rules for Propositional Logic Using Rules of Inference to Build Arguments Rules of Inference for Quantified Statements Building Arguments for Quantified Statements  Revisiting the Socrates Example We have the 2 premises: “All men are mortal.” “Socrates is a man.” And the conclusion: “Socrates is mortal.” How do we get the conclusion from the premises?  The Argument We can express the premises (above the line) & the conclusion (below the line) in predicate logic as an argument: We will see shortly that this is a valid argument.  Valid Arguments We will show how to construct valid arguments in 2 stages; first for propositional logic & then for predicate logic. The rules of inference are the essential building block in the construction of valid arguments. 1. Propositional Logic Inference Rules 2. Predicate Logic Inference rules for propositional logic plus additional inference rules to handle variables & quantifiers.  Arguments in Propositional Logic A argument in propositional logic is a sequence of propositions. All but the final proposition are called premises. The last 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 propositions are substituted into its propositional variables. If the premises are p1 ,p2, …,pn & the conclusion is q then (p1 ∧ p2 ∧ … ∧ pn ) → q is a tautology. Inference rules are all argument simple argument forms that will be used to construct more complex argument forms. Rules of Inference for Propositional Logic: Modus Ponens Corresponding Tautology: (p ∧ (p →q)) → q e.g., Let p be “It is snowing.” Let q be “I will study discrete math.” “If it is snowing, then I will study discrete math.” “It is snowing.” “Therefore , I will study discrete math.”  Modus Tollens Corresponding Tautology: (¬q∧(p →q))→¬p e.g., Let p be “it is snowing.” Let q be “I will study discrete math.” “If it is snowing, then I will study discrete math.” “I will not study discrete math.” “Therefore , it is not snowing.” Hypothetical Syllogism Corresponding Tautology: ((p →q) ∧ (q→r))→(p→ r) e.g., Let p be “it snows.” Let q be “I will study discrete math.” Let r be “I will get an A.” “If it snows, then I will study discrete math.” “If I study discrete math, I will get an A.” “Therefore , If it snows, I will get an A.” Disjunctive Syllogism Corresponding Tautology: (¬p∧(p ∨q))→q e.g., Let p be “I will study discrete math.” Let q be “I will study English literature.” “I will study discrete math or I will study English literature.” “I will not study discrete math.” “Therefore , I will study English literature.”  Addition Corresponding Tautology: p →(p ∨q) e.g., Let p be “I will study discrete math.” Let q be “I will visit Las Vegas.” “I will study discrete math.” “Therefore, I will study discrete math or I will visit Las Vegas.”  Simplification Corresponding Tautology: (p∧q) →p P e.g., Let p be “I will study discrete math.” Let q be “I will study English literature.” “I will study discrete math & English literature” “Therefore, I will study discrete math.”  Conjunction Corresponding Tautology: ((p) ∧ (q)) →(p ∧ q) e.g., Let p be “I will study discrete math.” Let q be “I will study English literature.” “I will study discrete math.” “I will study English literature.” “Therefore, I will study discrete math & I will study English literature.”  Resolution Resolution plays an important role in AI & is used in Prolog. Corresponding Tautology: ((¬p ∨ r ) ∧ (p ∨ q)) →(q ∨ r) e.g., Let p be “I will study discrete math.” Let r be “I will study English literature.” Let q be “I will study databases.” “I will not study discrete math or I will study English literature.” “I will study discrete math or I will study databases.” “Therefore, I will study databases or I will study English literature.”  Using the Rules of Inference to Build Valid Arguments A valid argument is a sequence of statements. Each statement is either a premise or follows from previous statements by rules of inference. The last statement is called conclusion. A valid argument takes the following form: S1 S2... Sn  Valid Arguments Example 1: From the single proposition Show that q is a conclusion. Solution:  Valid Arguments Example 2: With these hypotheses: “It is not sunny this afternoon & 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.” Using the inference rules, construct a valid argument for the conclusion: “We will be home by sunset.” Solution: 1. Choose propositional variables: 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.” 2. Translation into propositional logic: Continued on next slide  Valid Arguments 3. Construct the Valid Argument  Handling Quantified Statements Valid arguments for quantified statements are a sequence of statements. Each statement is either a premise or follows from previous statements by rules of inference which include: Rules of Inference for Propositional Logic Rules of Inference for Quantified Statements The rules of inference for quantified statements are introduced in the next several slides. Universal Instantiation (UI) e.g., Our domain consists of all man, and Javed is a man. “All men are mortal.” “Therefore, Javed is mortal.” Universal Generalization (UG) Used often implicitly in Mathematical Proofs. Existential Instantiation (EI) e.g., “There is someone who got an A in the course.” “Let’s call her a & say that a got an A” Existential Generalization (EG) e.g., “Michelle got an A in the class.” “Therefore, someone got an A in the class.”  Universal Modus Ponens Universal Modus Ponens combines universal instantiation & modus ponens into 1 rule. This rule could be used in the Socrates example.  Solution for Socrates Example Valid Argument  Using Rules of Inference Example 1: Using the rules of inference, construct a valid argument to show that “John Smith has 2 legs” is a consequence of the premises: “Every man has 2 legs.” “John Smith is a man.” Solution: Let M(x) denote “x is a man” & L(x) “ x has 2 legs” & let John Smith be a member of the domain. Valid Argument:  Using Rules of Inference Example 2: Use the rules of inference to Valid construct a valid argument showing that Argument: the conclusion “Someone who passed the first exam has not read the book.” follows from the premises “A student in this class has not read the book.” “Everyone in this class passed the first exam.” Solution: Let C(x) denote “x is in this class,” B(x) denote “ x has read the book,” & P(x) denote “x passed the first exam.” First we translate the Introduction to Proofs Section 1.7  Section Summary Mathematical Proofs Forms of Theorems Direct Proofs Indirect Proofs Proof of the Contrapositive Proof by Contradiction  Proofs of Mathematical Statements A proof is a valid argument that establishes the truth of a statement. In math, CS, & other disciplines, informal proofs which are generally shorter, are generally used. More than 1 rule of inference are often used in a step. Steps may be skipped. The rules of inference used are not explicitly stated. Easier for to understand & to explain to people. But it is also easier to introduce errors. Proofs have many practical applications: 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  Definitions A theorem is a statement that can be shown to be true using: definitions other theorems axioms (statements which are given as true) rules of inference A lemma is a ‘helping theorem’ or a result which is needed to prove a theorem. A corollary is a result which follows directly from a theorem. Less important theorems are sometimes called propositions. A conjecture is a statement that is being proposed to be true. Once a proof of a conjecture is found, it becomes a theorem. It may turn out to be false.  Forms of Theorems Many theorems assert that a property holds for all elements in a domain, such as the integers, the real numbers, or some of the discrete structures that we will study in this class. Often the universal quantifier (needed for a precise statement of a theorem) is omitted by standard mathematical convention. e.g., the statement: “If x > y, where x & y are positive real numbers, then x2 > y2 ” really means “For all positive real numbers x & y, if x > y, then x2 > y2.”  Proving Theorems Many theorems have the form: To prove them, we show that where c is an arbitrary element of the domain, By universal generalization the truth of the original formula follows. So, we must prove something of the form:  Proving Conditional Statements: p → q Trivial Proof: If we know q is true, then p → q is true as well. “If it is raining then 1=1.” Vacuous Proof: If we know p is false then p → q is true as well. “If I am both rich & poor then 2 + 2 = 5.” [ Even though these examples seem silly, both trivial & vacuous proofs  Definition: 1-Even & Odd Integers Definition: The integer n is even if there exists an integer k such that n = 2k, & n is odd if there exists an integer k, such that n = 2k + 1. Note that every integer is either even or odd & no integer is both even & 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.  1-Direct Proof: Proving Conditional Statements: p → q In Direct Proof: Assume that p is true. Use rules of inference, axioms, & logical equivalences to show that q must also be true. e.g., Give a direct proof of the theorem “If n is an odd integer, then n2 is odd.” Solution: Assume that n is odd. Then n = 2k + 1 for an integer k. Squaring both sides of the equation, we get: n2 = (2k + 1)2 = 4k2 + 4k +1 = 2(2k2 + 2k) + 1= 2r + 1, where r = 2k2 + 2k , an integer. We have proved that if n is an odd integer, then n2 is an odd integer. ( marks the end of the proof. Sometimes QED is used instead. )  2- Definition: Rational numbers Definition: The real number r is rational if there exist integers p & q where q≠0 such that r = p/q e.g., Prove that the sum of 2 rational numbers is rational. Answer: Assume that r and s are two rational numbers. Then there must be integers p, q and also t, u such that where v = pu + qt Thus, the sum is rational. w = qu ≠ 0  Indirect proof: Proving Conditional Statements: p → method. If we give a direct proof of ¬q → ¬p then weqhave a proof of p → q. 1-Proof by Contraposition: Assume ¬q & show ¬p is true also. This is sometimes called an indirect proof Why does this work? e.g., Prove that if n is an integer & 3n + 2 is odd, then n is odd. Solution: Assume n is even. So, n = 2k for some integer k. Thus 3n + 2 = 3(2k) + 2 =6k +2 = 2(3k + 1) = 2j for j = 3k +1 Therefore 3n + 2 is even. Since we have shown ¬q → ¬p , p → q must hold as well. If n is an integer & 3n + 2 is odd (not even) , then n is odd (not even). e.g., Prove that for an integer n, if n2 is odd, then n is odd. Solution: Use proof by contraposition. Assume n is even (i.e., not odd). Therefore, there exists an integer k such that n = 2k. Hence, n2 = 4k2 = 2 (2k2) & n2 is even(i.e., not odd). We have shown that if n is an even integer, then n2 is even. Therefore by contraposition, for an integer n, if n2 is odd, then n is odd.  Proving Conditional Statements: p → q 2-Proof by Contradiction: (AKA reductio ad absurdum). To prove p, assume ¬q & derive a contradiction such as p ∧ ¬p. (an indirect form of proof). Since we have shown that ¬p →F is true , it follows that the contrapositive T→p also holds. e.g., 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.  Theorems that are Biconditional Statements To prove a theorem that is a biconditional statement, that is, a statement of the form p ↔ q, we show that p → q & q →p are both true. e.g., Prove the theorem: “If n is an integer, then n is odd if & only if n2 is odd.” Solution: We have already shown (previous slides) that both p →q & q →p. Therefore we can conclude p ↔ q. Sometimes iff is used as an abbreviation for “if an only if,” as in “If n is an integer, then n is odd iif n2 is odd.”  Looking Ahead If direct methods of proof do not work: We may need a clever use of a proof by contraposition. Or a proof by contradiction. In the next section, we will see strategies that can be used when straightforward approaches do not work. In Chapter 5, we will see mathematical induction & related techniques. In Chapter 6, we will see combinatorial proofs Proof Methods & Strategy Section 1.8  Section Summary Proof by Cases Existence Proofs Constructive Nonconstructive Disproof by Counterexample Nonexistence Proofs Uniqueness Proofs Proof Strategies Proving Universally Quantified Assertions Open Problems  Without Loss of Generality e.g., Show that if x & y are integers & both x·y & x+y are even, then both x & y are even. Proof: Use a proof by contraposition. Suppose x & y are not both even. Then, one or both are odd. Without loss of generality, assume that x is odd. Then x = 2m + 1 for some integer m. Case 1: y is even. Then y = 2n for some integer n, so x + y = (2m + 1) + 2n = 2(m + n) + 1 is odd. 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.  Existence Proofs Srinivasa Ramanujan (1887-1920) Proof of theorems of the form. Constructive existence proof: Find an explicit value of c, for which P(c) is true. Then is true by Existential Generalization (EG). e.g., Show that there is a positive integer that can be written as the sum of cubes of positive integers in 2 different ways: Proof: 1729 is such a number since 1729 = 103 + 93 = 123 + 13 Godfrey Harold Hardy (1877-1947)  Nonconstructive Existence Proofs In a nonconstructive existence proof, we assume no c exists which makes P(c) true & derive a contradiction. e.g., Show that there exist irrational numbers x & y such that xy is rational. Proof: We know that √2 is irrational. Consider the number √2 √2. If it is rational, we have 2 irrational numbers x & y with xy rational, namely x = √2 & y = √2. So, we are done. But if √2 √2 is irrational, then we can take x = √2 √2 (irrational) & y = √2 (irrational) so that xy = (√2 √2 )√2 = √2 (√2 √2) = √2 2 = 2, which is rational. Done.  Counterexamples Recall. To establish that is true (or is false) find a c such that P(c) is true or P(c) is false. In this case c is called a counterexample to the assertion. e.g., “Every positive integer is the sum of the squares of 3 integers.” The integer 7 is a counterexample. So the claim is false.  Proof Strategies for proving p → q Choose a method. 1. First try a direct method of proof. 2. If this does not work, try an indirect method (e.g., try to prove the contrapositive). For whichever method you are trying, choose a strategy. 3. First try forward reasoning. Start with the axioms & known theorems & construct a sequence of steps that end in the conclusion. Start with p & prove q, or start with ¬q & prove ¬p. 4. If this doesn’t work, try backward reasoning. When trying to prove q, find a statement p that we can prove with the property p → q.  Backward Reasoning e.g., Suppose that 2 people play a game taking turns removing, 1, 2, or 3 stones at a time from a pile that begins with 15 stones. The person who removes the last stone wins the game. Show that the first player can win the game no matter what the second player does. Proof: Let n be the last step of the game. Step n: Player1 can win if the pile contains 1,2, or 3 stones. Step n-1: Player2 will have to leave such a pile if the pile that he/she is faced with has 4 stones. Step n-2: Player1 can leave 4 stones when there are 5,6, or 7 stones left at the beginning of his/her turn. Step n-3: Player2 must leave such a pile, if there are 8 stones. Step n-4: Player1 has to have a pile with 9,10, or 11 stones to ensure that there are 8 left.  Universally Quantified Assertions To prove theorems of the form ,assume x is an arbitrary member of the domain & show that P(x) must be true. Using UG it follows that. e.g., An integer x is even if & only if x2 is even. Solution: The quantified assertion is x [x is even x2 is even] We assume x is arbitrary. Recall that is equivalent to So, we have 2 cases to consider. These are considered in turn. Case 1. We show that if x is even then x2 is even using a direct proof (the only if part or necessity). If x is even then x = 2k for some integer k. Hence x2 = 4k2 = 2(2k2 ) which is even since it is an integer divisible by 2. This completes the proof of case 1. Case 2 on next slide  Universally Quantified Assertions Case 2. We show that if x2 is even then x must be even (the if part or sufficiency). We use a proof by contraposition. Assume x is not even & then show that x2 is not even. If x is not even then it must be odd. So, x = 2k + 1 for some k. Then x2 = (2k + 1)2 = 4k2 + 4k + 1 = 2(2k2 + 2k) + 1 which is odd & hence not even. This completes the proof of case 2. Since x was arbitrary, the result follows by UG. Therefore we have shown that x is even if & only if x2 is even.  An Open Problem The 3x + 1 Conjecture: Conjecture means not proven, may be correct, may be no. But people believe either correct or not. Let T be the transformation that sends an even integer x to x/2 & an odd integer x to 3x + 1. For all positive integers x, when we repeatedly apply the transformation T, we will eventually reach the integer 1. e.g., starting with x = 13: T(13) = 3·13 + 1 = 40, T(40) = 40/2 = 20, T(20) = 20/2 = 10, T(10) = 10/2 = 5, T(5) = 3·5 + 1 = 16,T(16) = 16/2 = 8, T(8) = 8/2 = 4, T(4) = 4/2 = 2, T(2) = 2/2 = 1 The conjecture has been verified using computers up to 5.6 · 1013.  Additional Proof Methods Later we will see many other proof methods: Mathematical induction, which is a useful method for proving statements of the form n P(n), where the domain consists of all positive integers. Structural induction, which can be used to prove such results about recursively defined sets. Cantor diagonalization is used to prove results about the size of infinite sets. Combinatorial proofs use counting arguments.