Discrete Mathematical

Structures
( CS330 )
S Brunda,
Assistant Professor,
CS&E,
SJCE, Mysuru
1
 Course Outcomes
CO1 : Knowledge of the concepts needed to test the
logic of the program.
CO2 : Demonstrate the understanding of relations and
able to determine the properties.
CO3 : Perceive, construct and decode group codes
based on the various methods.
CO4 : Demonstrate different traversal methods for
trees and graphs.

2
 Course Contents
Unit Course Content No. of
No. Hours
1. 08
Fundamental of Logic: Basic Connectives and Truth Tables, Logical
Equivalence: The Laws of Logic, Logical Implication: Rules of
Inference, The Use of Quantifiers, Quantifiers, Definitions and the
Proofs of Theorems.
2. 08
Relations: Properties of relations, Computer Recognition: Zeros- One
Matrices and Directed Graphs, Partial; orders: Hasse diagrams ,
Equivalence Relations and Partitions , Lattices.
3 08
Elements of coding theory and Hamming Metric, generation of codes
using Parity check and Generator matrices.
4. 08
Graph theory: Definitions and Examples, Subgraphs, Complements,
and Graph Isomorphism, Vertex degree, Euler trail and circuits, Planar
Graphs, Hamiltonian Paths and cycles.
5.
Trees: Definitions, Properties and Examples, Rooted trees, trees and
sorting weighted trees and prefix Codes.
07

3
 Text and Reference Books
Text Book:
1. Ralph.P.Grimaldi, B.V.Ramana, “Discrete and Combinatorial Mathematics”,

5th Edition, Pearson Education -2009.

Reference Books:
1. Kenneth. H.Rosen, “Discrete Mathematical Structures Theory and
Application”, V Edition, PHI/Pearson, Education, 2004.

2. Kolman, Busby and Ross, “Discrete Mathematical Structures”, Fourth Edition,

Prentice –Hall of India Pvt Ltd-2009.

4
 What is Discrete Mathematics?
Discrete mathematics is a study of discrete
structures which are abstract mathematical models
that deals with discrete objects and their
relationships.

5
 Applications of Discrete Mathematics

• Checking the correctness of a program

• Computer Networks
• Operating System
• Finite Automata
• Artificial Intelligence
• Algorithm Design etc.,

6
 Unit – 1

Fundamentals of Logic

7
 What is Logic ?
• Logic deals with the methods of reasoning
• Logic is extremely useful in decision making
problems
• Logic theory forms the basics for Artificial
intelligence, Fuzzy logic, Expert Systems etc.,

8
 Propositions
• A proposition is a statement or sentence that
can be determined to be either true or false
(but no both).
• Examples:
– The only positive integers that divide 7 are 1
and 7 itself. (True)
– Everybody likes chocolate.(False)
– It is raining outside (True or False)

9
 Continued…
Not all sentences are proposition
Eg.,
❖ x + 3 > 7 /* we cannot decide whether True or False
unless we know the value of x */
❖ Give your book /* It’s a sentence but not statement ,
hence its not a proposition */
❖ What a beautiful garden ! /* exclamation and
commands are sentences but not statements */

10
 Example
• Use variable(p, q, r..) to represent propositions

• p: 1+1=3
• q: It is raining outside
• r: Today is Tuesday
The statements represented by p, q, r are considered to be primitive
statements because they cannot be broken down into anything
simpler

11
 Connectives
If p and q are propositions, new compound
propositions can be formed by using
connectives
• Most common connectives:
– Conjunction (and) ^
– Disjunction (or) 
– Negation (not) ~ (¬)
– Exclusive-OR v
– Condition (if … then) →
– Bi-Condition 
12
 Example
• P: It is raining
• Q: It is cold

• Form a new compound statement by combining

these two statements
P  Q : It is raining and it is cold
P  Q : It is raining or it is cold

13
 Truth table of conjunction
• The truth values of compound propositions
can be described by truth tables.
• Truth table of conjunction
P Q PQ
T T T
T F F
F T F
F F F

• P Q is true only when both P and Q are

true. 14
 Example

• Let P = “A decade is 10 years”

• Let Q = “A millennium is 100 years”
• P  Q = “A decade is 10 years” and “A
millennium is 100 years”
• If P is true and Q is false then conjunction is
false

15
 Truth table of disjunction
• The truth table of disjunction is
P Q PQ
T T T
T F T
F T T
F F F

• p  q is false only when both p and q are false

• Example: p = "John is a programmer", q = "Mary is a lawyer"
• p v q = "John is a programmer or Mary is a lawyer"

16
 Truth table of Negation
• Negation of P: in symbols ~P or ⌐P
P ~P
T F

F T

• ~P is false when P is true, ~P is true when P

is false

17
 Negation Continued…
• E.g
• Example, P : "John is a programmer"
~P = "John is not a programmer"

• P: Paris is the capital of England

• ~P: Paris is not capital of England

18
 Exclusive disjunction
• “Either P or Q” (but not both), in symbols P  Q
P Q PvQ
T T F
T F T
F T T
F F F
• P  Q is true only when P is true and Q is false,
or P is false and Q is true.
❑ Example: p = "John is programmer, q = "Mary is a lawyer"
❑ p v q = "Either John is a programmer or Mary is a lawyer"

19
 More compound statements
• Let p, q, r be simple statements
• We can form other compound statements, such
as
(p  q)  r
p(q  r)
(~p)  (~q)
(p  q)  (~r)
and many others…

20
Example: truth table of (P Q)R
P Q R (P  Q)  R
T T T T
T T F F
T F T T
T F F F
F T T T
F T F F
F F T F
F F F F

21
 Conditional (Implication)
• A conditional proposition is of the form
“If P then Q”
• In symbols: P → Q
• Example:
P = " A bottle contains acid"
Q = “A bottle has a label”
P → Q = “If a bottle contains acid then it
has a label "

22
 Truth table of P → Q

P Q P→Q
T T T
T F F

F T T
F F T

P → Q is true when both p and q are true

or when P is false 23
 Example
• If the mathematics department gets an
additional amount of Rs. 40,000 then it will
hire one new faculty member.

• Let
P: The Mathematics Department gets an additional
Rs. 40,000
Q: The mathematics Department will hire one new
faculty member.
24
Hypothesis and conclusion

• In a conditional proposition P → Q,
P is called the hypothesis
Q is called the conclusion

25
 Example
• For all real number x if x > 0 then x2 > 0
• P: x>0
• Q: x2 > 0
For example x=3 , 3 > 0 then 32 > 0 both are true.
P→Q=T →T=T
x = -2 , -2 > 0 is false but -22 > 0 is true
P→Q=F→T=T

26
 Bi-Conditional
• The double implication “p if and only if q” is
defined in symbols as p  q
p q pq (p → q) ^ (q → p)
T T T T
T F F F
F T F F
F F T T

p  q is logically equivalent to (p → q)^(q → p)

27
 Exercise Problems
Design a truth table for given compound
statement
(p → q)  [(q  ¬ r) → (p  r)]

28
 (p → q)  [(q  ¬ r) → (p  r)]
p q r p→q q¬r p  r [(q  ¬ r) → (p  r)] a  b
(a) (b)
0 0 0 1 0 0 1 1

0 0 1 1 0 1 1 1

0 1 0 1 1 0 0 0

0 1 1 1 0 1 1 1

1 0 0 0 0 1 1 0

1 0 1 0 0 1 1 0

1 1 0 1 1 1 1 1

1 1 1 1 0 1 1 1
29
 Exercise Problems continues…
Let s, t and u denote the following primitive
statements
s : Phyllis goes out for walk
t : The moon is out
u : It is snowing
Express the following compound proposition in words
a) (t  ¬u) → s
b) t → (¬u → s)
c) ¬(s ↔ (u  t))
30
 Solution
a) If the moon is out and it is not snowing, then
Phyllis goes out for walk.
b) If the moon is out then if it is not snowing
then Phyllis goes out for a walk.
c) It is not that Phyllis goes out for a walk if and
only if it is snowing or the moon is out.

31
 Exercise problems continues…
Write the compound proposition for the following
sentences.
d) Phyllis will go out for walking if and only if the
moon is out. (s ↔ t)
e) If it is snowing and moon is not out, then
Phyllis will not go out for walk (u  ¬t) → ¬ s
f)It is snowing but Phyllis will still go out for a
walk. (u  s)

32
 Exercise problems continues…
Let p and q be primitive statement for which the
conditional p → q is false.
Determine the truth values of the following
compound propositions.
1. p л q
2. (¬p  q)
3. q → p
4. ¬q → ¬p
33
 Exercise problems continues…
Find the possible truth values of p, q and r in the
following cases
1. p →(q  r) is false
2. p л (q →r) is true

