The Foundation: Logic and Proofs

Logic gates

Propositional Logic

Applications of Propositional Logic

Propositional Equivalences

Predicates and Quantifiers

Nested Quantifiers
Introduction

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."

Understanding Statements Involving Nested Quantifiers

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))

The Loop View

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

The Order of Quantifiers

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.
Translating Mathematical Statements into Statements Involving Nested Quantifiers

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))

Translating from Nested Quantifiers into English

∀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))

Translating English Sentences into Logical Expressions

"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)))

Negating Nested Quantifiers
NOT COVERED SPRING 2018
Test Yourself!
  1. ∀x∃y(x + y = 0) is read as:
    1. For all x and y, x + y = 0
    2. For all y, there exists an x such that x + y = 0
    3. For all x, there exists a y such that x + y = 0
    4. For all x and y, xy = 0
  2. Let Q(x,y,z) denote the statement x^2 + y^2 = z^2. What is the truth value of Q(3,4,5)?
    1. Cannot determine
    2. True
    3. False
  3. Express the statement “for every x and for every y, x + y > 10”
    1. ∀x∀yP(y, y)
    2. ∀x∀yP(x, y)
    3. ∀yP(x > y)
    4. ∀x∀yP(x)
  4. How can we translate "Everybody loves somebody sometime."?
    1. ∀xL(x,y,z)
    2. ∀x∃y∃z(L(x, y, z))
    3. ∀x∃y(x,y)
    4. ∀zL(x,y,z)
  5. When are two quantifiers said to be nested?
    1. If one is within scope of the other
    2. If one is independent of the other
    3. If their domain is complex numbers only
    4. If their domain is integers only
Answers

1. c; 2. b; 3. b; 4. b; 5. a;

Rules of Inference
Introduction

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.

Valid Arguments in Propositional Logic

"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 for Propositional Logic
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
Using Rules of Inference to Build Arguments

"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)
Resolution

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."

Fallacies

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
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."

Combining Rules of Inference for Propositions and Quantified Statements

Universal modus ponens:
"All discrete mathematics professors have sparkling personalities."
"Professor Callahan is a discrete mathematics professor."
"Therefore..."

Test Yourself!
  1. Which rule of inference is used in each of these arguments: If it snows today, school will be closed. School is not closed today. Thus, it did not snow today.
    1. Resolution
    2. Addition
    3. Modus ponens
    4. Modus tollens
  2. Which rule of inference is used in each of these arguments: If it snows today, school will be closed. It is snowing today. Thus, school will be closed.
    1. Conjunction
    2. Simplification
    3. Modus tollens
    4. Modus ponens
  3. What rule of inference is used in this argument? "If I exercise, then I will be physically fit. If I will be physically fit, then I will stay healthy. Therefore, if I exercise, then I will stay healthy."
    1. Disjunctive syllogism
    2. Modus tollens
    3. Simplification
    4. Hypothetical syllogism
  4. Which of the following is NOT true about rules of inference?
    1. They are not reversible
    2. They are reversible
    3. They allow you to infer one formula from another
  5. What rule of inference is used in this argument? "Its raining and cloudy now. Thus, it is raining now."
    1. Simplification
    2. Conjunction
    3. Addition
    4. Disjunctive syllogism
Answers

1. d; 2. d; 3. d; 4. b; 5. a;

Introduction to Proofs
Introduction

A proof: a valid argument that establishes the truth of some mathematical statement.

Some Terminology
Understanding How Theorems Are Stated

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."
Becomes:
"If x > y, where x and y are postive real numbers, then x2 > y2."

Methods of Proving Theorems

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.

Direct Proofs

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 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.

Proof by Contraposition

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!

Proofs by Contradiction

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 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 = a2/b2
2b2 = a2
So a must be even.
So for some c, a = 2c. Then:
a2 = 4c2
So:
b2 = 2c2
So b is even as well!
But a/b was supposed to be a proper fraction. This is a contradiction.

Mistakes in Proofs

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 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

Test Yourself!
  1. A direct proof of a conditional statement p → q assumes:
    1. q is true so then p must be true
    2. p is true so then q must be true
    3. p and q both are false
    4. p and q both are true
  2. A theorem is a:
    1. false statement
    2. statement that is always true
    3. proof
    4. statement that can be proven to be true
  3. Indirect proofs make use of the following:
    1. p → q ⇔ ~p ∨ q
    2. p ∨ T ⇔ T
    3. p ∧ p ⇔ p
    4. p → q ⇔ ~q → ~p
  4. Which of the following is NOT true for mistakes in proofs?
    1. Most common errors are mistakes in arithmetic and basic algebra
    2. Conclusion needs to follow logically
    3. Each step should be correct
    4. Most common errors are mistakes in grammar
  5. What is wrong with this proof? 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.
    1. Because n is a complex number
    2. We cannot conclude that because we are not using a valid rule of inference
    3. If n2 is positive then n must be negative
    4. The proof is wrong due to grammatical errors
Answers

1. b; 2. d; 3. d; 4. d; 5. b;

Proof Methods and Strategy
Introduction

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.

Exhaustive Proof and Proof by cases

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.

Exhaustive Proof

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 ≥ 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

Proof by Cases

The proofs that must cover all the cases that arises in a theorem

Example:

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.

Test Yourself!
  1. A proof that proves a theorem by checking every possibility is called a/an:
    1. Exhaustive proof
    2. Irrational proof
    3. Proof by contraposition
    4. Proof by contradiction
  2. True or false: In 'proof by cases', proofs need not cover all cases that arise in a theorem.
    1. False
    2. True
  3. The following statement: 'if n is an integer, then n2 ≥ n' can be proven by using the 'proof by cases' method.
    1. True
    2. False
Answers

1. a; 2. a; 3. a;