逻辑命题

1 . Propositional Logic 09/28/18 1 

2 .Propositional Logic • A proposition is a statement that is either true or false. • We give propositions names such as p, q, and r. • E.g. p = “pigs have wings” • q = “Obama is U.S. president” • In this world anyway, p is false and q is true. 2 09/28/18 

3 .Truth Tables  “Not” p T ¬p F F T −  ¬p is also written p 3 09/28/18 

4 . Logical Operators/Connectives • Building propositions from propositions • “And” p • So “pigs have wings and Obama is US president” … q p ∧qq T T T T F F F T F F F F 4 09/28/18 

5 . Logical • “Or” Operators/Connectives p q p ∨qq T T T • So “pigs have wings or Obama is US president” … T • “Or” is ambiguous in English but not in Propositional Logic F T • E.g., “would you like coffee or ice cream?” F T T F F F 5 09/28/18 

6 . Logical Operators/Connectives  “Exclusive or” p q p ⊕ q T T F T F T F T T F F F 6 09/28/18 

7 . Some expressions can be defined in terms of others  p ⊕ q is equivalent to (p∨q) ∧¬(p∧q)  What does this actually mean?  That the truth value of the formula on the left is the same as the truth value of the formula on the right regardless of the truth values of p and q 7 09/28/18 

8 .Propositional Logic p q p ⊕ q pvq p^q ¬(p∧qq) (p v q) ^ ¬(p∧q) T T F T T F F T F T T F T T F T T T F T T F F F F F T F 8 09/28/18 

9 . Implies p q p ⇒ q q p ⇒q or p→q or p⊃q T T T T F F is equivalent to F T T ¬p∨q F F T So “If pigs have wings then Obama is US president” is true in this world In fact a false proposition implies any proposition 9 09/28/18 

10 . “Iff” or logical equivalence p q p⇔q T T T T F F F T F F F T • p ⇔ q means that p and q have the same truth value • Equivalent to (p ⇒ q) ∧ (q ⇒ p) 12 09/28/18