34
 Exercise problems continues…
If a proposition q has the true value 1, determine
all the truth assignment for the primitive
proposition p, q, r and s for which the truth value
of the following proposition is 1
[q→{(¬p  r) л ¬s}] л {¬s → (¬r л q)}

35
Solution :

36
Solution…

37
 Tautology
• A proposition is a tautology if its truth table
contains only true values for every case
– Example: p → p v q

p q p→pvq
T T T
T F T
F T T
F F T
38
 Contradiction
• A proposition is a Contradiction or
absurdity if its truth table contains only
false values for every case
– Example: p ^ ~p p p ^ (~p)
T F
F F

39
 Contingency
A compound proposition that can be true or false
( depending upon the truth values of its
components) is called Contingency.

i.e contingency is a compound proposition that is

neither tautology or contradiction

40
Exercise problems :
1. Prove that, for any proposition p,q,r the
following compound propositions are Tautology
a) [(p → q) Л (q → r)] → (p → r)
b) [p →(q →r)] → [(p →q) → (p →r)]

2. Show that [(pл q) л r ] → (s v t) is

contradiction

41
 Logical equivalence (⇔)
❑ Two propositions are said to be logically
equivalent ⇔ if their truth tables are identical.
P Q P→Q ~P  Q

T T T T
T F F F
F T T T
F F T T
❑Example: P → Q is logically equivalent to ~P  Q
P → Q ⇔ ~P  Q
42
Problems:
1. Prove that [(p  q) → r] ⇔ [( p →r)ᴧ (q →r)]
2. pᴧ(¬q  r) and p  (q ᴧ ¬r) are not logically
equivalent

43
 Definitions
• Implication p→q
• contrapositive, q→ p
• converse, q→ p
• inverse  p → q
 Converse
• The converse of p → q is q → p
p q p→q q→p
T T T T
T F F T
F T T F
F F T T

These two propositions

are not logically equivalent
45
 Contrapositive
• The contrapositive of the proposition p → q is ~q → ~p.

p q p→q ~q → ~p
T T T T
T F F F
F T T T
F F T T
They are logically equivalent.

46
 The Laws of Logic
We can prove whether the given Compound
proposition is Tautology, Contradiction ,
contingency or logically equivalent using Truth table
method.
But this method becomes tedious when the
number of primitive proposition involved is more.
Hence easiest method is to prove using the Laws of
Logic

47
1. De Morgan’s laws for logic

• The following pairs of propositions are

logically equivalent:

~ (p  q) and (~p)^(~q)
~ (p ^ q) and (~p)  (~q)

48
 Proof :
~ (p  q) and (~p)^(~q)

P q P  q ~(p q) ~p ~q ~(p) ᴧ~(q)

0 0 0 1 1 1 1

0 1 1 0 1 0 0

1 0 1 0 0 1 0

1 1 1 0 0 0 0

Therefore ~ (p  q) ⇔ (~p)^(~q)
49
 2. Distributive Law

• p ᴧ (q  r) ⇔ (p ᴧ q)  (p ᴧ r)

• p  (q ᴧ r) ⇔ (p  q) ᴧ (p  r)

50
 Laws of Logic
• Let P , Q and R be the propositional variables. T and F represent the True
and False respectively.

❖ ¬¬P ⇔ P Law of double

negation

❖ ¬(P v Q) ⇔ ¬P ^ ¬Q De Morgan’s laws

❖ ¬(P ^ Q) ⇔ ¬P v ¬Q

❖ (P v Q) ⇔ (Q v P) Commutative Laws
❖ (P ^ Q) ⇔ (Q ^ P)

❖ P ^ (Q ^ R) ⇔ (P ^ Q) ^ R Associative Laws
❖ P v (Q v R) ⇔ (P v Q) v R
51
Laws of Logic….
❖ P ^ (Q v R) ⇔ (P ^ Q) v (P ^ R) Distributive Laws
❖ P v (Q ^ R) ⇔(P v Q) ^ (P v R)

❖ (P ^ P) ⇔ P Idempotent Laws
(P v P) ⇔ P

❖ (P v F ) ⇔ P Identity Laws
❖ (P ^ T ) ⇔ P

❖ (P v ¬P ) ⇔ T Inverse Laws
❖ (P ^ ¬P) ⇔ F
52
Laws of Logic…
❖ (P v T ) ⇔ T Domination Laws
❖ (P ^ F) ⇔ F

❖ P v (P ^ Q) ⇔ P Absorption Laws
❖ P ^(P v Q) ⇔ P

❖ P→ Q⇔¬PvQ Implication Law

53
 Exercise Problems
Simplify the following compound proposition using the laws of
logic:
1. (p v q) ᴧ ¬ {(¬p) v q}

54
Exercise Problems
2. Prove that ( p v q )ᴧ ¬(¬p ᴧ q ) ⇔ p

55
Exercise Problems

3. Prove that ¬[¬{(p v q) ᴧ r} v ¬q] ⇔ q ᴧ r

56
Exercise Problems

57
Exercise Problems

58
Exercise Problem :

• Give reason for each step in the following

simplifications of the compound statement.

59
 Application to Switching Networks
• A switching network is made up of wires and
switches connecting two terminals say T1 and
T2.
• In such a network , each switch is open (so no
current flows through it) or closed(so that
current flows through it).
• If a switch is open, we assign the symbol 0 to it
and if it closed we assign 1.

60
 Switching Networks…
• There is a close analog between switches and their
states and proposition and their truth values.

• This shows a network with only one switch p, current

flows from terminal T1 to T2 only if switch p is closed.
i,e if p is 1

61
Switching Networks…

• This is a parallel network consisting of two switches p

and q in which the current flows from T1 to T2 if
either p or q or both are closed.
• Therefore this network can be represented by p v q

62
Switching Networks…

• This is a series network consisting of two switches p

and q in which the current flows from the terminal T1
to T2 only if both the switches p and q are closed.
• Therefore this network ca n be represented by p ᴧ q.

63
 Switching Networks..

• Any switching network is a combination of any

of these three types of networks.
• By applying the laws of logic on switching
network, we can obtain a new network which are
equivalent to the given network, may be with
fewer number of switches

64
 Examples:
Simplify the switching network shown below:

The above network can be represented by

(q v p v ¬q) ᴧ r

65
 Solution

• (q v p v ¬q) ᴧ r commutative Law

• (q v ¬q v p) ᴧ r Inverse Law
• Tᴧr Identity Law
• r
• This shows that the given network with 4 switches is
equivalent to a network that contains only one switch.

T1 __________ r __________T2

66
 Example 2…
• Simplify the network shown below

• [p v (p ᴧ q) v (p ᴧq ᴧ¬r)] ᴧ [(p ᴧ r ᴧ t) v t]

67
Solution :

68
Example 3 & 4

69
Solution 3

70
Solution 4:

71
Try It Yourself

72
 Duality
• Let s be a statement. If s contains no logical connectives
other than ᴧ and ᴠ, then the dual of s, denoted sd, is the
statement obtained from s by replacing each occurrence
of ᴠ by ᴧ and ᴧ by ᴠ respectively, and each
occurrence of T0 and F0 by F0 and T0, respectively.)

• Eg. s : (p ᴧ ¬q) ᴠ (r ᴧ T0)

• sd : (p ᴠ ¬q) ᴧ (r ᴠ F0)

73
Write down the duals for the following propositions :
1. p→q
= [ ¬p ᴠ q ]d
= ¬p ᴧ q

2. (p→q) →r
= ¬(p→q) ᴠ r
= ¬(¬p ᴠ q) ᴠ r
= [ p ᴧ ¬q ᴠ r ]d
= p ᴠ ¬q ᴧ r

3. p ↔ q ?

74
Principle of Duality
Let s and t be the statements that contain no
logical connectives other than ᴠ and ᴧ .
If s ⇔ t
then sd ⇔ td

75
 Example
Verify the principle of duality for the following logical
equivalence.

76
77
 Other Connectives : ↑ ↓
For any two propositions p and q, the DeMorgan’s law
states that

¬(p ˄ q) ⇔ ¬p ᴠ ¬q and
¬(p ᴠ q) ⇔ ¬p ᴧ ¬q

• The compound proposition ¬(p ˄ q) is read as “Not

of p and q” is also denoted by ( p ↑ q)
• The compound proposition ¬(p ᴠ q) is read as “ Not
of p or q” and is also denoted by ( p ↓ q)

78
• The symbol ↑ is called the NAND connective and is
the combination or not and and .
• The symbol ↓ is call the NOR connective and is the
combination of not and or
p q ¬p ¬q ¬pᴠ¬q ¬(p ˄ q)
↑

