Boolean Algebra ProblemsDate: 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/ |
Search the Dr. Math Library: |
[Privacy Policy] [Terms of Use]
Ask Dr. Math^{TM}
© 1994- The Math Forum at NCTM. All rights reserved.
http://mathforum.org/dr.math/