Discrete Mathematical Structures - Fundamentals of Logic - Principle of duality

Discrete Mathematical Structures
Fundamentals of Logic
Principle of Duality

1. PRINCIPLE OF DUALITY
By,
Lakshmi R
Asst. professor,
Dept. of ISE

2. PRINCIPLE OF DUALITY
Duality:
Letsbeastatement.IfScontainsnologicalconnectivesotherthan∧and∨,
thendualofsisdenoteds
d
,isthestatementobtainedfromsbyreplacingeach
occurrenceof∧and∨by∨and∧,respectively,andeachoccurrenceofTandF
byFandT,respectively.
Lakshmi R, Asst. Professor, Dept. Of ISE
(p ∧q) ∧(r ∨s ∧T) ∨F
(p q) (r s F) T∨∨ ∨ ∧∧
s=
s
d
=

3. PRINCIPLE OF DUALITY
Let sand t be statements that contain no logical
connectives other than ∧and ∨. If s ⇔t, thens
d
⇔t
d
Lakshmi R, Asst. Professor, Dept. Of ISE

4. Write duals for the following propositions.
1.( p →q) →r
2.p→( q →r)
Solution:
Lakshmi R, Asst. Professor, Dept. Of ISE
1.( ( p →q) →r)
d
⇔( (¬ p ∨q) →r)
d
⇔(¬ (¬ p ∨q) ∨r)
d
⇔((p ∧¬ q ) ∨r)
d
=(p ∨¬ q) ∧r
2.( p →(q →r))
d
⇔(p →(¬ q ∨r) )
d
⇔(¬ p ∨(¬ q ∨r) )
d
=¬ p ∧(¬ q ∧r)
Steps:
1.Write the given proposition in
terms of logical ∧and ∨by
using known equivalences
2.Replace all ∧and ∨by ∨
and ∧
1.( ( p →q) →r)
d
=(p ∨¬ q) ∧r
2.( p →(q →r))
d
=¬ p ∧(¬ q ∧r)

5. 2. Verify the principle of duality for the following equivalence
1.[ (¬ (p ∧q) → ¬ p ) ∨(¬ p ∨q ) ] ⇔(¬ p ∨q )
Solution:
Let s = [ (¬ (p ∧q) → ¬ p ) ∨(¬ p ∨q ) ]
and
t = (¬ p ∨q )
We need to prove that
s
d
⇔t
d
Lakshmi R, Asst. Professor, Dept. Of ISE

6. s = [ (¬ (p ∧q) →¬ p ) ∨(¬ p ∨q ) ]
s = [ (¬ ¬ (p ∧q) ∨¬ p ) ∨(¬ p ∨q ) ]
s = [ ((p ∧q) ∨¬ p ) ∨(¬ p ∨q ) ]
s = [ (p ∧q) ∨¬ p ∨¬ p ∨q ]
s
d
= [ (p ∨q) ∧¬ p ∧¬ p ∧q ]
⇔[(p ∨q) ∧¬ p ∧q ] -----Idempotent Law
⇔[q ∧(q ∨p) ∧¬ p ] -----Associative Law
⇔[q ∧¬ p ] -----Absorption Law
⇔[¬ p ∧q] -----Commutative Law
⇔t
d
-----By eq(1)
Lakshmi R, Asst. Professor, Dept. Of ISE
t = (¬ p ∨q )
t
d
= (¬ p ∧q ) -----eq(1)