Discrete Structure

Lecture 4
Class Conducted by
Bibek Ropakheti
Associate Professor : Cosmos College of Management and Technology
Visiting Faculty : NCIT
June 2020
 Chapter 1
Logic, Induction and Reasoning
Chapter Outline
• Proposition and Truth function • Proofs
• Propositional Logic • Informal Proofs
• Formal Proofs
• Expressing statements in Logic
Propositional Logic • Elementary Induction
• The predicate Logic • Complete Induction
• Validity • Consistency and Completeness of
the System
• Informal Deduction in Predicate
Logic
• Rules of Inference
• Methods of Tableaux
Last Class
• The Predicate Logic
• Predicates
• Quantifiers
• Universal Quantifiers
• Existential Quantifiers
• Other Quantifiers
• Quantifiers with restricted domain
• Precedence of Quantifiers
• Logical Equivalences involving Quantifiers
• Negating Quantified Expressions
• Translating From English to Logical Expression
Today’s Class
• Using Quantifiers in System Specifications
• Informal Deduction in Predicate Logic
• Validity
• Rules of Inference
• Methods of Tableaux
Using Quantifiers in System Specifications
• In argument, Premises are used to deduce conclusion
• So we need to start the translation of English expression into
mathematical statements
Using Quantifiers in System Specifications
• Example • Now we can express the given
English Expression statements
• All lions are fierce • ∀𝑥(𝐿 𝑥 → 𝐹 𝑥 )
• Some lions do not drink coffee • ∃𝑥(𝐿 𝑥 ∧ ¬𝐷 𝑥 )
• Some fierce creatures drink coffee • ∃𝑥(𝐹 𝑥 ∧ 𝐷 𝑥 )

Let us assume propositional

functions
• L(x): x is lion
• F(x): x is fierce
• D(x): x drinks coffee
Practice
• Question • ¬∀x(P(x)àI(x)) wrong
• No professor are ignorant • ∀x(P(x)à¬I(x)) for all professor
• All ignorant people are vain being ignorant is false
• Some professor are ignorant
• ¬∃x(P(x)^I(x)) there does not
exist a professor who is ignorant
• Premises
• ∀x ¬(P(x)∧I(x))
• P(x): x is a Professor
• I(x): x is ignorant • ∀x (¬P(x)∨¬I(x))
• V(x): x is vain • ∀x (P(x)à¬I(x))
Practice
• Question • ¬∀x(P(x)àI(x)) wrong
• No professor are ignorant • ∀x(P(x)à¬I(x)) for all professor
• All ignorant people are vain being ignorant is false
• Some professor are ignorant
• ¬∃x(P(x)^I(x)) there does not exist
a professor who is ignorant
• Premises
• P(x): x is a Professor
• ∀x ¬(P(x)∧I(x))
• I(x): x is ignorant • ∀x (¬P(x)∨¬I(x))
• V(x): x is vain • ∀x (P(x)à¬I(x))
• 2. ∀x(I(x)àV(x))
• 3. ∃x (P(x)∧I(x))
Nested Quantifiers
• One quantifier is within the scope of the other
• For example: ∀x ∃y (x+y=0)
• i.e. for all x there exists y that meets the condition that the sum of x and y is
zero
• Everything within the quantifier could be considered as a
propositional function
• For the same: ∀x ∃y (x+y=0)
• Could be expressed as ∀x Q(x)
• Where, Q(x) is ∃y P(x,y)
• Where, P(x,y) is x+y=0
Understanding statements with Nested Quantifiers
• Example:
• Assume the domain of x and y be real numbers, then
• ∀x ∀y (x+y=y+x)
• This statement describes the commutative law for addition of real numbers
• Another example:
• Assume the domain of x, y and z be real numbers, then
• ∀x ∀y ∀z ((x+y)+z=x+(y+z))
• This statement describes the associative law for addition of real numbers
Literals
Statement When True? When False?
∀x ∀y P(x,y) P(x,y) is true for every There is a pair x,y for
∀y ∀x P(x,y) pair x,y which P(x,y) is false
∀x ∃y P(x,y) For every x there is a y for There is an x such that
which P(x,y) is true P(x,y) is false for every y
∃x ∀y P(x,y) There is an x for which For every x there is a y for
P(x,y) is true for every y which P(x,y) is false
∃x ∃y P(x,y) There is a pair x,y for P(x,y) is false for every
∃y ∃x P(x,y) which P(x,y) is true pair x,y
Practice
• Translate into English
• ∀x ∀y ((x>0)∧(y<0)à(xy<0)), where, x and y are real numbers
• ∀x ( hascomputer(x) ∨ ∃y ( hascomputer(y) ∧ friends(x,y) ) )

• Translate into Logical expression

