Proofs
CSCI 170 Fall 2019 Lecture 8
Sandra Batista
1.1–1.2












































Proofs
• Constructive Proof
• Non-constructive Proof
• Proof by Cases
• Direct Proof of Implication
• Proof by Contraposition
• Proof by Contradiction
• Disprove a statement
1.1–1.2












































3Proof Method: Constructive Proof
A constructive proof is one that proves that a solution or property exists
by giving the solution or instance of the property directly.
Claim: Every 8x8 checkerboard can be tiled by dominos, 2x1 rectangular tiles with
a 1 dot in the first square and 2 dots in the second. The tiles of the domino are the
same size as each square of the checkerboard.












































4Constructive Proof Example 1
Claim: Every 8x8 checkerboard can be tiled by dominos, 2x1 rectangular tiles with a 1 dot in the first square and 2 dots
in the second. The tiles of the domino are the same size as each square of the checkerboard.
Proof: Give an algorithm to tile the checkerboard.












































Chi 4,21 KY 7,81 8,8
for Iai x sixttTE
e
for ly liyc.si HAE
Ifl y 2 1
Eplaceldominoso
place in Xi
l
zyatthid
in y
z 8,1 8181
Proofs
• Constructive Proof
• Non-constructive Proof
• Proof by Cases
• Direct Proof of Implication
• Proof by Contraposition
• Proof by Contradiction
• Disprove a statement
1.1–1.2












































6Proof Method: Non-constructive Proof
A non-constructive proof is when a proof shows that a solution exists
without giving the solution directly.
Claim: At a dinner with 9 guests at least 2 must have been born on the same day
of the week.
Proof: PHP












































let A be guests 13 be daysof
week
f A 7 B f person day of foreenk
Since IAI 9 7 1131 7 by PHP
at least 2 guest born on someweekday
Proofs
• Constructive Proof
• Non-constructive Proof
• Proof by Cases
• Direct Proof of Implication
• Proof by Contraposition
• Proof by Contradiction
• Disprove a statement
1.1–1.2












































8Useful Refresher
1. If an integer n is odd, then there exists an integer k such that n = 2k +1. If an integer n is
even, then there exists an integer k such that n = 2k.
2. If n is a rational, then there exists integers p and q that share no prime factors and q is non-
zero such that n = p/q.
3. An integer d evenly divides an integer n if it is a factor. Similarly the remainder when we
divide n by d is 0. We also say that n is divisible by d.
4. If n = mk + r and we divide n by m, we will be left with a remainder of r: n mod m = r
5. All even numbers are 0 mod 2. All odd numbers are 1 mod 2. Whether an integer is even or
odd is referred to as its parity.












































n dk for some
KEZ
9Proof Method: Proof by Cases
A proof by cases is when a proof of a claim exhaustively considers all
cases that are possible for the claim and shows that the claim would still
hold under all such cases.
Cases are often mutually exclusive.
Claim: Among any three integers there are two whose sum is even.
Proof: .












































let A be three integers 13 20,13
f A B fca x mod 2
Since I A1 3 IBI 2 by PHP
at least 2 have same parity
10
Proof Method: Proof by Cases
A proof by cases is when a proof of a claim exhaustively considers all
cases that are possible for the claim and shows that the claim would still
hold under all such cases.
Cases are often mutually exclusive.
Claim: Among any three integers there are two whose sum is even.
Proof (continued): .












































It sat 3integers S F subset
AES IA1 2
case I Both even x
214 y 2kg K kz
EZ
Xty 2 kit 2K z 21 kit ka mod 2
0
even
case 2
both odd X 2 Kitt Y 3Kat k lqE2
Xt y 2k t l t 2Kat1 2114tkzH
mod 2 0
also even
Proofs
• Constructive Proof
• Non-constructive Proof
• Proof by Cases
• Direct Proof of Implication
• Proof by Contraposition
• Proof by Contradiction
• Disprove a statement
1.1–1.2












































12
Proof Method: Direct Proof of an Implication
In a direct proof of implication we assume the premise P and use logic and
rules of inference to show that the conclusion Q follows.
Exercise: Let n be an integer. If n is odd, then n2 is odd.
Proof:












































Assume his odd f KEZ h 2kt I
Consider n2 12kt
2 4k't 4kt I
212k't2141 1
Since 2k't 2K C Z so NZ is odd
Proofs
• Constructive Proof
• Non-constructive Proof
• Proof by Cases
• Direct Proof of Implication
• Proof by Contraposition
• Proof by Contradiction
• Disprove a statement
1.1–1.2












































14
Proof Method: Proof by Contraposition
The contrapositive of P implies Q is not Q implies not P.
In a proof by contraposition of an implication P implies Q, we assume the
negation of the conclusion, i.e. not Q, and use logic and rules of inference to
show that the negation of the premise, i.e. not P, follows.
State the contrapositive and prove it directly.
Exercise: Let n be an integer. If n2 is odd, then n is odd.
Proof by Contraposition:
State the contrapositive and prove it directly.












































p q 7 of 77 p
p 8
If n is even then h2 is even
15
Proof by Contraposition Example
Exercise: Let n be an integer. If n2 is odd, then n is odd.
Proof by Contraposition:












































