1

1.2 The Fundamentals of Logic

Applications of Propositional Logic
 2
Applications of Propositional Logic
• Translating English to Propositional Logic
• System Specifications
• Boolean Searching (Not included)
• Logic Puzzles
• Logic Circuits (Not included)
 3
Translating English Sentences
• Steps to convert an English sentence to a statement in
propositional logic
• Identify atomic propositions and represent using
propositional variables.
• Determine appropriate logical connectives
• “If I go to London or to Paris I will not go shopping.”
• “If I go to London or to Paris, I will not go shopping.”
• p: I go to London
• q: I go to Paris If p or q then not r
• r: I will go shopping 𝑝 ∨ 𝑞 → ¬𝑟
 4
Example
Problem: Translate the following sentence into propositional
logic:
“You can access the Internet from campus only if you are a
computer science major or you are not a freshman.”
“You can access the Internet from campus only if you are a
computer science major or you are not a freshman.”
One Solution: Let
p represents “You can access the internet from campus”,
q represents “You are a computer science major”,
r represents “You are a freshman”
p → (q ∨ ¬ r )
 5
System Specifications
• System and Software engineers take requirements in English
and express them in a precise specification language based
on logic.
Example: Express in propositional logic:
“The automated reply cannot be sent when the file system is
full”
“The automated reply cannot be sent when the file system is
full”
Solution: One possible solution: Let
p denote “The automated reply can be sent”
q denote “The file system is full.” Contrapositive
q→¬p of r → s is
¬ (¬ p ) → ¬q p → ¬q ¬s → ¬r.
 6
Consistent System Specifications
Definition: A list of propositions is consistent if it is possible to
assign true/false values to the proposition variables so that each
proposition is true.
Exercise: Are these specifications consistent?
• “The diagnostic message is stored in the buffer or it is retransmitted.”
p∨q
• “The diagnostic message is not stored in the buffer.” ¬p
• “If the diagnostic message is stored in the buffer, then it is
retransmitted.” p→q
• p ∨ q, ¬p , p → q. When p is false and q is true all three statements
are true. So the specification is consistent.
 7
Logic Puzzles
• An island has two kinds of inhabitants, knights, who always tell the
truth, and knaves, who always lie.
• You go to the island and meet A and B.
• A says “B is a knight.”
• B says “The two of us are of opposite types.”
What are the types of A and B?
 8
Logic Puzzles
• A says “B is a knight.”
• B says “The two of us are of opposite types.”
Solution: Let
• p be the statement: A is a knight and
• q be the statement: B is a knight
So, then
• ¬ p represents the proposition: A is a knave and
• ¬ q: B is a knave.
• If A is a knight, then p is true. Since knights tell the truth, q must also be
true. This is a contradiction.
• If A is a knave, then B must not be a knight since knaves always lie. So, then
both ¬ p and ¬ q hold since both are knaves.
 1

1.3 The Fundamentals of Logic

Propositional Equivalences
 2
Propositional Equivalences
• Tautologies, Contradictions, and Contingencies.

• Logical Equivalence
• Important Logical Equivalences
• Showing Logical Equivalence

• Propositional Satisfiability

• Sudoku Puzzle (Not included)

 3
Tautologies, Contradictions, and Contingencies

•A tautology is a proposition which is

always true. Example: p ∨¬p
•A contradiction is a proposition which is
always false. Example: p ∧¬p
•A contingency is a proposition which is
neither a tautology nor a contradiction
Example: p p ¬p p ∨¬p p ∧¬p
T F T F
F T T F
 4
Logically Equivalent
• Two compound propositions r and s are
logically equivalent if r ↔ s is a tautology.
• Denoted by r ⇔ s or as r ≡ s
where r and s are compound propositions.
• In other words, two compound propositions r
and s are equivalent if and only if the
columns in a truth table giving their truth
values agree.
 5
Logically Equivalent

• This truth table show r: ¬p ∨ q is equivalent

to s: p → q.
p q ¬p ¬p ∨ q p → q
T T F T T
T F F F F
F T T T T
F F T T T
 6
De Morgan’s Laws
¬(p ∧ q) ≡ ¬p ∨ ¬q
¬(p ∨ q) ≡ ¬p ∧ ¬q
This truth table shows that De Morgan’s Second Law holds.
p q ¬p ¬q (p∨q) ¬(p∨q) ¬p∧¬q
T T F F T F F
T F F T T F F
F T T F T F F
F F T T F T T
 7

Key Logical Equivalences

• Identity Laws: p∧T≡p p∨F≡p
• Domination Laws: p ∨ T ≡ T p∧F≡F
• Idempotent laws: p ∨ p ≡ p p∧p≡p

• Double Negation Law: ¬(¬p) ≡ p

• Negation Laws: p ∨ ¬p ≡ T p ∧ ¬p ≡ F
 8

Key Logical Equivalences (cont)

• Commutative Laws: p ∨ q ≡ q ∨ p
p∧q≡q∧p
• Associative Laws: (p ∨ q) ∨ r ≡ p ∨ (q ∨ r)
(p ∧ q) ∧ r ≡ p ∧ (q ∧ r)
• Distributive Laws: p ∨ (q ∧ r) ≡ (p ∨ q) ∧ (p ∨ r)
p ∧ (q ∨ r) ≡ (p ∧ q) ∨ (p ∧ r)
• Absorption Laws: p ∨ (p ∧ q) ≡ p
p ∧ (p ∨ q) ≡ p
 9
Logical equivalences involving conditional
statement
p → q ≡ ¬p ∨ q ¬(p → q) ≡ p ∧ ¬q
p → q ≡ ¬q → ¬p (p → q) ∧ (p → r) ≡ p → (q ∧ r)
p ∨ q ≡ ¬p → q (p → q) ∨ (p → r) ≡ p → (q ∨ r)
p ∧ q ≡ ¬(p → ¬q) (p → r) ∧ (q → r) ≡ (p ∨ q) → r
(p → r) ∨ (q → r) ≡ (p ∧ q) → r
 10
Logical equivalences involving biconditionals
p ↔ q ≡ (p → q) ∧ (q → p)
p ↔ q ≡ ¬p ↔ ¬q
p ↔ q ≡ (p ∧ q) ∨ (¬p ∧ ¬q)
¬(p ↔ q) ≡ p ↔ ¬q
 11
Review: List of Logical Equivalences
pTp ; pF p Identity Laws

pT T; pF F Domination Laws

p  p  p; pp p Idempotent Laws

(p)  p Double Negation Law

pq qp;pq qp Commutative Laws

(p  q)  r  p  (q  r) ; (p  q)  r  p  (q  r)
Associative Laws
 12
List of Equivalences
p  (q  r)  (p  q)  (p  r) Distribution Laws
p  (q  r)  (p  q)  (p  r)

(p  q)  (p  q) De Morgan’s Laws

(p  q)  (p  q)
p  p  T OR Tautology
p  p  F AND Contradiction
(p  q)  (p  q) Implication Equivalence

p  q  (p  q)  (q  p) Biconditional Equivalence
 13
Constructing New Logical Equivalences
•We can show that two expressions are
logically equivalent by developing a series
of logically equivalent statements.
•To prove that A  B, we produce a series of
equivalences beginning with A and ending
with B. A  A1
A1  A2
AB .
.
.

An  B
 14
Equivalence Proofs
Example: Show that (p  (p  q))
is logically equivalent to (p  q)
Solution:
(p  (p  q))  p  (p  q) 2nd De Morgan L
 p  [(p )  q)] 1st De Morgan L
 p  (p   q) Double Negation L
 (p  p)  (p  q) 2nd Distribution L
 F  (p  q) (p  p)  F
 (p  q)  F Commutative L for Disjunction
 (p  q) Identity L for F
 15
Prove: p  q  q  p Contrapositive

pq
 p  q Implication Equivalence
 q  p Commutative
 (q)  p Double Negation
 q  p Implication Equivalence
 16
Prove: (p  q)  q  p  q
(p  q)  q Left-Hand Statement
 q  (p  q) Commutative
 (q  p)  (q  q) Distributive
 (q  p)  T OR Tautology
