L3_Propositional_Logic_III.pdf

COM1002: Foundations of Computer Science Lecture 3 Proposition Logic III Dr Paul Watton Todays lecture continues on propositional logic… I am in a maths lecture IMPLIES  I am sleeping Note, if the above propositional statement is TRUE, this does not imply that the following is true, i.e. I...

COM1002: Foundations of Computer Science Lecture 3 Proposition Logic III Dr Paul Watton Todays lecture continues on propositional logic… I am in a maths lecture IMPLIES  I am sleeping Note, if the above propositional statement is TRUE, this does not imply that the following is true, i.e. I am not in a maths lecture IMPLIES I am in a not sleeping  …I might also sleep when I’m not in a maths lecture (M  S)  (M  S) DOES NOT IMPLY I am in a IMPLIES maths lecture  I am sleeping a logically equivalent statement is. I am NOT sleeping (M  S) IMPLIES  I am in NOT in a maths lecture (S  M ) Equivalent Propositions Different propositions may be equivalent: (M  S) (S  M ) M  S How do we show they are logically equivalent ? Equivalent Propositions If p and q are logically equivalent propositional statements, then: their truth tables must be the same, And so the proposition p  q must be true; A proposition that must be true is called a tautology: A proposition that must be false is called a contradiction. Equivalent Propositions II To show logical equivalence of p and q: ❖construct the truth tables for both of them, or ❖construct the truth table for p  q, or ❖use the laws of propositional logic (to follow). Recap: Truth Tables p p T F F T p q pq p q p+q T T T T T F T F T T F T F T T F T T F F F F F F p q pq T T T F F F F T F F F F p q pq p q pq T T T T T T T F F T F F F T T F T F F F T F F T p T T F F Implication For propositions p and q: - written p  q, - p is the premise - q is the conclusion. q T F T F pq T F T T usually pronounced “p implies q”, or “if p then q”, (p  q) is TRUE if p is false, or q is true EQUIVALENTLY (p  q) is FALSE if, and only if, p is TRUE, and q is FALSE, Law for implication: p  q is equivalent to  q   p. Exercise 1.25 Construct truth tables for each of the following formulae to determine which are tautologies and which are contradictions. p  (p  q ) p  (q  p ) ( p  p )  p ( p  q )  ( p  q ) 10 p  (p  q ) T T F F T T F F T F T F p  (p  q ) T T F F F F T T T T F F T F T F p  (p  q ) T T F F F F T T T T F F F F T F T F T F p  (p  q ) T T F F T T T F F F T T T T F F F F T F T F T F Neither a tautology or a contradiction p  (q  p ) T T F F T F T F T T F F p  (q  p ) T T F F T F T F T T F T T T F F p  (q  p ) T T F F T T T T T F T F T T F T tautology T T F F ( p  p )  p T F ( p  p )  p T F F T F T ( p  p )  p T F F T F T F T ( p  p )  p T F F T F T T T tautology F T ( p  q )  ( p  q ) T T F F T F F F T F T F F F F F F F F T T T F F contradiction T T T F T F T F Algebraic Laws 1 These define equivalence of propositions: Commutativity: p  q  q  p p  q  q  p; Associativity: p  (q  r)  (p  q)  r p  (q  r)  (p  q)  r Idempotence: p  p  p and p  p  p Algebraic Laws 2 Distributivity: p  (q  r)  (p  q)  (p  r) p  (q  r)  (p  q)  (p  r) De Morgan’s Laws: (p  q)   p   q (p  q)   p   q Double Negation Law: ( p)  p; Algebraic Laws 3 Tautology Laws: p  true  true p  true  p; Contradiction Laws: p  false  p p  false  false; Excluded Middle Laws: p   p  true p   p  false; Absorption Laws: p  (p  q)  p p  (p  q)  p; Algebraic Laws 4 Implication Law: p  q   p  q; Contrapositive Law: (p  q)  ( q   p); Equivalence Law: (p  q)  (p  q)  (q  p). Summary p  q  q  p p  q  q  p p  (q  r)  (p  q)  r p  (q  r)  (p  q)  r Idempotence: p  p  p and p  p  p Distributivity: p  (q  r)  (p  q)  (p  r) p  (q  r)  (p  q)  (p  r) De Morgan’s Laws: (p  q)   p   q (p  q)   p   q Double Negation Law: ( p)  p; Tautology Laws: p  true  true p  true  p Contradiction Laws: p  false  p p  false  false Excluded Middle Laws: p   p  true p   p  false Absorption Laws: p  (p  q)  p p  (p  q)  p Implication Law: p  q   p  q Contrapositive Law: p  q   q   p Equivalence Law: (p  q)  (p  q)  (q  p) Commutativity: Associativity: Modelling with Prop. Logic: Ex 2 An Airplane Controller Example: Some current code: if (CabinPressure < MinPressure) then PrepareForLanding; if (FlightHeight < MinHeight) then PrepareForLanding; A programmer proposes optimisation: if ((CabinPressure < MinPressure) and (FlightHeight < MinHeight)) then PrepareForLanding; i) Is this a valid optimisation? ii) How do we verify whether this is a valid optimisation ? Solution: Define appropriate variables: let P be ‘CabinPressure < MinPressure’ let H be ‘FlightHeight < MinHeight’ let L be the action ‘PrepareForLanding’ Model the current behaviour: (P → L )  (H → L ) Consider two optimisations: (P  H ) → L (P  H ) → L Which of these formulae are correct ? (use Truth Tables) Solution (using truth tables) P H L (P  H ) (P  H ) P→L H →L (P  H ) → L (P  H ) → L ( P → L)  ( H → L) T T F T F F F T T T T T F F T F T F T F T T T T T F T F T F T F F T F F F T F F T T T T T F F F F F T T T T T T T T T T T T T T F T T F T F T T F T F F T F T T Solution (using truth tables) P H L (P  H ) (P  H ) P→L H →L T T T T T T T T T F T T F F T F T T F T T F F T F F T T T F T F (P  H ) → L (P  H ) → L ( P → L)  ( H → L) T F T T F F T T T T F T F T F F T T T T T T F T F F T F F F T F F T T T T T F F F F F T T T T T USING ALGEBRAIC LAWS, SHOW: (P → L )  (H → L ) 𝑃→𝐿 ∧ 𝐻→𝐿 ⇔  (P  H ) → L 𝑃→𝐿 ∧ 𝐻→𝐿 USING ALGEBRAIC LAWS, SHOW: (P → L )  (H → L ) 𝑃→𝐿 ∧ 𝐻→𝐿 Implication ⇔ ⇔  (P  H ) → L 𝑃→𝐿 ∧ 𝐻→𝐿 ¬𝑃 ∨ 𝐿 ∧ ¬𝐻 ∨ 𝐿 USING ALGEBRAIC LAWS, SHOW: (P → L )  (H → L ) 𝑃→𝐿 ∧ 𝐻→𝐿 ⇔ Implication ⇔ Commutativity (x2) ⇔  (P  H ) → L 𝑃→𝐿 ∧ 𝐻→𝐿 ¬𝑃 ∨ 𝐿 ∧ ¬𝐻 ∨ 𝐿 𝐿 ∨ ¬𝑃 ∧ 𝐿 ∨ ¬𝐻 USING ALGEBRAIC LAWS, SHOW: (P → L )  (H → L ) 𝑃→𝐿 ∧ 𝐻→𝐿 ⇔ Implication ⇔ Commutativity (x2) ⇔ Distributivity ⇔  (P  H ) → L 𝑃→𝐿 ∧ 𝐻→𝐿 ¬𝑃 ∨ 𝐿 ∧ ¬𝐻 ∨ 𝐿 𝐿 ∨ ¬𝑃 ∧ 𝐿 ∨ ¬𝐻 𝐿 ∨ ¬𝑃 ∧ ¬𝐻 USING ALGEBRAIC LAWS, SHOW: (P → L )  (H → L ) 𝑃→𝐿 ∧ 𝐻→𝐿 ⇔ Implication ⇔ Commutativity (x2) ⇔ Distributivity ⇔ De Morgan ⇔  (P  H ) → L 𝑃→𝐿 ∧ 𝐻→𝐿 ¬𝑃 ∨ 𝐿 ∧ ¬𝐻 ∨ 𝐿 𝐿 ∨ ¬𝑃 ∧ 𝐿 ∨ ¬𝐻 𝐿 ∨ ¬𝑃 ∧ ¬𝐻 𝐿∨¬ 𝑃∨𝐻 USING ALGEBRAIC LAWS, SHOW: (P → L )  (H → L ) 𝑃→𝐿 ∧ 𝐻→𝐿 ⇔ Implication ⇔ Commutativity (x2) ⇔ Distributivity ⇔ De Morgan ⇔ Commutativity ⇔  (P  H ) → L 𝑃→𝐿 ∧ 𝐻→𝐿 ¬𝑃 ∨ 𝐿 ∧ ¬𝐻 ∨ 𝐿 𝐿 ∨ ¬𝑃 ∧ 𝐿 ∨ ¬𝐻 𝐿 ∨ ¬𝑃 ∧ ¬𝐻 𝐿∨¬ 𝑃∨𝐻 ¬ 𝑃∨𝐻 ∨𝐿 USING ALGEBRAIC LAWS, SHOW: (P → L )  (H → L ) 𝑃→𝐿 ∧ 𝐻→𝐿 ⇔ Implication ⇔ Commutativity (x2) ⇔ Distributivity ⇔ De Morgan ⇔ Commutativity ⇔ Implication ⇔  (P  H ) → L 𝑃→𝐿 ∧ 𝐻→𝐿 ¬𝑃 ∨ 𝐿 ∧ ¬𝐻 ∨ 𝐿 𝐿 ∨ ¬𝑃 ∧ 𝐿 ∨ ¬𝐻 𝐿 ∨ ¬𝑃 ∧ ¬𝐻 𝐿∨¬ 𝑃∨𝐻 ¬ 𝑃∨𝐻 ∨𝐿 𝑃∨𝐻 →𝐿 • Proofs can be more elegant – but more difficult. • In the online (multiple choice) exam, you just need to identify which rules are being used. Exercise 1.27: Give derivations of the following equivalences: i. p  (p  q )  ii. ( p  q )  iii. pq p  q p  (q  r )  ( p  q)  ( p  r ) iv. ( p  q )  r  ( p  r )  (q  r ) Proofs are provided on the next slides for you to look through. You are not expected to be able to do the proofs. However, you should be able to understand the steps (appreciate how the application of an algebraic rule enables manipulation of formula from one line in proof to the next). Exercise 1.27(i): 1. p  ( p  q )  p  ( p  q )  (distributivity) pq p  ( p  q )  ( p  p )  ( p  q ) (excluded middle)  false  ( p  q) (commutativity laws)  ( p  q)  false (Contradiction Laws)  ( p  q) Exercise 1.27(i): 1. p  ( p  q )  p  ( p  q )  (distributivity) pq p  ( p  q )  ( p  p )  ( p  q ) (excluded middle)  false  ( p  q) (commutativity laws)  ( p  q)  false (Contradiction Laws)  ( p  q) Exercise 1.27(ii): ( p  q)  p  q ( p  q )  ( p  q ) (implication laws)  (p  q ) (De Morgan laws)  p  q (double negation)  p  q Exercise 1.27(ii): ( p  q)  p  q ( p  q )  ( p  q ) (implication laws)  (p  q ) (De Morgan laws)  p  q (double negation)  p  q Exercise 1.27(iii): p  (q  r )  ( p  q)  ( p  r ) p  (q  r )  p  (q  r ) (implication)  p  ( q  r ) (distributivity)  (p  q )  (p  r ) (implication)  ( p  q)  ( p  r ) Exercise 1.27(iii): p  (q  r )  ( p  q)  ( p  r ) p  (q  r )  p  (q  r ) (implication)  p  ( q  r ) (distributivity)  (p  q )  (p  r ) (implication)  ( p  q)  ( p  r ) Exercise 1.27(iv): ( p  q)  r ( p  q)  r (implication) (De Morgan)  ( p  r )  (q  r )  ( p  q)  r  ( p  q)  r  ( p  q )  r (Distributivity)  ( p  r )  (  q  r ) (Implication)  ( p  r )  (q  r ) Exercise 1.27(iv): (𝑝 ∨ 𝑞) ⇒ 𝑟 (implication) (De Morgan) (Distributivity) (Implication) ( p  q)  r ⇔ ⇔ ⇔ ⇔ ⇔  ( p  r )  (q  r ) (𝑝 ∨ 𝑞) ⇒ 𝑟 ¬(𝑝 ∨ 𝑞) ∨ 𝑟 (¬𝑝 ∧ ¬𝑞) ∨ 𝑟 (¬𝑝 ∨ 𝑟) ∧ (¬𝑞 ∨ 𝑟) (𝑝 ⇒ 𝑟) ∧ (𝑞 ⇒ 𝑟) Barking dogs don’t bite. My dog doesn’t bark Should we be concerned? Barking dogs don’t bite. Construct the truth table W denotes it barks (woofs) B denotes it bites W  ¬B W  ¬B W ¬B T T T T F F F T T F F T Barking dogs don’t bite. W  ¬B My dog doesn’t bark W  ¬B W ¬B T T T T F F F T T F F T ¬W Barking dogs don’t bite. W  ¬B My dog doesn’t bark ¬W W  ¬B W ¬B T T T T F F F T T F F T NOTICE ¬B can be TRUE or FALSE is consistent with the implication beingTRUE it might be a dog that doesn’t bark but bites OR it could be a dog that doesn’t bark and doesn’t bite Barking dogs don’t bite. My dog doesn’t bark Should we be concerned? MAYBE – WE DON’T KNOW 52 Barking dogs don’t bite. My dog bites What can we conclude? 53 Barking dogs don’t bite. W  ¬B B ¬W B ¬W T F F T F F T F F F T T F T T F F T T T T W ¬B T T T Equivalent propositions (B¬W)  Barking dogs  don’t bite. My dog bites & (W  ¬B) Identical Truth Tables Biting dogs don’t bark. Barking dogs don’t bite. EQUIVALENTLY Biting dogs don’t bark.  My dog doesn’t bark Barking dogs don’t bite. My dog doesn’t bite What can we conclude? 55 Barking dogs don’t bite. W  ¬B W ¬B T T T T F F F T T F F T My dog doesn’t bite ¬ B=T What can we conclude? Nothing – it might be a dog that barks that doesn’t bite OR it could be a dog that doesn’t bark and doesn’t bite Both are consistent with the implication being TRUE Summary: Propositional Logic • • • • • Propositions and deductions Syntax Trees Truth Tables Tautologies, contradictions Algebra of propositional logic Next… Set Theory – Lectures 4,5 Predicate logic – Lectures 6,7,8.