Drexel dragonThe Math ForumDonate to the Math Forum

Ask Dr. Math - Questions and Answers from our Archives
_____________________________________________
Associated Topics || Dr. Math Home || Search Dr. Math
_____________________________________________

Boolean Algebra Problems


Date: 12/05/97 at 23:30:51
From: John W. Fleming
Subject: Boolean algebra

Could you please help me solve the following boolean algebra problems?  

Prove x'y' + x'y + xy' = x' + y'

I have tried this problem several ways and always end up short or with
too many.  I cannot get both sides to be equal.

Prove x'y' + x'y + xy' + xy = Identity

On this problem I know what identity means, but I do not understand 
what the equation on the right should equal.  I know it should be 
equal to the identity, but for this problem, what does that mean?

Thank you.


Date: 12/06/97 at 08:18:42
From: Doctor Anthony
Subject: Re: Boolean algebra

(1)  Draw up the truth table as follows:

 x   y   x'   y' | x'y' + x'y + xy' = f1 |  x' + y' = f2  |
 ----------------------------------------------------------
 0   0   1    1  |  1   +  0  + 0   = 1  |  1  +  1 = 1   |
 0   1   1    0  |  0   +  1  + 0   = 1  |  1  +  0 = 1   |
 1   0   0    1  |  0   +  0  + 1   = 1  |  0  +  1 = 1   |
 1   1   0    0  |  0   +  0  + 0   = 0  |  0  +  0 = 0   |


The truth table for the two expressions, f1 and f2, is the same, so 
the two represent the same boolean function. i.e.  f1 = f2

(2) This is very similar to the last question except that we add xy 
to f1 and it is obvious that this makes the total 1 for all possible 
combinations of x, x', y, y'.

 x   y   x'   y' | x'y' + x'y + xy' + xy = f3
 --------------------------------------------
 0   0   1    1  |  1   +  0  + 0   +  0 = 1 
 0   1   1    0  |  0   +  1  + 0   +  0 = 1 
 1   0   0    1  |  0   +  0  + 1   +  0 = 1 
 1   1   0    0  |  0   +  0  + 0   +  1 = 1

The truth table shows that f3 = 1  for all x, y, x', y'

What you have called the identity (=1) is here called the universal 
set.
       
Here is an alternatve approach to these problems, not involving truth 
tables.

We use fact that xx' = 0,  yy' = 0,  x+x' = 1  and y+y' = 1

Then starting with the simpler expression we work towards the more 
complicated one.

So x' + y' = x'(y+y') + y'(x+x')

           = x'y + x'y' + xy' + x'y'  
               (we only need include one of the x'y')

           = x'y + x'y' + xy'  (the required expression)

For the second problem we start with:

    1 =  (x+x')(y+y')

      = xy + xy' + x'y + x'y'

In these problems this has proved a quicker method, but truth tables 
can be very useful if it is not easy to see in what way we should 
'complicate' the easy starting expression. 

-Doctor Anthony,  The Math Forum
 Check out our web site!  http://mathforum.org/dr.math/   
    
Associated Topics:
College Logic
High School Logic

Search the Dr. Math Library:


Find items containing (put spaces between keywords):
 
Click only once for faster results:

[ Choose "whole words" when searching for a word like age.]

all keywords, in any order at least one, that exact phrase
parts of words whole words

Submit your own question to Dr. Math

[Privacy Policy] [Terms of Use]

_____________________________________
Math Forum Home || Math Library || Quick Reference || Math Forum Search
_____________________________________

Ask Dr. MathTM
© 1994-2013 The Math Forum
http://mathforum.org/dr.math/