Sample Homework Solutions
Problem
#13:
Theorem:
If the average of three different integers is 20, then at least
one of the three must be greater than 20.
Proof::
Let w, x,and y be the three integers, and
suppose that w < x < y.
We are told that the average is 20, so that (w + x + y)
/ 3 = 20,
which means w + x + y
= 60. Suppose that all of the numbers are 20
or less. Then we have y <= 20, x <= 19 and w <= 18. (Here,
"<=" means "less than or equal to.") But then w + x + y
<= 57,
which is a contradiction.
Q.E.D.
Problem
#15:
Theorem:
At least one of the decimal digits 1, 2, ..., 9 must appear infinitely
often in the decimal expansion of pi.
Proof:
Suppose not. Then each of those digits appears a finite number of
times, so that after some point in the decimal expansion of pi we have
only zeros. But this would mean that the decimal expansion of pi
is
finite in length. Let N be the number of digits in pi after the
decimal
point. Then if we multiply pi by 10N, we get an
integer, say K.
This means pi = K / 10N. But this contradicts the
well-known fact
that pi is irrational. Q.E.D.
Problem
#3:
Theorem:
OR distributes over AND
Proof:
This is equivalent to proving that the compound proposition
p OR (q AND r) is logically equivalent to (p OR q) AND (p OR r).
We show this with a truth table:
p
|
q
|
r
|
q
AND r
|
p OR (q AND r) |
(p OR q) |
(p OR r) |
(p OR q) AND (p OR r) |
t
|
t
|
t
|
t
|
t
|
t
|
t
|
t
|
t
|
t
|
f
|
f
|
t
|
t
|
t
|
t
|
t
|
f
|
t
|
f
|
t
|
t
|
t
|
t
|
t
|
f
|
f
|
f
|
t
|
t
|
t
|
t
|
f
|
t
|
t
|
t
|
t
|
t
|
t
|
t
|
f
|
t
|
f
|
f
|
f
|
t
|
f
|
f
|
f
|
f
|
t
|
f
|
f
|
f
|
t
|
f
|
f
|
f
|
f
|
f
|
f
|
f
|
f
|
f
|
The two shaded columns are identical, showing that the two
compound propositions are logically equivalent under all
circumstances.