2
$\begingroup$

I'm trying to convert the following Boolean expression into a CNF (or DNF):

$(\neg p \vee \neg q) \rightarrow (q \rightarrow \neg p)$

I apply various laws until I get to:

$(p \wedge q) \vee (\neg p \vee \neg q)$

This doesn't fit the form of a CNF, but I'm not sure how to get that last expression into an 'and' statement, or a series of more ORs of ANDs. I can do it by making a truth table and just writing it out, but is there some law that I am supposed to apply to $(\neg p \vee \neg q)$ to make it a CNF?

$\endgroup$
1
$\begingroup$

It might help to think by analogy with algebraic expressions formed using multiplication and addition. Multiplication distributes through addition, i.e., you have $x \times (y + z) = (x \times y) + (x \times z)$. Hence you can write any expression as a sum of products of atoms, by pushing the multiplications in through additions. But note that addition does not distribute through multiplication, so you can't write every expression as a product of sums of atoms.

Boolean algebra, however is much more symmetric: not only does conjunction distribute through disjunction, i.e., $x \land (y \lor z) = (x \land y) \lor (x \land z)$ but also disjunction distributes through conjunction, i.e., $ x \lor (y \land z) = (x \lor y) \land (x \lor z)$. Hence (also using De Morgan's laws to push in negations), you get to choose whether to push the conjunctions in, which will lead you to DNF: a disjunction of conjunctions of literals, or to push the disjunctions in, which will lead you to a CNF: a conjunction of disjunctions of literals. (Here "literal" means an atom or negated atom.) For example, your formula can be transformed into a CNF like this:

$$ \begin{array}{rcl} [(p \land q) \lor \lnot p] \lor \lnot q &=& [(p \lor \lnot p) \land (q \lor \lnot p)] \lor \lnot q\\ &=& (p \lor \lnot p \lor \lnot q) \land (q \lor \lnot p \lor \lnot q) \end{array} $$

You can now do further simplifications if you wish, e.g., to arrive at $p \lor \lnot p$ (which is both a DNF and a CNF).

$\endgroup$
0
$\begingroup$

You wrote that you want to "get the last expression into an 'and'..." This sounds to me as though you were confusing CNF and DNF:

  • A formula is in CNF if it is a conjunction of (certain) disjunctions, e.g. $(p \vee q) \wedge (r \vee s) \wedge \neg t$
  • A formula is in DNF if it is a disjunction of (certain) conjunctions, e.g. $(p \wedge q) \vee (r \wedge \neg s)$

Your second formula already is in disjunctive normal form, as will become clear by omitting some brackets:

$$(p \wedge q) \vee \neg p \vee \neg q$$

Obviously, this is a tautology. So you just have to find tautological formula that is in CNF.

Hint: The simplest such formula is one that is both in CNF and in DNF.

$\endgroup$

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.