qp Identity
pq Commutative
Begin with exactly the left-hand side statement
End with exactly what is on the right
Justify EVERY step with a logical equivalence
Prove: p  q  p  q
p  q
 (p  q)  (q  p) Biconditional Equivalence
 (p  q)  (q  p) Implication Equivalence (twice)
 (p  q)  (q  p) Double Negation
 (q  p)  (p  q) Commutative
 (q  p)  (p  q) Double Negation
 (q  p)  (p  q) Implication Equivalence (twice)
 p  q Biconditional Equivalence
 18
Why do I have to justify everything?
•Note that your operation must have the same
order of operands as the rule you quote unless
you have already proven (and cite the proof)
that order is not important.
3+4=4+3
3/44/3
A * B  B * A for everything (for example, matrix
multiplication)
 19
Propositional Satisfiability
• A compound proposition is satisfiable if there is an
assignment of truth values to its variables that make it true.
When no such assignments exist, the compound proposition
is unsatisfiable.

• A compound proposition is unsatisfiable if and only if its

negation is a tautology.
 20
Propositional Satisfiability
Example: Determine the satisfiability of the following
compound propositions:
(p ∨￢q) ∧ (q ∨￢r) ∧ (r ∨￢p)
Solution: Satisfiable. Assign T to p, q, and r.
(p ∨ q ∨ r) ∧ (￢p ∨￢q ∨￢r)
Solution: Satisfiable. Assign T to p and F to q.
(p ∨￢q) ∧ (q ∨￢r) ∧ (r ∨￢p) ∧ (p ∨ q ∨ r) ∧ (￢p ∨￢q ∨￢r)
Solution: Unsatisfiable – Find out.
(p ∨￢q) ∧ (q ∨￢r) ∧ (r ∨￢p) and (p ∨ q ∨ r) ∧ (￢p ∨￢q ∨￢r) must both be true. For the first to be true, the three variables
must have the same truth values, and for the second to be true, at least one of three variables must be true and at least one
must be false. However, these conditions are contradictory. From these observations we conclude that no assignment of truth
values to p, q, and r makes the compound proposition true. Hence, it is unsatisfiable.
 21
Propositional Satisfiability
• Notation:
• ‫=𝑗𝑛ڀ‬1 𝑝𝑗 is used for p1  p2  …  pn

• 𝑛
‫=𝑗ٿ‬1 𝑝𝑗 is used for p1  p2  …  pn
1.4 Predicate and quantifiers
 3
1.4 Predicate and quantifiers
• Can be used to express the meaning of a wide range of
statements
• Allow us to reason and explore relationship between objects
• Predicates: statements involving variables e.g.
• “x > 3”
• “x = y + 3”
• “x + y = z”
• “computer x is under attack by an intruder”
• “computer x is functioning properly”
 4
Example: x > 3
• The variable x is the subject of the statement
• Predicate “is greater than 3” refers to a property that the
subject of the statement can have
• Can denote the statement by P(x)
• where P denotes the predicate “is greater than 3” and x is the
variable
• P(x): also called the value of the propositional function P at x
• Once a value is assigned to the variable x, P(x) becomes a
proposition and has a truth value
 5
Example
• Let P(x) denote the statement “x > 3”
• P(4): setting x = 4, 4 > 3 is true, thus P(4) is TRUE
• P(2): setting x = 2, 2 > 3 is false, thus P(2) is FALSE
• Let A(x) denote the statement “computer x is under attack by
an intruder”.
• Suppose that only CS2 and MATH1 are currently under attack
• A(CS1)? : FALSE
• A(CS2)? : TRUE
• A(MATH1)?: TRUE

• CS1, CS2, and MATH1 are computers’ names

 6
n-ary Predicate
• A statement involving n variables, x1, x2, …, xn, can be
denoted by P(x1, x2, …, xn)
• P(x1, x2, …, xn) is the value of the propositional function P at
the n-tuple (x1, x2, …, xn)
• P is also called n-ary predicate
 7
Universe of Discourse (domain)
• Consider the statement ‘x > 3’,
• does it make sense to assign to x the value
‘blue’?
• Intuitively, the universe of discourse
(domain) is
• the set of all things we wish to talk about;
• that is the set of all objects that we can
sensibly assign to a variable in a
propositional function.
• What would be the universe of discourse
for the propositional function below be:
Enrolled_CS200(x)=‘x is enrolled in CS200’
 Quantifiers (, )
8

• Express the extent to which a predicate is

TRUE
• In English, all, some, many, none, few
• Focus on two types: (, )
• Universal: a predicate is true for every
element under consideration 
• Existential: a predicate is true for one or
more elements under consideration 
• Predicate calculus: the area of logic that
deals with predicates and quantifiers
 9
Universal quantifier ()
• “P(x) for all values of x in the domain”
x P(x)
• Read it as “for all x P(x)” or “for every x P(x)”
• A statement x P(x) is false if and only if P(x) is not always
true
• An element for which P(x) is false is called a counterexample
of x P(x)
• A single counterexample is all we need to establish
that x P(x) is not true
 10
Example
• Let P(x) be the statement “x + 1 > x”.
• What is the truth value of x P(x)?
• Because P(x) is true for all real numbers x, the quantification
• x P(x) is true
• Implicitly assume the domain of a predicate is not empty
• Let Q(x) be the statement “x < 2”.
• What is the truth value of x Q(x) where the domain consists of all
real numbers?
• Q(x) is not true for every real number x, because, for instance,
Q(3) is false.
• That is, x = 3 is a counterexample for the statement ∀x Q(x).
• Thus ∀x Q(x) is false.
 11
Example
• Let P(x) be “x2 > 0”. To show that the statement
x P(x) is false where the domain consists of all
integers
• Show a counterexample with x = 0
• When all the elements can be listed, e.g.,
x1, x2, …, xn,
it follows that the universal quantification x P(x) is the
same as the conjunction
P(x1)  P(x2)  …  P(xn)
 12
Example
• What is the truth value of x P(x) where P(x) is the
statement “x2 < 10” and the domain consists of positive
integers not exceeding 4?
x P(x) is the same as
P(1)  P(2)  P(3)  P(4)
As P(4) = 16 is false, x P(x) is false
P(4) is a counterexample
 13
Existential quantification ()
• “There exists an element x in the domain such that P(x) (is
true)”
• Denoted as x P(x) where  is the existential quantifier
• In English, “for some”, “for at least one”, or “there is”
• Read as:
• “There is an x such that P(x)”,
• “There is at least one x such that P(x)”, or
• “For some x, P(x)”
 14
Example
• Let P(x) be the statement “x > 3”.
• Is x P(x) true for the domain of all real numbers? True
• Let Q(x) be the statement “x = x + 1”.
• Is x P(x) true for the domain of all real numbers? False
• When all elements of the domain can be listed, e.g.,
x1, x2, …, xn,
it follows that the existential quantification is the same as
disjunction
P(x1)  P(x2)  …  P(xn)
 15
Example
• What is the truth value of x P(x) where P(x) is the statement
“x2 > 10” and the domain consists of positive integers not
exceeding 4?
x P(x) is the same as
P(1)  P(2)  P(3)  P(4)
P(1) is 12 > 10 False
P(2) is 22 > 10 False
P(3) is 32 > 10 False
P(4) is 42 > 10 True
Thus, x P(x) is True
Actually, P(4) is 42 > 10 True
 16
Uniqueness quantifier (!  1)
• There exists a unique x such that P(x) is true
!x P(x)
• “There is exactly one”, “There is one and only one”
1x P(x)
 17
Quantifiers with restricted domains
• What do the following statements mean for the domain of real
numbers?
• x < 0 (x2 > 0)
• The square of a negative real number is positive.
• same as x (x < 0  x2 > 0)
• y  0 (y3  0)
• The cube of every nonzero real number is nonzero.
• same as y (y  0  y3  0)
• z > 0 (z2 = 2)
• There is a positive square root of 2.
• same as z (z > 0  z2 = 2)

Be careful about  and  in these statements

 18
Quantification Examples
• P(x) = “x + 1 = 2”
Domain is R (set of real numbers)

