Rules of Inferences
Section 1.5
Definitions
• Argument: is a sequence of propositions
(premises) that end with a proposition called
conclusion.
• Valid Argument: The conclusion must follow
from the truth of the previous premises, i.e.,
all premises → conclusion
• Fallacy: is an invalid argument or incorrect
reasoning.
• Rules of inference: rules we follow to
construct valid arguments.
Valid Arguments in Propositional Logic
• If we rewrite all premises (propositions)
in any argument using only variables
and logical connectors then we get an
argument form.
• Thus, an argument is valid when its
form is valid.
• Valid argument doesn’t mean the
conclusion is true.
Example
• Argument:
– If you have a password, then you can login to the
network.
– You have a password
– Therefore you can login to the network.
• Argument Form:
p→q
p
---------
∴q
• So it is a valid argument with correct
conclusion
Example
• Argument:
– If x≠0, then x2 > 1
– But ½ ≠0
– Thus ¼ > 1
• Argument Form:
p→q
p
---------
∴q
• So it is a valid argument with wrong
conclusion
Rules of Inference:
correct argument forms
Rule Name Tautology
p
p→q Modus Ponens p ∧(p → q) → q
-----------
∴q
¬q
p→q Modus Tollens ¬q ∧(p → q) → ¬ p
-----------
∴¬p
Rules of Inference:
correct argument forms
Rule Name Tautology
p→q
q→r Hypothetical (p → q) ∧(q → r)
----------- Syllogism → (p → r)
∴p→r
p∨q
¬p Disjunction (p ∨ q) ∧ ¬p → q
----------- Syllogism
∴q
Rules of Inference:
correct argument forms
Rule Name Tautology
p
----------- Addition p →p∨q
∴p∨q
p∧q
----------- Simplification p∧q→p
∴p
Rules of Inference:
correct argument forms
Rule Name Tautology
p
q Conjunction p∧q→p∧q
-----------
∴p∧q
p∨q
¬p ∨ r Resolution (p ∨ q) ∧ (¬p ∨ r) → q ∨ r
-----------
∴q∨r
Examples
• “It’s below freezing and raining now.
Therefore it’s below freezing”
• Argument form:
p∧q
-----------
∴p
• Simplification Rule
Examples
• “If x>1, then 1/x∈(0,1). If x∈(0,1),
then x2< x. Therefore, if x> 1, then
1/x2<1/x.”
• Argument Form:
p→q
q→r
-----------
∴p→r
• Rule: Hypothetical Syllogism
Using Rules of Inference to Build Arguments
Show that the hypotheses
– It’s not sunny this afternoon and it’s colder
than yesterday.
– We will go swimming only if it’s sunny
– If we don’t go swimming, then we will take
a canoe trip.
– If we take a canoe trip, then we will be
home by sunset.
lead to the conclusion “we will be home
by sunset”
Using Rules of Inference to Build Arguments
the hypotheses Hypothesis:
– It’s not sunny this afternoon
and it’s colder than yesterday.
¬s ∧ c
– We will go swimming only if it’s sunny w→s
– If we don’t go swimming, ¬w→t
then we will take a canoe trip.
– If we take a canoe trip,
t→h
then we will be home by sunset.
the conclusion Conclusion: h
“we will be home by sunset”
Using Rules of Inference
¬s ∧ c hypo
¬s simplification
w→s hypo
¬W Modus Tollens
¬w→t hypo
t Modus Ponens
t→h hypo
--------------
∴h Modus Ponens
Using Rules of Inference to Build Arguments
Show that the hypotheses
– If you send me an email message, then I’ll
finish writing the program.
– If you don’t send me an email, then I’ll go
to sleep early.
– If I go to sleep early, then I’ll wake up
feeling refreshed.
lead to the conclusion “if I don’t finish
writing the program then I’ll wake up
feeling refreshed”
Using Rules of Inference to Build Arguments
the hypotheses Hypothesis:
– If you send me an email message,
then I’ll finish writing the program.
s→f
– If you don’t send me an email, ¬s → p
then I’ll go to sleep early. p→w
– If I go to sleep early,
then I’ll wake up feeling refreshed.
the conclusion Conclusion:
“if I don’t finish writing the program ¬f → w
then I’ll wake up feeling refreshed”
s→f hypo
¬f → ¬ s Contrapositive
¬s → p hypo
p→w hypo
-----------
∴ ¬f → w Hypothetical Syllogism
Fallacies
• Incorrect reasoning based on contingencies
and not tautologies.
1. Fallacy of affirming the conclusion:
(p → q) ∧ q → p
• Example: If you solve every problem in this
book, then you’ll pass the course. You did
passed the course. Therefore, you did
solved every problem in this book.
Fallacies
2. Fallacy of denying the hypothesis:
(p → q) ∧ ¬ p → ¬ q
• Example:
• Since you didn’t pass the course, then
you didn’t solve every problem. 9
• Since you didn’t solve every problem,
then you didn’t pass the course. 8
Rules of Inference
for Quantified Statements
• Universal Instantiation:
∀ x p(x)
--------------
∴ p(c)
• Universal Generalization:
p(c) for arbitrary c
-------------------------
∴ ∀ x p(x)
Rules of Inference
for Quantified Statements
• Existential Instantiation:
∃ x p(x)
--------------------------
∴ p(c) for some c
• Existential Generalization:
p(c) for some c
-------------------------
∴ ∃ x p(x)
Combining Rules of Inference
• Universal Modus Ponens:
Universal Instantiation + Modus Ponens
∀ x (P(x) →Q(x))
P(a)
-------------------------
∴ Q(a)
Combining Rules of Inference
• Universal Modus Tollens:
Universal Instantiation + Modus Tollens
∀ x (P(x) →Q(x))
¬ Q(a)
-------------------------
∴ ¬ P(a)