Algebraic Manipulation Problem

Thread Starter

Eternal Sky

Joined Sep 11, 2008
2
I'm trying to find the minimum sum-of-products expression for the function:

f = x1x2'x3' + x1x2x4 + x1x2'x3x4'

I've read over the boolean rules for simplification on this site, but it didn't really help me understand what I should be doing. I attempted to simplify the function by pulling out the common x1 term, but this just produced the function:

f = x1(x2'x3' + x2x4 + x2'x3x4')

Doing that didn't seem to make things any easier.

If someone could just point me in the right direction, I would greatly appreciate it.
 

Thread Starter

Eternal Sky

Joined Sep 11, 2008
2
Sorry. I'll try to make it easier to read:

f = x1*x2'*x3' + x1*x2*x4 + x1*x2'*x3*x4'

where * = multiplication
and x1, x2, x3, x4 = input variables
also, the ' character indicates NOT
 

studiot

Joined Nov 9, 2007
4,998
Try using some the following identities; you may need to use some of them in reverse.
I have used letters instead of x1, x2 etc as its easier on the eye.
You can insert barackets anywhere and compare with my expressions.



b+1=1
a+ab=a
a(a+b)=a
a(a'+b)=ab
a+a'b=a+b
a+a'=1
a+bc=(a+b)(a+c)
(ab)'=a'+b'
a'b'=(a+b)'

the last two together are known as De Morgan's theorem.
 
Last edited:

Ratch

Joined Mar 20, 2007
1,070
Eternal Sky,

Sorry. I'll try to make it easier to read:

f = x1*x2'*x3' + x1*x2*x4 + x1*x2'*x3*x4'
Let me make it even easier to read.

A ==> x1
B ==> x2
C ==> x3
D ==> x4

F = AB'C' + ABD +AB'CD'

I've read over the boolean rules for simplification on this site, but it didn't really help me understand what I should be doing. I attempted to simplify the function by pulling out the common x1 term, but this just produced the function:

f = x1(x2'x3' + x2x4 + x2'x3x4')

Doing that didn't seem to make things any easier.

If someone could just point me in the right direction, I would greatly appreciate it.
First we expand the terms.

F = AB'C' + ABD +AB'CD'

F = AB'C'(D+D') + AB(C+C')D + AB'CD'
= AB'C'D + AB'C'D' +ABCD + ABC'D + AB'CD'

There are no duplicate terms to remove.

AB'C'D = 9
AB'C'D' = 8
ABCD = 15
ABC'D = 13
AB'CD' = 10

So the Boolean expression can be described by the minterms as (8,9,10,13,15)

Now simply using a Karnaugh map, or the Quine-McCluskey tabulation method we easily get

F = AB'D' + ABD + AB'C'
or
F = AB'D' + ABD + AC'D

You might want to read http://forum.allaboutcircuits.com/showthread.php?t=12279

and especially http://forum.allaboutcircuits.com/showthread.php?t=13854 , the second paragraph of post #13 concerning using algebraic methods to simplify Boolean expressions.

Ratch
 
Last edited:
Top