Additional Problem Set 4 Solutions
Additional Problem Set 4 Solutions
1
.Prove the Following Statements:
1
.1
.Let us assume that ∀x (F(x) ∨ G(x)) and ¬∃xG(x).
1
.1
.1
.∀x ¬G(x) (by generalized DeMorgan)
1
.1
.2
.Let x ∈.
1
.1
.3
.Case 1. F(x). In this case we get what we want to conclude.
1
.1
.4
.Case 2. G(x), but by 1.1.1 we have ¬G(x) so we can conclude G(x)∧¬G(x) a contradiction.
1
.2
.Let us assume ∀x(¬F(x)∨G(x)).
Note that ¬F(x)∨G(x) is equivalent to F(x)G(x).
By substituting equivalent formulas we get
∀x(F(x)G(x)).
Note that ¬F(x)∨G(x) is equivalent to F(x)G(x).
By substituting equivalent formulas we get
∀x(F(x)G(x)).
1
.3
.This is an instance of generalized DeMorgan
2
.Consider the statement: “For all integers n, if n is even, then 8n is even”
2
.1
.We will use a direct proof:
2
.1
.1
.Let n∈ be even.
8n = 2(4n)
Thus there is a number m=4n∈ such that 8n = 2m.
Thus by definition 8n is even.
8n = 2(4n)
Thus there is a number m=4n∈ such that 8n = 2m.
Thus by definition 8n is even.
2
.2
.The converse is “For all integers n if 8n is even, then n is even.”
2
.3
.The converse is false. We show this by a counter example.
Let n=1. We then have 8(1) = 8 is even, but n=1 is odd.
Let n=1. We then have 8(1) = 8 is even, but n=1 is odd.
3
.We use a proof by contrapositive:
Let n be an integer that is not odd,
Then n is even,
There is k ∈ such that n = 2k
5n = 5(2k) = 2(5k)
Thus there is r=5k∈ such that 5n = 2r.
Thus 5n is even, and thus not odd
Hence we showed that if 5n is odd then n is odd by proving the contrapositive
Let n be an integer that is not odd,
Then n is even,
There is k ∈ such that n = 2k
5n = 5(2k) = 2(5k)
Thus there is r=5k∈ such that 5n = 2r.
Thus 5n is even, and thus not odd
Hence we showed that if 5n is odd then n is odd by proving the contrapositive
4
.We will use a series of equivalent statements
4
.1
. x = y if an only ifx -y = 0 if and only if(x =0 if and only if-2xy+=0 if and only if +2xy+=4xy if an only if =xy
2
-y)
2
x
2
y
2
x
2
y
2
(x+y)
4
5
.Suppose you would like to prove the following implication:
“For all numbers n, if n is prime, then n is solitary”
How would you start and end your argument if you tried to prove the statement...
“For all numbers n, if n is prime, then n is solitary”
How would you start and end your argument if you tried to prove the statement...
5
.1
.Start: Let n be a prime number.
Finish: Conclude that n is solitary
Finish: Conclude that n is solitary
5
.2
.Start: Let n be a prime number and assume that it is not solitary for the sake of contradiction.
Finish: Arrive at a contradiction.
Finish: Arrive at a contradiction.
5
.3
.Start: Assume n is not a solitary number.
Finish: Conclude that n is not prime.
Finish: Conclude that n is not prime.
6
.The main flaw lies in the fact that we cannot start proofs by assuming what we want to conclude. Alternatively, if we wanted to show that the conclusion is equivalent to a true statement, the flaw lies in the fact that we cannot reverse the step going from 3 to 4. In particular but the converse is not always true.
a=b=
2
a
2
b