A use of nested quantifiers:
∀x∃y(x
+ y) = 0
How to read this? "For any number, there is another
number so that the first number plus the
second equals zero."
Let's try a few!
The commutative law for addition:
∀x∀y(x +
y = y + x)
The associative law for addition:
∀x∀y∀z
(x + (y + z) =
(x + y) + z)
One more, on your own:
∀x∀y((x > 0)
∧ (y < 0) →
(xy < 0))
Quantifications can be thought of as loops, e.g.:
∀x∀yP(x,
y)
can be thought of as:
for x in (domain of x)
for y in (domain of y)
if P(x, y) == False
return False
return True
Order matters when quantifiers are mixed.
Quantifications of Two Variables | ||
---|---|---|
Statement | When True? | When False? |
∀x∀yP(x,
y)
∀y∀xP(x, y) |
P(x, y) is true for every pair x, y. | There is a pair x, y for which P(x, y) is false. |
∀x∃yP(x, y) | For every x there is a y for which P(x, y) is true. | There is an x such that P(x, y) is false for every y. |
∃x∀yP(x, y) | There is an x for which P(x, y) is true for every y. | For every x there is a y for which P(x, y) is false. |
∃x∃yP(x, y) | There is a pair x, y for which P(x, y) is true. | P(x, y) is false for every pair x, y. |
The sum of two positive reals is always positive.
∀x∀y((x > 0
∧ y > 0) →
(x + y > 0))
Every real number except zero has a multiplicative
inverse.
∀x((x ≠ 0) →
∃y(xy = 1))
∀x(C(x) ∨
∃y(C(y) ∧
F(x, y))
C(x) means "x has a computer
and F(x, y) means
"x and y are friends."
"Every student either has a computer or has a friend
who has a computer."
∃x∀y∀z((F(x, y) ∧ F(x, z) ∧ (y ≠ z)) → ¬F(y, z))
"Everybody loves somebody sometime."
∀x∃y∃z(L(x,
y, z)
"Everybody has exactly one best friend."
∀x∃y(B(x,
y) ∧ ∀z((z ≠
y) → ¬B(x, z)))
1. c; 2. b; 3. b; 4. b; 5. a;
How to demonstrate that a mathematical argument is
valid?
Argument: a series of statements ending with a
conclusion.
Premise: The statements preceding the
conclusion.
Valid: The conclusion of the argument must be
true if each premise is true.
Fallacy: An invalid argument. Certain fallacies
are common.
"If you have a current password, then you can log onto
the network."
"You have a current password."
Therefore...
"You can log onto the network."
In formal terms:
p → q
p
∴q
Same form but different premises:
"If you have access to the network, then you can
change your grade."
"You have access to the network."
∴ "You can change your grade."
The above is false, because one of the premises is
false.
But, it is a valid argument.
It is the form of the argument that determines
its validity.
Rules of Inference | ||
---|---|---|
Rule of Inference | Tautology | Name |
p
p → q ∴q |
(p ∧ (p → q)) → q | Modus ponens |
¬q
p → q ∴¬p |
(¬q ∧ (p → q)) → ¬p | Modus tollens |
p → q
q → r ∴p → r |
((p → q) ∧ (q → r)) → (p → r) | Hypothetical syllogism |
p ∨ q
¬p ∴q |
((p ∨ q) ∧ ¬ p) → q | Disjunctive syllogism |
p
∴p ∨ q |
p → (p ∨ q) | Addition |
p ∧ q
∴p |
(p ∧ q) → p | Simplification |
p
q ∴p ∧ q |
((p) ∧ (q)) → (p ∧ q) | Conjunction |
p ∨ q
¬p ∨ r ∴q ∨ r |
((p ∨ q) ∧ (¬p ∨ r)) → (q ∨ r) | Resolution |
"It is not sunny this afternoon and
it is colder than yesterday."
"We will go swimming only if it is sunny."
"If we do not go swimming, we will take a canoe trip."
"If we take a canoe trip, then we
will be home by sunset."
When will we be home?
Step | Reason |
---|---|
1. ¬p ∧ q | Premise |
2. ¬p | Simplification |
3. r → p | Premise |
4. ¬r | Modus tollens using (2) and (3) |
5. ¬r → s | Premise |
6. s | Modus ponens using (4) and (5) |
7. s → t | Premise |
8. t | Modus ponens using (6) and (7) |
The logical form:
((p ∨ q)
∧ (¬p ∨ r))
→ (q ∨ r)
"You study hard OR get an A."
"You don't study hard OR
watch lots of movies."
"You will get an A or watch lots of movies."
An example -- fallacy of affirming the
conclusion:
1. "If you buy Professor Callahan many nice
presents, you will get an A."
2. "You got an A."
"Therefore you bought Professor Callahan
many nice presents."
Another -- fallacy of denying the
hypothesis:
Take (1) and (2) as in the previous paragraph.
If you did not buy Professor Callahan
many nice presents, does that mean
you did not get an A?
No!
((p → q) ^ ¬p)
→ ¬q
is not a tautology!
Rules of Inference for Quantified Statements | |
---|---|
Rule of Inference | Name |
∀xP(x)
∴P(c) |
Universal instantiation |
P(c) for an arbitrary c
∴∀xP(x) |
Universal generalization |
∃xP(x)
∴P(c) for some element c |
Existential instantiation |
P(c)
for some element c
∴∃xP(x) |
Existential generalization |
Using the rules:
"Everyone in this discrete mathematics class
has taken a course in computer science"
"Marla is a student in this class."
Therefore:
"Marla has taken a course in computer science."
Universal modus ponens:
"All discrete mathematics professors
have sparkling personalities."
"Professor Callahan is a discrete mathematics
professor."
"Therefore..."
1. d; 2. d; 3. d; 4. b; 5. a;
A proof: a valid argument that establishes the truth of some mathematical statement.
Often, when logically we have a universal
quantifier, mathematical works may simply
assume it. So:
"For all positive real numbers x
and y, if x > y,
then x^{2} >
y^{2}."
Becomes:
"If x > y, where x
and y are postive real numbers,
then x^{2} >
y^{2}."
We have a whole lotta proof methods going on! Devising a proof is a creative activity! There is no algorithm for infallibly arriving at a correct proof as easily as possible.
In this section, we will focus on proofs of theorems
of the form:
∀x(P(x) →
Q(x))
We will want to show that:
P(c) → Q(c)
is true for any arbitrary c.
This is a conditional statement.
So we will
focus on methods that show that if p is
true, q is true.
We want to avoid to many uses of "obviously"
and "clearly" -- story about Hardy!
Nevertheless, we can't always make every single step
explicit: the proofs would get way too long.
A direct proof of a conditional statement p → q assumes p is true, then takes steps to show that if p is true, then q must also be true.
Definition 1
The integer n is even if there exists an integer k such that n = 2k, and n is odd if there exists an integer k such that n = 2k + 1.
To prove: "If n is an odd integer, then
n^{2} is odd."
In symbolic logic:
∀n(P(n) →
Q(n))
P(n) means "n is an odd
integer" and Q(n) means
"n^{2} is odd".
By definition of odd, if n is odd,
then n = 2k + 1.
Then n^{2} =
(2k + 1)^{2}.
(2k + 1)^{2} =
4k^{2} + 4k + 1 =
2(2k^{2} + 2k) + 1.
2(2k^{2} + 2k) must be
an even integer, so that + 1 must be odd.
Indirect proofs do not start with the premise.
One species of such proofs are known as
proof by contraposition.
These proofs make use of the fact that
p → q
is equivalent to
¬q → ¬p
Example:
Prove that if n is an integer and 3n + 2 is odd,
then n is odd.
An attempt at a direct proof:
We assume 3n + 2 is odd, so that it equals
2k + 1 for some integer k.
Not sure where to go from there!
Instead, let's assume ¬q: assume n
is even. Then n = 2k for some integer
k.
Therefore...
3n + 2
= 3(2k) + 2
= 6k + 2
= 2(3k + 1)
But this contradicts our assumption that
3n + 2 is odd!
Suppose we want to prove that a statement
p is true.
Because a proof by contradiction does not
prove a result directly, it is another
type of indirect proof.
Example: Prove that 2^{1/2} is
irrational.
Suppose to the contrary that it is rational.
Then there must be some lowest terms,
call them a and b so that
the square root of two is equal to
a/b. Squaring both sides, we get:
2 = a^{2}/b^{2}
2b^{2} = a^{2}
So a must be even.
So for some c, a =
2c. Then:
a^{2} = 4c^{2}
So:
b^{2} = 2c^{2}
So b is even as well!
But a/b was supposed to
be a proper fraction. This is a contradiction.
There are many common errors made in constructing mathematical proofs. Most common of these errors are mistakes in arithemetic and basic algebra.
It is important to check such computations. Each step of mathematical proof needs to be correct and the conclusion needs to follow logically.
Example:
What is wrong with this
proof?
Theorem:
If n^{2} is positive,
then n is positive.
Proof: Suppose that n^{2} is positive. Because the conditional statement "If n is positive, then n^{2} is positive is true, we can conclude that n is positive.
Solution: Let P(n) be "n is positive" and Q(n) be "n^{2} is positive." Then n^{2} is positive is the statement ∀n (P(n) → Q(n)) and Q(n) is a hypothesis.
From the hypothesis and the statement,we cannot conclude P(n) because we are not using a valid rule of inference. A counterexample is for n = −1
1. b; 2. d; 3. d; 4. d; 5. b;
There are some commonly used proof methods, like method of proving a theorem by considering different cases seperately.
Also, there are strategies behind constructing proof which includes selecting a proof method and then succesfully constructing an argument step by step, based on this method.
Sometimes we cannot prove a theorem using a single argument that holds for all possible cases. We can prove a theorem, by considering different cases separately. This method is based on a rule of inference.
Proofs that prove a theorem by exhausting all the posibilities are called exhaustive proofs i.e., the theorem can be proved using relatively small number of examples.
Example:
Prove that (n + 1)^{3} ≥ 3^{n} if n is a positive integer with n ≤ 4
Solution We only need to verify the inequality (n + 1)^{3} ≥ 3^{n} for n = 1, 2, 3 & 4. For n = 1 we have (8, 3), n = 2 (27, 9), n = 3 (64, 27) and n = 4 (125, 81). For all the above cases we have (n + 1)^{3} ≥ 3^{n}
The proofs that must cover all the cases that arises in a theorem
Example:
Prove that if n is an integer, then n^{2} ≥ n
Solution We can prove that n ^{2} ≥ n for every integer by considering three cases, when n = 0,when n ≥ 1, and when n ≤ −1.
We split the proof into three cases because it is straightforward to prove the result by considering zero, positive integers, and negative integers separately
Case (i): When n = 0, because 0^{2} = 0, we see that 0^{2} ≥ 0. It follows that n^{2} ≥ n is true in this case.
Case (ii): When n ≥ 1, when we multiply both sides of the inequality n ≥ 1 by the positive integer n, we obtain n^{2} ≥ n * 1. This implies that n^{2} ≥ n for n ≥ 1.
Case (iii): In this case n ≤ −1. However, n^{2} ≥ 0. It follows that n^{2} ≥ n. Because the inequality n^{2} ≥ n holds in all three cases, we can conclude that if n is an integer, then n^{2} ≥ n.
1. a; 2. a; 3. a;