0 0 1 1 1 1
0 1 1 0 1 1
1 0 0 1 1 1
1 1 0 0 0 0

Thus, ( p ↑ q) ⇔ ¬(p ˄ q) ⇔ ¬p ᴠ ¬q and

( p ↓ q) ⇔ ¬(p ᴠ q) ⇔ ¬p ᴧ ¬q

79
Exercise problems:
For any proposition p and q, prove the following
1. ¬(p ↓q) ⇔ ¬p ↑ ¬q

80
2. ¬(p ↑ q) ⇔ ¬p ↓ ¬q

81
 Are ↑ and ↓ Associative ?
Is
p ↑(q ↑ r) ⇔ (p ↑ q) ↑ r ?

No they are not .

82
No!!

83
 Exercise problems:
Express the following propositions in terms of only
NAND and NOR connectives
1. ¬p
2. p ᴧ q
3. p ᴠ q
4. p → q

84
85
Converse, Inverse and Contrapositive: Logical
Implication
Consider a conditional p → q then,

1. q → p is called the Converse of p → q

2. ¬p →¬ q is called the Inverse of p → q
3. ¬ q → ¬ p is called the Contrapositive of p → q

86
State conditional , converse, inverse and contrapositive for
the following primitive propositions
p: It rains
q: the game will be cancelled
1. p→q : If it rains, then the game will be cancelled.
2. q→p : If the game is cancelled, then it has rained.
3. ¬p→¬q : If it doesnot rain, then the game will not be
cancelled.
4. ¬q→¬p : If the game is not cancelled, then it has not
rained.

87
Truth Table :
p q ¬p ¬q p→q q →p ¬p→¬q ¬q→¬p

0 0 1 1 1 1 1 1

0 1 1 0 1 0 0 1

1 0 0 1 0 1 1 0

1 1 0 0 1 1 1 1

From the above Truth Table we have the following important results:
1. The conditional and Contrapositive are logically equivalent for any proposition p and q
( p → q ) ⇔ ( ¬q→¬p )
2. The converse and Inverse of a conditional are logically equivalent for any proposition
p and q. ( q →p ) ⇔ ( ¬p→¬q )
And also ( p → q ) ⇔ ( q →p )
(¬p→¬q) ⇔ (¬q→¬p)

88
Logical Implication :
Consider the implication p→q, for any two propositions p
and q.
p : 6 is a multiple of 2
q : 3 is a prime number

Here p→q means “ If 6 is a multiple of 2, then 3 is a

prime number”. Here since p is true and q is also true,
p→q is also true, but this p→q does not make any sense
because there no consistency in the statement p→q
(though it is logical true)

89
• Hence we are interested in conditional p→q where p
and q are related in some way, so that the truth value of
q depends upon truth value of p or vice verse. Such
conditional are called Hypothetical statements or
Implicative statements.
• When a hypothetical statement p→q is such that q is
true whenever p is true , then we say that p logically
implies q and symbolically written as p ➔ q.
• When a hypothetical statement p→q is such that q is is
not necessarily true whenever p is true , then we say
that p does not logically implies q and symbolically
written as p ➔ q.

90
Necessary and Sufficient Conditions :
Suppose that p ➔ q , then in order that q may be
true if is sufficient that p is true, also if p is true ,
then it necessary that q is true.
i.e For p ➔ q p is sufficient for q
q is necessary for p

91
 Problems:
Using the truth table prove the following logical implication.
1. [ p ᴧ ( p→q ) ] ➔ q
p q p→q p ᴧ (p→q )
0 0 1 0
0 1 1 0
1 0 0 0
1 1 1 1

2. [ ( p→q ) ᴧ ¬q ] ➔ ¬q
p q p→q ¬q p→q ) ᴧ ¬q
0 0 1 1 1
0 1 1 0 0
1 0 0 1 0
1 1 1 0 0
3. The following are 3 valid arguments. Establish the validity of each
by the means of Truth Table. In each case, determine which rows of
the table are crucial for accessing the validity of the argument and
which rows can be ignored.
a. [ p ᴧ ( p → q) ᴧ r ] ➔ [ ( p ᴠ q ) → r ]
(a) (b)
p q r p→q (a) pᴠq (b)
0 0 0 1 0 0 1
0 0 1 1 0 0 1
0 1 0 1 0 1 0
0 1 1 1 0 1 1
1 0 0 0 0 1 0
1 0 1 0 0 1 1
1 1 0 1 0 1 0
1 1 1 1 1 1 1

93
b. [ [ ( p ᴧ q ) → r ] ᴧ ¬q ᴧ (p → r) ] ➔ (¬p ᴠ ¬q)
c. [ [ p ᴠ (q ᴠ r) ] ᴧ ¬q ] ➔ (p ᴠ r)

Solution b : Rows 1,2 and 6

Solution c : Rows 2,5 and 6

94
 Rules of Inferences
Establishing the validity of an argument by constructing the Truth
Table is tedious method for the following reasons.

• Table size depends on the no. of primitives

• For establishing the validity we need only those rows whose
truth value is true.

Solution : Truth Table method can be avoided for proving the

validity of an argument by using the technique called Rules of
Inference.
Rules of Inference are already valid arguments which can be used as
templates for establishing the validity of other arguments

95
 Rules of Inferences
Logical Implication: Rules of Inference

an argument: ( p1  p 2  p n ) → q

premises conclusion

is a valid argument
( p1  p 2  p n ) → q is a tautology
•

97
Rule 1, can be verified using the truth table

p q p→q p ᴧ p→q [p ᴧ p→q ] → q

0 0 1 0 1
0 1 1 0 1
1 0 0 0 1
1 1 1 1 1

Since [p ᴧ p→q ] → q is a Tautology, therefore its proved

98
•

99
100
•

101
102
103
•

104
•

105
106
•

107
 Problems 1:
P1 : if I study, I will not fail in the examination.
P2: If I don’t watch tv in the evening, I will study.
P3: I failed in the examination.
C : I must have watched tv in the evening

Let the primitives be

p : I study
q: I failed in the examination
r: I watch tv in the evening

108
Then the given arguments can be read as
p → ¬q
¬r → p
q
Therefore r

109
Problem 2:
I will get grade A in this course or I will not graduate.
If I don’t not graduate, then I will join army
I got grade A
Therefore I will not join the army
Let the primitives be
p: I get grade A in tis course
q: I graduated
r: I join the army

110
Solution

111
Problem 3:
Consider the following arguments
1) Rita is baking a cake
2) If Rita is baking a cake, then she is not practicing her flute
3) If Rite is not practicing her flute, then her father will not buy
her a car
4) Therefore Rita’s father will not buy her a car.

112
113
Problem 4:
Show that the following argument is valid (for primitive
statements p, r, s, t and u) and the conclusion ¬p
p→r , r→s , t ˅ ¬s , ¬t ˅ u , ¬u

114
Solution :

115
 Rule 4 : Rule of Conjunction
• This rule arises from the fact that if p and q are true statements
then p ˄ q is also a true statement.
• The statements p and q may occur in the development of an
argument as a given premises or may be the result that are
derived from the premises in the earlier arguments.
• Under these circumstances the two statements p and q can be
combined into their conjunction p ˄ q , and this new statement
can be used in later steps .
• Rule of Conjunction can be written as
p
q
Therefore p ˄ q

116
Problem on application of Rule of Conjunction
Test the validity of the following argument.
p˄q
p→(q→r)
r

117
Rule 5 : Rule of Disjunctive Syllogism
[ ( p V q) Л ¬p] → q

pVq
¬p
q

118
Rule 6 : Rule of Contradiction
Let ‘p’ denote an arbitrary statement, and F0 a
contradiction, then
(¬p → F0 ) → p i.e ¬p → F0
p

Rule 7 : Rule of Conjuctive Simplication

[ ( p Л q)] → p i.e pЛq
p

119
Rule 8 : Rule of Disjunctive Amplification
p → (p V q) i.e p
pVq

Problems :
1. Demonstrate the validity of the following argument
p→ r
¬p → q
q→s
¬r → s

120
121
2. Establish the validity of the argument
p→q
q→(r ᴧ s)
¬r ᴠ (¬t ᴠ u)
pᴧt
u

122
123
Show that the following argument is valid
If the band could not play rock music or the
refreshments were not delivered on time, then the New
year’s party would have been cancelled and Alicia
would have been angry.
If the party were cancelled , then refunds would be
made
No refunds were made
Therefore the band could play rock music.

124
125
 Quanitifier
• A sentence that involves a variable , such as x, cannot be called
as a statement.
• These cannot be called as proposition unless the valve of x is
specified.
• Eg., x+2 is an even integer.
x divides 16 etc.,
• Sentences of this kinds are called as Open Statements.
• If the open statement contains a variable ‘x’ and when we
restrict certain allowable choice for this ‘x’. These allowable
choices are called the Universe or Universe of Discourse for
open statement.

