Question

[(Food ^ Drinks => Party) v (Drinks ^ Dance => Party)] => (Party => Drinks)

Convert the left-hand side of this formula (in the brackets) into CNF and then into clauses. Show all steps of deriving the clauses.

1. Convert the right-hand side of this formula (not in the brackets) into CNF and then into clauses. Show all steps of deriving the clauses.

Answer 1

(A^B => C) ≡ (~(A^B) v C) ≡ (~A v ~B v C) .....(1) [Since (P=>Q) ≡ (~P v Q) and ~(P^Q) ≡ (~P v ~Q)]

LHS of formula:

[(Food ^ Drinks => Party) v (Drinks ^ Dance => Party)]

≡ [ ~Food v ~Drinks v Party v ~Drinks v ~Dance v Party] .....(From (1))

≡ [~Food v ~Drinks v ~Drinks v Party] [Since P v P ≡ P]

Thus there is only one clause : [~Food v ~Drinks v ~Drinks v Party]

RHS of formula:

Party => Drinks

≡ ~Party v Drinks [Since (P => Q) ≡ (~P v Q)]

The above is the CNF form and the clause is ~Party v Drinks.

If required, the clause can be converted into canonical normal form.

≡ (~Party v Drinks) ^ T [Since A ^ T ≡ A]

≡ (~Party v Drinks) ^ (~Dance v Dance) [Since ~A v A ≡ True]

≡ (~Party v Drinks v ~Dance) ^ (~Party v Drinks v Dance) [Distributive Law]

≡ ((~Party v Drinks v ~Dance) ^ T) ^ ((~Party v Drinks v Dance) ^ T)

≡ ((~Party v Drinks v ~Dance) ^ (~Food v Food)) ^ ((~Party v Drinks v Dance) ^ (~Food v Food))

≡ ((~Party v Drinks v ~Dance) ^ (~Food v Food)) ^ ((~Party v Drinks v Dance) ^ (~Food v Food))

≡ (~Party v Drinks v ~Dance v ~Food) ^ (~Party v Drinks v ~Dance v Food) ^ (~Party v Drinks v Dance v ~Food) ^ (~Party v Drinks v Dance v Food)

The above is the canonical CNF form with 4 clauses.