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!

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