Logical implication and rules of inference

Logical Implication

 Consider the implication (P1 ∧P2 ∧P3…Pn)

→q where ‘n’ is +ve integer.

 Here the statement P1,P2,...Pn are called

Premises of argument and Statement q is
called conclusion of argument.

 The argument P1 ∧P2 ∧P3…Pn →q is called

Valid is whenever each of Premises P1,....Pn

isTrue and conclusion q is likewise True.
Discrete Mathematical Structures: Theory and Applications 2
  If p,q are arbitary statement such that p→q is a
[Link] we say that P logically implies q
and is denoted by p q

 Let p,q,r denote Primitive Statements

P:Roger studies

q: Roger plays dennis

r: Roger passes DCS.

Discrete Mathematical Structures: Theory and Applications 3
  Let P1,P2,P3......denote Premises
P1: If Roger studies,then he will pass DCS.
P2: If Roger doesn’t plays tennis,then he
will study
P3:Roger fails DCS.

Discrete Mathematical Structures: Theory and Applications 4

  P1:p →r
 P2:¬q →p
 P3:¬r
P1˄p2˄P3=(p →r)˄(¬q →p)˄¬r →q
Using truth table..
(p →r)˄(¬q →p)˄¬r →q is valid argument.

Discrete Mathematical Structures: Theory and Applications 5

 Rules of Inferance

 Rule of inferance are fundamental ,The deep of step by

step validation of how the conclusion q logically follows
from the premises p1,p2,p3,....Pn in an implication of the
form(p1 ˄ p2 ˄ p3 ˄....pn) →q
 Rule P
A premise may be introduced at any point in
derivation.
 Rule T
A formula ‘s’ may be introduced in a derivation if ‘s’
tautologically implied by any one or preceeding
formulas in the derivation.
[Link] of Detatchment
p →q [(p →q) ˄p] →q
P
6
 Law of Syllogism
p →q
q →r
p →r

 Modus tollens Rule of conjunction

p →q p,q
¬q p˄q
¬P
Rule of disjunctive syllogism
p˅q
¬p
q

7
 Rule of contradiction

¬p →F
P

 Rule of conjunctive simlification

p˄q
p
 Rule of Disjunctive Amplification
p
p˅q

8
  Rule Conditional Proof

p˄q

p →(q →r)

 Rule of Proof By Cases

p →r

q →r

(pvq) →r
Discrete Mathematical Structures: Theory and Applications 9
 Rule of constructive Dilemma
p →q

r→s

pvr

qvs
 Rule of Destructive Dilemma
p →q

r→s

¬qv¬s

¬pv¬r

10
  Q1:
P Steps Reason
p →¬q 1) p Premise

¬q →¬r 2) p →¬q ”
¬r 3) ¬q 1,2 Modus Ponnens.

4) ¬q →¬r premise

5) ¬r 3,4 modus
ponnens.

Discrete Mathematical Structures: Theory and Applications 11

  Check whether ‘r’ is valid inferance from the
premises
p →q steps Reason
q →r 1. p →q Premises

p 2. q →r ”
3. p →r (1,2) Laws of Syllogisum
4. p premises
5. r (3,4) Rule of
detachment

Discrete Mathematical Structures: Theory and Applications 12

 Establish the validity of the argument

p →r steps Reason
r→s 1. p →r Premises
t ˅ ¬s 2. r →s ”
¬t˅ u 3. p →s (1,2) Law of syllogism
¬u 4. t ˅ ¬s Premises
5. ¬s ˅t Commutative Law.

6. s →t Subtn (¬s ˅t  s →t )
7. p →t (3,6) Law of Syllogism
8. ¬t ˅u Premises
9. t→u Subtn
10. p→u (7,9) Law of Syllogism
11. ¬u Premises
12. ¬p Modus tollens

13
 H.W
 Q1:
p →r
¬p →q
q→s
¬r →s

14
 Quantifiers
Declarative Sentence is an Open Statement

 If it contains one or more variables

 It is not a statement.
 It becomes a statement when the variables in it
are replaced by certain allowable choices.
Eg:x+2 is an even integer.
The above statement is true only when an even
integer is substituted.
The no. x+2 is an even integer is denoted by p(x).
15
 We use p(x,y) to represent an open statement