126
 Quantifier…
•

127
Quantifier…
• In the examples of p(x) and q(x,y) some substitutions
results in true statements and others results in false
statement.
• Therefore we can say
For some x, p(x) is True
For some x,y , q(x,y) is True
Similarly,
For some x, ¬p(x) is False
For some x,y , ¬q(x,y) is False
• The phrases “For some x” and “For some x,y” are said
to quantify the open statements p(x) and q(x,y)
respectively
128
 Quantifier…
•

129
 Quantifier…
•

130
Quantifier…

131
 Quantifier and Logical Connectives
•

132
Quantifier and Logical Connectives…
Write the Truth value for the following.
i) p(2)
ii) ¬q(4)
iii) p(-1) ᴧ q(1)
iv) ¬p(3) ᴠ r(0)
v) p(0) → q(0)
vi) p(1) ↔ ¬q(2)
vii) p(4) ᴠ [ q(1) ᴧ r(2)]
viii) p(2) ᴧ [q(0) ᴠ ¬r(2)]

133
 Solution :
i. True
ii. False
iii. False
iv. False
v. True
vi. False
vii. False
viii.True

134
Converse, Inverse and Contrapositive for open
statements
•

135
Exercise Problems:

136
Solution:

137
138
 Truth values of Quantified Statements
•

139
Rules of Inference for Open Statement:

140
Logical Equivalence

141
Rules of Negation of Quantified Statements

142
Problems:

143
Solution:

144
Problem :

• Consider the following program segment

for n=1 to 10
A[n] = n * n – n
Write the following statements in quantified form
a. Every entry in the array is non-negative
b. There exit two consecutive entries in A where the
larger entry is twice the smaller.
c. The entries in the array are sorted in ascending order

145
 Solution
•

146
Validity of a Open Statement :

The Rule of universal specification indicates that the truth

of an open statement in one particular instances follows
( as a special case ) from a more general ( for the entire
universe) truth of that universally quantified open
statement

Eg., For the universe of all the people, consider the open
statements
m(x) : x is a mathematics professor
c(x) : x has studied Calculus

147
•

148
149
 Problems
• Consider the universe of all triangles in the plane in conjunction
with the open statement
• p(t) : t has two sides of equal length
q(t) : t is an isosceles triangle
r(t) : t has two angles of equal measures
The arguments are
In triangle xyz there is no pair of angles of equal measure
If a triangle has 2 sides of equal length, then it is isosceles
If a triangle is isosceles, then it has two angles of equal measure.
Therefore triangle xyz has no two sides of equal length.

150
•

Therefore it’s a Valid Argument

151
2. Check the validity of the following argument
Consider the universe to be the set of all quadrilateral and the open
statements are

p(x) : x is square
q(x) : x has four sides

Arguments are
All square have four sides
The quadrilateral ABCD has four sides
Therefore ABCD is a square

152
153
Find whether the following argument is valid or not.( consider the
all the engineering students as universe)

No engineering student of 1st or 2nd semester studies logic design

Anil is an engineering student who studies logic design
Therefore Anil is not in Second Semester.

154
•

155
156
The Rule of Universal Generalization
•

157
Solution:

158
159
 1

Unit 2 - Relations
Definition : 2
Let A and B be two sets. Then a subset of A X B is called a Binary Relation or
just a Relation from A to B.

Thus, if R is a relation from A to B, then R is a set of ordered pairs (a,b) such

that a ∈ A and b ∈ B

If (a,b) ∈ R , we say that “ a is related to b by R” and denoted as aRb.

If (a,b) ∉ R, we say that “a is note related to b by R” and denoted as aRb

For example, consider Set A = {1,2,3} and Set B = {r,s}

Then R = {(1,r),(2,s),(3,r)} is a relation from A to B and 1Rr,2Rs,3Rr
This relation can be depicted in a diagram as below which is called 3
the Arrow diagram.

1
r
2

3
s
Example: 4
Let A = {1,2,3,4,5}
Define a relation R on set A by aRb if a<b
R = { (1,2),(1,3),(1,4),(1,5),(2,3),(2,4),(2,5),(3,4),(3,5),(4,5) }

Define a relation R1 on set A such that (a,b)∈R1 iff “a divides b”

R1 = {(1,1),(1,2),(1,3),(1,4),(1,5),(2,2),(2,4),(3,3),(4,4),(5,5)}
Properties of Relation 5
❖ Reflexive Relation
❖ Irreflexive Relation
❖ Symmetric Relation
❖ Asymmetric Relation
❖ Anti-symmetric Relation
❖ Transitive Relation
❖ Equivalence Relation
❖ Partial Ordered Relation
Reflexive Relation 6

A relation R on a set A is called Reflexive if for all a∈A, (a,a) ∈ R

Eg., A = {1,2,3,4}
Consider R1 = {(1,1),(2,4),(3,3),(4,1),(4,4)}
Here R1 is relation on A, but Non Reflexive relation because (2,2) ∉ R

Consider R2 = {(1,1),(2,2),(2,3),(3,3),(4,4)} is Reflexive Relation

R3 = {(a,b)|a,b ∈ A, a ≤ b} is reflexive or not
Irreflexive Relation 7

A relation R on a set A is said to be irreflexive if (a,a)∉ R for any

a ∈ A.
A relation R is irreflexive if no elements of A is related to itself by
R
Eg., A={1,2,3,4}
R = {(1,2),(2,1),(3,3),(4,4)}
The R is not irreflexive because (3,3) and (4,4) ∈ R
Nor its not reflexive because (1,1) and (2,2) ∉ R
 Irreflexive Relation…. 8
Whether these Relations are irreflexive?
R1 = A x A ( reflexive )
R2 = ∅ (irreflexive)
R3 = “ is less than” (irreflexive)
R4 = “ greater than or equal to” (reflexive)
Symmetric Relation 9

A relation R on set A is to be symmetric if (a,b) ∈ R then (b,a) ∈ R

i.e., aRb =bRa
Eg., A = {1,2,3}
R1 = {(1,1),(2,1),(1,2)} Symmetric
R2 = {(2,3),(3,2),(1,2)} not symmetric as (2,1) ∉ R2
A Relation which is not symmetric is called Asymmetric relation.
R3 = A x A (symmetric)
R4 = ∅ (symmetric)
Asymmetric Relation 10
A relation R on a set A is said to be asymmetric relation if
(a,b) ∈ R , then (b,a) ∉ R

Eg., A = {1,2,3,4}
R = {(1,2),(2,3),(3,1),(4,3)} Asymmetric
R1 = {(1,2),(2,1),(1,1)} Not Asymmetric but
symmetric
Antisymmetric Relation 11
A relation R on a set A is said to be antisymmetric if (a,b) ∈ R
and (b,a) ∈ R ,then a=b

Eg., A = {1,2,3,4}
R = {(1,2),(3,4),(4,3),(1,1)} Not antisymmetric
R1 = {(1,1),(2,2),(2,3),(4,2)} antisymmetric.
A relation can be both symmetric and Antisymmetric 12

Let A = {1,2,3}
R1 = {(1,1),(2,2)} is both symmetric and Antisymmetric

A relation neither be symmetric nor antisymmetric

R2 = {(1,2),(2,1)(2,3)}
Is neither symmetric because (3,2) ∉ R2
Nor Antisymmetric because (2,1) ∈ R2
Transitive Relation 13

A relation R on a set A is said to be transitive

if (a,b) ∈ R and (b,c) ∈ R ,then (a,c) ∈ R
Eg., A = {1,2,3}
R = {(1,2),(2,1),(1,1),(2,2)} Transitive
R = {(1,2),(1,3)} Transitive
R1= {(1,2),(2,3),(1,3),(3,1)} Not Transitive
Equivalence Relation (RST) 14

A relation R on a Set A is a Equivalence Relation if and only if

i) R is Reflexive, ∀𝑎 ∈ 𝐴, 𝑎, 𝑎 ∈ 𝑅
ii) R is Symmetric, if (a,b) ∈ 𝑅, then (b,a) ∈ 𝑅
iii) R is Transitive, (a,b) ∈ 𝑅 and(b,c) ∈ 𝑅 then (a,c) ∈ 𝑅,
Eg., A = {a,b,c}
R = {(a,a),(b,b),(c,c)} RST therefore Equivalence relation
R1 = {(a,a),(b,b),(c,c),(b,a)} R but not S, don’t check for T
R2= {(a,a),(a,c),(b,a),(c,a)} Its not R, so don’t check for ST
Partial Ordered Relations (RAT) 15

A relation R on a set A is said to be Partial Order Relation if

