[Math] Disjunctive normal form expansion

boolean-algebradiscrete mathematicslogic

I do not understand this at all.

Find the sum-of-products expansions of these Boolean functions.

$F(x, y, z) = x + y + z$

$F(x, y, z) = (x + z)y$

$F(x, y, z) = x$

$F(x, y, z) = x y$

How is $x$ not just $x$? This makes no sense to me at all and my book wants me to memorize about 20 laws and stuff to transform these to some form that I don't understand. I don't understand the point of this, I don't understand the goal of this and I don't understand the procedure. I can't even find an explanation online that makes sense to me.

What am I supposed to do?

$x+y+z$ looks like a sum of products to me already. What is wrong with it?

Why isn't $(x+y)z$ just $xz + zy$? My book says that is wrong.

Books answers:

$xyz + xy\bar z + x \bar yz + x\bar y \bar z + \bar x yz + \bar x y \bar z + \bar x\bar y z$

*$ xyz + xy \bar z + \bar xyz$

$xyz + xy \bar z + x \bar y z + x \bar y\bar z $

$ x\bar yz + x\bar y \bar z$

Best Answer

Each of the above except for $(x + y) z$ is already expressed as the sum-of-products (SOP). $$(x + y)z = xz + yz = xz + zy$$

You are correct that $F(x, y, z) = x$ is already in disjunctive normal form (SOP form). Perhaps your book wants you to write $F(x, y, z) = x = 1x + 0y + 0z$, but I find that a bit pedantic!

In that spirit, $F(x, y, z) = x + y + z = 1x + 1y + 1z$, and $F(x, y, z) = xy = xy + 0z$. But by most authoritative sources on the matter, these alternatives are unnecessary, and all but $F(x, y, z) = (x + y)z$ are perfectly respectable ways to express the functions as a sum-of-pr0ducts.

Related Solutions

[Math] Boolean algebra – sum of products form

As far as I understand it correctly and $+$ means "or"; $\cdot$ means "and"; $\bar{x}$ means negation, it can surely be reduced. Btw, there is a mistake, because $(1)$ is not true if $x\bar y\bar z=1$, i.e., $(x,y,z)=(1,0,0)$, whereas $(2)$ obviously contains all $8$ cases and is therefore always true.

A general method to reduce such expressions is to "redistribute" by the following equivalent operations:

$1=B+1=B+\bar B$ (maximality of $1$ and the tautology $B$ or $B$ negation);
$A=AB+A\bar B$ for any $A,B$ (distributive law);
$\overline{A+B}=\bar A\bar B$ and $A+B=\overline{\bar A\bar B}$ (de Morgan's laws).
$\bar{\bar A}=A$ (negation is involution).

Using these we reduce $(1)$ to $\overline{x\bar y \bar z}$. There're surely algorithms for this (I don't know them), but it is similar to simplification of any formula, it takes some practice.

[Math] Applying De Morgan’s Laws

1) Using De Morgan's Laws, simplify the following: Not(A AND B) OR A

The trick for this one is as follow:

    NOT(A AND B) OR A
<=> NOT(A) OR NOT(B) OR A      // The trick is here. Literally De Morgan's law.
<=> (NOT(A) OR A) OR NOT(B)
<=> TRUE OR NOT(B)
<=> TRUE

So this (1) is a tautology.

2) Using De Morgan's Laws, show that A + A.B = A

And for this one, here is the trick:

    A + A.B
<=> A OR (A AND B)       
<=> A AND (TRUE OR B)    // The trick is here. like in Math:  x + (x*y) = x*(1+y)
<=> A AND TRUE
<=> A

I hope this help.

Best Answer

Related Solutions

[Math] Boolean algebra – sum of products form

[Math] Applying De Morgan’s Laws

Related Question