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$

2 Answers 2

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$

You must log in to answer this question.

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