Proposition Truth Value

x P(x) F
x P(x) F
x P(x) T
x P(x) T
!x P(x) T
!x P(x) F
 19
Quantification Examples
• P(x) = “x2 > 0”
Domain Proposition Truth Value
R x P(x) F
Z x P(x) F
Z - {0} x P(x) T
Z !x P(x) T
N = {1,2, ..} x P(x) F
 20
Quantification Examples
Proposition Truth Value
x  R (x2  x) F
!x  R (x2 < x) F
x  (0,1) (x2 < x) T
x  {0,1} (x2 = x) T
x   P(x) T

if the domain is empty, then ∀xP(x) is true for any propositional

function P(x) because there are no elements x in the domain for
which P(x) is false.
 21
Precedence of quantifiers
•  and  have higher precedence than all logical operators
from propositional calculus
x P(x)  Q(x) is equivalent to (x P(x))  Q(x)

Rather than x (P(x)  Q(x))

 22
Binding variables
• When a quantifier is used on the variable x, this occurrence
of variable is bound
• If a variable is not bound, then it is free
• All variables occur in propositional function of predicate
calculus must be bound or set to a particular value to turn it
into a proposition
• The part of a logical expression to which a quantifier is
applied is the scope of this quantifier
 23
Example
What are the scopes of these expressions?
Are all the variables bound?

x (x + y = 1) x is bound, but y is free

x (P(x)  Q(x))  x R(x) All variables are bound

Same as:
x (P(x)  Q(x))  y R(y)
The same letter is often used to represent variables bound by
different quantifiers with scopes that do not overlap
 24
Logical equivalences
• S ≡ T: Two statements S and T involving predicates and
quantifiers are logically equivalent If and only if
• they have the same truth value no matter which predicates are
substituted into these statements and which domain is used for
the variables.
• Example: x (P(x)  Q(x))  x P(x)  x Q(x)
i.e., we can distribute a universal quantifier over a
conjunction
• Example: x (P(x)  Q(x))  x P(x)  x Q(x)
i.e., we can distribute a existential quantifier over a
disjunction
 25
x (P(x)  Q(x))  x P(x)  x Q(x)
• Both statements must take the same truth value
no matter the predicates P and Q, and no
matter which domain is used
• Show
• If LHS is true, then RHS is true (LHS → RHS)
• If RHS is true, then LHS is true (RHS → LHS)

x (P(x)  Q(x))  x P(x)  x Q(x)

x (P(x)  Q(x))  x P(x)  x Q(x)

x P(x)  x Q(x)  x (P(x)  Q(x))
 26
Negating Quantified Expressions
• x P(x)  x P(x)
• Negation of the statement “Every student in the class has taken a
course in Calculus”
• “It is not the case that every student in the class has taken a course in
Calculus.”
• This is equivalent to
• “There is a student in the class who has not taken a course in Calculus”
• x Q(x)  x Q(x)
• Negation of the statement “There is a student in this class who has
taken a course in calculus.”
• “It is not the case that there is a student in this class who has taken a
course in calculus.”
• This is equivalent to
“Every student in this class has not taken calculus”
 27
Negating quantified expressions
Negation: ￢∃ xP(x)
Equivalent Statement: ∀x ￢P(x)
When Is Negation True: For every x, P(x) is false.
When False: There is an x for which P(x) is true.

Negation: ￢∀x P(x)

Equivalent Statement: ∃x ￢P(x)
When Is Negation True: There is an x for which P(x) is false.
When False: P(x) is true for every x.

Negate the following statement

“There is an honest politician”
“Every politician is dishonest”
 28
Examples
What is the negations of the statement ∀x (x2 > x)?
Solution:
￢∀x (x2 > x)
 ∃x ￢(x2 > x)
 ∃x (x2 ≤ x)

What is the negations of the statement ∃x (x2 = 2)?

Solution:
￢ ∃x (x2 = 2)
 ∀x ￢(x2 = 2)
 ∀x (x2  2)
 29
Show that ￢∀x (P(x) → Q(x))  ∃x (P(x) ∧ ￢Q(x))
Solution:

￢∀x (P(x) → Q(x))

 ∃x (￢(P (x) → Q(x))) De Morgan’s Law

 ∃x (￢(￢P(x)  Q(x))) Implication Equivalence

 ∃x (￢(￢P(x)) ∧ ￢Q(x)) De Morgan’s Law

  ∃x (P(x) ∧ ￢Q(x)) Double Negation

 30
Translating English into logical expressions
• “Every student in this class has studied calculus”
Let C(x) be “x has studied calculus”.
Let S(x) be “x is in this class”
If the domain consists of students of this class
∀x C(x)
If the domain consists of all people
∀x(S(x) → C(x))
What about:
∀x(S(x) ∧ C(x)) Why?
This statement says that all people are students in this class and have
studied calculus
 31
Using quantifiers in system specifications
• “Every mail message larger than one megabyte will be
compressed”
• Let S(m,y) be “mail message m is larger than y megabytes”
where m has the domain of all mail messages and y is a positive
real number. Let C(m) denote “message m will be compressed”

∀m (S(m, 1) → C(m)).
 32
Example
• “If a user is active, at least one network link will be available”
• Let A(u) represent “user u is active” where u has the domain of all
users
• and let S(n, x) denote “network link n is in state x” where
• n has the domain of all network links, and
• x has the domain of all possible states, {available, unavailable}.
∃u A(u) → ∃n S(n, available)
1.5 Nested Quantifiers
 2
1.5 Nested quantifiers
Assume the domain for the variables x, and y consists of
real numbers R
∀x ∃y (x + y) = 0 says:
For every real number x, there exists a real number y
where x + y = 0
(this is true if we let y be –x)
∀x ∃y (x + y) = 0 same as ∀x Q(x) where
Q(x) is ∃y P(x, y) and P(x, y) is (x + y) = 0
∀x ∀y (x + y) = (y + x) says:
For every real number x, and every real number y,
(x + y) = (y + x)
- commutative law for addition of real numbers
 3
Nested quantifiers

Similarly, the associative law:

∀x ∀y ∀z (x + (y + z)) = ((x + y) + z)
Example: the domain is R
∀x ∀y ((x < 0)  (y < 0) → (xy > 0)) says ?
The multiplication of two negative real numbers is
a positive real number
 4
Quantification as loop
∀x ∀y P(x, y)

∀x ∃y P(x, y)

∃x ∀y P(x, y)

∃x ∃y P(x, y)
 5
Quantification as loop
• For every x, for every y ∀x ∀y P(x,y)
• Loop through x and for each x loop through y
• If we find P(x,y) is true for all x and y, then the
statement is true
• If we ever hit a value x for which we hit a value for which
P(x,y) is false, the whole statement is false
• For every x, there exists y ∀x ∃y P(x,y)
• Loop through x until we find a y that P(x,y) is true
• If for every x, we find such a y, then the statement is true
 6
Quantification as loop
• ∃x ∀y P(x,y): we loop through the values for x until we find
an x for which P(x, y) is always true when we loop through all
values for y. Once we find such an x, then it is true.
• ∃x ∃y P(x,y) : loop though the values for x where for each x
loop through the values of y until we find an x for which we
find a y such that P(x,y) is true.
• False only if we never hit an x for which we never find y
such that P(x,y) is true
 7
Order of quantification
Order is important unless all quantifiers are universal quantifiers
or all are existential quantifiers
Let P(x, y) be the statement “x + y = y + x”, domain is R.
What are the truth values of
∀x ∀y P(x, y)
∀y ∀x P(x, y)
 8
Order of quantification
∀x ∀y P(x, y) means
“for all real numbers x, for all real numbers y, x + y = y + x.”
an axiom for the real numbers R
∀x ∀y P(x, y) is true
∀y ∀x P(x, y) means
“for all real numbers y, for all real numbers x, x + y = y + x.”
same meaning as the above statement
∀y ∀x P(x, y) is true
The order of nested universal quantifiers in a statement without other
quantifiers can be changed without changing the meaning of the quantified
statement. ∀x ∀y P(x, y)  ∀y ∀x P(x, y)
 9
