Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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

share|improve this question
add comment

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
add comment

Your Answer

 
discard

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.