CMPS 211 Homework Assignment 02 Solution, Fall 2014

CMPS 211 – Fall 2014 1 Assignment 2 Solution Exercise 1: Let p be “the file system is locked” Let q be “the new messages will be queued” Let r be “new messages will be sent to a buffer” Let s be “the system is functioning normally” i. p → ¬q ∧ ¬r ii. ¬p → q iii. p ↔ ¬s iv. ¬q → r v. ¬r Let r be false, q be true, p be false, and s be false i. F → F ∧ T => T ii. T → T => T iii. F ↔ F => T iv. F → F => T v. T => T � The system specifications are consistent. Exercise 2: Let A be Amy, L be Laura, D be Dianna and N be Nivine. a) D said that she hasn’t met Amy yet but N said that she saw them together. So one of them is lying so the thief is D or N. L said that N and A dislike each other and A and D are friends. So this shows that N is the thief even though it is not a very strong proof. b) Either D or N is lying since D said that she didn’t see A and N said that she saw D with A. If D was the thief, N is not the thief and L is the thief since she said that A and D are friends (but D stole from A) and A and N are not friends (but N didn’t steal). And what proves this more is what N said, which is that she saw L and D with A. If N was the thief, both L and D will be innocent (check part a) CMPS 211 – Fall 2014 2 Original Question: The police have three suspects for the murder of Mr. Cooper: Mr. Smith, Mr. Jones, and Mr.Williams. Smith, Jones, and Williams each declare that they did not kill Cooper. Smith also states that Cooper was a friend of Jones and that Williams disliked him. Jones also states that he did not know Cooper and that he was out of town the day Cooper was killed. Williams also states that he 24 1 / The Foundations: Logic and Proofs saw both Smith and Jones with Cooper the day of the killing and that either Smith or Jones must have killed him. Can you determine who the murderer was if a) one of the three men is guilty, the two innocent men are telling the truth, but the statements of the guilty man may or may not be true? b) innocent men do not lie? Answer: a) We look at the three possibilities of who the innocent men might be. If Smith and Jones are innocent (and therefore telling the truth), then we get an immediate contradiction, since Smith said that Jones was a friend of Cooper, but Jones said that he did not even know Cooper. If Jones and Williams are the innocent truth-­‐tellers, then we again get a contradiction, since Jones says that he did not know Cooper and was out of town, but Williams says he saw Jones with Cooper (presumably in town, and presumably if we was with him, then he knew him). Therefore it must be the case that Smith and Williams are telling the truth. Their statements do not contradict each other. Based on Williams’ statement, we know that Jones is lying, since he said that he did not know Cooper when in fact he was with him. Therefore Jones is the murderer. b) This is just like part (a), except that we are not told ahead of time that one of the men is guilty. Can none of them be guilty? If so, then they are all telling the truth, but this is impossible, because as we just saw, some of the statements are contradictory. Can more than one of them be guilty? If, for example, they are all guilty, then their statements give us no information. So that is certainly possible. CMPS 211 – Fall 2014 3 Exercise 3: a) ¬(A ∧ B) ∧ ¬(¬C) ≡ (¬A ∨ ¬B) ∧ C b) ¬((A ∧ B) ∨ ¬C) ≡ ¬(A ∧ B) ∧ C ≡ (¬A ∨ ¬B) ∧ C Exercise 4: a) (p → r) → [(p → q) ∨ (q → r)] p q r p→r p→q q→r (p→q)∨(q→r) (p→r)→[(p→q)∨(q→r)] T T T T T T T T T T F F T F T T T F T T F T T T T F F F F T T T F T T T T T T T F T F T T F T T F F T T T T T T F F F T T T T T b) (p ∧ q) → [(p → q) ∨ ¬q] p q ¬q p∧q p→q (p→q)∨¬q (p∧q)→[(p→q)∨¬q] T T F T T T T T F T F F T T F T F F T T T F F T F T T T CMPS 211 – Fall 2014 4 c) [(p ∧ q) ∧ (¬r → q)] → p p q r ¬r p∧q ¬r→q (p∧q)∧(¬r→q) [(p∧q)∧(¬r→q)]→p T T T F T T T T T T F T T T T T T F T F F T F T T F F T F F F T F T T F F T F T F T F T F T F T F F T F F T F T F F F T F F F T d) [(q → r) ∧ (p ∧ q) ∧ (p → r)]→p p q r q→r p∧q p→r (q→r)∧(p∧q)∧(p→r) [(q→r)∧(p∧q)∧(p→r)]→p T T T T T T T T T T F F T F F T T F T T F T F T T F F T F F F T F T T T F T F T F T F F F T F T F F T T F T F T F F F T F T F T Exercise 5: a) (p → r) → [(p → q) ∨ (q → r)] ≡ ¬(p → r) ∨ [(p → q) ∨ (q → r)] ≡ ¬(¬p ∨ r) ∨ [(¬p ∨ q) ∨ (¬q ∨ r)] ≡ (p ∧ ¬r) ∨ [¬p ∨ (q ∨ ¬q) ∨ r] ≡ (p ∧ ¬r) ∨ T ≡ T b) (p ∧ q) → [(p → q) ∨ ¬q] ≡ ¬(p ∧ q) ∨ [(p → q) ∨ ¬q] ≡ ¬p ∨ ¬q ∨ [(¬p ∨ q) ∨ ¬q] ≡ ¬p ∨ ¬q ∨ ¬p ∨ q ∨ ¬q ≡ T CMPS 211 – Fall 2014 5 c) [(p ∧ q) ∧ (¬r → q)] → p ≡ ¬[(p ∧ q) ∧ (r ∨ q)] ∨ p ≡ [¬(p ∧ q) ∨ ¬(r ∨ q)] ∨ p ≡ ¬p ∨ ¬q ∨ (¬r ∧ ¬q) ∨ p ≡ T d) [(q → r) ∧ (p ∧ q) ∧ (p → r)] → p ≡ ¬[(¬q ∨ r) ∧ (p ∧ q) ∧ (¬p ∨ r)] ∨ p ≡ [¬(¬q ∨ r) ∨ ¬(p ∧ q) ∨ ¬(¬p ∨ r)] ∨ p ≡ [(q ∧ ¬r) ∨ (¬p ∨ ¬q) ∨ (p ∧ ¬r)] ∨ p ≡ (q ∧ ¬r) ∨ (p ∧ ¬r) ∨ [p ∨ ¬p] ∨ ¬q ≡ T Exercise 6: p q p ↓ q p ∨ q ¬(p ∨ q) T T F T F T F F T F F T F T F F F T F T They are equivalent since they have the same truth-­‐values Exercise 7: (p ↔ q) ∧ (q ↔ r) ≡ p → q ∧ q → p ∧ q → r ∧ r → q ≡ (p → q ∧ q → r) ∧ (r → q ∧ q → p) ≡ (p → r) ∧ (r → p) ≡ p ↔ r CMPS 211 – Fall 2014 6 Exercise 8: These follow directly from the definitions. An unsatisfiable compound proposition is one that is true for no assignment of truth values to its variables, which is the same as saying that it is false for every assignment of truth values, which is the same saying that its negation is true for every assignment of truth values. That is the definition of a tautology. Conversely, the negation of a tautology (i.e., a proposition that is true for every assignment of truth values to its variables) will be false for every assignment of truth-­‐values, and therefore will be unsatisfiable. Exercise 9: a) (p∨¬r∨¬s) ∧ (¬p∨¬q∨¬s) ∧ (p∨¬q∨¬s) ∧ (p∨q∨¬s) ∧ (p∨q∨¬r) Let p be true and s be false T ∧ T ∧ T ∧ T ∧ T ≡ T => Satisfiable b) (¬p∨¬r∨¬s) ∧ (p∨q∨¬s) ∧ (p∨¬q∨s) ∧ (¬p∨¬q∨r) ∧ (p∨¬r∨¬s) ∧ (¬p∨q∨¬r) Let p be true, q be false and r be false T ∧ T ∧ T ∧ T ∧ T ∧ T ≡ T => Satisfiable c) (q∨r∨s) ∧ (p∨¬q∨¬s) ∧ (p∨q∨¬s) ∧ (¬p∨r∨s) ∧ (p∨q∨r) ∧ (¬p ∨¬q∨¬r) ∧ (¬p∨r∨¬s) ∧ (¬p∨¬q∨s) Let p be false, q be true and s be false T ∧ T ∧ T ∧ T ∧ T ∧ T ∧ T ∧ T ≡ T => Satisfiable CMPS 211 – Fall 2014 7 Exercise 10: a) (p ↔ q) ↔ r ≡ p ↔ (q ↔ r) p q r p ↔ q q ↔ r (p ↔ q) ↔ r p ↔ (q ↔ r) T T T T T T T T T F T F F F T F T F F F F T F F F T T T F T T F T F F F T F F F T T F F T T F T T F F F T T F F b) Well, more than two statements combined together can be ambiguous… a. It might mean that all the propositions P1 through Pn are all true at the same time, or false at the same time… b. It might mean the following: c. (…((P1 ↔ P2) ↔ P3) ↔ P4) ↔…Pn) … in this case, the truth value of the statement depends on the count of false propositions, if they are even, then it is true, else it is false. Remember that the order of the propositions doesn’t matter, as can be shown directly from part a.