[Math] Boolean algebra – sum of products form

boolean-algebra

I have a logic circuit where the output can be represented with the following boolean expression

(1)$\overline {xy}$ + x $\bar y z$ + $\overline {\bar x + z} $ + y

Using truth tables I found the complete sum of products form as:

(2)$xyz + xy \bar z + x \bar y z + x \bar y \bar z + \bar xyz + \bar x y \bar z + \bar x\bar yz + \bar x\bar y\bar z$

However, I would like to be able to find the sum of products form by using boolean identities to rearrange (1) above. I am unable to see how we can get from (1) to (2) though. Maybe it is the case that (2) can be reduced further?? Please could someone advise on this

Thanks

Best Answer

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.