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

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)

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
Math Forum Home || Math Library || Quick Reference || Math Forum Search