Order of quantification
Let Q(x, y) denote “x + y = 0.” What are the truth values of the
quantifications ∃y ∀x Q(x, y) and ∀x ∃y Q(x, y), Domain is R.
∃y ∀x Q(x, y) denotes the proposition
“ There is a real number y such that for every real number x, Q(x, y).”
No matter what value of y is chosen, there is only one value of x for which
x + y = 0. Because there is no real number y such that x + y = 0 for all real
numbers x, the statement ∃y ∀x Q(x, y) is false.
∀x ∃y Q(x, y) denotes the proposition
“For every real number x there is a real number y such that Q(x, y).”
Given a real number x, there is a real number y such that x + y = 0;
namely, y = −x. Hence, ∀x ∃y Q(x, y) is true.
Here the order in which quantifiers appear makes a difference. Be careful
with the order of existential and universal quantifiers!
 10
Quantification of two variables
Statement When True? When False?
∀x∀yP(x, y) P(x, y) is true for every pair There is a pair x, y for which
∀y∀xP(x, y) x, y. P(x, y) is false.
For every x there is a y for There is an x such that P(x, y)
∀x∃yP(x, y)
which P(x, y) is true. is false for every y.
There is an x for which P(x, y) For every x there is a y for
∃x∀yP(x, y)
is true for every y. which P(x, y) is false.
∃x∃yP(x, y) There is a pair x, y for which P(x, y) is false for every pair
∃y∃xP(x, y) P(x, y) is true. x, y.
 11
Order of Quantifiers
 Example: Let Q(x, y, z) be the statement “x + y = z”. What are the
truth values of the quantifications
∀x ∀y ∃z Q(x, y, z) and ∃z ∀x ∀y Q(x, y, z), where the domain for all
variables consists of all real numbers?

 Sol: ∀x ∀y ∃z Q(x, y, z) = “For all real numbers x and for all real
numbers y there is a real number z such that x + y = z” is true.
The order of quantification is important here. Since
∃z ∀x ∀y Q(x, y, z) = “There is a real number z such that for all real
numbers x and for all real numbers y, x + y = z”, is false, because
there is no z that satisfies the equation x + y = z for all real numbers
x and y
 12
Translating mathematical statements with Nested Quantifiers
• “The sum of two positive integers is always positive”
• First: we rewrite it so that the implied quantifiers and a
domain are shown:
• “For every two integers, if these integers are both
positive, then the sum of these integers is positive.”
• Next: we introduce the variables x and y to obtain
• “For all positive integers x and y, x + y is positive.”
• Next: ∀x ∀y ((x > 0) ∧ (y > 0) → (x + y > 0))
• where the domain for both variables consists of all
integers.
 13
Translating mathematical statements with Nested Quantifiers
• Note that we could also translate this using the positive
integers as the domain
• “The sum of two positive integers is always positive”
• “For every two positive integers, the sum of these integers is
positive”
• ∀x ∀y (x + y > 0)
• where the domain for both variables consists of all
positive integers.
 14
Example
• “Every real number except zero has a multiplicative inverse”
• (A multiplicative inverse of a real number x is a real number y
such that xy = 1.)
• “For every real number x except zero, x has a multiplicative
inverse.”
• “For every real number x, if x  0, then there exists a real
number y such that xy = 1.”
• ∀x ((x  0) → ∃y (xy = 1))
• Where the domain for both variables consists of real numbers
 15
Translating predicates with nested Quantifiers to English
• Assume C(x) is “x owns a computer ”,
F(x,y) is “x and y are friends”, and the domain for x and y
consists of all students in An-Najah.
• Express the following in English:
• ∀x (C(x) ∨ ∃y (C(y) ∧ F(x, y)))

• Answer: Every An-Najah student owns a computer

or is a friend of a An-Najah student who owns a
computer.
 16
Translating predicates to English
• Assume F(x,y) means x and y are friends, and the domain
consists of all students in An-Najah
• Express the following in English:
•∃x∀y∀z((F (x, y) ∧ F(x, z) ∧ (y  z))→￢F(y,z))
•There is a student none of whose friends are
also friends with each other.
 17
Negating nested quantifiers
￢∀x ∃y (xy = 1)
 ∃x ￢∃y (xy = 1)
 ∃x ∀y ￢(xy = 1)
 ∃x ∀y (xy  1).
 18
Negating nested quantifiers
• Use quantifiers to express:
• There does not exist a woman who has taken a
flight on every airline in the world.
• Sol:
• This statement is the negation of the statement
“There is a woman (w) who has taken a flight (f)
on every airline (a) in the world”
• ￢∃w ∀a ∃f (P(w, f) ∧ Q(f, a))
• where P(w, f) is “w has taken f ”, and
Q(f, a) is “f is a flight on a”
1.6 Rules of Inference
 2
1.6 Rules of Inference
•Proof: valid arguments that establish the truth of
a mathematical statement
•Argument: a sequence of statements that end
with a conclusion
•Valid: the conclusion or final statement of the
argument must follow the truth of preceding
statements or premises of the argument
 3
Argument and inference
•An argument is valid if and only if it is impossible
for all the premises to be true and the
conclusion to be false
•Rules of inference: use them to deduce
(construct) new statements from statements
that we already have
•Basic tools for establishing the truth of
statements
 4
Valid arguments in propositional logic
•Consider the following arguments involving
propositions
p

p→q
“If you have a current password,
then you can login to the network” q
p “You have a current password” premises

∴ therefore, p→q
q “You can login to the network” conclusion p→q
______
∴q
 5
p
Valid arguments p→q
______
• (p ∧ (p → q)) → q is tautology ∴q

•When (p ˄ (p → q)) is true, both p and p → q are

true, and thus q must be also be true
•This form of argument is true because when the
premises are true, the conclusion must be true
 6
p
Valid arguments p→q
______
∴q
(p ∧ (p → q)) → q is is a tautology (always true)

p q p→q (p → q)  p ((p → q)  p) → q
0 0 1 0 1
0 1 1 0 1
1 0 0 0 1 ∴ therefore
1 1 1 1 1

This is another way of saying that

 9
Rules of inference for propositional logic
• Can always use truth table to show an argument form
is valid
• For an argument form with 10 propositional variables,
the truth table requires 210 rows (1024)
• The tautology (p ∧ (p → q)) → q is the rule of
inference called modus ponens (mode that affirms),
or the law of detachment p
p→q
______
∴q
 10
Example
•If both statements
• “If it snows today, then we will go skiing” p → q
• “It is snowing today” p
are true
•By modus ponens,
• it follows the conclusion
p
• “We will go skiing” q p→q
is true ______
∴q
 11
Example
• is the following argument valid? Is the conclusion true?
If . We know that

Consequently,

• Let p be . Let q be p→q

• The premises of the argument are p → q and p, p
• the conclusion is q ______
• This argument is valid by using modus ponens ∴q
3
• But one of the premises ( 2 > ) is false, consequently we cannot
2
conclude the conclusion is true
• The conclusion is false.
 12
Rules of Inference
•Means to draw conclusions from other
assertions
•Rules of inference provide justification of steps
used to show that a conclusion follows from a
set of hypotheses (premises)
•The next several slides illustrate specific rules of
inference
 13
Addition

A true hypothesis implies that the disjunction

of that hypothesis and another are true

p
_______
or p  (p  q)
pq
 14
Simplification

If the conjunction of 2 propositions is true,

then each proposition is true

pq
_______ or (p  q)  p
p
 15
Conjunction

If p is true and q is true, then p  q is true

p
q or ((p)  (q))  p  q
_______
pq
 16
Modus Ponens

If a hypothesis and implication are both true,

then the conclusion is true

p
pq or (p  (p  q))  q
_______
q
 17
Modus Tollens

If a conclusion is false and its implication

is true, then the hypothesis must be false

q
pq or (q  (p  q))  p
_______
p
 18
Hypothetical Syllogism

If an implication is true, and the implication

formed using its conclusion as the hypothesis is
also true, then the implication formed using the
original hypothesis and the new conclusion is
also true
pq
qr or ((p  q)  (q  r))  (p  r)
_______
pr
 19