that contains two variable.
 The number y+2,x-y,x+2y are even integer.

 The open Statement p(x) & p(x,y) can be

quantified as for some x p(x)
 for some x,y p(x,y).
 Iet p(x) & p(x,y) are true only for few values in
the universe.
 Such quantification is called existential
quantification & is denoted as ᴲx p(x) and ᴲxᴲy
p(x,y).
16
  ᴲx—existential quantifier.

 Let q(x) be the sentence 2x is an even integer

here q(x) can be quantified has ‘for every x q(x)’
or ‘for all x q(x)’ ie for all members in universe
q(x) is true.

 Such quantification is called universal

quantification & is denoted as ˅ x q(x)

 ˅ x=Universal Quantifies.

Discrete Mathematical Structures: Theory and Applications 17

 Free and Bound Variables
 Formula containing a part of the form
Xp(x) or ᴲxp(x) such a part is called ‘x bound part
of formula’
Any variable appearing in x bound part of formula is
called “bound variable”.
 Any formula immediately following x or ᴲx is
called scope of quantifier.
 ˅ x[p(x,y)]-In this statement above x is said to be
bound and scope of x is upto p(x,y) and y is “free
variable”.

Discrete Mathematical Structures: Theory and Applications 18

 Rules for Negating Statement with one
quantifier
1) ¬[˅x p(x)]  ᴲx ¬p(x)
2) ¬[ᴲx p(x)]  ˅x ¬p(x)
3) ¬[ᴲx ¬p(x)]  ˅x p(x)
4) ¬[˅¬ p(x)]  ᴲx p(x)

˅x[p(x) q(x)]  ˅x[¬q(x) ¬p(x)]

Contrapositive
 ˅x[q(x) p(x)]
Converse
19
  ˅x[¬p(x) ¬q(x)]
Inverse

Discrete Mathematical Structures: Theory and Applications 20

 Logical Equivalences
 Two open statements p(x) and q(x) are called
Logically equivalent when p(a) ⇔q(a) is true for
each replacement ‘a’ from the universe.
**it is denoted as ˅[p(x) ⇔q(x)].

 A Statement p(x) is said to be Logically Implies

q(x) when p(a) →q(a) is true for each
replacement ‘a’ in the universe.

Discrete Mathematical Structures: Theory and Applications 21

 Logical Equivalence and Logical
Implication
1) ᴲx[p(x)˄q(x)]
2) [˅x p(x)˅ ˅x q(x)]
3) ᴲx[p(x)˅q(x)] ⇔
4) ˅x[p(x)˄q(x)] ⇔
5) ˅x ¬¬p(x) ⇔
6) ˅x ¬[p(x)˄q(x)] ⇔
7) ˅x ¬[p(x)˅q(x)] ⇔

22
 Write a Stmnt “for all students are clever”

Some Students are not Successful

Some Students are clever and successful.

Every clever students are successful.

Discrete Mathematical Structures: Theory and Applications 23

 Negate and Simplify the quantified stmnt
ᴲx[[p(x)˅q(x)] →r(x)]

˅x ᴲy{[p(x,y)˄q(x,y)] →r(x,y)}

Discrete Mathematical Structures: Theory and Applications 24

 Sentence Meaning
1) ˅x p(x) All true
2)ᴲx p(x) atleast one true
3)¬[ᴲx p(x)] None True
4)˅ x[¬p(x)] All false
5) ᴲx[¬p(x)] at least one false
6)¬[ᴲx (¬p(x)] None false
7)¬[˅x p(x)] Not all true
8)¬[˅x ¬p(x)] Not all false

Discrete Mathematical Structures: Theory and Applications 25

 Rule of Universal Specification

If an open stmnt becomes true ,for all

replacement by the members in the given
universe then that open stmnt is [Link]
each specific individual member in that
universe.
Ie, if p(x) is an open stmnt for a given
universe and if ˅x p(x) is true,then p(a) is
true for each ‘a’ in the universe.

Discrete Mathematical Structures: Theory and Applications 26

 Rule of Universal generalisation
