Mathematical Foundations of Computing

Unit 3

RULES OF INFERENCE
& PROOFS

Definitions
 An Argument in propositional logic is a sequence of
propositions.
 All but (except) the final proposition are called premises.
 The final proposition is called conclusion.
 An argument is valid if the truth of all premises implies that
the conclusion is true.
 i.e. (p1  p2  …  pn)  q is a tautology,

where p1 , p2 , … , pn are premises and q is conclusion

 To deduce new statements from statements we use rules of
inference which are templates for constructing valid
arguments.
 Rules of inference are our basic tools for establishing the truth
of statements
 Rules of Inference
 Valid Arguments: assume you are given the following
statements:
 “you are in this class”
 “if you are in this class, you will get a grade”
 Therefore, “You will get a grade”

p
Replacing the propositions by
pq propositional variables,
q changes the argument to
ARGUMENT FORM

( p  (p → q) ) → q

Rule of inference: Modus Ponens

 Consider (p  (p→q)) → q

A truth table can be used to show that an argument

form is valid, by showing that whenever the premises
p are true, the conclusion must also be true (i.e. The
argument is a Tautology).
pq  Instead, we can show that an argument in
q propositional logic is valid by showing that its argument
form is valid.
These simple argument forms are called rules of
inference. They can be used as building blocks to
construct more complicated valid argument forms.
 Modus Ponens example
 Assume you are given the following two statements:
 “you are in this class”
 “if you are in this class, you will get a grade”

What conclusion can be made?

 Let p = “you are in this class”

 Let q = “you will get a grade”

 By Modus Ponens, you can conclude that you will get a

grade

Rule of Inference: Modus Tollens

 Assume that we know: ¬q and p → q what will
the conclusion be ?
 Recall that p → q  ¬q → ¬p (contrapositive of conditional
statement)
 Thus, we know ¬q and ¬q → ¬p
 We can conclude ¬p (using Modus Ponens)

q
pq
p
 Modus Tollens example
 Assume you are given the following two statements:
 “you will not get a grade”
 “if you are in this class, you will get a grade”

What conclusion can be made?

 Let p = “you are in this class”

 Let q = “you will get a grade”

 By Modus Tollens, you can conclude that you are not in

this class

Rules of Inference:
Addition & Simplification
 Addition: If you know that p is true, then p  q will
ALWAYS be true
p
pq

 Simplification: If p  q is true, then p will ALWAYS be

true
pq
p
 Example of Proof (i)
 We have the hypotheses:
1. “It is not sunny this afternoon and it is colder than yesterday”
2. “We will go fishing only if it is sunny”
3. “If we do not go fishing, then we will take a canoe trip”
4. “If we take a canoe trip, then we will be home by sunset”
 Does this imply that “we will be home by sunset”?

SOLUTION
Let:
p = “It is sunny this afternoon”
q = “it is colder than yesterday”
r = “We will go fishing”
s = “we will take a canoe trip”
t = “we will be home by sunset”

(( p  q)  (r  p)  ( r  s)  (s  t))  t ???

Example of Proof (i)

(( p  q)  (r  p)  ( r  s)  (s  t))  t ???

1. ¬p  q 1st hypothesis
2. ¬p Simplification using step 1
3. r→p 2nd hypothesis
4. ¬r Modus tollens using steps 2 & 3
5. ¬r → s 3rd hypothesis
6. s Modus ponens using steps 4 & 5
7. s→t 4th hypothesis
8. t Modus ponens using steps 6 & 7
 More Rules of Inference

 Conjunction: if p and q are true separately, then pq is

true

 Disjunctive syllogism: If pq is true, and p is false,

then q must be true

 Resolution: If pq is true, and ¬pr is true, then qr

must be true

 Hypothetical syllogism: If p→q is true, and q→r is

true, then p→r must be true

Summary: Rules of Inference

p q
Modus ponens pq Modus tollens pq
q p

pq pq
Hypothetical Disjunctive
qr p
syllogism syllogism
pr q

p pq
Addition Simplification
pq p

p pq
Conjunction q Resolution pr
pq qr
 Summary: Rules of Inference

Example of Proof (ii)

 Example
1. “If it does not rain or if it is not foggy, then I will drive to
Riyadh and I will attend the conference”
( r   f)  (d  c)
2. “If I will drive to Riyadh, then the test will be canceled ”
dt
3. “The test was not canceled”
t
 Can you conclude: “It rained (r)?
 Example of Proof (ii)
 ( r   f)  (d  c)
 dt
 t
 r?
1. ¬t 3rd hypothesis
2. d→t 2nd hypothesis
3. ¬d Modus tollens using steps 1 & 2
4. (¬r¬f)→(dc) 1st hypothesis
5. ¬(dc)→¬(¬r¬f) Contrapositive of step 4
6. (¬d¬c)→(rf) DeMorgan’s law and double negation law
7. ¬d¬c Addition from step 3
8. rf Modus ponens using steps 6 & 7
9. r Simplification using step 8

