0
$\begingroup$

The propositional logic textbook I'm working through explains how to convert a formula in conjunctive normal form to clausal form, for instance:

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

has a clausal form of:

{{¬p, ¬q, r}, {¬p, q, ¬r}}

What I'm unsure about is why there are only 2 sets, and not 4 sets, as there are 4 conjuncts in the CNF formula. For instance, I would expect the following to be the clausal form for the formula:

{{r}, {¬p, ¬q, r}, {q}, {¬p, q, ¬r}}

Furthermore, the following examples are provided:

  1. (¬p ∨ ¬p) ∧ (p ∨ p) equates to {{¬p}, {p}}, which I understand

  2. (¬p ∨ p ∨ q) ∧ (¬p ∨ p ∨ q) equates to , which I don't quite understand - there can't be duplicate sets, but surely 1 of the instances can be present in the clausal form? I would expect the clausal form to be the following: {{q}}

  3. (¬p ∨ p) ∧ (¬p ∨ q) ∧ (¬p ∨ ¬q ∨ p) equates to {{¬p, q}}, which I don't quite understand - why are all the clauses put into 1 set, and not into separate sets, as with example 1 above? I would expect the clausal form to be the following: {{¬p, q}, {¬q}}

Clearly I'm missing something here. The textbook unfortunately does not explain the conversion process in a lot of detail, so I'm getting a bit lost.

Thanks!

$\endgroup$

1 Answer 1

1
$\begingroup$

Any conjunct that contains $p \lor \lnot p$ is automatically true and can thus be omitted.

$\endgroup$
1
  • $\begingroup$ Oh so if the conjunct contains a literal with its complement, the entire conjunct can be omitted, together with any other literals in that conjunct? That is the part I seem to have missed - but it does make logical sense. Thank you! $\endgroup$ Commented Apr 2, 2023 at 5:57

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .