COM1002 Foundations of Computer Science Autumn 2023 Lecture 2: Propositional Logic II PDF

COM1002 Foundations of Computer Science: Autumn Semester 2023 Lecture 2: Propositional Logic II Dr Paul Watton [email protected] Exercise 1, Q3: Kangaroo Puzzle • The only animals in this house are cats. • Every animal that loves to gaze at the moon is suitable for a pet. When I detest an...

COM1002 Foundations of Computer Science: Autumn Semester 2023 Lecture 2: Propositional Logic II Dr Paul Watton [email protected] Exercise 1, Q3: Kangaroo Puzzle • The only animals in this house are cats. • Every animal that loves to gaze at the moon is suitable for a pet. When I detest an animal, I avoid it. • No animals are carnivorous, unless they prowl at night. • No cat fails to kill mice. • No animal ever takes to me, except those that are in this house. Kangaroos are not suitable for pets. • None but carnivora kill mice. • I detest animals that do not take to me. • Animals that prowl at night always love to gaze at the moon. Exercise 1 Q3: Express the above statements with propositional logic. What can we conclude about Kangaroos? I leave this for you to attempt yourself. However, I will go through a similar example now. Example • • • • • No one, who is going to a party, ever fails to brush their hair No one looks fascinating, if they are untidy Opium-eaters have no self-control Everyone, who has brushed their hair, looks fascinating No one wears deely boppers, unless they are going to a party • A person is always untidy, if they have no self-control. Do opium eaters wear Deely Boppers ? 3 Solving strategy… • • • • • • No one, who is going to a party, ever fails to brush their hair No one looks fascinating, if they are untidy Opium-eaters have no self-control Everyone, who has brushed their hair, looks fascinating No one wears deely boppers, unless they are going to a party A person is always untidy, if they have no self-control. 1. Identify the propositions and represent with variables 2. Try to rephrase the implication statements in the form: If * * * then * * * 3. Express statements with propositional logic variables. 4. Use the rules for inference to derive a deduction Solving strategy… • • • • • • No one, who is going to a party, ever fails to brush their hair No one looks fascinating, if they are untidy Opium-eaters have no self-control Everyone, who has brushed their hair, looks fascinating No one wears deely boppers, unless they are going to a party A person is always untidy, if they have no self-control. 1. Identify the propositions (REMEMBER: propositions can only be either TRUE or FALSE) Solving strategy… Identify the propositions. The statements are about individual people and recall a proposition can only be TRUE or FALSE. • No one, who is going to a party, ever fails to brush their hair • No one looks fascinating, if they are untidy • Opium-eaters have no self-control • Everyone, who has brushed their hair, looks fascinating • No one wears deely boppers, unless they are going to a party • A person is always untidy, if they have no self-control. These statements are referring to people. Suppose ‘they’ in this context refers to a general person. • No one, who is going to a party, ever fails to brush their hair P = they is going to a party B = they has brushed hair • No one looks fascinating, if they are untidy F= they looks fascinating T = they is tidy • Opium-eaters have no self-control O= they is an opium eater S= they has self-control • Everyone, who has brushed their hair, looks fascinating B = they has brushed hair F= they looks fascinating • No one wears deely boppers, unless they are going to a party D = they is wearing deely boppers P = they is going to a party • A person is always untidy, if they have no self-control. T = they is tidy C = they has self-control Solving strategy… • • • • • • No one, who is going to a party, ever fails to brush their hair No one looks fascinating, if they are untidy Opium-eaters have no self-control Everyone, who has brushed their hair, looks fascinating No one wears deely boppers, unless they are going to a party A person is always untidy, if they have no self-control. 2. Try to rephrase the implication statements in the form: If * * * then * * * 3. Express statements with propositional logic variables. No one, who is going to a party, ever fails to brush their hair If it is going to a party then it has brushed hair P = it is going to a party; B = it has brushed hair; PB Recall: (A  B) (¬B  ¬A) So, equivalently: ¬B  ¬P If it hasn’t brushed hair then it is not going to a party http://www.healthnewsreview.org/review/the-guardians-bad-hairday-no-cortisol-in-hair-cant-reveal-future-mental-health-risk-inchildren/ Rephrased in English: Everyone without brushed hair isn’t going to a party No one looks fascinating, if they are untidy F = it looks fascinating; T = it is tidy; If it is not tidy then it does not look fascinating ¬T  ¬F Equivalently: FT If it looks fascinating then it is tidy Rephrased in English: All people who look fascinating are tidy Opium-eaters have no self-control C = it has self-control; O = it is an opium eater; If it is an opium eater then it has no self-control O  ¬C Equivalently: C  ¬O If it has self control then is it not an opium eater Rephrased in English: Everyone who has self-control is not an opium eater Every one, who has brushed their hair, looks fascinating; B = it has brushed hair; If it has brushed hair F = it looks fascinating; then it looks fascinating BF Equivalently: If it does not look fascinating ¬F  ¬B then it has not brushed hair Rephrased in English: Every one, who doesn’t look fascinating has not brushed their hair; No one wears deely boppers, unless they are going to a party P = it is going to a party; If it is wearing deely boppers D = it is wearing deely boppers then it is going to a party DP Equivalently: If ¬P  ¬D it is not going to a party then it is not wearing deely boppers Rephrased in English: Everyone not going to a party is not wearing deely boppers A person is always untidy, if they have no self-control. C = it has self-control; If it has no self-control then T = it is tidy; it is not tidy (¬C  ¬T) (T  C) Equivalently: if it is tidy then they it has self-control Rephrased in English: tidy people have self control No one, who is going to a party, ever fails to brush their hair PB No one looks fascinating, if they are untidy ¬T  ¬F Opium-eaters have no self-control O  ¬C Every one, who has brushed their hair, looks fascinating BF No one wears deely boppers, unless they are going to a party D P ¬C  ¬ T PB BF equivalently equivalently ¬F  ¬B ¬ B  ¬P ¬P  ¬D A person is always untidy, if they have no self-control O  ¬C ¬C  ¬T ¬T  ¬F O  ¬D Opium eaters do not wear deely boppers D  ¬O People who wear deely boppers are not opium eaters To do… • Exercise sheet 1 will be uploaded to blackboard today. • Please attempt questions 1-3 on exercise sheet 1. (Exercises 4-6 can be attempted after the Lecture On Tuesday Oct 3rd) • Try to attempt all the exercises before the tutorial (Friday 6th October). 16 Use the same approach to solve the Kangaroo puzzle…(Ex1, Q3) • The only animals in this house are cats. • Every animal that loves to gaze at the moon is suitable for a pet. When I detest an animal, I avoid it. • No animals are carnivorous, unless they prowl at night. • No cat fails to kill mice. • No animal ever takes to me, except those that are in this house. Kangaroos are not suitable for pets. • None but carnivora kill mice. • I detest animals that do not take to me. • Animals that prowl at night always love to gaze at the moon. TIP: All statements are about animals. For the first statement, you could use the propositions: H = it is in this house C = it is a cat If it is in this house then it is a cat Truth Tables Negation For a proposition p: • written  p, • usually pronounced “not p”, • meaning of  p is “p is false”. Laws for negation: •  true = false, and  false = true; • for any p,   p = p • the law of double negation. p p F T T F Disjunction For propositions p and q: • • • • written p  q, usually pronounced “p or q”, is true if either p is true, or q is true, or both, p and q are often called disjuncts. Law for disjunction: p   p = true the law of the excluded middle. p F F T T q F T F T pq F T T T Conjunction For propositions p and q: • • • • written p  q, usually pronounced “p and q”, is true if both p is true and q is true, p and q are often called conjuncts. p F F T T q F T F T pq F F F T Law for conjunction: p   p = false. p F F T T Implication For propositions p and q: - written p  q, - p is the premise - q is the conclusion. q F T F T pq T T F 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. Equivalence For propositions p and q: p F F T T written p  q, usually pronounced “p is equivalent to q”, or “p, if and only if q”, q F T F T pq T F F T is true if both p and q have the same value Law for equivalence: p  q is equivalent to (p  q)  (q  p). Propositional Logic Syntax Defines propositional formulae: Atomic formulae: - two constants (true, false), - single variables P, Q, R, …; Compound formulae: - formulae linked by the connectives, -  p, p  q, p  q, p  q, p  q. Propositional Logic Syntax 2 Parentheses and Precedences Example from ordinary algebra: • 5 + 3 x 2 is understood as 5 + (3 x 2), • the brackets specify the order of execution, • but the operators have a “precedence”: multiplication has higher precedence than addition. Precedence in propositional logic: • highest is , then , , , lowest is , • there is also a right-to-left rule, • but if in doubt: use brackets. Syntax Trees Diagrammatic representations of the structures of formulae: Describe how a sentence is formed from simpler sentences. Eg the formula (P  Q)   (P  Q), the tree is: Root – last connective added in the formula construction   Every branch ends with a propositional variable (leaf). P   Q P Try: exercise 1.23 Q Exercise 1.23 Construct syntax trees and the truth tables for the following formulae: (P  Q ) (P  Q )  (P  Q ) P  (Q  R ) Please attempt each in turn and I’ll go through the solutions (P  Q ) Construct Syntax Tree and Truth Table Finished (i) ?  (P  Q )  Syntax Tree  P Q Truth Table P Q ¬Q T T T F F T F F F T F T P¬Q F T T F ¬(P¬Q) T F F T (P  Q )  (P  Q ) Finished (ii) ? Construct Syntax Tree and Truth Table (P  Q )  (P  Q )  Syntax Tree P P Q T T T F F T F F   P  Q ¬P ¬Q T F F F F F T T F T F T Q ¬P  ¬Q F F F T   P Q (P  Q)(¬P  ¬Q) T F F T (P  Q )  (P  Q ) PQ T T T T T T F F F T F T F F F F F T F T F F T F T F F F F F F F T T T T (4) (2) (3) (2) Step order (1) (3) (1) P  (Q  R ) Finished (iii) ? Construct Syntax Tree and Truth Table P  (Q  R )  Syntax Tree  P  Q R P  (Q  R ) P Q R T T T T T F T T T T F T F F F F T F T T T T T T T F F T T T T F F T T F T F T T F T F F T F F F F F T F T T T T F F F F T T T F (4) (2) (3) Step order (1) (1) Tips: combinations of truth values for a compound forumula with 2, 3 and 4 propositions. P Q R S T T T T T T T F T T F T P Q R T T F F T T T T F T T P Q T T F T F T F T T T F T T F F T T F T F F T F F F F T F T T F T T T F F F T F F T T F F F T F T F T F F F F T F F F F T T F F T F F F F T F F F F36