Universal Quantifier Rules of Inference

 Assume that we know that x P(x) is true

 Can we conclude that P(c) is true, where c stands for some

specific constant ?
 YES

 This is called “universal instantiation”

 Assume that we know that P(c) is true for any value of c

 Can we conclude that x P(x) is true ?

 YES

 This is called “universal generalization”

 Existential Quantifier Rules of Inference

 Assume that we know that x P(x) is true

 Can we can conclude that P(c) is true for some value of c ?

 YES

 This is called “existential instantiation”

 Assume that we know that P(c) is true for some value of c

 Can we can conclude that x P(x) is true ?

 YES

 This is called “existential generalization”

Summary_ Rules of Inference for Quantifiers

 Example of Proof (i)

 Given the hypotheses (universe is all people):

 “Mostafa, a student in this class, owns a red car”

 “Everybody who owns a red car has gotten at least one speeding

ticket”
 Can you conclude: “Somebody in this class has gotten a speeding ticket”?
 Let C(x) = “x is a student in this class”
 Let R(x) = “x owns a red car”
 Let T(x) = “x has gotten a speeding ticket”

SOLUTION
C(Mostafa)
R(Mostafa)
x (R(x)→T(x))
???? x (C(x)T(x))

Example of Proof (ii)

C(Mostafa)
R(Mostafa)
x (R(x)→T(x))
x (C(x)T(x)) ???
1. x (R(x)→T(x)) 3rd hypothesis
2. R(Mostafa) → T(Mostafa) Universal instantiation using step 1
3. R(Mostafa) 2nd hypothesis
4. T(Mostafa) Modes ponens using steps 2 & 3
5. C(Mostafa) 1st hypothesis
6. C(Mostafa)  T(Mostafa) Conjunction using steps 4 & 5
7. x (C(x)T(x)) Existential generalization using step 6

Thus, we have shown that “Somebody in this class has

gotten a speeding ticket”
 Example of proof (iii)
 Given the hypotheses (universe is all people):
 “There is someone in this class who has been to Makkah”

 “Everyone who goes to Makkah visits the Haram mosque”

Can you conclude: “Someone in this class has visited the

Haram mosque”?
SOLUTION
Let C(x) = “x is a student in this class”
Let M(x) = “x has been to Makkah”
Let H(x) = “x has visited the Haram mosque”

x (C(x)M(x))
x (M(x)→H(x))
x (C(x)H(x))

x (C(x)M(x))
Example of Proof (iv) x (M(x)→H(x))
x (C(x)H(x))
x (C(x)M(x))  x (M(x)→H(x)) → x (C(x)H(x))

1. x (C(x)M(x)) 1st hypothesis

2. C(y)  M(y) Existential instantiation using step 1
3. M(y) Simplification using step 2
4. C(y) Simplification using step 2
5. x (M(x)→H(x)) 2nd hypothesis
6. M(y) → H(y) Universal instantiation using step 5
7. H(y) Modus ponens using steps 3 & 6
8. C(y)  H(y) Conjunction using steps 4 & 7
9. x (C(x)H(x)) Existential generalization using step 8

Thus, we have shown that “Someone in this class has

visited the Haram mosque”
 Introduction to Proofs
 Terminology:
 Theorem: a statement that can be shown true. Sometimes
called facts.
 Proposition: less important theorem

 Proof: Demonstration that a theorem is true.

 Axiom: A statement that is assumed to be true.
 Lemma: a less important theorem that is useful to prove a
theorem.
 Corollary: a theorem that can be proven directly from a
theorem that has been proved.
 Conjecture: a statement that is being proposed to be a true
statement.

Direct Proofs
 A direct proof shows that a conditional statement p → q is true by
showing that if p is true, then q must also be true, so that the
combination p true and q false never occurs.
 To perform a direct proof of a conditional statement p → q,
assume p is true, and show that q must therefore be true
Example:
 Show that the square of an even number is an even number
 Rephrased: if n is even, then n2 is even
The integer n is even if there exists an integer k such that n = 2k
The integer n is odd if there exists an integer k such that n = 2k + 1

Solution (Proof)
Assume n is even
Thus, n = 2k, for some k (definition of even numbers)
n2 = (2k)2 = 4k2 = 2(2k2)
As n2 is 2 times an integer, n2 is thus even
 Indirect Proofs:
1. Proof by contraposition
 Consider an implication: p→q
 Its contrapositive (¬q → ¬p ) is logically equivalent to the original
implication; i.e. p → q  ¬q → ¬p

 Thus, to perform an indirect proof, show that if ¬q is

