How to convert $((x\land y)\lor(z\land u))\land((x\land\neg z)\lor (\neg y \lor u))\land((y\land z)\lor(x\land u))$ to the disjunctive normal form?

Question

Is there a faster way than doing a gigantic truth table? I tried some transformation but didn't find a way to simplify the problem.

Answer 1

Hint:

Use the following rules multiple times:

$$ (a\lor b)\land c = (a\land c)\lor(b\land c)$$ $$ (a\land b)\lor c = (a\lor c)\land(b\lor c)$$

Answer 2

Using associativity and commutativity of $\land$ and $\lor$, and the following rules: \begin{align} A \land (B \lor C) &\equiv (A \land B) \lor (A \land C) \\ A \land \lnot A &\equiv \bot \\ A \land A &\equiv A \\ A \land \bot &\equiv \bot \\ A \lor \bot &\equiv A \end{align}

you get: \begin{align} \big((x \land y)\lor(z\land u)\big) \land \big((x\land\neg z)\lor \neg y \lor u \big) \land \big((y\land z)\lor (x\land u)\big) \equiv \end{align}

\begin{align} \big( (x \land y) \land (x\land\neg z) \land (y\land z) \big) \lor \big( (x \land y) \land (x\land\neg z) \land (x\land u) \big) \lor \big( (x \land y) \land \neg y \land (y\land z) \big) \lor \big( (x \land y) \land \neg y \land (x\land u) \big) \lor \big( (x \land y) \land u \land (y\land z) \big) \lor \big( (x \land y) \land \neg y \land (x\land u) \big) \lor \big( (z \land u) \land (x\land\neg z) \land (y\land z) \big) \lor \big( (z \land u) \land (x\land\neg z) \land (x\land u) \big) \lor \big( (z \land u) \land \neg y \land (y\land z) \big) \lor \big( (z \land u) \land \neg y \land (x\land u) \big) \lor \big( (z \land u) \land u \land (y\land z) \big) \lor \big( (z \land u) \land \neg y \land (x\land u) \big) \equiv \end{align}

\begin{align} \bot \lor (x \land y \land \lnot z \land u) \lor \bot \lor \bot \lor (x \land y \land z \land u) \lor \bot \lor \bot \lor \bot \lor \bot \lor (y \land z \land u) \lor (x \land \lnot y \land z \land u) \equiv \end{align}

\begin{align} (x \land y \land \lnot z \land u) %\lor (x \land y \land z \land u) \lor (y \land z \land u) \lor (x \land \lnot y \land z \land u) \end{align}

All the formulas above, except the first one, are DNF (disjunctive normal forms) logically equivalent to the first one.

As a mnemonic rule, you have to think of $\land$ and $\lor$ as $\cdot$ and $+$, respectively; so, your initial formula can be seen as an expression of the shape $(a + b)(c + d + e)(f + g)$ where we apply the usual algebraic transformations:

$(a + b)(c + d + e)(f + g) = (ac + ad + ae + bc + bd + be)(f + g) = acf + acg + adf + adg + aef + aeg + bcf + bcg + bdf + bdg + bef + beg$

(this explains the transformation from the first formula to the second formula).