L3-PropositionalLogic

The Logic of Compound StatementsThe Logic of Compound Statements cont. CSE 215, Computer Science 1, Fall 2011 Stony Brook UniversityStony Brook University http://www.cs.stonybrook.edu/~cse215 Refresh from last time: Logical Equivalences  Commutativity of ר : p ר q ≡ q ר p  Commutativity of ש : p ש q ≡ q ש pCommutativity of ש : p ש q q ש p  Associativity of ר : p ר (q ר r) ≡ (p ר q) ר r  Associativity of ש : p ש (q ש r) ≡ (p ש q) ש r  Idempotence: p ≡ p ר p ≡ p ש p  Absorption: p ≡ p ר (p ש q) ≡ p ש (p ר q)  D M ' L  De Morgan's Laws: ~(p ר q) ≡ ~p ש ~q ~(p ש q) ≡ ~p ר ~q(p q) p q (c) 2010 Cengage Learning & P.Fodor (CS Stony Brook) 2 Refresh from last time: Logical Equivalences  Distributivity of ר : p ר (q ש r) ≡ (p ר q) ש (p ר r)  Distributivity of ש : p ש (q ר r) ≡ (p ש q) ר (p ש r) Distributivity of ש : p ש (q ר r) (p ש q) ר (p ש r)  Contradictions: p ר F ≡ F ≡ p ר ~p  Identities: p רT ≡ p ≡ p ש F  Tautologies: p שT ≡ T ≡ p ש ~p (c) 2010 Cengage Learning & P.Fodor (CS Stony Brook) 3 Refresh from last time: Symbolic proofs  p ר q ≡ (p ש ~q) ר q  Proof: which laws are used at each step?p (p ש ~q) ר q ≡ q ר (p ש ~q) (1) Commutativity of ר ≡ (q ר p) ש (q ר ~q) (2) Associativity of ר ≡ (q ר p) ש F (3) Contradiction ≡ (q ר p) (4) Identity ≡ ר (5) Commutati it of ר≡ p ר q (5) Commutativity of ר (c) 2010 Cengage Learning & P.Fodor (CS Stony Brook) 4 Today: Logical Arguments (c) 2010 Cengage Learning & P.Fodor (CS Stony Brook) 5 But first, please submit Homework 1 The task was to provide the truth tables for the following expressions:expressions: 1. ׽p ר q 2. ׽(p ר q) ש (p ש q)(p q) (p q) 3. p ר (q ר r ) 4. p ר (׽q ש r ) 5. (p ש (׽p ש q)) ר ~(q ר ~r)  Any problems? (c) 2010 Cengage Learning & P.Fodor (CS Stony Brook) 6 Homework 2  Due on Wednesday 9/21 at the beginning of the class  1. (4 points) Express natural language sentences into symbolic notation.1. (4 points) Express natural language sentences into symbolic notation.  2. (5 points) and 3. (5 points) use De Morgan’s laws to write negations for numerical statements.  4. (5 points) use truth tables to establish if statement forms are tautologies or contradictions.  5 (6 points) and 6 (5 points) write symbolic proofs (and specify which 5. (6 points) and 6. (5 points) write symbolic proofs (and specify which laws are used at each step).  7. (10 points) rewrite statement forms with implication and biconditional using:  7.1 ש, ר and ~  7 2 only ר and ~ (c) 2010 Cengage Learning & P.Fodor (CS Stony Brook)  7.2 only ר and .  The total is 40 points. 7 Quiz 2  Symbolic proof: Prove that ~(~r ר ~q) ש p is logically equivalent with p ש q ש r using symbolic proofs with the standard logical equivalences. Write which laws are used at each step.  The standard logical equivalence laws are:  The standard logical equivalence laws are:  Commutativity of ר : p ר q ≡ q ר p  Commutativity of ש : p ש q ≡ q ש p  Associativity of ר : p ר (q ר r) ≡ (p ר q) ר r Associativity of ר : p ר (q ר r) ≡ (p ר q) ר r  Associativity of ש : p ש (q ש r) ≡ (p ש q) ש r  Idempotence: p ≡ p ר p ≡ p ש p  Absorption: p ≡ p ר (p ש q) ≡ p ש (p ר q) Absorption: p ≡ p ר (p ש q) ≡ p ש (p ר q)  De Morgan's Laws: ~(p ר q) ≡ ~p ש ~q ~(p ש q) ≡ ~p ר ~q  Distributivity of ר : p ר (q ש r) ≡ (p ר q) ש (p ר r) Distributivity of ר : p ר (q ש r) (p ר q) ש (p ר r)  Distributivity of ש : p ש (q ר r) ≡ (p ש q) ר (p ש r)  Contradictions: p ר F ≡ F ≡ p ר ~p  Identities: p רT ≡ p ≡ p ש F (c) 2010 Cengage Learning & P.Fodor (CS Stony Brook) : p p p  Tautologies: p שT ≡T ≡ p ש ~p 8 Quiz 2 ~(~r ~q) p = ( ) t ti it f = p ~(~r ~q) commutativity of = p (~~r ~~q) deMorgan i i i f = p ~~r ~~q associativity of = p r ~~q double negation d bl = p r q double negation (c) 2010 Cengage Learning & P.Fodor (CS Stony Brook) 9 Logical Arguments  An argument (form) is a (finite) sequence of statements (forms) usually written as follows:(forms), usually written as follows: p1 ... pn q  We call p1,..., pn the premises (or assumptions or hypotheses) and q the conclusion, of the argument.  We read: “p1, p2, ..., pn, therefore q” OR (c) 2010 Cengage Learning & P.Fodor (CS Stony Brook) “From premises p1, p2, ..., pn infer conclusion q” 10 Logical Arguments  Argument forms are also called inference rules  An inference rule is said to be valid or (logically) sound if it is  An inference rule is said to be valid, or (logically) sound, if it is the case that, for each truth valuation, if all the premises true, then the conclusion is also true Theorem: An inference rule is valid if, and only if, the conditional p1 p2 ... pn → q is a tautology.  An argument form consisting of two premises and a conclusion is called a syllogism (c) 2010 Cengage Learning & P.Fodor (CS Stony Brook) 11 Determining Validity or Invalidity  Testing an Argument Form for Validity 1 Identify the premises and conclusion of the argument form1. Identify the premises and conclusion of the argument form. 2. Construct a truth table showing the truth values of all the premises and the conclusion. 3. A row of the truth table in which all the premises are true is called a critical row. If there is a critical row in which the conclusion is false, then the argument form is which the conclusion is false, then the argument form is invalid. If the conclusion in every critical row is true, then the argument form is valid (c) 2010 Cengage Learning & P.Fodor (CS Stony Brook) 12 Determining Validity or Invalidity p →q ש ׽ r q → p ר r q p ׵ p →r (c) 2010 Cengage Learning & P.Fodor (CS Stony Brook) 13 Modus Ponens  Modus Ponens: p →q “method of affirming” pmethod of affirming p Latin q (c) 2010 Cengage Learning & P.Fodor (CS Stony Brook) 14 Modus Ponens The following argument is valid: If Socrates is a man, then Socrates is mortal. Socrates is a man. Socrates is mortal. (c) 2010 Cengage Learning & P.Fodor (CS Stony Brook) 15 Modus Ponens  Example: If the sum of the digits of 371 487 is divisible by 3If the sum of the digits of 371,487 is divisible by 3, then 371,487 is divisible by 3. The sum of the digits of 371 487 is divisible by 3The sum of the digits of 371,487 is divisible by 3. 371,487 is divisible by 3. (c) 2010 Cengage Learning & P.Fodor (CS Stony Brook) 16 Modus Tollens  Modus Tonens: p →q “method of denying” ~q Latin ~p  Modus Tollens is valid because  modus ponens is valid and the fact that a conditional statement is logically equivalent to its contrapositive, OR  it can be established formally by using a truth table it can be established formally by using a truth table. (c) 2010 Cengage Learning & P.Fodor (CS Stony Brook) 17 Modus Tollens  Example: (1) If Zeus is human then Zeus is mortal(1) If Zeus is human, then Zeus is mortal. (2) Zeus is not mortal. ׵ Zeus is not human.  An intuitive proof is proof by contradiction  if Zeus were human, then by (1) he would be mortal.  But by (2) he is not mortal.  Hence, Zeus cannot be human. (c) 2010 Cengage Learning & P.Fodor (CS Stony Brook) 18 Recognizing Modus Ponens and Modus Tollens If there are more pigeons than there are pigeonholes, then at least two pigeons roost in the same hole.least two pigeons roost in the same hole. There are more pigeons than there are pigeonholes. ? (c) 2010 Cengage Learning & P.Fodor (CS Stony Brook) 19 Recognizing Modus Ponens and Modus Tollens If there are more pigeons than there are pigeonholes, then at least two pigeons roost in the same hole.least two pigeons roost in the same hole. There are more pigeons than there are pigeonholes. At least two pigeons roost in the same hole. p g by modus ponens (c) 2010 Cengage Learning & P.Fodor (CS Stony Brook) 20 Recognizing Modus Ponens and Modus Tollens If 870,232 is divisible by 6, then it is divisible by 3. 870 232 is not divisible by 3870,232 is not divisible by 3. ? (c) 2010 Cengage Learning & P.Fodor (CS Stony Brook) 21 Recognizing Modus Ponens and Modus Tollens If 870,232 is divisible by 6, then it is divisible by 3. 870 232 is not divisible by 3870,232 is not divisible by 3. 870,232 is not divisible by 6. by modus tollens (c) 2010 Cengage Learning & P.Fodor (CS Stony Brook) 22 Other Rules of Inference  Generalization: p and qp and q p q p q  Example: Example: Anton is a junior. (more generally) Anton is a junior or Anton is a senior.( o e ge e a y) to s a ju o o to s a se o . (c) 2010 Cengage Learning & P.Fodor (CS Stony Brook) 23 Other Rules of Inference  Specialization: p q and p qp q and p q p q  Example: Example: Ana knows numerical analysis and Ana knows graph algorithms.g p g (in particular) Ana knows graph algorithms. (c) 2010 Cengage Learning & P.Fodor (CS Stony Brook) 24 Other Rules of Inference  Elimination : p q and p qp q and p q ~q ~p p qp q  If we have only two possibilities and we can rule one out, the other one must be the case  Example: x − 3 =0 or x + 2 = 0 x + 2  0. x − 3 =0. (c) 2010 Cengage Learning & P.Fodor (CS Stony Brook) 25 Other Rules of Inference  Transitivity : p → qp → q q → r p → rp → r  Example: If 18,486 is divisible by 18, then 18,486 is divisible by 9.If 18,486 is divisible by 18, then 18,486 is divisible by 9. If 18,486 is divisible by 9, then the sum of the digits of 18,486 is divisible by 9.y If 18,486 is divisible by 18, then the sum of the digits of 18,486 is divisible by 9. (c) 2010 Cengage Learning & P.Fodor (CS Stony Brook) 26 Proof Techniques  Proof by Contradiction: ~p → c where c is a contradiction~p → c, where c is a contradiction p  The usual way to derive a conditional ~p → c is to assume ~p The usual way to derive a conditional p c is to assume p and then derive c (i.e., a contradiction).  Thus, if one can derive a contradiction from ~p, then one may l d h conclude that p is true. (c) 2010 Cengage Learning & P.Fodor (CS Stony Brook) 27 Knights and Knaves: knights always tell the truth and knaves always lie A says: B is a knight. B says: A and I are of opposite type. Suppose A is a knight. ׵What A says is true. by definition of knight B i l k i h Th ’ h A id׵ B is also a knight. That’s what A said. ׵What B says is true. by definition of knight ׵A and B are of opposite types. That’s what B said. ׵We have arrived at the following contradiction: A and B are both ׵We have arrived at the following contradiction: A and B are both knights and A and B are of opposite type. ׵The supposition is false. by the contradiction rule ׵A is not a knight. negation of suppositionA is not a knight. negation of supposition ׵A is a knave. since A is not a knight, A is a knave. ׵What A says is false. by definition of knave ׵ B is not a knight. ~(what A said) by definition of knave g ( ) y ׵ B is also a knave. by elimination (c) 2010 Cengage Learning & P.Fodor (CS Stony Brook) 28 Proof Techniques  Proof by Division into Cases: p qp q p → r q → rq → r r  If a disjunction p ש q has been derived and the goal is to prove r, j p q g p , then according to this inference rule it would be sufficient to derive p → r and q → r. E l Example: x is positive or x is negative. If x is positive, then x2 > 0. If x is negative, then x2 > 0. (c) 2010 Cengage Learning & P.Fodor (CS Stony Brook) g , ׵ x2 > 0. 29 Quine’s Method  The following method can be used to determine whether a given propositional formula is a tautology, a contradiction, or a contingency. Let p be a propositional formulaLet p be a propositional formula.  If p contains no variables, it can be simplified to T or F, and hence is either a tautology or a contradiction.  If p contains a variable, then 1. select a variable, say q, l f b h T d d h l f d 2. simplify both p[q := T] and p[q := F], denoting the simplified formulas by p1 and p2, respectively, and 3. apply the method recursively to p1 and p2.pp y y p1 p2  If p1 and p2 are both tautologies, so is p.  If p1 and p2 are both contradictions, so is p. (c) 2010 Cengage Learning & P.Fodor (CS Stony Brook)  In all other cases, p is a contingency. 30 Quine’s Method Example (p ~q → r) (r → p q) (p → ~r) (p q r) → q We first select a variable say q and then consider the two We first select a variable, say q, and then consider the two cases, q := T and q := F. 1. For q := T, the formula ...→T can be simplified to T.q , p 2. For q := F, (p ~F → r) (r → p F) (p → ~r) (p F r) → F(p ) ( p ) (p ) (p ) ≡ (p T → r) (r → p) (p → ~r) (p r) → F ≡ (p → r) (r → p) (p → ~r) (p r) → Fp p p p ≡ ~[(p → r) (r → p) (p → ~r) (p r)] (c) 2010 Cengage Learning & P.Fodor (CS Stony Brook) 31 Quine’s Method Example cont. ~[(p → r) (r → p) (p → ~r) (p r)] We select the variable pWe select the variable p 1. For p := T ~[(T→ r) (r → T) (T → ~r) (T r)] [(T→ r) (r → T) (T → r) (T r)] ≡ ~[r T ~r T] ≡ ~[r ~r] ≡ ~F ≡ T 2. For p := F2. For p : F ~[(F→ r) (r → F) (F→ ~r) (F r)] ≡ ~[T ~r T r] ≡ ~[~r r] ≡ ~F ≡ T[ ] [ ]  This completes the process. All formulas considered, including the original formula, are tautologies. (c) 2010 Cengage Learning & P.Fodor (CS Stony Brook) 32