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 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/   
    
Associated Topics:
High School Discrete Mathematics
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/