Convert and simplify the following sentences to Conjunctive

Convert and simplify the following sentences to Conjunctive Normal Form(CNF):

(a) (P (Q R)) (P (R Q))

(b) (P Q) (¬P Q)

(c) ((P Q) ¬Q) ¬P

Solution

Replace P Q with (¬P v Q)
       P <-> Q with (¬P v Q) (P v ¬Q)

(a) (P (Q R)) (P (R Q))
=> (P (¬Q v R)) (P (¬R v Q))
=> (¬P v (¬Q v R)) (¬P v (¬R v Q))
=> (¬P v ¬Q v R) (¬P v ¬R v Q)
=> ¬(¬P v ¬Q v R) v (¬P v ¬R v Q)
=> (P Q ¬R) v (¬P v ¬R v Q)       by De Morgan\'s laws
=>   (Q v ¬P v ¬R)                       by distributive laws

(b) (P Q) (¬P Q)
=> ¬(P Q) v (¬P Q)
=> (¬P v ¬Q) v ((P v Q) (¬P v ¬Q))
=> (¬P v ¬Q)                           by distributive laws

(c) ((P Q) ¬Q) ¬P
=> ¬((P Q) ¬Q) v ¬P
=>    ¬((¬P v Q) ¬Q) v ¬P
=> (¬(¬P v Q) v Q) v ¬P
=> ((P ¬Q) v Q) v ¬P
=>    (P v Q) v ¬P                       by distributive laws
=> Q