Issue with converting to conjunctive normal form

59 Views Asked by At

I am learning how to convert proposition logic formulae into conjunctive normal form, and came across this example:

¬(¬p ∧ (q ∨ ¬(r ∧ s))) [line 1]

≡ ¬¬p ∨ ¬(q ∨ ¬(r ∧ s))) [line 2, using De Morgan's law]

≡ p ∨ (¬q ∨ ¬¬(r ∧ s)) [line 3]

≡ p ∨ (¬q ∨ (r ∧ s)) [line 4]

For line 3, wouldn't you need to apply De Morgan's law again on '¬(q ∨ ¬(r ∧ s)))' (from line 2), so that line 3 should be:

p ∨ (¬q ∧ ¬¬(r ∧ s))

I am not sure why the final result is p ∨ (¬q ∨ (r ∧ s)) and not p ∨ (¬q ∧ (r ∧ s)). Any insights are appreciated.

1

There are 1 best solutions below

0
On

It is clear that there is some mistake in the quoted material at line 3, so there might be other mistakes as well if this is from some Notes. Assuming line 1 is correct, then we can determine

p v (¬q ∧ (r ∧ s))

and as remarked this is in disjunctive normal form, usually more directly presented without the extra brackets within disjuncts (ie using the ∧ associative law) as:

p v (¬q ∧ r ∧ s)

If the request is to translate this into Conjunctive Normal Form, then we need a conjunct between disjunctives:

(p v ¬q) ∧ (p v r) ∧ (p v s)

by the distributive law between v and ∧.