1
$\begingroup$

I was working on an examples from my textbook concerning transforming formulae into disjunctive-normal form (DNF) until I found an expression that I cannot solve. I hope somebody can help me transform the following statement into DNF:

$ (\lnot q \lor r) \land ( q \lor \lnot r)$

4 Answers 4

4

$ (\lnot q \lor r) \land ( q \lor \lnot r)\tag{1}$ $[(\lnot q \lor r) \land q] \lor [(\lnot q \lor r) \land \lnot r]\tag{2}$ $[(\lnot q \land q) \lor (r \land q)] \lor [(\lnot q \land \lnot r) \lor (r \land \lnot r)]\tag{3}$ $ \text{False} \lor (r \land q) \lor (\lnot q \land \lnot r) \lor \text{False}\tag{4}$

$(q \land r) \lor (\lnot q \land \lnot r)\tag{5}$

Note that $(5)$ is is in disjunctive normal form (DNF), and is equivalent to $(1)$.

$(1) \to (2)$: Distribution;
$(2) \to (3)$: Distribution, twice;
$(3) \to (4)$: Contradictions $\lnot q \land q \rightarrow \text{False}$ and $\lnot r \land r\rightarrow \text{False}$;
$(4) \to (5)$: Simplification (removal of contradictory disjuncts).

Observation: both $(1)$ and $(5)$ are equivalent to $q \leftrightarrow r$:
To see this, you can rewrite $(1)$ as: $(\lnot q \lor r) \land (\lnot r \lor q) \iff (q \rightarrow r) \land (r\rightarrow q) \iff (q \leftrightarrow r).$

$q \leftrightarrow r\; \text{ is true if and only if }\;(q \land r) \text{ is true or}\; (\lnot q \land \lnot r)\text{ is true.}$ $\text{That is,}\;q \leftrightarrow r\; \text{ is true if and only if }\;\;(q \land r) \lor (\lnot q \land \lnot r).\tag{5} $

p | q |$\;\lnot q \lor r$ | $q \lor \lnot r\;$|$\;(\lnot q \lor r) \land (q\lor \lnot r)$
T | T | $\quad$T $\quad$|$\quad$ T $\quad$| $\quad\quad\quad\quad$T$\quad\quad\leftarrow\quad\;\; (q \land r)$
T | F | $\quad$F $\quad$|$\quad$ T $\quad$| $\quad\quad\quad\quad$F
F | T | $\quad$T $\quad$|$\quad$ F $\quad$| $\quad\quad\quad\quad$F
F | F | $\quad$T $\quad$|$\quad$ T $\quad$| $\quad\quad\quad\quad$T$\quad\quad\leftarrow\quad (\lnot q \land \lnot r)$

4

Make a table

 q  r  result  0  0     1  0  1     0  1  0     0  1  1     1 

Now you can get the DNF formula, by "or-ing" all the rows with result=1: $ (\lnot q \land \lnot r ) \lor ( q \land r )$

1

Think of it as an expression with $+$ and $\cdot$ and use the distributive law (I'll use $q'$ as notation for $\neg q$:

$(q' + r)(q + r') = q'q + q'r' + rq + rr' = q'r' + rq$

I cancelled $q'q$ and $r'r$ because $q$ cannot be true and false (and same for $r$). With your symbols, this gives

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

You can (and should) check that this is correct with a truth table.

1

By the distibution law one obtains $(\lnot q \lor r) \land ( q \lor \lnot r) \leftrightarrow ((\lnot q \lor r) \land q) \lor ((\lnot q \lor r) \land \lnot r) \leftrightarrow (\lnot q \land q) \lor (r \land q)\lor (\lnot q \land \lnot r) \lor (r \land \lnot r)\leftrightarrow (r \land q)\lor (\lnot q \land \lnot r)$