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.:
can be thought of as:
for x in (domain of x)
for y in (domain of y)
if P(x, y) == False
Order matters when quantifiers are mixed.
|Quantifications of Two Variables|
|Statement||When True?||When False?|
|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
∀x((x ≠ 0) → ∃y(xy = 1))
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
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
"You have a current password."
"You can log onto the network."
In formal terms:
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 → q
|(p ∧ (p → q)) → q||Modus ponens|
p → q
|(¬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||Disjunctive syllogism|
∴p ∨ q
|p → (p ∨ q)||Addition|
p ∧ q
|(p ∧ q) → p||Simplification|
∴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?
|1. ¬p ∧ q||Premise|
|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
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
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?
((p → q) ^ ¬p) → ¬q
is not a tautology!
|Rules of Inference for Quantified Statements|
|Rule of Inference||Name|
P(c) for an arbitrary c
∴P(c) for some element c
for some element c
Using the rules:
"Everyone in this discrete mathematics class has taken a course in computer science"
"Marla is a student in this class."
"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."
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 x2 > y2."
"If x > y, where x and y are postive real numbers, then x2 > y2."
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.
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
n2 is odd."
In symbolic logic:
∀n(P(n) → Q(n))
P(n) means "n is an odd integer" and Q(n) means "n2 is odd".
By definition of odd, if n is odd, then n = 2k + 1.
Then n2 = (2k + 1)2.
(2k + 1)2 = 4k2 + 4k + 1 = 2(2k2 + 2k) + 1.
2(2k2 + 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
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.
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 21/2 is
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 = a2/b2
2b2 = a2
So a must be even.
So for some c, a = 2c. Then:
a2 = 4c2
b2 = 2c2
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.
What is wrong with this
Theorem: If n2 is positive, then n is positive.
Proof: Suppose that n2 is positive. Because the conditional statement "If n is positive, then n2 is positive is true, we can conclude that n is positive.
Solution: Let P(n) be "n is positive" and Q(n) be "n2 is positive." Then n2 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.
Prove that (n + 1)3 ≥ 3n if n is a positive integer with n ≤ 4
Solution We only need to verify the inequality (n + 1)3 ≥ 3n 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 ≥ 3n
The proofs that must cover all the cases that arises in a theorem
Prove that if n is an integer, then n2 ≥ 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 02 = 0, we see that 02 ≥ 0. It follows that n2 ≥ 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 n2 ≥ n * 1. This implies that n2 ≥ n for n ≥ 1.
Case (iii): In this case n ≤ −1. However, n2 ≥ 0. It follows that n2 ≥ n. Because the inequality n2 ≥ n holds in all three cases, we can conclude that if n is an integer, then n2 ≥ n.
1. a; 2. a; 3. a;