Discrete Mathematics: Lecture 4 - Inference Rules.pdf

discrete math

1. Math211
Discrete Mathematics
Rules of Inference
SAHAR SELIM

2. Agenda
1.6 Rules of Inference
1.6.1 Rules of inference
Modus ponens, addition, simplification, conjunction, modus tollens,
contrapositive, hypothetical syllogism, disjunctive syllogism, resolution,
1.6.2 Proofs with quantifiers
Discrete Mathematics and Its Applications
Kenneth H. Rosen
Sahar Selim MATH211 Lecture 4 | Rules of Inference
2

3. Motivation
“Mathematical proofs, like diamonds, are hard and clear, and
will be touched with nothing but strict reasoning .” -John Locke
Mathematical proofs are, in a sense, the only true knowledge we have
They provide us with a guaranteeas well as an explanation
(and hopefully some insight)
Sahar Selim MATH211 Lecture 4 | Rules of Inference
3

4. Motivation
Mathematical proofs are necessary in CS
You must always (try to) prove that your algorithm
terminates
is sound, complete, optimal
finds optimal solution
You may also want to show that it is more efficient than another method
Proving certain properties of data structures may lead to new, more
efficient or simpler algorithms
Arguments may entail assumptions. You may want to prove that the
assumptions are valid
Sahar Selim MATH211 Lecture 4 | Rules of Inference
4

5. 1.6.1 Rules of Inference
Sahar Selim MATH211 Lecture 4 | Rules of Inference

6. Sahar Selim MATH211 Lecture 4 | Rules of Inference
6

7. Rules of Inference
Inference is deriving conclusionsfrom evidences.
The rules of inferenceare the means used to draw conclusions
from other assertions, and to derive an argument or a proof
An argument is valid
If, whenever all the hypotheses are true,
Then, the conclusion also holds
Sahar Selim MATH211 Lecture 4 | Rules of Inference
7

8. Example
Consider the following argument involving propositions (which, by
definition, is a sequence of propositions):
“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.”
Sahar Selim MATH211 Lecture 4 | Rules of Inference
8

9. Example
Use
p to represent “You have a current password”
q to represent “You can log onto the network”
Then, the argument has the form
p → q
p
∴q
Sahar Selim MATH211 Lecture 4 | Rules of Inference
9

10. Inference Rules -General Form
Inference Rule
Pattern establishing that if we know that a set of hypothesesare all true,
then a certain related conclusion statement is true.
“∴” means “therefore”
Sahar Selim MATH211 Lecture 4 | Rules of Inference
10
Hypothesis 1
Hypothesis 2 …
__________________________
∴conclusion
Premises
Conclusion

11. Inference Rules & Implications
Each logical inference rule corresponds to an implication
that is a tautology.
Corresponding tautology:
((Hypoth. 1) ∧(Hypoth. 2) ∧…) →conclusion
From a sequence of assumptions, p
1, p
2, …, p
n,
you draw the conclusion q.
(p
1∧p
2∧… ∧p
n) →q
Sahar Selim MATH211 Lecture 4 | Rules of Inference
11
p
1
p
2
…
p
n
q
Premises
Conclusion

12. Rules
Sahar Selim MATH211 Lecture 4 | Rules of Inference

13. Contrapositive
The contrapositive is the following tautology
(p →q) →(¬q→¬p)
Usefulness
If you are having trouble proving the p implies q in a direct manner
You can try to prove the contrapositive instead!
Sahar Selim MATH211 Lecture 4 | Rules of Inference
13

14. Modus Ponens
p →q Rule of modus ponens
p (a.k.a. law of detachment)
∴q
In logic terminology, modus ponens is the tautology:
(p ∧(p→q)) →q
Example
“If it snows today, then we will go skiing” and
“It is snowing today” imply“We will go skiing”
“the mode of
affirming”
Sahar Selim MATH211 Lecture 4 | Rules of Inference
14

15. Modus Tollens
p →q
¬q Rule of modus tollens
∴¬p
Similar to the modus ponens, modus tollensis based on the following
tautology
((p→q) ∧¬q) →¬p
Example
“if you are in this class, you will get a grade”
“you will not get a grade”
By Modus Tollens, you can conclude that you are not in this class
“the mode
of denying”
Let p = “you are in this class”
Let q = “you will get a grade”
Sahar Selim MATH211 Lecture 4 | Rules of Inference
15