Disjunctive Syllogism

If a proposition is false, and the disjunction of it

and another proposition is true, the second
proposition is true

pq
p
_____ or, ((p q)  p)  q
q
 20
Resolution

pq
p  r
_____ or, ((p  q)  (p  r ))  (q  r)
qr
21
 22
Example

Let p = “It is Sunday” and

p  q = “If it is Sunday, I have Physics Lab today”
If these statements are both true,
then by Modus Ponens: p
(p  (p  q))  q p→q
we can conclude “I have Physics Lab today” (q) ______
∴q
 23
Example

Let q = “I don’t have Physics Lab today” and

p  q = “If it is Sunday, I have Physics Lab today”
If both of the above are true, then by Modus Tollens:
(q  (p  q))  p q
we can conclude “It is not Sunday” (p) pq
_______
p
 24
Example of proof
• We have the hypotheses (premises):
• “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, then we will take a canoe
trip”
• “If we take a canoe trip, then we will be home by
sunset”
• Does this imply that “we will be home by sunset”?
 25
Solution
hypotheses (premises)
• We have the hypotheses:
p, q • “It is not sunny this afternoon and it is
colder than yesterday” ¬p  q
r • “We will go swimming only if it is sunny” r→p
• “If we do not go swimming, then we will
s take a canoe trip” ¬r → s
t • “If we take a canoe trip, then we will be s→t
home by sunset”
Conclusion
• Does this imply that “we will be home by t?
sunset”?
 26
Solution (continued) Premises
1. ¬p  q 1st hypothesis (premise) ¬p  q
2. ¬p Simplification using step 1
3. r → p 2nd hypothesis r→p
4. ¬r Modus tollens using steps 2 & 3
5. ¬r → s 3rd hypothesis ¬r → s
6. s Modus ponens using steps 4 & 5
7. s → t 4th hypothesis s→t
8. t Modus ponens using steps 6 & 7

pq p q
________
p→q p→q
∴p _________ _________
∴q ∴p
 27
So what did we show?
hypotheses (premises)
• We showed that:
• ((¬p  q)  (r → p)  (¬r → s)  (s → t)) → t
¬p  q
• That when the 4 hypotheses are true, then
the implication is true r→p
• In other words, we showed the above is a ¬r → s
tautology!
s→t
Conclusion
t
 28
So what did we show?
• To show this, enter the following into the truth table
generator at
http://turner.faculty.swau.edu/mathematics/materialslibrary/truth/
((~P & Q) & (R > P) & (~R > S) & (S > T)) > T
•Do you want to search for other truth table
generators?
 29
Example
– Show that the premises (hypotheses)
– “If you send me an email message, then I will finish my
program”
– “If you do not send me an email message, then I will go to
sleep early”
– “If I go to sleep early, then I will wake up feeling refreshed”
–lead to the conclusion
–“If I do not finish writing the program, then I will wake up
feeling refreshed”
 30
Solution
•Let
• p “You send me an e-mail message”
• q “I will finish writing the program”
• r “I will go to sleep early”
• s “I will wake up feeling refreshed”
 31
Solution
– Show that the premises  Premises (Hypotheses)
– “If you send me an email message,  p→q
then I will finish my program”
– “If you do not send me an email
message, then I will go to sleep  ￢p → r
early”
– “If I go to sleep early, then I will wake  r→s
up feeling refreshed”
– lead to the conclusion
– “If I do not finish writing the program,
 Conclusion
then I will wake up feeling refreshed”  ￢q → s

• p “You send me an e-mail message” • r “I will go to sleep early”

• q “I will finish writing the program” • s “I will wake up feeling refreshed”
 32
So given p → q, ￢p → r, r → s show ￢q → s
Step Reason
[1] p → q Premise
[2] ￢q → ￢p Contrapositive of (1)
[3] ￢p → r Premise
[4] ￢q → r Hypothetical syllogism using (2) and (3)
[5] r → s Premise
[6] ￢q → s Hypothetical syllogism using (4) and (5)

• p “You send me an e-mail message” • r “I will go to sleep early”

• q “I will finish writing the program” • s “I will wake up feeling refreshed”
 33
Special case of Resolution
• Based on the tautology ((p  q)  (p  r ))  (q  r)
• Resolvent: (q  r)
• Let r = q, we have ((p  q)  (p  q ))  q
• Let r = F, we have ((p  q)  p )  q
• Important in logic programming, AI, etc.
 34
Example
“It is hot or Sami is reading” p  q
“It is not hot or Ali is swimming ” p  r
 imply 
“Ali is swimming or Sami is reading” q  r

• ((p  q)  (p  r ))  (q  r) (Resolution)

 35
Example
• To construct proofs using resolution as the only rule of
inference, the hypotheses and the conclusion must be
expressed as clauses
• Clause: a disjunction of variables or negations of these
variables
• To show that (p  q)  r and r  s imply p  s
We start by showing
• (p  q)  r  (p  r)  (q  r) Expressed as two clauses
• r  s  r  s Expressed as a clause
Then we continue
 36
Fallacies
• Inaccurate arguments
• Is ((p  q)  q)  p a tautology? Find out!
• ((p  q)  q)  p is not a tautology as it is FALSE when p is
FALSE and q is TRUE
• If you do every problem in this book, p
then you will learn discrete mathematics. q
• You learned discrete mathematics. q
Therefore you did every problem in this book
(p  q)  q
Fallacy
 37
Example
• ((p  q)  p) is it correct to conclude q?
• Is ((p  q)  p)  q a tautology? Find out!
(p  q)  q  p
•Fallacy: the incorrect argument is of the form as
p does not imply q
 38
Rules of Inference for Quantified Statements
•Universal instantiation:
x P(x)
____________
 P(c) if c  U (U is the domain (Universe of Discourse))

•Universal generalization:
P(c) for arbitrary c  U (U is the domain (Universe of Discourse))
___________________
 x P(x) Note: c must be arbitrary
 39
Rules of Inference for Quantified Statements
• Existential instantiation:
x P(x)
______
 P(c) for some c  U (U is the domain (Universe of Discourse))
Note that value of c is not known; we only know it exists
• Existential generalization:
P(c) for some c  U
________________
 x P(x)
 40
Inference with quantified statements

Instantiation:
c is one particular member
of the domain

Generalization:
for an arbitrary member c
 41
Example
Let P(x) = “A man is mortal”; then
x P(x) = “All men are mortal”

Assuming r = “Ali is a man” is true, show that

s = “Ali is mortal” is implied

This is an example of universal instantiation:

P(Ali) = “Ali is mortal”;

Since x P(x)
_______
 P(c)
 43
Example
Show that
“A student in this class has not read the book”, and “Everyone
in this class passed the first exam” imply “Someone who
passed the first exam has not read the book”

• Assume C(x) represents x is a student in the class

• Assume B(x) represents x has read the book
• Assume P(x) represents x has passed the first exam
 44
Example
Step Reason
[1] ∃x (C(x) ∧ ￢B(x)) Premise
[2] C(a) ∧ ￢B(a) Existential instantiation from [1]
[3] C(a) Simplification from [2]
[4] ∀x (C(x) → P(x)) Premise
[5] C(a) → P(a) Universal instantiation from [4]
[6] P(a) Modus ponens from [3] and [5]
[7] ￢B(a) Simplification from [2]
[8] P(a) ∧ ￢B(a) Conjunction from [6] and [7]
[9] ∃x (P(x) ∧ ￢B(x)) Existential generalization from [8]

Show that “A student in this class has not read the book”, and “Everyone in this class passed the first
exam” imply “Someone who passed the first exam has not read the book”
C(x): x is a student in the class. B(x): x has read the book. P(x): x has passed the first exam
 45
Universal modus ponens
•Use universal instantiation and modus ponens to
derive new rule
∀x (P(x) → Q(x))
P(a), where a is a particular element in the domain

∴ Q(a)
 46
