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.

  • $\begingroup$ I agree with you about line $3$, but isn't your result in disjunctive normal form? $\endgroup$ – saulspatz Feb 8 '19 at 4:58

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 ∧.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.