L5-PredicativeLogic

The Logic of Quantified Statements CSE 215, Computer Science 1, Fall 2011 Stony Brook UniversityStony Brook University http://www.cs.stonybrook.edu/~cse215 Refresh from last time: Digital Circuits (c) 2010 Cengage Learning & P.Fodor (CS Stony Brook) 2 Today: The Logic of Quantified Statements All men are mortal. Socrates is a manSocrates is a man. Socrates is mortal.  Propositional calculus: analysis of ordinary compound  Propositional calculus: analysis of ordinary compound statements (last classes)  Predicate calculus: symbolic analysis of predicates and y y p quantified statements P stands for “is a student at SBU”  P is a predicate symbol “x is a student at SBU”  i di i bl (c) 2010 Cengage Learning & P.Fodor (CS Stony Brook)  x is a predicate variable 3 Predicates and Quantified Statements  A predicate is a sentence that contains a finite number of variables and becomes a statement when specific values are variables and becomes a statement when specific values are substituted for the variables.  The domain of a predicate variable is the set of all values that may be substituted in place of the variable.  Example: P(x) is the predicate “x2 > x” , x has as a domain the set R of all real numbers P(2): 22 > 2. True.P(2): 2 2. True. P(1/2): (1/2)2 > 1/2. False. (c) 2010 Cengage Learning & P.Fodor (CS Stony Brook) 4 Truth Set of a Predicate  If P(x) is a predicate and x has domain D, the truth set of P(x), {x D | P(x)}, is the set of all elements of D that make P(x){x D | P(x)}, is the set of all elements of D that make P(x) true when they are substituted for x.  Example: Q(n) is the predicate for “n is a factor of 8.” if the domain of n is the set Z of all integers The truth set is {1, 2, 4, 8,−1,−2,−4,−8} (c) 2010 Cengage Learning & P.Fodor (CS Stony Brook) 5 The Universal Quantifier:  Quantifiers are words that refer to quantities (“some” or “all”) and tell for how many elements a given predicate is true.and tell for how many elements a given predicate is true.  Universal quantifier: “for all”  Example: p human beings x, x is mortal. “All human beings are mortal”g  If H is the set of all human beings x H, x is mortal, (c) 2010 Cengage Learning & P.Fodor (CS Stony Brook) 6 Universal statements  A universal statement is a statement of the form “ x D Q(x)” where Q(x) is a predicate and D is the domain of xx D, Q(x) where Q(x) is a predicate and D is the domain of x.  ׊x א D, Q(x) is true if, and only if, Q(x) is true for every x in D  ׊x א D, Q(x) is false if, and only if, Q(x) is false for at least one x in D Q( ) , y , Q( ) (the value for x is a counterexample)  Example: ׊x א D, x2 ≥ x for D = {1, 2, 3, 4, 5} 12 ≥ 1, 22 ≥ 2, 32 ≥ 3, 42 ≥ 4, 52 ≥ 5  Hence “׊x א D x2 ≥ x” is true Hence ׊x א D, x ≥ x is true. (c) 2010 Cengage Learning & P.Fodor (CS Stony Brook) 7 The Existential Quantifier:  Existential quantifier: “there exists”  Example: Example:  “There is a student in CSE 215” a person p such that p is a student in CSE 215a person p such that p is a student in CSE 215 p P a person p such that p is a student in CSE 215 where P is the set of all peoplep p (c) 2010 Cengage Learning & P.Fodor (CS Stony Brook) 8 The Existential Quantifier:  An existential statement is a statement of the form “ x D such that Q(x)” where Q(x) is a predicate and D the domain x D such that Q(x) where Q(x) is a predicate and D the domain of x  ׌x א D, Q(x) is true if, and only if, Q(x) is true for at least one x in DQ y Q  ׌x א D, Q(x) is false if, and only if, Q(x) is false for all x in D  Example:  ׌m א Z such that m2 = m 12 = 1 True (c) 2010 Cengage Learning & P.Fodor (CS Stony Brook) 9 Universal Conditional Statements  Universal conditional statement: x if P(x) then Q(x)x, if P(x) then Q(x)  Example: If a real number is greater than 2 then its square is greater than 4.If a real number is greater than 2 then its square is greater than 4. ׊x א R, if x > 2 then x2 > 4 (c) 2010 Cengage Learning & P.Fodor (CS Stony Brook) 10 Equivalent Forms of Universal and Existential Statements  x U, if P(x) then Q(x) can be rewritten in the form x D Q(x) by narrowing U to be the domain D consisting of x D, Q(x) by narrowing U to be the domain D consisting of all values of the variable x that make P(x) true.  Example: ׊x, if x is a square then x is a rectanglep f q g ׊ squares x, x is a rectangle.  x such that P(x) and Q(x) can be rewritten in the form “ x D such that Q(x) where D consists of all values of the variable x that make P(x) true (c) 2010 Cengage Learning & P.Fodor (CS Stony Brook) 11 Implicit Quantification  P(x) Q (x) means that every element in the truth set of P(x) is in the truth set of Q(x) or equivalently x P(x)→ Q(x)is in the truth set of Q(x), or, equivalently, x, P(x)→ Q(x)  P(x) Q(x) means that P(x) and Q(x) have identical truth sets or equivalently x P(x)↔ Q(x)sets, or, equivalently, x, P(x)↔ Q(x). (c) 2010 Cengage Learning & P.Fodor (CS Stony Brook) 12