disc03-regular-sols

Q2. Propositional Logic (a) Provide justification for whether each of the following are correct or incorrect. (i) ( X ∨ Y ) | = Y Incorrect: ( X ∨ Y ) | = Y if and only if ( X ∨ Y ) ∧ ¬ Y is unsatisfiable; however, the latter is satisfied by X = true and Y = false . (ii) ¬ X ∨ ( Y ∧ Z ) | = ( X = ⇒ Y ) Correct: Via the same reasoning as the previous part, we can attempt to show that ( ¬ X ∨ ( Y ∧ Z )) ∧ ¬ ( X = ⇒ Y ) is unsatisfiable as follows: • ( ¬ X ∨ ( Y ∧ Z )) ∧ ¬ ( X = ⇒ Y ) • ( ¬ X ∨ ( Y ∧ Z )) ∧ ¬ ( ¬ X ∨ Y ) • ( ¬ X ∨ ( Y ∧ Z )) ∧ ( X ∧ ¬ Y ) Its clear that for the RHS to evaluate to true, X = true and Y = false . However, setting that automatically makes the LHS evaluate to false. Thus, the whole thing is unsatisfiable, so the original must be correct. (iii) ( X ∨ Y ) ∧ ( Z ∨ ¬ Y ) | = ( X ∨ Z ) Correct: In general, A | = B if and only if A = ⇒ B is valid. To show that this works for this problem, we can write it as an implication and prove by counterexample that the statement is always valid. Consider ( X ∨ Y ) ∧ ( Z ∨ ¬ Y ) = ⇒ ( X ∨ Z ). In general, A = ⇒ B only evaluates to false if A = true and B = false . In order for the RHS to evaluate to false, X = false and Z = false . Plugging those in, the LHS evaluates to ( false ∨ Y ) ∧ ( false ∨¬ Y ), which can never evaluate to true. Therefore, that case never holds, so the implication is valid. (b) Consider the following sentence: [( Food = ⇒ Party ) ∨ ( Drinks = ⇒ Party )] = ⇒ [( Food ∧ Drinks ) = ⇒ Party ] . (i) Determine, using enumeration, whether this sentence is valid, satisfiable (but not valid), or unsatis- fiable. A simple truth table has eight rows, and shows that the sentence is true for all models and hence valid. (ii) Convert the left-hand and right-hand sides of the main implication into CNF. For the left-hand side we have: • ( Food = ⇒ Party ) ∨ ( Drinks = ⇒ Party ) • ( ¬ Food ∨ Party ) ∨ ( ¬ Drinks ∨ Party ) • ( ¬ Food ∨ Party ∨ ¬ Drinks ∨ Party ) • ( ¬ Food ∨ ¬ Drinks ∨ Party ) For the right-hand side we have: • ( Food ∧ Drinks ) = ⇒ Party • ¬ ( Food ∧ Drinks ) ∨ Party • ( ¬ Food ∨ ¬ Drinks ) ∨ Party • ( ¬ Food ∨ ¬ Drinks ∨ Party ) (iii) What do you observe about the LHS and RHS after converting to CNF? Explain how your results prove the answer to part b.i. The two sides are identical in CNF, and hence the original sentence is of the form P = ⇒ P , which is valid for any P . 2