1
$\begingroup$

Using the distributive laws, I need to convert the formula $(X\lor Y )\land (W \lor Z)$ into disjunctive normal form.

The answer needs to be equivalent to this formula by means of a truth table.

Can you help with this as I am struggling with this subject? Many thanks.

$\endgroup$
3
$\begingroup$

I'll leave you to do the truth-tables to confirm the following equivalence, using the distributive law repeatedly:

$$\begin{align} (X\lor Y )\land(W \lor Z) & \equiv [(X \lor Y) \land W] \lor [(X \lor Y) \land Z \\ \\ &\equiv (X \land W) \lor (Y \land W) \lor (X \land Z)\lor(Y \land Z)\end{align}$$

The proposition is now in disjunctive normal form.


To find the conjunctive normal directly from a truth-table:

When you construct a truth-table for the proposition $(X \lor Y) \land (W \lor Z)$, in the column immediately below the proposition, you can first look for all the rows that evaluate to true: $T$. Then you can read off the corresponding truth-value assignments for the four variables. For example, we'll have a row where the proposition is true and the truth-values listed in the row for the variables consist of $X = T,\; Y = T,\; W = T,\; Z = T$. Then we'd write that true row as $$X \land Y \land W \land Z$$

We'll also have a row where $X = T,\;Y = F,\;W = T,\; Z = F$. We'd write this as $$X \land \lnot Y \land W \land \lnot Z$$

So far, then, we have that the proposition is true when $(X \land Y \land W \land Z)$ or when $(X \land \lnot Y \land W \land \lnot Z)$, that is, when $$(X \land Y \land W \land Z) \lor(X \land \lnot Y \land W \land \lnot Z) \lor (\cdots) $$

And we'd do this for every row in the truth-table where the proposition is true. We'll get a very lengthy proposition which can then be whittled down and simplified to the disjunctive normal form given at the start, but you'd find yourself using the distributive law many more times than simply using it from the start, as we did at the start of this post.

$\endgroup$
  • $\begingroup$ How does this not have more TU's? +1 $\endgroup$ – Amzoti Oct 27 '13 at 0:09

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.