i) R is Reflexive, ∀𝑎 ∈ 𝐴, 𝑎, 𝑎 ∈ 𝑅
ii) R is AntiSymmetric, if (a,b) ∈ 𝑅 and (b,a) ∈ 𝑅 , then a=b
iii) R is Transitive, (a,b) ∈ 𝑅 and(b,c) ∈ 𝑅 then (a,c) ∈ 𝑅
Eg., A = {1,2,3}
R = { ∅ } Not POR Because its not reflexive
R1 = {(1,1),(2,2),(3,3)} Its RAT, therefore POR
R2 = {(1,1)(2,2)(3,3)(1,3)(2,3)} its RAT therefore POR
R3 = {(1,1)(1,2)(2,3)(1,3)} is not R therefore not POR
 16

Computer Recognition
REPRESENTATION OF RELATION FOR COMPUTER RECOGNITION
Tools for representation of a relation 17
1. Relation Matrix (Zero-One Matrix)
2. Directed Graphs (Digraphs)

Relation Matrix (Zero-One Matrix) :

Consider the sets A = {a1,a2,a3………am} and B = {b1,b2,b3……bn}
of m and n size respectively.
Then, AXB (cartesian product) consists of all the ordered pair of the
form (ai,bj), such that 1 ≤ 𝑖 ≤ 𝑚, 1 ≤ 𝑗 ≤ 𝑛, therefore the total of mXn
elements
Relation Matrix (Zero-One Matrix)…. 18

Let R be a relation from A to B , so that R is a subset of AXB,

Then, R can be represented by a m X n matrix denoted as M(R),
M(R) = [mij ] defined as
mij = 1 if (ai ,bj ) ∈ R
0 if (ai ,bj ) ∉ R
Such a matrix is called as the “Relation matrix” for R, and since M(R)
contains only 0’s and 1’s as its elements its also called as the
“ Zero-One Matrix ”
Note : Rows of the matrix corresponds to the elements in set A and
columns corresponds to the elements in set B
Relation Matrix (Zero-One Matrix)…. 19
p q
Example 1: Consider A = {0,1,2} and B = { p, q}
0 1 0
R = { (0,p),(1,q),(2,p)} M(R)= 1 0 1
2 1 0

Example 2 : Consider A= {1,2,3,4} and a relation R defined on A

R = {(1,2),(1,3),(2,4),(3,2)}
0 1 1 0
0 0 0 1
0 1 0 0
0 0 0 0
Directed Graphs (Digraphs) : 20
❖ A graph G is denoted by G = ( V, E ) , where V are vertices
and E are the edges
❖ In digraph for relation, G = ( V , E) ,
❖ V is called the Vertex Set of G and E is called the Edge set of
G
❖ If a,b ∈ V and (a,b) ∈ E, then there is a edge from a to b
❖ Here, the vertex ‘a’ is called the origin or source of the edge and
vertex ‘b’ is called the terminating / terminus vertex.
Directed Graphs (Digraphs) : Example : 21
Let A = {1,2,3,4}
R = {(1,1),(1,2),(2,1),(2,2),(2,3),(2,4),(3,4),(4,1)}
2

1
3

4
Directed Graphs (Digraphs) :….. 22
A vertex which is neither a source or terminus vertex is called
Isolated Vertex
The vertex in which the source and terminating vertex are same
is called as the Self-loop
The number of edges terminating at a vertex is called the
In-degree of the vertex
The number of edges leaving the vertex is called the Out-
degree of that vertex
Problems : 23
1. Let A= {1,2,3,4} and let R be the relation on A defined by xRy if and only
“x divides y” written as x|y
a) Write down R as a set of ordered pairs.
b) Draw the digraph of R.
c) Determine the In-degree & Out-degree of the vertices in the
digraph.
1 2
a. R = {(1,1),(1,2),(1,3),(1,4),(2,2),(2,4),(3,3),(4,4)}

1 2 3 4
In-Degree 1 2 3 3 4 3
Out-Degree 4 2 1 1
Problems :…. 24
2. Let A = {1,2,3,4,6} and R be a relation on A defined by aRb if and only
if ‘a is multiple of b’. Represent the relation R as a matrix and draw its
diagraph. R = {(1,1),(2,1),(3,1),(4,1),(6,1),(2,2),(4,2),(6,2),(3,3),(6,3),(4,4),(6,6)}

1 0 0 0 0
1 1 0 0 0
M(R) = 1 0 1 0 0
1 1 0 1 0
1 1 1 0 1
Problems…. 25
3. Find the relation R on set A determined by the digraph given below, also
write the relation matrix.
Representation of properties of relation using Zero-One matrix 26
and digraph

Reflexive Relation : A relation R on a set A is called Reflexive if for all a∈A,

(a,a) ∈ R
Consider a set A = {a,b,c} and R = {(a,a),(a,b),(a,c),(b,b),(c,b),(c,c)}

1 1 1
0 1 0
0 1 1

Diagonal elements should be 1 i.e Mij = 1 (i=j)

Each vertex should have self loop
 27
Irreflexive Relation : A relation R on a set A is said to be irreflexive if (a,a)∉
R for any a ∈ A.

0 1 0
0 0 1
1 0 0

None of the diagonal elements should be 1 i.e mij ≠ 1(i=j)

None of the vertex should have self loop
 28
Symmetric Relation: A relation R on set A is to be symmetric if (a,b) ∈ R
then (b,a) ∈ R

0 1 1
1 0 0
1 0 0

If mij = 1 then mji =1

There should arrows in both the direction
 29
Asymmetric Relation : A relation R on a set A is said to be asymmetric
relation if (a,b) ∈ R , then (b,a) ∉ R

If mij = 1 then mij ≠ 1

None of the pair of vertex should have bi-directional arrows
Antisymmetric Relation : A relation R on a set A is said to be antisymmetric 30
if (a,b) ∈ R and (b,a) ∈ R ,then a=b

1 1 1
0 1 0
0 1 1

If mij = 1 then mji = 0 but mij = 1.(i=j)

None of the pair of vertex should have bi-directional arrows but any vertex
can have self loop
Transitive Relation : A relation R on a set A is said to be transitive 31
if (a,b) ∈ R and (b,c) ∈ R ,then (a,c) ∈ R

1 1 1
0 0 1
1 1 0

If mik = 1 and mij =1 then mij = 1

If there is a path of length greater than 1 from vertex a to b, then there is
path of length 1 from a to b
Problems : 32
Find the nature of the relation represented by the following matrices.
1. 0 1 1 0 2. 1 0 1 0 3. 0 0 1 1
1 1 0 0 0 1 0 1 0 0 1 0
1 0 1 1 1 0 1 0 0 0 0 1
0 0 1 1 0 1 0 1 1 0 0 0
Operations on Relations : 33

Since a relation is a subset of the cartesian product of 2 sets, the set

operations can be used to construct new relations from the given relations.
Union of Relations : (R1 ∪ R2 )
Is defined as a relation from A to B with ,the property that (a,b)∈ R1 ∪ R2 ,
If and only if (a,b) ∈ R1 or (a,b) ∈ R2
Intersection of Relations : (R1 ∩ R2 )
Is defined as if (a,b) ∈ R1 ∩ R2 , If and only if (a,b) ∈ R1 and (a,b) ∈ R2
Complement of a Relation: R
Complement of R is a relation such that (a,b) ∈ R, if and only if (a,b)∉R
 34
Converse of a Relation : Rc
Is defined as a relation from B to A with property that (a,b)∈Rc
If and only if (b,a) ∈ R
Problems : 35

Consider A = {a,b,c} B = {1,2,3} and

R = {(a,1),(b,1),(c,2),(c,3)}
S = {(a,1),(a,2),(b,1),(b,2)}
Determine R, S, R∩ S, R ∪ S, Rc , Sc
A X B ={(a,1),(a,2),(a,3),(b,1),(b,2),(b,3),(c,1),(c,2),(c,3)}
R = {(a,2),(a,3),(b,2),(b,3),(c,1)} AX B - R
S = {(a,3),(b,3),(c,1),(c,2),(c,3)} A X B –S
R ∪ S = {(a,1),(a,2),(b,1),(b,2),(c,2),(c,3)}
R∩ S = {(a,1),(b,1)}
Rc = {(1,a),(1,b),(2,c),(3,c)}
Sc = {(1,a),(2,a),(1,b),(2,b)}
Problem…. 36
Let A = {1,2,3} and B = {1,2,3,4}, the relations R and S from A to B are
represented by the following relation matrices, Determine the relation R ,
R∩ S, R ∪ S, Sc and their matrix representation.

