1 2 3 4 .... 1  1  1  1  1 .........  ?

1 2  3 4 ....
Discrete mathematics

The
Foundations:
 x    y  ( x  y )
Logic and

x( | x )

1
Proofs
 x 1  ?
x

 x 1 x ?

RIZOAN TOUFIQ
ASSISTANT PROFESSOR
DEPARTMENT OF COMPUTER SCIENCE & ENGINEERING
RAJSHAHI UNIVERSITY OF ENGINEERING & TECHNOLOGY
Rules of Inference

Section 1.6
 Section Summary

 Valid Arguments
 Inference Rules for Propositional Logic
 Using Rules of Inference to Build Arguments
– Resolution
– Fallacies
 Rules of Inference for Quantified Statements
 Combining Rules of Inference for Propositions and Quantified
Statements
 Valid Arguments in
Propositional Logic
 We have the two premises:
– “If you have a current password, then you can log onto the
network.”
– “You have a current password.”
 And the conclusion:
– “You can log onto the network.”
 How do we get the conclusion from the premises?
 Valid Arguments in
Propositional Logic
 Use p to represent “You have a current password” and q to
represent “You can log onto the network.” Then, the argument has
the form

TRUE

 Where ∴ is the symbol that denotes “therefore.”

Q: The statement
((p → q) ∧ p) → q
is a tautology?
 Valid Arguments in
Propositional Logic

p q p→q (p → q) ∧ p ((p → q) ∧ p) → q
0 0 1 0 1
0 1 1 0 1
1 0 0 0 1
1 1 1 1 1

PROVED

We say this form of argument is valid because

Whenever all its premises are true,
The conclusion must also be true.
 Valid Arguments in
Propositional Logic
 p is true, but p → q is false

 The argument we obtained is a valid argument, but because one of

the premises, namely the first premise, is false, we cannot conclude
that the conclusion is true.
 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 variables.
 If the premises are p1 ,p2, …,pn and the conclusion is q then
(p1 ∧ p2 ∧ … ∧ pn ) → q is a tautology.
 Inference rules are all simple argument forms that will be used to
construct more complex argument forms.
 Rules of Inference for
Propositional Logic
Modus Ponens

Corresponding Tautology:
(p ∧ (p →q)) → q
Example:
Let p be “It is snowing.”
Let q be “I will study discrete math.”

“It is snowing.”
“If it is snowing, then I will study discrete math.”

Therefore , “I will study discrete math.”

 Rules of Inference for
Propositional Logic
Modus Tollens

Corresponding Tautology:
(¬q∧(p →q))→¬p

Example:
Let p be “it is snowing.”
Let q be “I will study discrete math.”

“I will not study discrete math.”

“If it is snowing, then I will study discrete math.”

Therefore , “ it is not snowing.”

 Rules of Inference for
Propositional Logic

Hypothetical Syllogism

Corresponding Tautology:
((p →q) ∧ (q→r))→(p→ r)

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.”

 Rules of Inference for
Propositional Logic

Disjunctive Syllogism

Corresponding Tautology:
(¬p∧(p ∨q))→q

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.”

 Rules of Inference for
Propositional Logic

Addition
Corresponding Tautology:
p →(p ∨q)

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.”

 Rules of Inference for
Propositional Logic
Simplification

Corresponding Tautology:
(p∧q) →p

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.”

 Rules of Inference for
Propositional Logic
Conjunction

Corresponding Tautology:
((p) ∧ (q)) →(p ∧ q)

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.”
Rules of Inference for
Propositional Logic
Rules of Inference for
Propositional Logic
 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
 Using the Rules of Inference to
Build Valid Arguments
Example 1: From the single proposition

Show that q is a conclusion.

Solution:
 Using the Rules of Inference to
Build Valid Arguments
Example 2:
 With these hypotheses/premises:
“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.”
q : “It is colder than yesterday.”
r : “We will go swimming.”
s : “We will take a canoe trip.”
t : “We will be home by sunset.”
 Using the Rules of Inference to
Build Valid Arguments
Example 2:
 With these hypotheses/premises:
“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.”

2. Translation into propositional logic:

 Using the Rules of Inference to
Build Valid Arguments
Example 2:
 With these hypotheses/premises:
“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.”
3. Construct the Valid Argument
 Resolution

Resolution
Corresponding Tautology:
((¬p ∨ r ) ∧ (p ∨ q)) →(q ∨ r)
*Resolution plays an important role in
AI and is used in Prolog.

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.”
 Fallacies
 Several common fallacies arise in incorrect arguments.
 The proposition ((p → q) ∧ q) → p is not a tautology, because it is false when p is
false and q is true.
 Example: Is the following argument valid?
• If you do every problem in this book, then you will learn discrete
mathematics.
• You learned discrete mathematics.
• Therefore, you did every problem in this book.
 p: you do every problem in this book
 q: you will learn discrete mathematics
 r: you did every problem in this book.(conclusion)
p  q
q

 p

 This type of incorrect reasoning is called the fallacy of affirming the conclusion.
 Fallacies

 The proposition ((p → q) ∧¬p) →¬q is not a tautology, because it is false when p is
false and q is true.
 Example: Is the following argument valid?
• If you do every problem in this book, then you will learn discrete
mathematics.
• you did not do every problem in this book.
• Therefore, You did not learned discrete mathematics.
p  q
p

 q

 This type of incorrect reasoning is called the fallacy of denying the hypothesis.
Rules of Inference for
Quantified Statements
 Universal Instantiation (UI)

Example:

Our domain consists of all dogs and Fido is a dog.

“All dogs are cuddly.”

“Therefore, Fido is cuddly.”

Universal Generalization (UG)

Used often implicitly in Mathematical Proofs.

 Existential Instantiation (EI)

Example:

“There is someone who got an A in the course.”

“Let’s call her a and say that a got an A”
Existential Generalization (EG)

Example:

“Michelle got an A in the class.”

“Therefore, someone got an A in the class.”
 Rules of Inference for
Quantified Statements
Example 1: Given premises:
“Every man has two legs.”
“John Smith is a man.”
Using the rules of inference, construct a valid argument to show that
“John Smith has two legs”
Solution: Let
M(x) denote “x is a man”
L(x) “ x has two legs”
John Smith be a member of the domain.
Valid Argument:
 Rules of Inference for
Quantified Statements
Example 2: Use the rules of inference to construct a valid argument
showing that the conclusion
“Someone who passed the first exam has not read the book.”
follows from the premises
“A student in this class has not read the book.”
“Everyone in this class passed the first exam.”

Home Task
 Universal Modus Ponens

Universal Modus Ponens combines universal instantiation and

modus ponens into one rule.
 Universal Modus Tollens

Universal Modus Ponens combines universal instantiation and

modus tollens into one rule.
 Query???

1 2 3 4 ....
 x    y  ( x  y )  ?

  1
 x 1 x ?
 x 1  ?
x

 x( | x )  ?  x    y  ( x  y )  ?

 1
1 2 3 4 .... ?
 x 1  ?
1  1  1  1  1 .........  ? x