Take the 2-minute tour ×

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


share|improve this question

1 Answer 1

up vote 1 down vote accepted

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.

share|improve this answer
Sorry (1) contained a typo which I have amended now. Thanks for the points you highlighted –  bosra Nov 26 '12 at 21:09

Your Answer