78
Assume his even F KE Z
n 2K
Consider n
2 12142 442 21219
single'EL h2 is even
p
16
Proof Method: Proof by Contraposition
The contrapositive of P implies Q is not Q implies not P.
In a proof by contraposition of an implication P implies Q, we assume the
negation of the conclusion, i.e. not Q, and use logic and rules of inference to
show that the negation of the premise, i.e. not P, follows.
State the contrapositive and prove it directly.
Exercise: Let y not equal 0. If x/y is irrational, then either x is irrational or y is
irrational.
Proof by contraposition:
State the contrapositive and proof it directly.












































let x YER p Of
H x is rational and y is rational
is rational
17
Proof by Contraposition Example
Exercise: Let y not equal 0. If x/y is irrational, then either x is irrational or y is irrational.
Proof by contraposition:












































Assume 7g Assume is rational and
y is rational F p g e 2 g to x Pig and
F P2,952 pit 0 go o y If
Consider Pgtp2 pga peg
EZ 139 O
E is rational Tp
Proofs
• Constructive Proof
• Non-constructive Proof
• Proof by Cases
• Direct Proof of Implication
• Proof by Contraposition
• Proof by Contradiction
• Disprove a statement
1.1–1.2












































19
Proof Method: Proof by Contradiction
To prove a statement by contradiction: Negate the statement and show any
contradiction.
Template for an implication: P implies Q
1)This implication is logically equivalent to not P or Q
2)Assume the negation:
3)Show any contradiction. When we show a contradiction occurs, we show that
the negation is false, so the original statement is true.
p q p q→ ≡¬ ∨
( )p q p q¬ ¬ ∨ ≡ ∧¬












































20
Proof by Contradiction Example
Exercise: Prove the following by contradiction: n3 is not O(n2 )
Proof by contradiction:
Assume












































n340 n
negation Assume h3E 01h2 F no e 0
for all n Ino OE n'sE Cn
for all n Zuo OE n E e
let n MaxEnotictis n't SC
a contradiction so n 4064
21
Proof by Contradiction Example
Exercise: If 15x + 111y = 55057 for real numbers x and y, then either x is not an integer or y is not an integer.
Proof by contradiction:
Assume












































p a
p n of Assume 15kt My 55057 x y
EIR
and X is integer and y is integer
Consider 154 t My 3 5 1 37 y 55057
5 37 y55035751 37 y Eh but 5 0357 Z
contradiction
22
Proof by Contradiction Example 2
Exercise: Show square root of 5 is irrational.
Proof by contradiction:












































Assume negation Ms is rational
NB Pq for some Piof
E Z f FO PigShane
no common factors
As Pq 5 Pff
5of p2
5 divides P2
5 divides p
p 5C CEL
23
Proof by Contradiction Example 2
Exercise: Show square root of 5 is irrational.
Proof by contradiction (continued):












































5g p
2
Gq 2 642
of
2 5 a
5 divides q2 5dividesof
However
5 divides both p and g
This is
a contradiction because pana of
share no primefactors
24
Proof by Contradiction Example 2
Exercise: Show square root of 12 is irrational.
Proof by contradiction:












































Assume negation Assume NE isrational
V12 Pq pig
C Z f to p g share no
12 Pq 12q2 pz
Prime factors
2 3q2 p2 forsoft2
the Carynfee
2 divides p p 2C
3 divides p p 3 c
25
Proof by Contradiction Example 2
Exercise: Show square root of 12 is irrational.
Proof by contradiction (continued):













i p 2C
3g
s ginsine
223 q2 1242 o is divisible
ca
l by3
Ii let p 3C for some CEZ
223 q2 1342
22q2 38
Since 3 doesnot divide 2 then
3 divides of
p of share no prime
factors
Proofs
• Constructive Proof
• Non-constructive Proof
• Proof by Cases
• Direct Proof of Implication
• Proof by Contraposition
• Proof by Contradiction
• Disprove a statement
1.1–1.2
27
Proof Method: Disprove a statement
A statement is true or its negation is true.
To disprove a statement, prove that its negation is true.
Disprove the statement: All primes are odd.
Write the statement in predicate logic and its negation. Let the predicate P(x) be “x is prime”.
Why would a counterexample suffice?
tf x c Z Pay Of
01 1 x is prime
nesaytimj.az Pan m Oki at
counterexample X 2
28
Disprove a Statement Example
Disprove: Let x, y, and z be integers. There exists x and y such that for any z, x+y = z.
Write the statement in predicate logic and its negation. Why isn’t a single counterexample enough?
Fx Fy Hz Xty 2
negation
Fx Hy F z Xtytz
Kitty let z XtyH
29
Disprove a Statement Example
Disprove: Let x, y, and z be integers. There exists a z for any x and y such that x+y = z.
Write the statement in predicate logic and its negation. Then prove that the negation is true.
Proofs
• Constructive Proof
• Non-constructive Proof
• Proof by Cases
• Direct Proof of Implication
• Proof by Contraposition
• Proof by Contradiction
• Disprove a statement
1.1–1.2