I'm trying to convert the negation of the following formula to CNF:
(p → (q → r)) → ((p → q) → (p → r))
These are the steps I am following:
¬((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 ∧ ¬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 ∧ ¬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 ∨ q) ∧ (¬¬p ∧ ¬r)))
(¬p ∨ (¬q ∨ r)) ∧ ((¬p ∨ q) ∧ (p ∧ ¬r))
(¬p ∨ ¬q ∨ r) ∧ (¬p ∨ q) ∧ (p ∧ ¬r)
This is where I'm getting stuck - I am now left with 2 sets of disjunctions, and 1 conjunction. I know CNF is a conjunction of disjunctions, so clearly I must've done something wrong here.
The only thing I can think of to convert the conjunction to a disjunction is perhaps using the distributive law, but I can't figure out how to apply it in a case like this.
Can anyone please point out my mistake?
Thank you!
Good so far. Now just remove the rightmost pair of parentheses. $$ \lnot [(p \implies (q \implies r)) \implies ((p \implies q) \implies (p \implies r))] \\ \lnot [\lnot (\lnot p \lor (\lnot q \lor r)) \lor (\lnot (\lnot p \lor q) \lor (\lnot p \lor r))] \\ (\lnot p \lor (\lnot q \lor r)) \land \lnot (\lnot (\lnot p \lor q) \lor (\lnot p \lor r)) \\ (\lnot p \lor (\lnot q \lor r)) \land ((\lnot p \lor q) \land \lnot (\lnot p \lor r)) \\ (\lnot p \lor (\lnot q \lor r)) \land ((\lnot p \lor q) \land (p \land \lnot r)) \\ (\lnot p \lor \lnot q \lor r) \land (\lnot p \lor q) \land p \land \lnot r $$ This is already in CNF. But you can simplify it by noting that $p$ prevents $\lnot p$ and $\lnot r$ prevents $r$, yielding: $$ \lnot q \land q \land p \land \lnot r, $$ which is always false.