1 0 1 0 1 1 1 1
M(R) = 0 0 0 1 M(S) = 0 0 0 1
1 1 1 0 0 1 0 1
Problems… 37
The digraph of two relations R and S on a set A = {a,b,c} are given below
Draw the digraph of R, R∩ S, R ∪ S and Sc
Solution 38
Problems.. 39

Let A = {1,2,3,4,5} and R and S be relations on A whose corresponding digraphs

are as given below .Find R ,Rc , R∩ S
Composition of Relations : ∘ 40

❖ Let R be a relation from Set A to Set B and S be a relation

from set B to set C.
❖ With these two relations R and S, we can define a new
relation from set A to set C called product or the
composition of R and S from the set A to the Set C.
❖ This new relation is denoted by R∘S and defined as : If ‘a’ is
in A and ‘c’ is in C ,then (a,c)∈ R∘S if and only if there is
some ‘b’ in B such that (a,b) ∈ R and (b,c) ∈ S.
❖ Note that R⊆ (AxB), S ⊆ (BxC) and R∘S ⊆ (AxC).
Composition ….. 41

R s

a b c

R∘ s

A B C
Problems: 42
Let A = {1,2,3,4} B={w, x, y, z} and C={5,6,7}
Also, Let R1 be a relation from A to B
R1 = {(1,x)(2,x)(3,y)(3,z)}
And R2 and R3 be relation from B to C defined by
R2 = {(w,5)(x,6)} R3 = {(w,5)(w,6)}
Find R1∘R2 and R1∘R3
R1 R2
1 W
5
2 X
6
3 Y
7
4 z

R1∘R2 = {(1,6)(2,6)}
 R1 R3 43
1 W
5
2 X
6
3 Y
7
4 z

R1∘R3 = {∅}
Composition ….. 44
If R is a relation A , then we can define the composition of R with itself namely R∘R, this is
denoted by R2 , similarly R∘( R∘R) = R3
In general Rn is a relation on A defined recursively by R1 = R, Rn = R∘Rn-1

Eg., Let A = {1,2,3,4} and Let R = {(1,2)(1,3)(2,4)(4,4)}

R R
1 1 1
R2 = {(1,4)(2,4)(4,4)} 2
2 2
3 3 3
4 4 4

R R2
1 1
1
R3 = {(1,4)(2,4)(4,4)} 2
2 2
3 3
3
4 4
4
Problems: 45
1. Let A = {1,2,3} B={w,x,y,z} C = {4,5,6}
Define the relations R1⊆ AxB , R2 ⊆BxC and R3 ⊆BxC where,
R1={(1,w) (3,w) (2,x)(1,y)}
R2= {(w,5)(x,6)(y,4)(y,6)}
R3={(w,4)(w,5)(y,5)}
a) Determine R1 ∘ (R2∪R3) and (R1 ∘R2) ∪(R1 ∘R3)
b) Determine R1 ∘(R2∩R3) and (R1 ∘R2) ∩(R1 ∘R3)
Solution: 46

a) R1 ∘ (R2∪R3) = {(1,5)(1,4)(3,5)(3,4)(2,6)(1,6)}
(R1 ∘R2) ∪(R1 ∘R3) = {(1,5)(3,5)(2,6)(1,4)(1,6)(3,4)}

b) R1 ∘(R2∩R3) = {(1,5)(3,5)}
(R1 ∘R2) ∩(R1 ∘R3) = {(1,5)(3,5)(1,4)}
Problems:… 47

2. For the relation R1 and R2 on set A to B and B to C. find M(R1) ,M(R2)

And M(R1 ∘R2) and verify that M(R1 ∘R2) = M(R1) . M(R2)
A = {1,2,3,4} B = {w,x,y,z} C = {5,6,7}
R1 = {(1,x)(2,x)(3,y)(3,z)}
R2 = {(w,5),(x,6)}
Solution : 48

0 1 0 0 1 0 0
M(R1) = 0 1 0 0 M(R2) = 0 1 0
0 0 1 1 0 0 0
0 0 0 0 0 0 0

0 1 0 0 1 0
0 1 0 0 1 0
M(R1 ∘R2) = M(R1) . M(R2) = 0 0 0
0 0 0
0 0 0 0 0 0
Problems:… 49

Let A = {a,b,c} and R and S be relation on A whose matrices are

as given below

1 0 1 1 0 0
M(R) = 1 1 1 M(S) = 0 1 1
0 1 0 1 0 1

Compute R∘S , S∘R , R∘R , S∘S and their matrices

Equivalence Relation , equivalence class and Partition 50
Equivalence Relation : A relation R on a set A is said to be an
equivalence relation on a Set A if
i) R is Reflexive
ii) R is Symmetric
iii) R is Transitive
Equivalence Class : Let R be an equivalence relation on a set
A and a∈A, Then the set of all those elements x of A which are
related to ‘a’ by R is called equivalence class of ‘a’ with respect to
R. And denoted by R(a) or [a] or a .
R(a) = [a] = a = {x∈A|(x , a)∈R}
Example : 51
consider a equivalence relation R on a Set A = {1,2,3}
R = {(1,1)(1,3)(2,2)(3,1)(3,3)}

We find that the element x of A for which (x,1)∈R, in this

example we found x=1 and x=3 , therefore {1,3} are class of 1

Similarly [1] = {1,3} [2] ={2} [3] = {1,3}

 52
Partition of a Set :
Let A be a non-empty set. Suppose there exists non-empty subset
A1,A2,A3…..An of A such that the following two conditions hold
Condition 1: A is the Union of of A1,A2,A3…..An , that is
A1∪ A2 ∪ A3 ∪ …….. ∪ An = A

Condition 2 : Any two of the subsets A1,A2,A3…..An are disjoint, that is

Ai ∩Aj = ∅.
Then the set p = {A1,A2,A3…..An } is called the partition of A and
A1,A2,A3…..An are called the blocks or cells of the partition.
 53

Eg., A = {1,2,3,4,5,6,7,8}
and following are its subsets
A1 = {1,3,5,7}
A2 = {2,4}
A3 = {6,8}

The above subsets are partitions of a because A1∪A2∪A3 = A and A1∩A2 = ∅

Therefore p = {A1,A2,A3} is partition of A and A1,A2 and A3 are called Blocks
Fundamental Theorem on Equivalence relations 54
This theorem brings out the connection between equivalence relation and
partition of a set.
That is if A is a non-empty set then,
1) Any equivalence relation R on A induces a partition of A.
2) Any partition of A gives rise to an equivalence relation R on A.
Problems :
1. For the equivalence relation. 55
R = {(1,1)(1,2)(2,1)(2,2)(3,4)(4,3)(3,3)(4,4)}
Defined on the set A = {1,2,3,4}, determine the partition induced.
Solution :
From the given relation R ,we find that the equivalence classes of the elements of A w.r.t R
are
[1] = {1,2} [2] = {1,2} [3] = {3,4} [4] = {3,4}
Of the equivalence classes only [1] and [3] are distinct, therefore these two constitutes
partition.
p = {[1],[3]} = {{1,2},{3,4}} and also [1] ∪ [2] = {1,2,3,4} = A and [1] ∩ [2] = ∅
Similarly, any partition of A gives rise to an equivalence relation R on A
Eg., Let p = {{1,2},{3,4}} be a partition of A . Find pairing of each individual equivalence
class to get the Equivalence Relation R on A from p
R={(1,1)(1,2)(2,1)(2,2)(3,3)(3,4)(4,3)(4,4)}
Problems : 56
2. Consider a set A = {1,2,3,4,5} and its equivalence relation
R = {(1,1)(2,2)(2,3)(3,2)(3,3)(4,4)(4,5)(5,4)(5,5)} defined on A.
Find the partition of A induced by R.

3. Let A = {a,b,c,d,e} ,Consider the partition p={{a,b},{c,d},{e}} of A.

Find the equivalence relation induced by this partition.
Partial Order and Hasse Diagrams(simplified Graphs) 57
A relation R on a set a is said to be a partial ordered relation or a partial
order on A if
i) R is reflexive
ii) R is Antisymmetric
iii) R is transitive on A

A set A with a partial order R defined on it is called partially ordered set or a

POSET and is denoted by the pair (A,R)
 58
Eg., Let A = {1,2,3,4} and R = {(1,1)(1,2)(2,2)(2,4)(1,3)(3,3)(3,4)(1,4)(4,4)}
Hasse Diagram : 59
Conventions used in Hasse Diagram
1. Since, partial order is reflexive, each vertex will have self-loop, hence we
need not exhibit such cycles or loop explicitly , it is implicitly
understood.
2. Since, partial order is transitive, if there is an edge from a to b and an edge 60
from b to c, there should be an edge from a to c(transitive), we need have to
exhibit this transitive edge a to c explicitly,

3. Vertices are represented by dot.

 61