16. Addition
p Rule of Addition
∴p ∨q
Addition involves the tautology
p →(p ∨q)
Example: “It is below freezing now. Therefore, it is either below
freezing or raining now.”
Sahar Selim MATH211 Lecture 4 | Rules of Inference
16

17. Simplification
p ∧q Rule of Simplification
∴p
Simplification is based on the tautology
(p∧q)→p
(p∧q)→q
Example: “It is below freezing and raining now. Therefore, it is
below freezing now.
Sahar Selim MATH211 Lecture 4 | Rules of Inference
17

18. Conjunction
p Rule of Conjunction
q
∴p ∧q
The conjunction is almost trivially intuitive.
It is based on the following tautology:
((p) ∧(q))→(p∧q)
Sahar Selim MATH211 Lecture 4 | Rules of Inference
18

19. Hypothetical Syllogism
p →q Rule of hypothetical syllogism
q →r
∴p →r
Hypothetical syllogism is based on the following tautology
((p→q) ∧(q→r)) →(p→r)
Example:
If you don’t get a job, you won’t have money
If you don’t have money, you will starve.
Therefore, if you don’t get a job, you’ll starve
Sahar Selim MATH211 Lecture 4 | Rules of Inference
19

20. Disjunctive Syllogism
p ∨q Rule of disjunctive syllogism
¬p
∴q
A disjunctive syllogism is formed on the basis of the tautology
((p∨q)∧¬p)→q
Example
The sky is either blue or grey
Well it isn’t blue
Therefore, the sky is grey
Sahar Selim MATH211 Lecture 4 | Rules of Inference
20

21. Resolution
p∨q Resolution
¬p∨r
∴q ∨r
For resolution, we have the following tautology
((p∨q)∧(¬p∨r)) →(q ∨r)
Essentially,
If we have two true disjunctions that have mutually exclusive propositions
Then we can conclude that the disjunction of the two non- mutually exclusive
propositions is true
Sahar Selim MATH211 Lecture 4 | Rules of Inference
21

22. Rules of Inference
Sahar Selim MATH211 Lecture 4 | Rules of Inference
22

23. Rules of Inference
Sahar Selim MATH211 Lecture 4 | Rules of Inference
23

24. Example 1
Premise: p ^ (p → q)
Conclusion: q
Sahar Selim MATH211 Lecture 4 | Rules of Inference
24
p →q
p____
∴q
modus
ponens
p→q
¬q___
∴¬p
modus tollens
p______
∴p ∨q
Addition
p ∧q
∴p
Simplification
p
q_____
∴p ^ q
Conjunction
p →q
q →r
∴p →r
hypothetical syllogism
p ∨q
¬p___
∴q
disjunctive syllogism
p ∨q
¬p ∨r
∴q ∨r
Resolution

25. Example 1
Premise: p ^ (p → q)
Conclusion: q
1p ^ (p → q)Premise
2p Simplification on 1
∵(p ^ q)
∴ p
3p → q Simplification on 1
4q Modus Ponens on 2 & 3
∵[(p → q) ^ p ]
∴ q
Sahar Selim MATH211 Lecture 4 | Rules of Inference
25
p →q
p____
∴q
modus
ponens
p→q
¬q___
∴¬p
modus tollens
p______
∴p ∨q
Addition
p ∧q
∴p
Simplification
p
q_____
∴p ^ q
Conjunction
p →q
q →r
∴p →r
hypothetical syllogism
p ∨q
¬p___
∴q
disjunctive syllogism
p ∨q
¬p ∨r
∴q ∨r
Resolution

26. Example 2
Assume that the statements below hold:
•(p→q)
•(r→s)
•(r ∨p)
Assume that q is false
Show that s must be true
Premises
(p→q)
(r→s)
(r ∨p)
~q
Conclusion
s
Sahar Selim MATH211 Lecture 4 | Rules of Inference
26

27. Sahar Selim MATH211 Lecture 9 | Mathematical Induction
27
p →q
p____
∴q
modus
ponens
p →q
¬q___
∴¬p
modus tollens
p______
∴p ∨q
Addition
p ∧q
∴p
Simplification
p
q_____
∴p ^ q
Conjunction
p →q
q →r
∴p →r
hypothetical syllogism
p ∨q
¬p___
∴q
disjunctive syllogism
p ∨q
¬p ∨r
∴q ∨r
Resolution
p→q
r→s
r ∨p
¬q
_______
s