Example: Universal modus ponens
• Assume “For all positive integers n, if n is greater than 4, then n2 is
less than 2n” is true. Show 1002 < 2100.
• Solution:
• Let P(n) be “n > 4” and Q(n) be “n2 < 2n”
• The statement “For all positive integers n, if n is greater than 4, then
n2 is less than 2n” can be represented by ∀n(P(n) → Q(n))
• where the domain consists of all positive integers.
• We are assuming that ∀n(P(n) → Q(n)) is true.
• Note that P(100) is true because 100 > 4. It follows by universal
modus ponens that Q(100) is true, namely that 1002 < 2100
 47
Universal modus tollens
•Combine universal modus tollens and universal
instantiation
∀x (P(x) → Q(x))
￢Q(a), where a is a particular element in the domain
∴ ￢P(a)
1.7 Introduction to proofs
 3
Some terminology
• Theorem ‫ نظرية‬: a mathematical statement that can be shown to be true
(fact or result)
• Proposition ‫فرضية‬: less important theorem
• Axiom ‫( بديهية‬postulate ‫)مسلمة‬: a statement that is assumed to be true
• Lemma: less important theorem that is helpful in the proof of other
results
• Corollary ‫الزمة‬: a theorem that can be established directly from a
theorem that has been proved
• Conjecture ‫حدس‬: a statement proposed to be true, but not proven yet
 4
Proof Techniques (Methods)
 Four primary proof methods:
 Direct Proof

 Indirect Proof

 Proof by Contradiction

 Proof by Induction

 We will cover Proof by Induction later

 5
Direct Proof
• Used to prove: “p  q” Or x (P(x)  Q(x))
• To prove such statements
• Assume that p (or P(c) for arbitrary c) is true
• Use all possible facts, lemmas, theorems, and rules of
inference and try to show that q (or Q(c)) is true.
• A direct proof often uses the form:
p  p1  p2 …  pn  q
• Because  is transitive,
we conclude that p  q
 6
Definition
• The integer n is even if there exists an integer k such that
n = 2k Ex: 82 = 2 × 41 Ex: 120 = 2 × 60
• The integer n is odd if there exists an integer k such that
n = 2k + 1 Ex: 131 = 2 × 65 + 1 Ex: 17 = 2 × 8 + 1
• The integer n is a perfect square if there exists an integer k
such that n = k2 Ex: 144 = 122 Ex: 25 = 52
• Note that an integer is either even or odd Zero is even
Let Z be the set of integers: (negative, zero, positive) Zero is neither
1. n  Z is even  k  Z such that n = 2k positive nor
2. n  Z is odd  k  Z such that n = 2k + 1 negative

3. n  Z is a perfect square  n = k2 for some k  Z.

Note: n  Z  n is either even or n is odd
 7
Direct Proof – Example
Prove that if n  Z is odd, then n2 is odd, i.e.,
n  Z (n is odd  n2 is odd).
Proof (direct):
Assume that n  Z is odd, then by definition
k  Z such that n = 2k + 1
Then n2 = (2k + 1)2 = 4k2 + 4k + 1
= 2(2k2 + 2k) + 1 = 2m + 1 for some integer m = (2k2 + 2k)
Thus, n2 is odd.
 8
Direct Proof – Example
Prove that if n, m  Z are perfect squares, then nm is a perfect
square.
Proof (direct):
Let n, m be perfect squares.
Then n = k2 and m = j2 for some k, j  Z.
Then nm = k2 j2
=kkjj=kjkj
(using commutativity and associativity of multiplication)
= (k j)2
= r2 for some integer r r = (k j)
Thus, nm is a perfect square.
 9
