The Foundations: Logic
and Proofs
Chapter 2, Part III: Proofs
Rules of Inference
Section Summary
Valid Arguments
Inference Rules for Propositional Logic
Using Rules of Inference to Build Arguments
Rules of Inference for Quantified Statements
Building Arguments for Quantified
Statements
Revisiting the Socrates Example
We have the two premises:
“All men are mortal.”
“Socrates is a man.”
And the conclusion:
“Socrates is mortal.”
How do we get the conclusion from the
premises?
The Argument
We can express the premises (above the line)
and the conclusion (below the line) in
predicate logic as an argument:
We will see shortly that this is a valid
argument.
Valid Arguments
We will show how to construct valid
arguments in two stages; first for
propositional logic and then for predicate
logic. The rules of inference are the
essential building block in the construction
of valid arguments.
1. Propositional Logic
Inference Rules
2. Predicate Logic
Inference rules for propositional logic plus additional
inference rules to handle variables and
quantifiers.
Arguments in Propositional Logic
A argument in propositional logic is a sequence of
propositions. All but the final proposition are called
premises. The last statement is the conclusion.
The argument is valid if the premises imply the conclusion.
An argument form is an argument that is valid no matter
what propositions are substituted into its propositional
If the premises are p1 ,p2, …,pn and the conclusion is q then
variables.
(p1 ∧ p2 ∧ … ∧ pn ) → q is a tautology.
Inference rules are all argument simple argument forms that
will be used to construct more complex argument forms.
Rules of Inference for Propositional Logic:
Modus Ponens
(p ∧ (p →q)) → q
Corresponding Tautology:
Example:
Let p be “It is snowing.”
Let q be “I will study discrete math.”
“If it is snowing, then I will study discrete
math.”
“It is snowing.”
“Therefore , I will study discrete math.”
Modus Tollens
Corresponding
(¬q∧(p →q))→¬p
Tautology:
Example:
Let p be “it is snowing.”
Let q be “I will study discrete math.”
“If it is snowing, then I will study discrete
math.”
“I will not study discrete math.”
“Therefore , it is not snowing.”
Hypothetical Syllogism
((p →q) ∧ (q→r))→(p→ r)
Corresponding Tautology:
Example:
Let p be “it snows.”
Let q be “I will study discrete math.”
Let r be “I will get an A.”
“If it snows, then I will study discrete math.”
“If I study discrete math, I will get an A.”
“Therefore , If it snows, I will get an A.”
Disjunctive Syllogism
Corresponding
(¬p∧(p ∨q))→q
Tautology:
Example:
Let p be “I will study discrete math.”
Let q be “I will study English literature.”
“I will study discrete math or I will study English
literature.”
“I will not study discrete math.”
“Therefore , I will study English literature.”
Addition
p →(p ∨q)
Corresponding Tautology:
Example:
Let p be “I will study discrete math.”
Let q be “I will visit Las Vegas.”
“I will study discrete math.”
“Therefore, I will study discrete math or I will
visit
Las Vegas.”
Simplification
(p∧q) →p
Corresponding Tautology:
Example:
Let p be “I will study discrete math.”
Let q be “I will study English literature.”
“I will study discrete math and English
literature”
“Therefore, I will study discrete math.”
Conjunction
Corresponding
((p) ∧ (q)) →(p ∧ q)
Tautology:
Example:
Let p be “I will study discrete math.”
Let q be “I will study English literature.”
“I will study discrete math.”
“I will study English literature.”
“Therefore, I will study discrete math and I will
study English literature.”
Resolution Resolution plays an important
role in AI and is used in
Prolog.
((¬p ∨ r ) ∧ (p ∨ q)) →(q ∨ r)
Corresponding Tautology:
Example:
Let p be “I will study discrete math.”
Let r be “I will study English literature.”
Let q be “I will study databases.”
“I will not study discrete math or I will study English
literature.”
“I will study discrete math or I will study databases.”
“Therefore, I will study databases or I will study
English literature.”
Using the Rules of Inference to Build Valid
Arguments
A valid argument is a sequence of statements. Each statement
is either a premise or follows from previous statements by
rules of inference. The last statement is called conclusion.
A valid argument takes the following form:
S1
S2
.
.
.
Sn
C
Valid Arguments
Example 1: From the single proposition
Show that q is a conclusion.
Solution:
Valid Arguments
Example 2:
With these hypotheses:
“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.”
Using the inference rules, construct a valid argument for the conclusion:
“We will be home by sunset.”
Solution:
1. Choose propositional variables:
p : “It is sunny this afternoon.” r : “We will go swimming.” t : “We will be
home by sunset.”
q : “It is colder than yesterday.” s : “We will take a canoe trip.”
2. Translation into propositional logic:
Continued on next slide
Valid Arguments
3. Construct the Valid Argument