28. Example 2
Premises
(p→q)
(r→s)
(r ∨p)
~q
Conclusion
s
1.(p→q)
2.¬q
3.(¬q ∧(p →q)) →¬p
4.(r ∨p)
5.(r ∨p) ∧¬p) →r
6.(r→s)
7.(r∧(r →s)) →s
Premise
Premise
by modus tollenson 1 + 2
Premise
by disjunctive syllogism 3 + 4
Premise
by modus ponens 5 + 6
Sahar Selim MATH211 Lecture 4 | Rules of Inference
28

29. Example 3
Suppose we have the following premises:
“It is not sunny and it is cold.”
“if it is not sunny, we will not swim”
“If we do not swim, then we will canoe.”
“If we canoe, then we will be home early.”
Given these premises, prove the theorem
“We will be home early”using inference rules.
Sahar Selim MATH211 Lecture 4 | Rules of Inference
29

30. Example 3
“It is not sunny and it is cold.”
“if it is not sunny, we will not swim”
“If we do not swim, then we will canoe.”
“If we canoe, then we will be home early.”
Given these premises, prove the
theorem
“We will be home early”using inference
rules.
Sahar Selim MATH211 Lecture 4 | Rules of Inference
30
Let us adopt the following abbreviations:
sunny = “It is sunny”; cold = “It is cold”;
swim = “We will swim”; canoe = “We will canoe”;
early = “We will be home early”.

31. Example 3
“It is not sunny and it is cold.”
“if it is not sunny, we will not swim”
“If we do not swim, then we will canoe.”
“If we canoe, then we will be home early.”
Given these premises, prove the
theorem
“We will be home early”using inference
rules.
Sahar Selim MATH211 Lecture 4 | Rules of Inference
31
Let us adopt the following abbreviations:
sunny = “It is sunny”; cold = “It is cold”;
swim = “We will swim”; canoe = “We will canoe”;
early = “We will be home early”.
Then, the premises can be written as:
(1) ¬sunny∧cold
(2) ¬sunny→¬swim
(3) ¬swim →canoe
(4) canoe →early

32. Sahar Selim MATH211 Lecture 9 | Mathematical Induction
32
p →q
p____
∴q
modus
ponens
p →q
¬q___
∴¬p
modus tollens
p______
∴p ∨q
Addition
p ∧q
∴p
Simplification
p
q_____
∴p ^ q
Conjunction
p →q
q →r
∴p →r
hypothetical syllogism
p ∨q
¬p___
∴q
disjunctive syllogism
p ∨q
¬p ∨r
∴q ∨r
Resolution
¬sunny∧cold
¬sunny→¬swim
¬swim →canoe
canoe →early
________________
early

33. Example 3
Step Proved by
1. ¬sunny∧cold Premise #1.
2. ¬sunny Simplification of 1.
3. ¬sunny→¬swim Premise #2.
4. ¬swim Modus tollenson 2,3.
5. ¬swim→canoe Premise #3.
6. canoe Modus ponens on 4,5.
7. canoe→early Premise #4.
8. early Modus ponens on 6,7.
Sahar Selim MATH211 Lecture 4 | Rules of Inference
33

34. 1.6.2 Rules of Inference for Quantified Statements
Sahar Selim MATH211 Lecture 4 | Rules of Inference

35. Inference Rules for Quantifiers
Rules of inference can be extended in a
straightforward manner to quantified statements
1.Universal Instantiation (UI)
2.Universal Generalization (UG)
3.Existential Instantiation (EI)
4.Existential Generalization (EG)
Sahar Selim MATH211 Lecture 4 | Rules of Inference
35

36. Universal Instantiation (UI)
∀xP(x)
∴P(o)(substitute anyobject o)
Example
All dogs are cute
Oliver is a dog
Therefore, Oliver is cute
Sahar Selim MATH211 Lecture 4 | Rules of Inference
36
UI =
∀????????????????????????(????????????)
∴????????????(????????????)

37. Universal Generalization (UG)
(for ga general element of u.d.)
Example 1:
Oliver is a dog that has 4 legs.
Then,All dogs have 4 legs.
Example 2:
Ahmed is an Egyptian that loves falafel.
Then, ALL Egyptians love falafel
UG =
????????????(????????????)
∴∀????????????????????????(????????????)
Sahar Selim MATH211 Lecture 4 | Rules of Inference
37
We will mainly
focus on valid
cases