If an open stmnt p(x) is proved to be true.
When x is replaced by an arbitarly,chosen
element ‘c’ from the universe,then
universaly quantified stmnt ˅x p(x) is true.
• The rule extends beyond a single variable.
If an open stmnt q(x,y) is proved to be
True when x and y are replaced by some
choice elements from the same universe
then universly quantified stmnt ˅x ˅y
q(x,y) is true.
27
Consider the open stmnts m(x),c(x)
M(x): x is mathematics professor
C(x): x has studied calculus.
All mathematics professors has studied
calculus
Leena is a mathematics Professor

Therefore leena has studied calculus

28
 ˅x[m(x) c(x)]
m(l)
c(l)

Discrete Mathematical Structures: Theory and Applications 29

 Steps Reason
˅x[m(x) →c(x)] Premise
m(l) →c(l) 1,U.S
m(l) Premise
C(l) 2,3 Modus Ponnens

Discrete Mathematical Structures: Theory and Applications 30

 P(t) be an open stmnt, ‘t’ has two sides of
equal length
q(t):t is an Isosceles
r(t): t has 2 angles of equal measure.
1) In a xyz There is no pair of angles of
equal measure
2)If a has two sides of equal length,Then
it is isosceles
3)If a is isosceles then it has two angles
of equal measure

Discrete Mathematical Structures: Theory and Applications 31

 Therefore xyz has no 2 sides of equal
length.

Discrete Mathematical Structures: Theory and Applications 32

 ¬r(x)
˅x[p(t) →q(t)]
˅x[q(t) →r(t)]
¬p(x)

Discrete Mathematical Structures: Theory and Applications 33

 Steps Reason
1)˅x[p(t) →q(t)] Premise
2)P(x) →q(x) 1,U.S
3)˅x[q(t) →r(t)] Premise
4)q(x) →r(s) 3,U.S
5)P(x) →r(s) 2,4 Law of Syllogism
6)¬r(x) Premise
7)¬p(x) 5,6 modus tolens.

Discrete Mathematical Structures: Theory and Applications 34

 J(x): x is a junior
S(x): x is a senior
P(x): x is entrolled in physical education
class
1) No junior/senior is entrolled in
[Link].
2) Mary is entrolled in a [Link].
3)Therefore mary is not a senior.
Discrete Mathematical Structures: Theory and Applications 35
 ˅x[j(x)˅s(x) →¬p(x)]
P(m)
¬(s(m))

Discrete Mathematical Structures: Theory and Applications 36

 Steps Reason
1) ˅x[j(x)˅s(x) →¬p(x)] Premise
2)j(m)˅s(m) →¬p(m) 1,Rule of U.S
3)p(m)→¬(j(m)˅s(m)) 2,Contrapositive
4)p(m) Premise
5)¬(j(m)˅s(m)) 3,4 modus ponnens
6)¬(j(m))˄¬s(m) 5, Demorgans
7)¬s(m) 6,Rule of [Link]

Discrete Mathematical Structures: Theory and Applications 37

 ˅x ˅y[p(x,y) →w(x,y)]
¬w(a,b)
¬p(a,b)

˅x[p(x) →q(x)]
˅x[q(x) →r(x)]

˅x[p(x) →r(x)]

Discrete Mathematical Structures: Theory and Applications 38

 Let n be an integer,we call ‘n’ even if ‘n’ is
divisible by 2
ie if there exists an integer ‘r’ so that n=2r
If ‘n’ is not even, Then we call ‘n’ odd .
for this case , there exists an integer ‘s’
where
n=2s+1..

Discrete Mathematical Structures: Theory and Applications 39

 Theorem-1

For all integers k&L if (K,L) are both odd

then K+L=even.

40
 Theorem-2

For all integer K&L if K,L are odd and the

product (KL) is odd.

41
 Theorem-3

If ‘m’ is an even integer then m+7 is odd.

Contradiction method
M+7 is even then m is odd integer.

Discrete Mathematical Structures: Theory and Applications 42

 Prove that if ‘n’ is [Link] n2 is odd

Discrete Mathematical Structures: Theory and Applications 43

 Theorem-4

For all +ve real number x&y the pdt xy

exceeds 25 then x>5 or y>5.

Discrete Mathematical Structures: Theory and Applications 44

 Consider negation of the conclusion
0<x<=5 , 0<y<=5

0<xy<=5*5
0<xy<=25

Discrete Mathematical Structures: Theory and Applications 45