Definitions: Rational vs. Irrational Numbers
A real number r is rational iff there are two integers n
and m such that r = n / m where m  0.
Examples: 7 = 7/1, 1/2, 0.333333… = 1/3
A real number r is irrational iff it is not rational.
Examples:
π (Pi) = 3.1415926535897932384626433832795…
Note: 22/7 is an approximation for π
22/7 = 3.1428571428571...
The number e (Euler's Number)
2.7182818284590452353602874713527…
We use Q to denote the set of rational numbers.
 10
Direct Proof – Example
Prove that the sum of two rational numbers is a rational number.
Proof (direct):
Let x, y  Q. Q denotes the set of rational numbers.
Then x = n1 / m1 , y = n2 / m2, where n1, m1, n2, m2, are integers and
m1  0 and m2  0
Then (x + y) = n1 / m1 + n2 / m2 = (n1m2 + n2m1) / (m1m2) = k / j for
some integers k, j and j  0 k = (n1m2 + n2m1) and j = (m1m2)
Consequently, (x + y)  Q
 11
Indirect Proof (Proof by contraposition)
• An indirect proof of p  q uses the contrapositive

• Because p  q  q  p, we can prove p  q by

proving q  p

• Thus an indirect proof of p  q starts by assuming q

and continues to show p; i.e., the proof uses the form

q  r1  r2 …  rn  p
 12
Indirect Proof – Example
Prove that for an integer n, if 3n + 2 is odd, then n is odd.
Proof (by contraposition):
We need to show that if n is not odd then 3n + 2 is not odd
We need to show that if n is even then 3n + 2 is even
Thus, we assume that n is even
Then n = 2k for some integer k
Thus, 3n + 2 = 6k + 2 = 2 (3k + 1) = 2m for some integer m m = (3k + 1)
Thus, 3n + 2 is even. Hence if n is even then 3n + 2 is even. The
contrapositive of this statement is
if 3n + 2 is odd, then n is odd. This completes the proof.
 13
When to use an indirect proof
• Sometimes a direct proof leads to a dead end.
Theorem: Prove that if n  Z and n2 is even,
then n is even. (We will use this theorem in a latter proof)
Proof :
Try a direct proof: (start with p) n2 = 2k, and so
n = 2𝑘, and then ....???
Try an indirect proof (using contrapositive):
(q) n is odd  n = 2k + 1  n2 = (2k + 1)2 = 4k2 + 4k + 1
= 2(2k2 + 2k) + 1 = 2m + 1 for some integer m
 n2 is odd (p)
 14
Example
• Prove that if n = ab, where a and b are positive integers, then 𝑎 ≤ 𝑛
or 𝑏 ≤ 𝑛.
Prove that if 𝑎 > 𝑛 and 𝑏 > 𝑛,
• What is the contrapositive?? where a and b are positive integers,
then n ≠ ab.
Prove by contraposition (p → q  ￢q → ￢p)
Assume ￢(𝑎 ≤ 𝑛  𝑏 ≤ 𝑛)
 (𝑎 > 𝑛  𝑏 > 𝑛)
𝑎𝑏 > 𝑛. 𝑛 = 𝑛
𝑎𝑏 ≠ 𝑛, which contradicts the statement n = ab ￢(n = ab)
• Because the negation of the conclusion of the conditional statement implies that
the hypothesis is false, the original conditional statement is true. We have Proven
that if n = ab, where a and b are positive integers, then 𝑎 ≤ 𝑛 or 𝑏 ≤ 𝑛.
 15
Proof by Contradiction (another type of indirect proof)
• Can be used to prove statements of the form: p or p  q
• To prove p by contradiction, we show that the negation of p
(i.e., p) leads to some kind of a contradiction (false
proposition) like (r  r)
• To prove p  q by contradiction, we assume the
negation of p  q and try to get a contradiction.
• (p  q)  (p  q)  (p  q)
• (i.e., we assume p  q) and try to get a contradiction,
i.e., (p q)  F or (p q)  p [or (p q)  q]
 16
Proof by Contradiction – Ex: Prove that 2 is irrational.
• Assume 2 is not irrational, i.e., 2 is rational. i.e., 2 = n/m for
some integers n and m  0 where n and m have no common factors.
• If 2 = n/m then 2 = n2/m2, i.e., 2m2 = n2 (1)
• (1) states that n2 is even  n is even (by previous theorem) (P)
• Because n is even (assume n = 2k), we can rewrite (1) as
• 2m2 = 4k2
• Thus (by dividing both sides by 2),
• m2 = 2k2 (2)
• (2) state that m2 is even  m is even (by previous theorem) (Q)
• We have just shown (P and Q) that both n and m are even, i.e., they
have a common factor. This is a contradiction with our starting
assumption.
 17
Example
• Proof by contradiction “If 3n + 2 is odd,
then n is odd”
• Let p be “3n + 2 is odd” and q be “n is odd”
• So we want to prove that p  q or (p  q) is true.
• To construct a proof by contradiction, assume both p
and q (n is even) are both true, i, e. (p  q)
• Since n is even, let n = 2k, then 3n + 2 = 6k + 2
= 2(3k + 1). So 3n + 2 is even, i.e. p,
• Both p and p are true, so we have a contradiction
 18
Proof by Contradiction – Example
Prove that if 16 bicycles are painted red, white and
green then at least 6 bicycles will have the same color.
Proof (by contradiction):
• Assume not, i.e., for each color there is < 6 (i.e.,  5)
bicycles.
• Then (compute the number of cycles from the view
point of colors) the number of cycles is
(3 × ( 5))  15 bicycles,
which contradicts the premise that there are 16
bicycles.
 19
Theorem
• n is even if and only if nk is even for any integer k > 1.
• n is odd if and only if nk is odd for any integer k > 1.

• Notes:
• “p if and only if q” is often written as
p ↔ q (that is, p → q and q → p)
• To prove “p if and only if q”, we must prove “if
p then q” and “if q then p”.
 20
Example
• Prove the theorem “If n is a positive integer, then n
is odd if and only if n2 is odd”
• To prove “p if and only if q” where p is “n is odd” and
q is “n2 is odd”
• Need to show p → q and q → p
“If n is odd, then n2 is odd”, and “If n2 is odd, then n
is odd”
• We have proved p → q and q → p in previous
examples and thus prove this theorem with iff
 21
Proof of equivalence
•To prove a theorem that is a biconditional
statement p ↔ q, we show p → q and q → p
•The validity is based on the tautology
(p ↔ q) ↔ ((p → q) ˄ (q → p))
 22
Proving Equivalence of Three Propositions
• To prove that P  Q  R, it suffices (and is more efficient) to
prove:
(P  Q)  (Q  R)  (R  P)
• In general,
[p1  p2  …  pn] 
[(p1  p2)  (p2  p3)  …  (pn  p1)]

• Example: Prove that the following are equivalent

• P: n is even
• Q: n - 1 is odd
• R: n2 is even
 23
Prove that the following are equivalent:
P: n is even, Q: n - 1 is odd, R: n2 is even

• (P) n is even  n = 2k
 n - 1 = 2k - 1 = 2(k - 1) + 1 = 2m + 1
 n - 1 is odd (Q)
• (Q) n - 1 is odd  n - 1 = 2k + 1  n = 2k + 1 + 1
 n = 2(k + 1)  n2 = 4 (k + 1)2 = 2 (2 (k + 1)2) = 2m
 n2 is even (R)
• (R) n2 is even  n is even (P) by a previous theorem
 24
Equivalent theorems
• p1 ↔ p2 ↔ … ↔ pn
• For i and j with 1 ≤ i ≤ n and 1 ≤ j ≤ n,
pi and pj are equivalent
[p1 ↔ p2 ↔ … ↔ pn] ↔
[(p1 → p2) ˄ (p2 → p3) ˄ … ˄ (pn → p1)]
• More efficient than prove pi → pj for i ≠ j with
1 ≤ i ≤ n and 1 ≤ j ≤ n
• Order is not important as long as we have chain
 25
Prove False by a Counterexample
• Prove that every positive integer is the sum of
the squares of two integers.
• The statement to be proven is false.
• The following is a counterexample:
For number 3, 3 = 2 + 1 or 3 = 3 + 0.
None of these cases is a sum of two squares.
 26
Vacuous & Trivial Proofs
Consider p  q
• Vacuous proof: if p is false then p  q is always true.
• Trivial proof: if q is true then p  q is always true.
• Examples:
• If 0 > 1, then n2 > n for any integer n.
• (vacuous proof)

• For integers a, b if a > b, then a2  0

• (trivial proof)
 27
Vacuous Proofs
• The implication p  q is always true if the premise
p is false
• A vacuous proof is a proof that relies on the fact
that no element in the universe of discourse
satisfies the premise (thus the statement exists in
vacuum (empty domain)).
• Examples:
• If x is a prime number divisible by 16, then x2 is
negative
• No prime number is divisible by 16, thus this
statement is true
 28
Trivial Proofs
• The implication p  q is always true if the
conclusion q is true
• A trivial proof is where the conclusion is shown to
be (always) true independent of the premise p
• Examples:
• “if you score A+ then 2 > 1”
• “If Math is easy then the Earth is round”
 29
Trivial Proofs
 Prove If x > 0 then (x + 1)2 – 2x  x2
Proof:
It is easy to see:
(x + 1)2 – 2x
= (x2 + 2x + 1) – 2x
= x2 + 1
 x2
• Note that the conclusion holds without using the hypothesis.
 30
Mistakes in proofs
•What is wrong with this proof
• “if a = b then 1 = 2”?
1) a = b (given)
2) a2 = ab (multiply both sides of 1 by a)
3) a2 - b2 = ab - b2 (subtract b2 from both sides of 2)
4) (a - b) (a + b) = b (a - b) (factor both sides of 3)
5) a + b = b (divide both sides of 4 by (a - b))
6) 2b = b (replace a by b in 5 as a = b and simply)
7) 2 = 1 (divide both sides of 6 by b)
(a - b) equals zero. Dividing by zero is invalid.
 31
What is wrong with this proof?
• “Theorem”: If n2 is positive, then n is positive not valid
“Proof”: Suppose n2 is positive. As the statement
“If n is positive, then n2 is positive” is true, we
conclude that n is positive
• P(n): If n is positive, Q(n): n2 is positive. The
statement is ∀n(P(n) → Q(n))
• The hypothesis is Q(n). From these, we cannot
conclude P(n) as no valid rule of inference can be
applied
• Counterexample: n = -1
 32
What is wrong with this proof?
• “Theorem”: If n is not positive, then n2 is not positive not valid
“Proof”: Suppose that n is not positive. Because the
conditional statement “If n is positive, then n2 is positive”
is true, we can conclude that n2 is not positive.
• P(n): If n is positive, Q(n): n2 is positive. The statement is
∀n(P(n) → Q(n))
• From our hypothesis (￢P(n)) and ∀n(P(n) → Q(n)) we
cannot conclude ￢Q(n) as no valid rule of inference can
be used
• Counterexample: n = -1
 33
Circular reasoning (begging the question)
• Is the following argument correct to show that
If n2 is even, then n is even
Suppose that n2 is even, then n2 = 2k for some
integer k. Let n = 2y for some integer y. This shows
that n is even
• Wrong argument as the statement “n = 2y for some
integer y” is used in the proof
• No argument shows n can be written as 2y
• Circular reasoning as this statement is equivalent to
the statement being proved
 34
Proofs
• Learn from mistakes
• Even professional mathematicians make mistakes in
proofs
• Quite a few incorrect proofs of important results
have fooled people for years before subtle errors
were found
• Some other important proof techniques
• Mathematical induction
• Combinatorial proof
 1

5.1 & 5.2 Mathematical Induction

 2
Structure of a Proof by Induction
• Induction can be used to prove that a given
proposition, P(n), holds for all integers n  n0,
where n0 is some fixed integer.

• The proof consists of two steps:

Base step:
Prove P(n0)
Induction step:
Prove
n  n0 P(n)  P(n + 1)
 3
Structure of a Proof by Induction
• The proof consists of two steps:
Base step: Prove P(n0)
Induction step: Prove
n  n0 P(n)  P(n + 1)
In other words, for an arbitrary integer n (where
n  n0) we assume that P(n) is true and show as a
consequence that P(n + 1) is true.
The left side of the implication (P(n)) is called the
induction hypothesis (IH) because it is what is
assumed in the induction step.
 4
Structure of a Proof by Induction
• The induction step is also equivalent to:
• Prove n > n0 P(n  1)  P(n)
(Note the inequality)
and
• Prove k  n0 P(k)  P(k + 1)
(Can use any letter instead of n)
 5