38. Inference Rules for Quantifiers
Existential Instantiation (EI)
∃xP(x)
∴P(c) (substitute a newconstantc)
Existential Generalization(EG)
P(o) (substitute any extant object o)
∴∃xP(x)
Sahar Selim MATH211 Lecture 4 | Rules of Inference
38

39. Rules of Inference for Quantified
Statements
Sahar Selim MATH211 Lecture 4 | Rules of Inference
39

40. Example 1
Show that “A car in the garage has an engine problem” and “Every car in the garage has
been sold” imply the conclusion “A car has been sold has an engine problem”
Let
G(x): “x is in the garage”
E(x): “x has an engine problem”
S(x): “x has been sold”
Let UoDbe the set of all cars
The premises are as follows:
∃x (G(x) ∧E(x))
∀x (G(x)→S(x))
The conclusion we want to show is: ∃x (S(x) ∧E(x))
Sahar Selim MATH211 Lecture 4 | Rules of Inference
40

41. Sahar Selim MATH211 Lecture 9 | Mathematical Induction
41
p →q
p____
∴q
modus
ponens
p →q
¬q___
∴¬p
modus tollens
p______
∴p ∨q
Addition
p ∧q
∴p
Simplification
p
q_____
∴p ^ q
Conjunction
p →q
q →r
∴p →r
hypothetical syllogism
p ∨q
¬p___
∴q
disjunctive syllogism
p ∨q
¬p ∨r
∴q ∨r
Resolution
∃x (G(x) ∧E(x))
∀x (G(x)→S(x))
________________
∃x (S(x) ∧E(x))
∀????????????????????????(????????????)
∴????????????(????????????)
Universal
Instantiation
????????????(????????????)
∴∀????????????????????????(????????????)
Universal Generalization
∃????????????????????????(????????????)
∴????????????(????????????)
Existential
Instantiation
????????????(????????????)
∴∃????????????????????????(????????????)
Existential
Generalization

42. Example 1 –Solution
1.∃x (G(x) ∧E(x)) 1
st
premise
2.(G(c)∧E(c)) Existential instantiation of (1)
3.G(c) Simplification of (2)
4.∀x (G(x)→S(x)) 2
nd
premise
5.G(c) →S(c) Universal instantiation of (4)
6.S(c) Modus ponens on (3) and (5)
7.E(c) Simplification from (2)
8.S(c) ∧E(c) Conjunction of (6) and (7)
9.∃x (S(x) ∧E(x)) Existential generalization of (8)
QED
Sahar Selim MATH211 Lecture 4 | Rules of Inference
42

43. Example 2
“Everyone in this discrete math class has taken a course in computer
science” and“Ali is a student in this class” imply“Ali has taken a course in
computer science”
D(x): “x is in discrete math class”
C(x): “x has taken a course in computer science”
∀x(D(x) →C(x))
D(Ali)
∴C(Ali)
Sahar Selim MATH211 Lecture 4 | Rules of Inference
43

44. Sahar Selim MATH211 Lecture 9 | Mathematical Induction
44
p →q
p____
∴q
modus
ponens
p →q
¬q___
∴¬p
modus tollens
p______
∴p ∨q
Addition
p ∧q
∴p
Simplification
p
q_____
∴p ^ q
Conjunction
p →q
q →r
∴p →r
hypothetical syllogism
p ∨q
¬p___
∴q
disjunctive syllogism
p ∨q
¬p ∨r
∴q ∨r
Resolution
∀x (D(x) →C(x))
D(Ali)
________________
∴C(Ali)
∀????????????????????????(????????????)
∴????????????(????????????)
Universal
Instantiation
????????????(????????????)
∴∀????????????????????????(????????????)
Universal Generalization
∃????????????????????????(????????????)
∴????????????(????????????)
Existential
Instantiation
????????????(????????????)
∴∃????????????????????????(????????????)
Existential
Generalization

45. Example 2 –Solution
Step Proved by
1. ∀x(D(x) →C(x)) Premise #1.
2. D(Ali) →C(Ali) Univ. instantiation.
3. D(Ali) Premise #2.
4. C(Ali) Modus ponens on 2,3.
Sahar Selim MATH211 Lecture 4 | Rules of Inference
45

46. Example 3
“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 in this class”
B(x): “x has read the book”
P(x): “x passed the first exam”
Sahar Selim MATH211 Lecture 4 | Rules of Inference
46
∃x (C(x)∧¬B(x))
∀x(C(x) →P(x))
∴∃x(P(x)∧¬B(x))

