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
$\endgroup$1 Answer
$\begingroup$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.
$\endgroup$ 1