true, then ¬p is true

 In other words, to perform an indirect proof, do a

direct proof on the contrapositive

Example
 If n2 is an odd integer then n is an odd integer

 Prove the contrapositive: If n is an even integer,

then n2 is an even integer

 Proof: n=2k for some integer k (definition of even

numbers)
 n2 = (2k)2 = 4k2 = 2(2k2)
 Since n2 is 2 times an integer, it is even

 When do you use a direct proof versus an indirect

proof?
 Example of which to use
 Prove that if n is an integer and n3+5 is odd, then n is even
 Via direct proof
 n +5 = 2k+1 for some integer k (definition of odd numbers)
3

 n = 2k-4
3

 Umm… ???
n  2k  4
3

 Since direct proof didn’t work out.

So: indirect proof (proof by contraposition)
 Contrapositive: If n is odd, then n +5 is even
3

 Assume n is odd, and show that n +5 is even
3

 n=2k+1 for some integer k (definition of odd numbers)

 n +5 = (2k+1) +5;
3 3

 Remember that (A+B) = A + 3A B + 3AB + B

3 3 2 2 3

= 8k +12k +6k+6 = 2(4k +6k +3k+3)

3 2 3 2

As 2(4k3+6k2+3k+3) is 2 times an integer, it is even

Indirect Proofs:
2. Proof by Contradiction

 Proof by contradiction can be used to prove conditional

statements.
 In such proofs, we first assume the negation of the conclusion. We then
use the premises of the theorem and the negation of the conclusion to
arrive at a contradiction.
 (The reason that such proofs are valid rests on the logical
equivalence of p → q  (p ∧￢q) → F.
 To see that these statements are equivalent, simply note that each is
false in exactly one case, namely when p is true and q is false.)
 To make a proof by contradiction of p → q we suppose that both p
and ￢q are true. Then, we show that ￢p is true. This leads to the
contradiction p ∧￢p, completing the proof.
 Proof by Contradiction Example

 Prove that if n3+5 is odd, then n is even

 Rephrased: If n3+5 is odd, then n is even

 Assume p is true and ¬ q is true

 Assume that n3+5 is odd, and n is odd
 n=2k+1 for some integer k (definition of odd numbers)
 n3+5 = (2k+1)3+5 = 8k3+12k2+6k+6 = 2(4k3+6k2+3k+3)
 As 2(4k3+6k2+3k+3) is 2 times an integer, it must be even
 Contradiction! Because both p (n3+5 is odd) and ¬p
are true then we have a contradiction (p /\ ¬p) ≡ F

Vacuous and Trivial Proofs

 Vacuous Proof
 Consider an implication: p→q
 If it can be shown that p is false, then the implication is always
true
 By definition of an implication

 Trivial Proof
 Consider an implication: p→q
 If it can be shown that q is true, then the implication is always
true
 By definition of an implication
 Vacuous Proof Example
 Shown that p is false, then the implication
is always true

 Consider the statement:

 All medical major students in CS103 are male
 Rephrased: If you are a medical major and you are
in CS103, then you are male

 Since there are no medical majors in CS103,

the antecedent is false, and the implication is
true

Trivial Proof Example

 Show that q is true, then the
implication is always true

 Consider the statement:

 If you are tall and are in CS103 then you
are a student

 Since all people in CS103 are students,

the implication is true
 Proofs of Equivalence

 To prove a theorem that is a bi-conditional statement

(of the form p  q), we show that p → q and q → p
are both true.

 The validity of this approach is based on the tautology:

(p  q)  [(p → q)  (q → p)]

Example
Use the proof of equivalence to show that
“If n is a positive integer, then n is odd
if and only if n2 is odd”
Solution

1. This theorem has the form p if and only if q where p

is n is odd and q is n2 is odd

2. To prove this theorem, we need to show that

p →q and q → p are true

3. We have already shown (in previous examples) that

p → q and q → p are true

4. Then the theorem is true

 Counter examples
 To show that a statement of the form x P(x) is false,
we need only find a counterexample, that is, an
example of x for which P(x) is false

 When is counterexample needed?

 If there is a statement of the form x P(x):
 which we believe to be false

 or which has resisted all proof attempts

 Note that this is DISPROVING a UNIVERSAL

statement by a counterexample

Examples
 x ¬R(x), where R(x) means x has red hair
 Find one person (in the domain) who has red hair
 Every positive integer is the square of another
 Square root of 5 is 2.236, which is not an integer

Example
Show (prove) that the statement “every positive
integer is the sum of the squares of two integers”
is false

Solution
1. To show that this statement is false, we look for a
counterexample, which is a particular integer that is
not the sum of the squares of two integers
2. The integer 3 cannot be written as the sum of the
squares of two integers
3. Consequently, we have shown that Every positive
integer is the sum of the squares of two integers is
false