47. Sahar Selim MATH211 Lecture 9 | Mathematical Induction
47
p →q
p____
∴q
modus
ponens
p →q
¬q___
∴¬p
modus tollens
p______
∴p ∨q
Addition
p ∧q
∴p
Simplification
p
q_____
∴p ^ q
Conjunction
p →q
q →r
∴p →r
hypothetical syllogism
p ∨q
¬p___
∴q
disjunctive syllogism
p ∨q
¬p ∨r
∴q ∨r
Resolution
∃x (C(x) ∧¬B(x))
∀x (C(x) →P(x))
________________
∴∃x(P(x) ∧¬B(x))
∀????????????????????????(????????????)
∴????????????(????????????)
Universal
Instantiation
????????????(????????????)
∴∀????????????????????????(????????????)
Universal Generalization
∃????????????????????????(????????????)
∴????????????(????????????)
Existential
Instantiation
????????????(????????????)
∴∃????????????????????????(????????????)
Existential
Generalization

48. Example 3 –Solution
Step Proved by
1. ∃x(C(x)∧¬B(x)) Premise #1.
2. C(a) ∧¬B(a) Exist. Instantiation of 1.
3. C(a) Simplification on 2.
4. ∀x(C(x) →P(x)) Premise #2.
5. C(a) →P(a) Univ. instantiation of 4.
6. P(a) Modus ponens on 3,5
7. ¬B(a) Simplification on 2
8. P(a) ∧¬B(a) Conjunction on 6,7
9. ∃x(P(x)∧¬B(x)) Exist. Generalization of 8
Sahar Selim MATH211 Lecture 4 | Rules of Inference
48

49. Supplementary Material
Discrete Math -1.6.1 Rules of Inference for Propositional Logic
Discrete Math -1.6.2 Rules of Inference for Quantified
Statements
Sahar Selim MATH211 Lecture 4 | Rules of Inference
49

50. Next Lecture
Introduction to proofs
direct proof, proof by contraposition, proof by contradiction, proof by
cases.
Sahar Selim MATH211 Lecture 4 | Rules of Inference
50

51. Sahar Selim MATH211 Lecture 4 | Rules of Inference

52. Problem 1
The premises
“If you send me an e- mail message, then I will finish writing the program ,”
“If you do not send me an e-mail message, then I will go to sleep early,”
“If I go to sleep early, then I will wake up feeling refreshed”
The conclusion
“If I do not finish writing the program, then I will wake up feeling refreshed .”
Sahar Selim MATH211 Lecture 4 | Rules of Inference
52

53. Solution
Step Reason
1. p → q
2. ￢q →￢p
3. ￢p → r
4. ￢q → r
5. r → s
6. ￢q → s
Premise
Contrapositive of (1)
Premise
Hypothetical syllogism using (2) and (3)
Premise
Hypothetical syllogism using (4) and (5)
Sahar Selim MATH211 Lecture 4 | Rules of Inference
53

54. Problem 2
Is this argument correct or incorrect?
“AllTAs compose easy quizzes. Rana is a TA. Therefore, Rana
composes easy quizzes.”
Sahar Selim MATH211 Lecture 4 | Rules of Inference
54

55. Solution
First, separate the premises from conclusions:
Premise #1: All TAs compose easy quizzes.
Premise #2: Rana is a TA.
Conclusion: Rana composes easy quizzes.
Next, re-render the example in logic notation.
Premise #1: All TAs compose easy quizzes.
Let U.D. = all people
Let T(x) :≡ “xis a TA”
Let E(x) :≡ “xcomposes easy quizzes”
Then Premise #1 says: ∀x, T(x)→E(x)
Sahar Selim MATH211 Lecture 4 | Rules of Inference
55

56. Solution cont…
Premise #2: Rana is a TA.
Let R :≡ Rana
Then Premise #2 says: T(R)
Conclusion says: E(R)
The argument is correct, because it can be reduced to a
sequence of applications of valid inference rules, as follows:
Sahar Selim MATH211 Lecture 4 | Rules of Inference
56

57. The Proof in Detail
Statement How obtained
1.∀x, T(x) → E(x) (Premise #1)
2.T(Rana) → E(Rana) (Universal instantiation)
3.T(Rana) (Premise #2)
4.E(Rana) (Modus Ponensfrom statements #2 and #3)
Sahar Selim MATH211 Lecture 4 | Rules of Inference
57