4. Digraph is drawn such that all edges are upward and directed edges
can be replaced with undirected edges.
Problems : 62

1. The digraph for a relation on the set A = {1,2,3,6,8} is as shown below .

Verify that (A,R) is a poset and write its Hasse Digram .
Solution : 63
Problems:… 64

2. Define R on A = {1,2,3,4} by xRy if x|y that is x exactly divides y. Prove

that (A,R) is a poset . Draw its Hasse diagram.
Solution 2: 65
Problems:… 66
3. Draw the Hasse diagram for the divisibility relation on the set A
A = {3,6,12,36,72}
The Relation R of Divisibility is aRb if and only if ‘a’ divides ‘b’
Solution :
72
36

12

6
3
Problems:… 67
4. Draw the Hasse diagram for the divisibility relation on the set A
A = {2,3,6,12,24,36}
Solution 4: 68
Problems:… 69

5. Consider a set representing the positive divisors of 36 and

relation R representing the divisibility relation . Draw the Hasse
diagram.

D36 = {1,2,3,4,6,9,12,18,36}
Problems : .. 70

6. The Hasse diagram of a partial order R on the set A =

{1,2,3,4,5,6} is as given below. Write down the subset of AxA
construct its digraph.
Solution 6: 71
R = {(1,1)(1,4)(1,6)(2,2)(2,5)(2,6)(3,3)(3,5)(3,6)(4,4)(4,6)(5,5)(5,6)(6,6)}
7. Determine the matrix of the partial order whose Hasse diagram 72
is given below.
 R={(1,1)(1,2)(1,4)(1,3)(1,5)(2,2)(2,4)(3,3)(3,5)(4,4)(5,5)} 73

1 1 1 1 1
0 1 0 1 0
M(R) = 0 0 1 0 1
0 0 0 1 0
0 0 0 0 1
8. Draw the Hasse diagram of the relation R on a set 74
A = {1,2,3,4,5} whose matrix is as given below

1 0 1 1 1
0 1 1 1 1
M(R) = 0 0 1 1 1
0 0 0 1 0
0 0 0 0 1
 Solution 8: 75
 76
Draw the Hasse Diagram for the relation on set A
[1,2,3,5,6,10,15,30, /]
 77
Solution
Total Order 78
Let R be a partial order on a set A , then R is called a Total Order
or linear order or totally ordered set or chain on A if ∀x,y ∈A is
such that either xRy or yRx. In this case the poset(A,R) is called
Totally Ordered Set

Eg., Consider the divisibility relation on the set A = {1,2,4,8}

R = {(1,1)(1,2)(1,4)(1,8)(2,2)(2,4)(2,8)(4,4)(4,8)(8,8)} is a Total
Order on A
 79
But, the same divisibility relation on the set A = {1,2,4,6,8}
R = {(1,1)(1,2)(1,4)(1,6)(1,8)(2,2)(2,4)(2,6)(2,8)(4,4)(4,8)(6,6)(8,8)}
But, neither 4 divides 6 nor 6 divides 8, Therefore its not Total
Order

Note : “Every Total order is a partial order, but not every

partial order is a Total order”
 80
Whether the relation “ ≤ ” on a set of natural numbers N
is total order or not ? (N, ≤)
Topological Sorting 81
Consider a relation (A,R) which is partial order, but not a total order.
If we wish to find the total order T on A such that R⊂ T.
The Technique of constructing such a T for a set A is known as
Topological Sorting.
Topological Sorting Algorithm…. 82
Repeat step 2 and 3 till all the vertices are deleted from the H, with the
vertices V1,V2,V3,…….Vn-1 removed one by one in that order.
If now a relation T on A is defined by (Vi,Vj)∈T. if i>=j for i,j =1,2,3,….n
then, T serves as the required total order and the Hasse diagram of T appear
as below
V1
V2 Represented as
V3 vn<vn-1<……..v2<v1
V4 ( < stands for below o before)
Vn-1

Vn
 83
Example :
Consider a set A = {1,2,3,4,5} and the partial order R on a set A whose
Hasse diagram its as given below. Find the Topological Sorting
Solution : 84
Step 1: Find a vertex V1 in the Hasse diagram that has no outgoing edge.
delete it and remove all the edges connected to it.

V1 = 1

Step 2: Next vertex under consideration for deletion can be 2 or 5

V2 = 2
Step 3: Next vertex is 3 Thus v1 = 1,v2=2,v3=3,v4=5 85
v5=4, Therefore the total
V3 =3 order T on A is given by
4<5<3<2<1

1
Step 4: Next vertex is 5 2

3
5
V4 = 5 and V5=4
4
 Compare the Hasse diagram and Topological sorted total order 86
diagram.
 We observe that all the ordered pairs belonging to R are in T as
well , furthermore T contains ordered pairs that are not in R.

R = {(1,1)(2,2)(3,3)(4,4)(2,1)(3,2)(3,1)(4,2)(4,1)(4,5)(5,5)}

T = {(4,4)(4,5)(5,3)(4,3)(3,2)(5,2)(5,5)(3,3)(2,2)(1,1)(2,1)(3,1)(4,1)(5,1)(4,2)}
Note that : (4,3)(5,3)(5,2)(5,1) belong to T but not R. Thus we
have obtained the total order T on A such that R⊂T
Problem: 87
The digraph for a relation on set A = {1,2,3,4} is shown in figure
a) Verify that (A,R) is a poset and draw its Hasse diagram.
b) Topological sort (A,R)
c) How many more directed edges are needed in the digraph
of R to extend R to a total order?
Extremal Elements : 88
Maximal and Minimal Elements
1. In a poset , if an elements is not related to any other element
is called the Maximal Element.
2. In a poset, if no element is related to an element, that
element is called the Minimal Element.
 89
Greatest Element : (Maximum Element)
An element a∈A is called a Greatest element of A if xRa
∀x∈A

Least Element : (Minimum Element)

An element a∈A is called a Least element of A if aRx ∀x∈A
 90

According to the Hasse diagram, the ordered pairs are

(1,1) (1,2) (2,2) (2,3) (1,3) (3,5) (1,5) (3,3) (2,5) (2,4) (1,4) (4,4) (4,5) (5,5)

Therefore 5 is the Greatest/Maximum element

Therefore 1 is the Least/Minimum element

 91

Find the Greatest and the Least element.

Upper Bound : Let B be a subset of a set A. An elements x∈A is in upper 92
bound of B if (y,x)∈ Poset, ∀y∈B
Lower Bound : Let B be a subset of a set A. An elements x∈A is in lower
bound of B if (x,y)∈ Poset, ∀y∈B
Eg: Consider the Hasse diagram of a poset (A,R) given below. Find the
upper bound and lower bound for the subset B = {c,d,e} on S
Consider B = {c,d,e}
(c,d)(d,f)(c,f)(c,e)(e,f)(c,f) (f,g) (c,g)(d,g) (f,h) (e,h)(c,h)(d,h)
UPPER BOUND (B) = {f, g, h}

(a,c)(b,c)(c,c)(c,d)(a,d)(c,e)(b,e)
LOWER BOUND (B) = {a, b, c}
Problems : 93
Find the Upper Bound and Lower Bound the Hasse diagrams show below.
1. 2. 3.

B1 = {e,c} B2={c,f,d} B1={5,10} B2={5,10,2,4} B1= {d, g} B2={e, f}

UB(B1) = UB(B1) = UB (B1) =
LB (B2) = LB (B2) = LB (B2) =
Solution : 94
Find the Upper Bound and Lower Bound the Hasse diagrams show below.
1. 2. 3.

B1 = {e,c} B2={c,f,d} B1={5,10} B2={5,10,2,4} B1= {d, g} B2={e, f}

UB(B1) = {g,e} UB(B1) = {50,10,100,200} UB(B1) = {g}
UB(B2) ={f,g,h} UB (B2) = {100,200} UB(B2) = {f,g}
LB (B1) = {a,b,c} LB (B1) = {1,5} LB(B1) = {a,b,e,d}
LB(B2) = {∅ } LB (B2) = {1} LB(B2) = {a,e}
 95
Least Upper Bound (LUB/Supremum/Sup/Join/∨ :
(Minimum element of upper bound)
An element a∈A, is called the least upper of a subset B of A if the following
two conditions is satisfied.
i) ‘a’ is an upper bound of B
ii) If d is an upper bound of B, then aRd

