Boolean Algebra ProofsDate: 09/25/1999 at 06:20:06 From: John Perego Subject: Boolean algebra Hi Dr. Math! Could you please help me solve the following Boolean algebra problems? Problem 1: Prove ab + bc + ca' = ab + ca' I have tried in several ways and I cannot get both sides equal. The solution should be found without a truth table. Problem 2: Use the Boolean relation of contraposition (A->B <=> B'->A') to prove the following: 2(q^2) does not equal (p^2) when p, q are integers without common divisors (that means one is even, the other one is odd). This problem has something to do with the irrationality of the square root of 2, but I do not really understand why and how to link it with the logical expression. Thank you really much for your help, John Date: 09/25/1999 at 16:47:23 From: Doctor Anthony Subject: Re: Boolean algebra Problem 1: Prove ab + bc + ca' = ab + ca' We must show that bc is subset of ab + ca' We have abc is subset of ab and a'bc is subset of ca' ------------------------------- adding abc + a'bc is subset of ab + ca' bc(a+a') is subset of ab + ca' but a+a' = 1 so bc is subset of ab + ca' Therefore ab + bc + ca' = ab + ca' The truth table proof is as shown below. a b c ab bc ca' ab+bc+ca' ab+ca' ----------------------------------------------- 0 0 0 0 0 0 0 0 0 0 1 0 0 1 1 1 0 1 0 0 0 0 0 0 0 1 1 0 1 1 1 1 1 0 0 0 0 0 0 0 1 0 1 0 0 0 0 0 1 1 0 1 0 0 1 1 1 1 1 1 1 0 1 1 ----------------------------------------------- Problem 2: If p, q are relatively prime then 2.q^2 = p^2 implies that p^2 is even. Therefore p is even. So we let p = 2m then p^2 = 4.m^2 And we have 2.q^2 = 4.m^2 q^2 = 2.m^2 Therefore q^2 is even. Therefore q is even. But then we have both p and q as even numbers, contrary to the given condition that they are relatively prime. It follows that we cannot have 2.q^2 = p^2 with p and q relatively prime. - Doctor Anthony, The Math Forum 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/