Why Induction Proof is Valid
• An induction proof establishes the
following propositions:
P(n0), P(n0 + 1), P(n0 + 2), ... and so on.
• First note that the induction step
establishes:
P(n0)  P(n0 + 1),
P(n0 + 1)  P(n0 + 2), … and so on.
 6
Why Induction Proof is Valid
• P(n0) is established by the base step
• P(n0 + 1) is established by (modus ponens)
P(n0)  P(n0 + 1) , and P(n0)
• P(n0 + 2) is established by
P(n0 + 1)  P(n0 + 2) and P(n0 + 1)
• This shows that the proof method is
sound. It is being gradually established for
each successive value of n.
 7
Why Induction Proof is Valid
• A proof by induction is similar to climbing
a ladder (having an infinite number of steps).
• One is able to climb all the ladder steps if both
of the following propositions are true:

1. He is able to climb to the first step; this is

the base step.
2. From an arbitrary step n, he is able to
climb one step higher; this is the induction
step.
 8
Induction Proof – Example 1
• Prove that 1 + 2 + … + n = n(n + 1)/2 for all integers n  1.
• Base step: We show P(n) for n = 1. In this case,
LHS = 1 and RHS = 1(1 + 1)/2 = 1. Thus, the proposition is true for n = 1.
• Induction step: We must show that, for n  1, P(n)  P(n + 1). Thus, we
assume (induction hypothesis) the following:
1 + 2 + … + n = n(n + 1)/2 (1)
We must show P(n + 1). That is,
1 + 2 + … + n + (n + 1) = (n + 1)((n + 1) + 1)/2 = (n + 1)(n + 2)/2 (2)

LHS of Equation (2) = 1 + 2 + … + n + (n + 1) = n(n + 1)/2 + (n + 1), where the

sum of the first n terms on the LHS is replaced by the RHS of Equation (1).
The latter expression = (n + 1)(n/2 + 1) = (n + 1)(n/2 + 2/2) = (n + 1)(n + 2)/2 =
RHS of Equation (2).
 9
Induction Proof – Example 2
• Conjecture a formula for the sum of the first n positive
odd integers. Then prove the conjecture using induction.
1 = 1, 1 + 3 = 4, 1 + 3 + 5 = 9 , 1 + 3 + 5 + 7 = 16,
1 + 3 + 5 + 7 + 9 = 25, 1 + 3 + 5 + 7 + 9 + 11 = 36
• It is reasonable to conjecture that the sum of first n odd
integers is n2, that is, 1 + 3 + 5 + … + (2n - 1) = n2.
• In the preceding proposition, n ranges over integers (and
not odd integers). Thus, it is appropriate to use induction
to prove it.
 10
Induction Proof – Example 2 – Cont.
• Let p(n) denote the proposition 1 + 3 + 5 + … + (2n - 1) = n2
• Base step: p(1) (that is, n = 1): LHS = 1, RHS = 12 . LHS = RHS.
• Induction step: Assume that p(k) is true, i.e.,
1 + 3 + 5 + … + (2k - 1) = k2
We must show p(k + 1), that is,
1 + 3 + 5 + … + (2k + 1) = (k + 1)2 (1)
LHS of (1) = 1 + 3 + 5 + … + (2k - 1) + (2k + 1)
= k2 + 2k + 1 = (k + 1)2 = RHS of (1)
• We have completed both the base and induction steps. That is,
we have shown p(1) is true and p(k)  p(k + 1). Consequently,
p(n) is true for all positive integers n.
 11
Induction Proof – Example 3
• Use induction to show that n < 2n for all integers n  1.
• Base step: p(1) is true because 1 < 21 .
• Induction step: Assume p(k) is true, i.e., k < 2k
We need to show that p(k + 1) is true, that is k + 1 < 2k + 1
k < 2k  k + 1 < 2k + 1 and 2k + 1 ≤ 2k + 2k = 2k + 1
Thus k + 1 < 2k + 1 which means that p(k + 1) is true.
 12
Induction Proof – Example 4
• Use induction to show that 2n < n! for n ≥ 4.
• Let p(n) be the proposition, 2n < n! for n ≥ 4.
• Base step: p(4) is true as 24 = 16 < 4! = 24
• Induction step: Assume p(k) is true, i.e., 2k < k! for k ≥ 4.
We need to show that p(k + 1) is true: 2k + 1 < (k + 1)! for k ≥ 4.
2k + 1 = 2 . 2k < 2 k! < (k + 1) k! = (k + 1)! for k ≥ 4.
This shows p(k + 1) is true when p(k) is true.
• We have completed the base and induction steps; thus, we
have shown that p(n) is true for n ≥ 4.
 13
Induction Proof – Example 5
• Prove that n3 – n is divisible by 3 for all integers n ≥ 1.
• Let p(n) be the proposition that n3 – n is divisible by 3.
• Base step: p(1) is true as 13 – 1 = 0 which is divisible by 3.
• Induction step: Assume p(k) is true, that is, k3 – k is divisible by 3.
• We must show that p(k + 1) is true, that is,
(k + 1)3 – (k + 1) is divisible by 3.
(k + 1)3 – (k + 1) = k3 + 3k2 + 3k + 1 – (k + 1) = (k3-k) + 3(k2 + k)
The term (k3 - k) is divisible by 3 by the induction hypothesis, while
the term 3(k2 + k) is clearly divisible by 3 (it is a multiple of 3).
Thus, (k + 1)3 – (k + 1) is divisible by 3.
 14
Template for Proofs by Mathematical Induction
1.Express the statement that is to be proved in the form “for all n ≥ b, P(n)” for a
fixed integer b.
2.Write out the words “Basis Step.” Then show that P(b) is true, taking care that the
correct value of b is used. This completes the first part of the proof.
3.Write out the words “Inductive Step.”
4.State, and clearly identify, the inductive hypothesis, in the form “assume that P(k)
is true for an arbitrary fixed integer k ≥ b.”
5.State what needs to be proved under the assumption that the inductive
hypothesis is true. That is, write out what P(k + 1) says.
6.Prove the statement P(k + 1) making use the assumption P(k). Be sure that your
proof is valid for all integers k with k ≥ b, taking care that the proof works for small
values of k, including k = b.
7.Clearly identify the conclusion of the inductive step, such as by saying “this
completes the inductive step.”
8.After completing the basis step and the inductive step, state the conclusion,
namely that by mathematical induction, P(n) is true for all integers n with n ≥ b.
 15
Strong induction
• In strong induction, for the induction step, we use a
stronger induction hypothesis than (weak) induction.
• To prove p(n) for all n ≥ 1: Instead of assuming p(k),
you can assume the statements, p(1), p(2), …, p(k) to
prove p(k + 1).
• Weak induction and strong induction are equivalent.
• Any proof using weak induction can also be
considered to be a proof by strong induction
• It is sometimes difficult to convert a proof by strong
induction to one that uses weak induction.
 16
Strong induction - Example 1
• Use strong induction to show that if n is an integer
greater than 1, then n can be written as a product of
(one or more) primes.
• Let p(n) be the proposition that n can be written as a
product of primes.
• Base step: p(2) is true (why?)
• Induction hypothesis: Assume p(j) is true for 2 ≤ j ≤ k;
that is, j (2 ≤ j ≤ k) can be written as a product of primes.
 17
Strong induction - Example 1 (cont.)
• Use strong induction to show that if n is an integer greater than 1, then n can be written as a product of (one or more)
primes.
• Let p(n) be the proposition that n can be written as a product of primes.
• Base step: p(2) is true (why?)
• Induction hypothesis: Assume p(j) is true for 2 ≤ j ≤ k;
that is, j (2 ≤ j ≤ k) can be written as a product of primes.

• To complete the proof, we need to show p(k + 1) is true

• (i.e., k + 1 can be written as a product of primes)
• There are two cases: k + 1 is either prime or composite
• If k + 1 is prime, we immediately see that p(k + 1) is true
• If k + 1 is composite then k + 1 = ab for some two positive integers a
and b, with 2 ≤ a ≤ b ≤ k; by the inductive hypothesis, both a and b
can be written as product of primes
• So k + 1 can be written as a product of primes