Boolean Algebra Proofs

Date: 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/