Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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|cite|improve this question
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|cite|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


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.