Greater Lower Bound (GLB/Infinum/Inf/Meet/∧ :

(Maximum or greatest element in lower bound)
Examples: 96

B1 = {c,d} B2 = {a,b} B3 ={e,f}

UB(B1) = {e} UB(B2) = {e,d,f} UB(B3) = {∅ }
LUB(B1) = {e} LUB(B2) = {d} LUB(B3)= {∅ }

LB(B1) = {a} LB(B2)= {∅} LB(B3) = {a,b,d}

GLB(B1) = {a} GLB(B2) = {∅} GLB(B3) = {d}
B1 = {a,c,f} B2 = {d,c} 97
UB(B1) = {e,f} UB(B2)= {d,e}
LUB(B1) = {f} LUB(b2) = {d}

LB(B1) = {a} LB(B2) = {a,c}

GLB(B1)={a} GLB(B2) = {c}

B1 = {d,e} B2 = {b.c}

UB(B1)= {f} UB(B2)={d,ef}

LUB(B1) = {f} LUB(B2)={∅}

LB(B1) = {a,b,c} LB(B2)= {a}

GLB(B1) = {∅} GLB(B2)={a}
 98

B = {b,f}

UB(B) = { }
LUB(B) = { }

LB(B) = { }
GLB(B)= { }
Lattice: 99
The poset (A,R) is called a Lattice, if for all x,y∈A, the element
LUB{x, y} and GLB{x, y} exists in A .
A lattice is denoted as (L,R).
 100
Check whether the poset [D12,/] is Lattice
Solution: 101
After removing all the reflexive, transitive pairs
R = {(1,2)(1,3)(2,4)(2,6)(3,6)(4,12)(6,12)}
 1

Coding Theory
 2
Introduction:

 In Digital communication system, information is transmitted in the

form of Strings of 0’s and1’s
 While transmitted the information certain problems may raise due
to noise in the transmission channel.
 Therefore, when certain signal is transmitted, a different signal may
be received causing the receiver to make wrong decision.
 In this chapter we study about the techniques that help to detect and
perhaps even to correct the transmission Errors.
 3
Basics

 Consider a set Z2 = {0,1} ,

 then Z2n = Z2 x Z2 x Z2 …(n factors)
 ={(a1,a2,a3…….an}| a1,a2,……an ∈ Z2}
 Thus, every element of Z2n is a tuple (a1,a2,….an) in which every ai belong to Z2 so
that it is a 0 or 1
 Eg., Z43 = (1,2,3) // elements in this group is with 4 and has 3 elements(3-tuple)
 Z45 = (2,3,3,1,1) // elements in this group is with 4 and has 5 elements (5-tuple)
 Similarly, the word/string 00101 is a 5-tuple (0,0,1,0,1)∈Z25
 4
Transmission of a word

 When a word c = c1c2c3……cn ∈ Z2n is transmitted from a point A

through a transmission channel T.
 In ideal situation (if no noise) this word would be received at a point B
without any changes.
 But in actual practice, transmission channels suffer disturbances called
noise that may cause a ‘0’ to be transmitted a ‘1’ or vice versa.
 Hence a word ‘c’ transmitted from A is received as a different word ‘r’ ∈
Z2n at B
 5
Transmission of word…

 The word ‘r’ will be of the form r = r1r2r3….rn where each ri is a 0

or 1 but rj ≠ cj for some j, 1≤ j≤ n
 r can be written as r = c + e where c is a word in Z2n and e is error
pattern
Transmission Channel T
Word c∈Z2n Word r = T(c) ∈Z2n
Transmitted Received

A
B
 6
Symmetric Channel

 Suppose ‘P1’ is the probability(likelihood) that the transmitted

signal 0 is received as the signal 1 and ‘P2’ is the probability that
transmitted signal 1 is received as 0.
 The transmission channel is said to be symmetric if P1=P2.
 Thus, in Symmetric Channel the probability that a transmitted
signal 1 is received as the signal 0 is equal to the probability that a
transmitted signal 0 is received as 1.
 7
Binary Symmetric Channel

 If p is the probability of incorrect transmission that a signal (0 or 1) is

received correctly is 1-p

 As we are transmitting only 0 or 1 (digital transmission) the symmetric

channel is referred to as Binary Symmetric Channel
 8

 Suppose ‘r’ differs from ‘c’ in exactly one place (say jth place), then, r1=
c1, r2= c2,r3=c3, rj-1 = cj-1 , rj ≠ cj , rj+1 = cj+1 ……rn = cn
Since the probability that ri = ci is (1-p) for each i, the probability
that r1 = c1 , r2=c2 …… rj-1 = cj-1 is (By the product rule)
▪ (1-p)(1-p)(1-p)(1-p) = (1 - p) j-1 // (j-1) factors

▪ Similarly the probability that , rj+1 = cj+1 ……rn = cn

(1-p)(1-p)(1-p)(1-p) = (1 - p) n-j // (n-j) factors

▪ Probability that rj ≠ cj is p
 9
Continued….

 Therefore, the probability that

r1= c1, r2= c2,r3=c3, rj-1 = cj-1 , rj ≠ cj , rj+1 = cj+1 ……rn = cn is
= (1 - p) j-1 . p . (1 - p) n-j
= p. (1-p)n-1
This is probability that ‘r’ differs from ‘c’ in exactly one place, Similarly the
probability that ‘r’ differs from ‘c’ in ‘k’ places is
= pk . (1-p)n-k
 10
Problems:

1. The word c = 110101 is transmitted through a binary symmetric channel T. if the

error pattern e=101010, find the word r=T(c) received.
Solution : c = 110101 ∈ Z26
e = 101010 ∈ Z26
r=c+e
= (1,1,0,1,0,1) + (1,0,1,0,1,0)
= (1+1, 1+0, 0+1, 1+0, 0+1,1+0)
r = 0 1 1 1 1 1 // (1+1 = 2-2) in Z2
 11
Problems..

2. The word c = 1010110 is transmitted through a binary symmetric channel.

If e=0101101 is the error pattern, find the word r received, if p = 0.05 is the
probability that a signal is incorrectly received, find the probability with
which r is received.
Solution : Here the transmitted word c = 1010110 ∈ Z27 and error pattern
e = 0101101 ∈ Z27 and we know that r = c + e , where + is the addition
in Z27
r = c+e =(1,0,1,0,1,1,0) +(0,1,0,1,1,0,1)
= (1+0 , 0+1, 1+0, 0+1, 1+1, 1+0, 0+1)
r = 1 1 1 1 0 1 1
 12
Problems….

c=1010110
r=1111011
Comparing c and r, r differs from c in 4 places,
Therefore probability with which r is received is = p4 (1-p)7-4
= (0.05)4 (1-0.05)3
= 0.000053
 13
Problems…

3. The word c=1010011 sent through a binary symmetric channel is received as the word
r=T(c) = 1100110. Find the error pattern.
Solution : c=1010011 , r= 1100110
r = c+ e
1=1+e1, Therefore e1=0
1=0+e2, e2=1
0=1+e3, e3=1
0=0+e4, e4=0
1=0+e5, e5=1
1=1+e6, e6=0
0=1+e7, e7=1 Therefore error pattern e = 0110101
 14
Problems..

4. A word c transmitted through a binary symmetric channel is received as

r=0000111. if e=0101111 is the error pattern , determine c.
Solution: r = c + e
0=c1+0, c1=0
0=c2+1, c2=1
0=c3+0, c3=0
0=c4+1, c4=1
1=c5+1, c5=0
1=c6+1, c6=0
1=c7+1, c7=0 Therefore c=0101000
 15
Problems..

5. The word c=1010110 is sent through a binary symmetric channel. If p=0.02 is the
probability of incorrect receipt of a signal. Find the probability that c is received as
r=1011111, determine error pattern.

6. A binary symmetric channel has probability p=0.05 of incorrect transmission . If

the word c = 011011101 is transmitted, what is the probability that.
i) Single error occurs
ii) Double error occurs
iii) Triple error occurs
 16
Solution:

The probability that exactly ‘k’ errors are made in the transmission is

nCk pk (1-p)n-k
Scanned by CamScanner
Scanned by CamScanner
Scanned by CamScanner
Scanned by CamScanner
Scanned by CamScanner
Scanned by CamScanner
Scanned by CamScanner
Scanned by CamScanner
Scanned by CamScanner
Scanned by CamScanner
Scanned by CamScanner
Scanned by CamScanner
Scanned by CamScanner
Scanned by CamScanner
Scanned by CamScanner
Scanned by CamScanner
Scanned by CamScanner
Scanned by CamScanner
Scanned by CamScanner
Scanned by CamScanner
Scanned by CamScanner
Scanned by CamScanner
Scanned by CamScanner
Scanned by CamScanner
Scanned by CamScanner
Scanned by CamScanner
Scanned by CamScanner
Scanned by CamScanner
Scanned by CamScanner
Scanned by CamScanner
Scanned by CamScanner
Scanned by CamScanner
Scanned by CamScanner
Scanned by CamScanner
Scanned by CamScanner
Scanned by CamScanner
Scanned by CamScanner
Scanned by CamScanner