• If a person is female and is a parent, then this person is someone’s mother
• There is a girl in the class who has bought book from every shop in the city
Practice: Answer
• ∀x ∀y ((x>0)∧(y<0)à(xy<0)), where, x and y are real numbers
• For every pair of a positive and a negative number, the product is negative
• ∀x ( hascomputer(x) ∨ ∃y ( hascomputer(y) ∧ friends(x,y) ) )
• For every person, he has a computer or there exist another person who has a
computer and is a friend of the first person
• If a person is female and is a parent, then this person is someone’s
mother
• ∀x (F(x) ∧ P(x) à ∃y M(x,y)) ≡ ∀x ∃y (F(x) ∧ P(x) à M(x,y))
Practice: Answer
• There is a girl in the class who has bought book from every shop in
the city
• ∃g ∀s ∃b ( bought(g, b) ∧ from(b, s))
Informal Deduction in Predicate Logic
• Deduction is used to deduce new knowledge from existing hypothesis
• Argument is a sequence of propositions written
P1
P2
.
.
.
Pn
∴Q
Where, P1, P2 … Pn are hypothesis or premises and Q is the conclusion.
Validity
• Concept of authentication of any mathematical expression is validity
• Refers to the relation between propositions
• Between the set of propositions that serves as premises and the
proposition that serves as conclusion
• If the conclusion follows with logical necessity or sensible reasoning
from its hypothesis then the argument is valid
• Used more in deductive reasoning
Rules of Inference
• We cant use truth table to validated every type of arguments
• So we need to establish the validity of some relatively simple
argument forms, called rules of inference
• These rules of inference will be used to deduce new statements from
the existing ones
• We use rules of Inference to build arguments
Rules of Inference
Rules of Inference Tautology Name
P
PàQ {P∧(PàQ)}àQ MODUS PONENS
∴Q
¬Q
PàQ {¬Q∧(PàQ)}à¬P MODUS TOLLENS
∴¬P
PàQ
QàR {(PàQ)∧(QàR)}à(PàR) HYPOTHETICAL SYLLOGISM
∴PàR
P∨Q
¬P {(P∨Q)∧¬P}àQ DISJUNCTIVE SYLLOGISM
∴Q
Rules of Inference
Rules of Inference Tautology Name
P
Pà(P∨Q) ADDITION
∴P∨Q
P∧Q
(P∧Q)àP SIMPLIFICATION
∴P
P
Q {(P)∧(Q)}à(P∧Q) CONJUNCTION
∴P∧Q
P∨Q
¬P∨R {(P∨Q)∧(¬P∨R)}à(Q∨R) RESOLUTION
∴Q∨R
Example
• Show the hypothesis
• If you send me an email message, then I will finish writing the program
• If you do not send me an email message, then I will go sleep early
• If I go to sleep early, then I will wake up feeling refreshed
• Lead to the conclusion
• If I do not finish writing the program, then I will wake up feeling refreshed
Example: Solution
• Let the Propositions be:
• P: You send me an email message
• Q: I will finish writing the program
• R: I will go to sleep early
• S: I will wake up feeling refreshed
• Then the premises will be
• If you send me an email message, then I will finish writing the program
PàQ
• If you do not send me an email message, then I will go sleep early
¬PàR
• If I go to sleep early, then I will wake up feeling refreshed
RàS
Example: Solution Continues
• Conclusion: Step Reason
• If I do not finish writing the 1. PàQ Hypothesis
program, then I will wake up
2. ¬PàR Hypothesis
feeling refreshed
¬QàS 3. RàS Hypothesis
• Then Contrapositive
4. PàQ≡¬Qà¬P
Equivalent from 1
Hypothetical
5. ¬QàR
Syllogism from 4 & 2
Hypothetical
6. ¬QàS
Syllogism from 5 & 3
Practice
Solve
• If today is Tuesday, I have test in DS or I have OOSE class
• If my DS Instructor is busy, I will not have a test in DS
• Today is Tuesday and my DS Instructor is busy
• Hence, I have OOSE class
Solution
• Propositions Number Step Reason
• T: Today is Tuesday 1. T à (D ∨ O) Hypothesis
• D: I have test in DS 2. B à ¬D Hypothesis
• O: I have OOSE class 3. T∧B Hypothesis
• B: My DS Instructor is Busy 4. T Simplification from 3
• Premises 5. B Simplification from 3
• T à (D ∨ O) Modus Ponens from 5
6. ¬D
&2
• B à ¬D
Modus Ponens from 4
• T∧B 7. (D ∨ O)
and 1
• Conclusion 8. O
Disjunctive Syllogism
•O from 6 and 7
Method of Tableaux
• An analytic tableau is a tree structure computed for a logical formula,
having at each node a sub-formula of the original formula to be proved
or refuted
T∧B

T à (D ∨ O) T B B à ¬D

D∨O ¬D

O (Disjunctive Syllogism)
Exercise
• Pg 64
• Q. 1, 2, 5, 6, 8, 9, 12, 13, 14, 16, 18, 20, 36, 37
• Pg 78
• Q. 3, 4 , 9
Reference Books
• Keneth Rosen, Discrete Mathematical Structures with Applications to
Computer Science, WCB/ McGraw Hill
• G. Birkhoff, T.C. Bartee, Modern Applied Algebra, CBS Publishers.
• R. Johnsonbaugh, Discrete Mathematics, Prentice Hall Inc.
• G.Chartand, B.R.Oller Mann, Applied and Algorithmic Graph Theory,
McGraw Hill
• Joe L. Mott, Abrahan Kandel, and Theodore P. Baker, Discrete
Mathematics for Computer Scientists and Mathematicians, Prentice-
Hall of India
Let us Discuss
Any Issues?
Thank You