MA4201: Mathematical Foundations of Computer Science MSc (M&SC), I Sem

Lecture-1
Department of Mathematics, NIT Warangal Scribe: Dr. Y. Sreenivasa Rao

Propositions
A proposition is a declarative sentence (or an assertion) which is either true or false, but not
both.
Examples of propositions

1. 3 is a prime number (true)

2. Warangal is the capital of India (false)

3. 1 + 5 = 6 (true)

4. 6 divides 13 (false)

Examples that are not propositions

1. Read this carefully (order)

2. Are you attending this class?

3. x + y = 7

4. a − b > 3

Truth value of a proposition

If a proposition is true, the truth value, associated with it, is denoted by T or 1.
If a proposition is false, the truth value, associated with it, is denoted by F or 0.
Notation. (i) Throughout this course, we use 1 and 0 for true and false, respectively.
(ii) The proposition that is always true is denoted by T and the proposition that is always false
is denoted by F.
Propositional Variables
Variables that represent propositions are called propositional variables.
The letters p, q, r, s, . . . are used to denote propositions (with unspecified truth values).
Note. In some text books P, Q, R, S, . . . have been using.
Examples
p : 3 is a prime number.

1
q : 1 + 9 = 10.
r : 6 divides 11.
Compound Propositions
The propositions which are framed from existing propositions using the following logical con-
nectives are called compound propositions.
Negation ¬ (NOT),
Conjunction ∧ (AND),
Disjunction ∨ (OR),
Implication =⇒ (if),
Biconditional ⇐⇒ (if and only if),
Exclusive or ⊕ (XOR)
Negation ¬ (NOT). It is a unary operator.
If p is a proposition, then the negation of p is denoted by ¬p. (Other notations are ∼ p or p̄.)
Truth table for ¬p

p ¬p
1 0
0 1

Example
p : 4 is a prime number.(0)
¬p : 4 is not a prime number.(1)
Conjunction ∧ (AND). It is a binary operator.
If p, q are propositions, then the conjunction of p, q is (denoted by p ∧ q) is “p and q”.
Example
p : 4 is a prime number.
q : 3 + 2 = 5.
p ∧ q : 4 is a prime number and 3 + 2 = 5.
Truth table for p ∧ q

p q p∧q
0 0 0
0 1 0
1 0 0
1 1 1

2
Disjunction ∨ (OR). It is a binary operator.
If p, q are propositions, then the disjunction of p, q is (denoted by p ∨ q) is “p or q”.
Example
p : 4 is a prime number.
q : 3 + 2 = 5.
p ∨ q : 4 is a prime number or 3 + 2 = 5.
Truth table for p ∨ q

p q p∨q
0 0 0
0 1 1
1 0 1
1 1 1

Exclusive OR (⊕). It is a binary operator.

If p, q are propositions, then the exclusive OR of p, q is (denoted by p ⊕ q) is “p XOR q”.
Truth table for p ⊕ q

p q p⊕q
0 0 0
0 1 1
1 0 1
1 1 0

Implication (−→ or =⇒). It is a conditional statement.

If p, q are propositions, then p −→ q is a conditional statement or implication which is read as
“if p, then q”.
Truth table for p −→ q

p q p −→ q
0 0 1
0 1 1
1 0 0
1 1 1

Example
If Warangal is capital of Telangana then NewDelhi is not capital of India. (1)
3
In p −→ q, p is hypothesis (antecedent or premise) and q is conclusion (or consequence).
Note. we can read p −→ q as any one of the following types.
if p, then q
p implies q
p only if q
p is sufficient condition for q
q is necessary condition for p.
q follows from p
q whenever p
q if p

Reference
1. Kenneth H Rosen. Discrete Mathematics and Its Applications with Combinatorics and
Graph Theory, 7th Edition, Tata McGraw Hill, 2017.

4
 Department of Mathematics, NIT Warangal
MA4201: Mathematical Foundations of Computer Science
MSc (M&SC), I Semester (AY 2022-23)
Quiz-1 (29-8-2022)
Duration: 15 mins Max. Marks: 5

Name: Roll No:

Q. Five persons A, B, C, D, E are in a compartment in a train. A, C, E are men and B, D are

women. The train passes through a tunnel and when it emerges, it is found that E is
murdered. An enquiry is held. A, B, C, D make the following statements.
A says
p: I am innocent
q: B was talking to E when the train was passing through the tunnel.
B says
r: I am innocent
s: I was not talking to E when the train was passing through the tunnel.
C says
t: I am innocent
u: D committed the murder.
D says
v: I am innocent
w: one of the men committed the murder.

Four of these eight statements are true and four are false. Assuming only one person
committed the murder, who did it?

Answer.
 MA4201: Mathematical Foundations of Computer Science MSc (M&SC), I Sem
Lecture-2
Department of Mathematics, NIT Warangal Scribe: Dr. Y. Sreenivasa Rao

From p −→ q, we can form new conditional statements

(i) q −→ p is the converse of p −→ q.
(ii) ¬q −→ ¬p is the contrapositive of p −→ q.
(iii) ¬p −→ ¬q is the inverse of p −→ q.
Note. (1) p −→ q and ¬q −→ ¬p always have the same truth value.
(2) q −→ p and ¬p −→ ¬q always have the same truth value.
Example. Let p : I study well, q : I excel in life.
Write the converse, contrapositive and the inverse of p −→ q.
Biconditional (or Equivalence) (←→ or ⇐⇒). It is a conditional statement.
If p, q are propositions, then the biconditional statement of p, q (denoted by p ←→ q) is “p iff q”.
Truth table for p ←→ q

p q p ←→ q
0 0 1
0 1 0
1 0 0
1 1 1

Note. we can read p ←→ q as any one of the following types.

p is equivalent to q,
p if and only if q,
p is necessary and sufficient condition for p,
If p then q and if q then p
Fact. The compound statements p ←→ q and (p −→ q) ∧ (q −→ p) always have the same truth
value.
Example. Construct the truth table of the compound proposition (p −→ q) ∧ (¬p −→ q).
Example. Construct the truth table of the compound proposition (p ←→ q) ∨ (¬q ←→ r).
Exercise. Construct the truth table for the following compound propositions
(i) p −→ (¬q ∨ r)
(ii) ¬p −→ (q −→ r)
(iii) (p −→ q) ∨ (¬p −→ r)

1
(iv) (p −→ q) ∧ (¬p −→ r)
(v) (¬p ←→ ¬q) ←→ (q ←→ r)
( )
(vi) (p ∧ q) ∨ ¬r ←→ p
Precedence of Logical Operators

Operator Precedence
¬ 1
∧ 2
∨ 3
−→ 4
←→ 5

Bitwise AND, Bitwise OR, Bitwise XOR

A bit is either 0 or 1.
A bit string is a sequence of bits.
Length of a string = number of bits in the string.
Example. 10101001 is a bit string of length 8 (i.e., byte).
Example.
(i) 1110 ∧ 0010 = 0010
(ii) 1110 ∨ 0010 = 1110
(iii) 1110 ⊕ 0010 = 1100
Exercise. Evaluate the following
(i) (01010 ⊕ 11011) ⊕ 01000
(ii) (11011 ∨ 01010) ∧ (10001 ∨ 11011)

Reference
1. Kenneth H Rosen. Discrete Mathematics and Its Applications with Combinatorics and
Graph Theory, 7th Edition, Tata McGraw Hill, 2017.

2
 MA4201: Mathematical Foundations of Computer Science MSc (M&SC), I Sem
Lecture-3
Department of Mathematics, NIT Warangal Scribe: Dr. Y. Sreenivasa Rao

Tautology. A compound proposition that is true in all possible cases.

Example. (i) p ∨ ¬p (ii) (p ∧ q) −→ (p ∨ q)
Contradiction. A compound proposition that is false in all possible cases.
Example. (i) p ∧ ¬p (ii) (p ←→ q) ∧ (¬p ∧ q)
Contingency. A compound proposition that is neither a tautology nor a contradiction.
Example. (p ∨ q) −→ ¬r
Logical Equivalence. Two compound propositions that have the same truth value in all
possible cases are called logically equivalent compound propositions.
Notation. Logical equivalence is denoted by ≡
We have already seen that (i) p −→ q ≡ ¬q −→ ¬p and (ii) q −→ p ≡ ¬p −→ ¬q
Result. Show that ¬(p ∧ q) ≡ ¬p ∨ ¬q
Exercise. (i) Show that ¬(p −→ q) is a logically equivalent to p ∧ ¬q
(ii) Show that p ⊕ q ≡ (¬p ∧ q) ∨ (p ∧ ¬q)
Some Important Logical Equivalences

Idempotent laws (i) p ∧ p ≡ p (ii) p ∨ p ≡ p

Double Negation law ¬(¬p) ≡ p
Commutative laws (i) p ∧ q ≡ q ∧ p (ii) p ∨ q ≡ q ∨ p
Associative laws (i) (p ∨ q) ∨ r ≡ p ∨ (q ∨ r) ≡ p ∨ q ∨ r
(ii) (p ∧ q) ∧ r ≡ p ∧ (q ∧ r) ≡ p ∧ q ∧ r
Distributive laws (i) p ∨ (q ∧ r) ≡ (p ∨ q) ∧ (p ∨ r)
(ii) p ∧ (q ∨ r) ≡ (p ∧ q) ∨ (p ∧ r)
DeMorgan laws (i) ¬(p ∧ q) ≡ ¬p ∨ ¬q (ii) ¬(p ∨ q) ≡ ¬p ∧ ¬q
Absorption laws (i) p ∨ (p ∧ q) ≡ p (ii) p ∧ (p ∨ q) ≡ p
Identity laws (i) p ∧ 1 ≡ p (ii) p ∨ 0 ≡ p
Domination laws (i) p ∧ 0 ≡ 0 (ii) p ∨ 1 ≡ 1
(i) p ∧ ¬p ≡ 0 (ii) p ∨ ¬p ≡ 1
p −→ q ≡ ¬p ∨ q
p ←→ q ≡ (p ∧ q) ∨ (¬p ∧ ¬q)

Note. p −→ q −→ r, p −→ (q −→ r), (p −→ q) −→ r are all different.

1
 ( )
Example. (i) Simplify ¬ p ∨ ¬(p ∧ q)
(ii) Simplify (p ∧ q) −→ (p ∨ q)
( )
(iii) Show that ¬ p ∨ (¬p ∧ q) ≡ ¬p ∧ ¬q
Example. Convert the following sentences into a compound proposition.
p : you get an A on the final exam.
q : you do every exercise in the book.
r : you get an A in this class.
(1) You get an A in this class, but you do not do every exercise in the book.
(2) To get an A in this class, it is necessary for you to get an A on the final.
(3) If you get an A on the final, but you do not do every exercise in the book, then you get an
A in this class.
(4) Getting an A on the final and doing every exercise in the book is sufficient for getting an A
in this class.
(5) You will get an A in this class if and only if you either do every exercise in the book or you
get an A on the final.
Example. Write english sentences for the following compound propositions.
p : X is playing cricket.
q : X is reading his book.
r : X is inside the room.
(1) p −→ ¬q (2)¬p ∧ ¬q (3) r −→ q (4) (r ∧ q) −→ ¬p (5) p −→ (¬q ∧ ¬r) (6) ¬(r ∧ q)
Topological Implication
Let P and Q be compound propositions. If P −→ Q is a tautology, we say that P tautologically
implies Q. Sometimes we denote it by P =⇒ Q (If P is true then Q is true).
Example. (i) p ∧ q =⇒ p
(ii) p ∧ q =⇒ q
(iii) p =⇒ p ∨ q
(iv) q =⇒ p ∨ q
(v) q =⇒ p −→ q (i.e., q −→ (p −→ q) is a tautology)
(vi) ¬p =⇒ p −→ q (i.e., ¬p −→ (p −→ q) is a tautology)

Reference
1. Kenneth H Rosen. Discrete Mathematics and Its Applications with Combinatorics and
Graph Theory, 7th Edition, Tata McGraw Hill, 2017.

2
 MA4201: Mathematical Foundations of Computer Science MSc (M&SC), I Sem
Lecture-4
Department of Mathematics, NIT Warangal Scribe: Dr. Y. Sreenivasa Rao

Predicates and Quantifiers

x
|{z} is greater than3
| {z }
variable/subject predicate

• We write P (x) : x is greater than 3.

Where x is a variable and
P is the predicate “is greater than 3”
We need to specify the universe of discourse (or universe or domain) for x denoted by U .
P (x) is the value of “the propositional function P at x”.
P (4) : 4 is greater than 3. (T )
P (1) : 1 is greater than 3. (F )

• Let Q(x, y) : x − y = 3, where universe for both x and y is R.

Then Q(1, 2) : 1 − 2 = 3. (F )

• P (x) is unary predicate .

• Q(x, y) is binary predicate.

• R(x1 , x2 , · · · , xn ) is an n-ary predicate (or n-place predicate).

• R(a1 , a2 , · · · , an ) is a proposition, where a1 , a2 , · · · , an ∈ U .

• If P (x1 , x2 , · · · , xn ) is true for all a1 , a2 , · · · , an ∈ U , then P (x1 , x2 , · · · , xn ) is said to be

valid in U .

• If P (x1 , x2 , · · · , xn ) is true for some a1 , a2 , · · · , an ∈ U , then P (x1 , x2 , · · · , xn ) is said to

be satisfiable in U .

• If P (x1 , x2 , · · · , xn ) is not true for all a1 , a2 , · · · , an ∈ U , then P (x1 , x2 , · · · , xn ) is said to

be unsatisfiable in U .

Converting predicates into propositions

(i) One can create a proposition from P (x, y) by binding variables x and y by giving values
to them.
1
 (ii) Binding variables using quantifiers
1. Universal quantifier (∀)
2. Existential quantifier (∃)

1. The universal quantification of P (x) is the statement ∀x P (x).

We read it as:
for all x P (x),
for every x P (x),
for each x P (x),
for arbitrary x P (x).
Truth Table for Universal quantifier

True False
∀x P (x) P (a) is true for every a ∈ U P (a) is false for some a ∈ U

Examples.
(1) Let U = Set of all integers.
P (x) : x + 1 > x,
Q(x) : x = 1,
R(x) : x = x + 1.
Then ∀x P (x) true, ∀x Q(x) False, ∀x R(x) False.
(2) Let U = {1, 2, 3, 4}
P (x) : x is even,
Q(x) : x ̸= 5,
Then ∀x P (x) false, ∀x Q(x) true.
2. The existential quantification of P (x) is the statement ∃x P (x).
We read it as :
There exists x such that P (x),
For some x P (x).
Truth Table for existential quantifier

True False
∃x P (x) P (a) is true for some a ∈ U P (a) is false for every a ∈ U

Examples.
(1) Let U = Set of all integers.
P (x) : x + 1 > x,
2
Q(x) : x = 1,
R(x) : x = x + 1.
Then ∃x P (x) true, ∃x Q(x) true, ∃x R(x) False.
(2) Let U = {1, 2, 3, 4}
P (x) : x > 5
Q(x) : x is even,
Then ∃x P (x) false, ∃x Q(x) true.
Terminology.

(i) P (x, y, z) is a trinary predicate,

because all the three x, y, z are free variables.

(ii) ∀x P (x, y, z) is a binary predicate,

because x is bound and y, z are free variables

(iii) ∃y∀x P (x, y, z) is a unary predicate,

because x, y are bounds and z is a free variable

(iv) ∃y∀x P (x, y, 5) is a proposition

Scope of a quantifier
The part of a logical expression to which the quantifier is applied.
Example. (1) ∃x P (x)
The scope of ∃x is P (x).
( )
(2) ∃x P (x) ∧ Q(x) ∨ ∀x R(x)
The scope of ∃x is P (x) ∧ Q(x) and the scope of ∀x is R(x).
Note. The following are tautological implications corresponding to quantifiers.
(i) ∀x P (x) =⇒ P (c) where c is arbitrary element of U .
(ii) P (c) =⇒ ∃x P (x) for some c.
(iii) ∀x P (x) =⇒ ∃x P (x)
Expressing quantifiers using conjunctions and disjunctions
(1) If U = {a1 , a2 , · · · , an }. Then
∀x P (x) ≡ P (a1 ) ∧ P (a2 ) ∧ · · · ∧ P (an )
∃x P (x) ≡ P (a1 ) ∨ P (a2 ) ∨ · · · ∨ P (an )
(2) If U = {a1 , a2 , · · · }. Then
∀x P (x) ≡ P (a1 ) ∧ P (a2 ) ∧ · · ·
∃x P (x) ≡ P (a1 ) ∨ P (a2 ) ∨ · · ·
Note. ∀y P (x, z) ≡ ∃y P (x, z) ≡ P (x, z)
3
Example. Translate the following sentences into logical expression.
(1) All students are clever.
(2) Some students are clever.
Note. Let U = set of all real numbers. Then
(1) ∀x < 0(x2 > 0) ≡ ∀x(x < 0 −→ x2 > 0)
(2) ∀y ̸= 0(y 3 ̸= 0) ≡ ∀y(y ̸= 0 −→ y 3 ̸= 0)
(3) ∃z > 0(z 2 = 2) ≡ ∃z(z > 0 ∧ z 2 = 2)
Exercise. Translate the following sentences into logical expression.
(1) All prime integers are positive.
Answer. ∀x (P (x) → Q(x))
(2) Not all primes are odd.
Answer. ¬∀x (P (x) → R(x))
(3) Every integer is even or odd.
Answer. ∀x (E(x) ∨ R(x))

Reference
1. Kenneth H Rosen. Discrete Mathematics and Its Applications with Combinatorics and
Graph Theory, 7th Edition, Tata McGraw Hill, 2017.

4
 MA4201: Mathematical Foundations of Computer Science MSc (M&SC), I Sem
Lecture-5
Department of Mathematics, NIT Warangal Scribe: Dr. Y. Sreenivasa Rao

Logical equivalences involving quantifiers

( )
(1) ∀x P (x) ∧ Q(x) ≡ ∀x P (x) ∧ ∀x Q(x)
(Distributivity of ∀ over ∧)
Note. ∀ and ∃ has highest priority than ¬, ∨, ∧, −→, ←→.
( )
(2) ∀x P (x) ∨ Q(x) ̸≡ ∀x P (x) ∨ ∀x Q(x)
Example. Let E(x) : x is even
O(x) : x is odd.
Then
( )
∀x E(x) ∨ O(x) : every integer is even or odd. (T )
∀x E(x) ∨ ∀x O(x) : all integers are even or all integers are odd. (F )
( )
∴ ∀x E(x) ∨ O(x) ̸≡ ∀x E(x) ∨ ∀x O(x)
( )
Note. ∀x P (x) ∨ Q(x) ⇐= ∀x P (x) ∨ ∀x Q(x)
( )
(3) ∃x P (x) ∨ Q(x) ≡ ∃x P (x) ∨ ∃x Q(x)
(distributivity of ∃ over disjunction ∨)
( )
(4) ∃x P (x) ∧ Q(x) ̸≡ ∃x P (x) ∧ ∃x Q(x)
( )
Note. ∃x P (x) ∧ Q(x) =⇒ ∃x P (x) ∧ ∃x Q(x)

(5) ¬∀x P (x) ≡ ∃x ¬P (x)

(6) ¬∃x P (x) ≡ ∀x ¬P (x)

Example. (i) ¬∀x(x2 > x) ≡ ∃x¬(x2 > x) ≡ ∃x(x2 ≤ x)

(ii) ¬∃x(x2 = 2) ≡ ∀x¬(x2 = 2) ≡ ∀x(x2 ̸= 2)
( ) ( )
Exercise. Show that ¬∀x P (x) −→ Q(x) ≡ ∃x P (x) ∧ ¬Q(x)
( )
(7) i) ∀x P (x) ∧ q ≡ ∀x P (x) ∧ q
( )
ii) ∃x P (x) ∧ q ≡ ∃x P (x) ∧ q
( )
(8) i) ∀x P (x) ∨ q ≡ ∀x P (x) ∨ q
( )
ii) ∃x P (x) ∨ q ≡ ∃x P (x) ∨ q

1
Reference
1. Kenneth H Rosen. Discrete Mathematics and Its Applications with Combinatorics and
Graph Theory, 7th Edition, Tata McGraw Hill, 2017.

2
 MA4201: Mathematical Foundations of Computer Science MSc (M&SC), I Sem
Lecture-6
Department of Mathematics, NIT Warangal Scribe: Dr. Y. Sreenivasa Rao

Nested Quantifiers. Two quantifiers are said to be nested if one is within the scope of the
other.
Example. ∃x∀yP (x, y), here the scope of ∃x is ∀yP (x, y).
Note. 1. ∀x∀yP (x, y) ≡ ∀y∀xP (x, y)
2. ∃x∃yP (x, y) ≡ ∃y∃xP (x, y)
3. ∃x∀yP (x, y) ̸≡ ∀y∃xP (x, y)
Example. P (x, y) : x2 = y where Ux = {2, 3, 4} and Uy = {4, 9, 16}
Truth value of ∃x∀yP (x, y) is False. (check this!)
Truth value of ∀y∃xP (x, y) is True. (check this!)
Note. ∃x∀yP (x, y) =⇒ ∀y∃xP (x, y). (for some a, ∀yP (a, y) true =⇒ ∀y∃xP (x, y) true)
Example. Express the definition of a limit using quantifiers.
Example. Express the fact that limx→a f (x) does not exist, with the help of quantifiers and
predicates.
Example. Express the negation of the statement ∃x∀y∃z (x + y + z ≥ 10) so that no negation
precedes a quantifier.

Reference
1. Kenneth H Rosen. Discrete Mathematics and Its Applications with Combinatorics and
Graph Theory, 7th Edition, Tata McGraw Hill, 2017.

1
 MA4201: Mathematical Foundations of Computer Science MSc (M&SC), I Sem
Lecture-7
Department of Mathematics, NIT Warangal Scribe: Dr. Y. Sreenivasa Rao

Rules of Inference
Argument form (in propositional logic). A sequence of compound propositions

H , H , · · · , Hn , C
|{z}
| 1 2{z }
premises conclusion

involving propositional variables.

Notation. We use the following notation to write an argument form

H1
H2
..
.
Hn
∴C

Definition. The argument form H1 , H2 , · · · , Hn , C is said to be valid if

H1 ∧ H2 ∧ · · · ∧ Hn =⇒ C

i.e., H1 ∧ H2 ∧ · · · ∧ Hn −→ C is a tautology.

Checking validity of an argument form.

1. By constructing a truth table

2. By using rules of inference

1
Rules of inferences (in propositional logic)

H1 : p
p ∧ (p → q) =⇒ q
1. H2 : p→q Modus ponens ( )
i.e., p ∧ (p → q) → q is a tautology
∴C : q
H1 : ¬q
2. H2 : p→q Modus tollens ¬q ∧ (p → q) =⇒ ¬p
∴C : ¬p
H1 : p→q
3. H2 : q→r Hypothetical syllogism (p → q) ∧ (q → r) =⇒ p → r
∴C : p→r
H1 : p∨q
4. H2 : ¬p Disjunctive syllogism (p ∨ q) ∧ ¬p =⇒ q
∴C : q
H1 : p
5. Addition p =⇒ p ∨ q
∴C : p∨q
H1 : p∧q
6. Simplification p ∧ q =⇒ p
∴C : p
H1 : p
7. H2 : q Conjunction (p) ∧ (q) =⇒ p ∧ q
∴C : p∧q
H1 : p∨q
8. H2 : ¬p ∨ r Resolution (p ∨ q) ∧ (¬p ∨ r) =⇒ q ∨ r
∴C : q∨r

Example. Check the validity of the following argument.

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.
Therefore, we will be at home by sunset.

Fallacies

(i) The fallacy of affirming the conclusion

(p → q) ∧ q =⇒ p is not valid.
( )
(p → q) ∧ q → p is not a tautology.
2
 Because it is false when p is 0, and q is 1.

Example
If you do every problem in this book, then you will learn Discrete Maths.
you learnt discrete maths.
————————————————————————————————-
Therefore, you did every problem in this book.
————————————————————————————————-
This is not a valid argument.

(ii) The fallacy of denying the hypothesis

(p → q) ∧ ¬p =⇒ ¬q is not valid.
( )
(p → q) ∧ ¬p → ¬q is not a tautology.
Because it is false when p is 0, and q is 1.
Example
If you do every problem in this book, then you will learn Discrete Maths.
you did not do every problem in the book.
————————————————————————————————-
Therefore, you did not learn discrete maths.
————————————————————————————————-
which is not a valid argument.

First Order Logic. The predicate logic in which the quantification takes place over variables
only.
Example. ∀x P (x), ∃x∀y P (x, y)
Second Order Logic. Which is the extension of first order logic obtained by introducing
quantification of predicates.
Example. ∀P ∃x P (x)
Exercise. Validate the following argument.
(1) If today is tuesday, I have a test in MFCS or Algebra.
(2) If my Algebra professor is sick, I will not have a test in Algebra.
(3) Today is tuesday and my Algebra professor is sick.
————————————————————————————
∴ I have a test in MFCS.
Reference
1. Kenneth H Rosen. Discrete Mathematics and Its Applications with Combinatorics and
Graph Theory, 7th Edition, Tata McGraw Hill, 2017.
3
 MA4201: Mathematical Foundations of Computer Science MSc (M&SC), I Sem
Lecture-8
Department of Mathematics, NIT Warangal Scribe: Dr. Y. Sreenivasa Rao

Rules of inference involving quantifiers

∀x P (x)
∴ P (c)
1. Universal instantiation
c is an arbitrary element in U .

P (c) for arbitrary c ∈ U

2. ∴ ∀x P (x) Universal generalization

∃x P (x)
3. ∴ P (c) for some c ∈ U Existential instantiation

P (c) for some c ∈ U

4. ∴ ∃x P (x) Existential generalization

Example. Show that the premises

(1) A student in this class has not read the book.
(2) Everyone in this class passed the exam
imply the conclusion, someone who passed the exam has not read the book.

Example. Check the validity of the following argument.

(1) Every living thing is a plant or animal.
(2) Alice’s cow is alive and it is not a plant.
(3) All animals have hearts.
—————————————————————
∴ Alice’s cow has a heart.

1
 Universal modus ponens
( )
∀x P (x) → Q(x)
P (a) (where a is a particular element of U )
——————————————————————–
∴ Q(a) .
Universal modus tollens
( )
∀x P (x) → Q(x)
¬Q(a) (where a is a particular element of U )
—————————————————————–
∴ ¬P (a)

Example.
( )
∀x P (x) ∨ Q(x) .
( )
∀x ¬Q(x) ∨ S(x) .
( )
∀x R(x) → ¬S(x)
∃x¬P (x)
———————————-
∴ ∃x¬R(x) .

Reference
1. Kenneth H Rosen. Discrete Mathematics and Its Applications with Combinatorics and
Graph Theory, 7th Edition, Tata McGraw Hill, 2017.

2
 MA4201: Mathematical Foundations of Computer Science MSc (M&SC), I Sem
Lecture-9
Department of Mathematics, NIT Warangal Scribe: Dr. Y. Sreenivasa Rao

Resolution Principle
Literal. A variable or the negation of a variable.
Example. p, ¬p, q, ¬q, · · ·
Product. Conjunction of literals.
Sum. Disjunction of literals.
Clause. A disjunction of literals, e.g., p ∨ ¬q, ¬q ∨ r ∨ s, etc.
Note. (i) The complementary of a literal p is ¬p.
(ii) The complementary of a literal ¬p is p.
Resolvent of two clauses C1 and C2 (containing a pair of complementary literals)

C1 = p ∨ q ∨ r
C2 = ¬p ∨ ¬s ∨ t

∴ Resolvent of C1 and C2 , C = q ∨ r ∨ ¬s ∨ t
Note. We can apply Resolvent rule only when one clause has a complementary literal of some
literal existed in the other clause.
Theorem: Given two clauses C1 , C2 , a resolvent C of C1 and C2 is a logical consequence of C1
and C2 . (that is, if C1 and C2 are true, then C is true. C1 ∧ C2 =⇒ C)
The resolution principle: Given a set S of clauses, a (resolution) deduction of C from S is a
finite sequence C1 , C2 , · · · , Ck of clauses such that each Ci either is a clause in S or a resolvent
of clauses preceding C and Ck = C.
A deduction of (empty clause) is called a refutation or a proof of S.
Problem Solving Technique.

1. Put each Hi in clause form and add to it ¬C in clause form.

2. Try to derive (empty clause) from these sequence of clauses, using Resolution Principle.

3. If it is possible, the given argument form is valid. Else, not valid.

Example. Show that the following argument is correct using the resolution principle.
If today is tuesday, I have a test in in MFCS or Algorithms.
If my Algorithms professor is sick, I will not have a test in Algorithms.
1
Today is tuesday and my Algorithms professor is sick.
Therefore, I have a test in MFCS.
Example.
(1) p → (q ∨ r)
(2) p ∧ ¬q
(3) r → s
————————-
∴s
————————-
Reference
1. Kenneth H Rosen. Discrete Mathematics and Its Applications with Combinatorics and
Graph Theory, 7th Edition, Tata McGraw Hill, 2017.

2
 MA4201: Mathematical Foundations of Computer Science MSc (M&SC), I Sem
Lecture-10
Department of Mathematics, NIT Warangal Scribe: Dr. Y. Sreenivasa Rao

1. Normal Forms (in propositional logic)

Well formed formula (wff ). A string consisting of propositional variables p, q, r, · · · , connec-

tives ¬, ∨, ∧, →, ↔ and parentheses used in the proper manner.
( ) ( )
Example. (i) (p ∨ q) ∧ (q → r) ∨ ¬p → (q ∧ r ∧ s) is a wff.
(ii) ¬p ∧ q → r ∧ s is not wff.
Literal. A variable or the negation of a variable.
Eg. p, ¬p, q, ¬q, · · ·
Elementary Product. Conjunction of literals.
Eg. p ∧ ¬q ∧ r
Elementary Sum. Disjunction of literals.
Eg. p ∨ ¬p ∨ q

(i) Disjunctive Normal Form (DNF). Sum of elementary products.

Eg. (p ∧ ¬q) ∨ (p ∧ q) ∨ (p ∧ ¬r)

(ii) Conjunctive Normal Form (CNF). Product of elementary sums.

Eg. (p ∨ q) ∧ (p ∨ ¬r) ∧ (p ∨ ¬q) ∧ (r ∨ p)

Example. Obtain DNF of ¬(p ∧ q) ↔ (p ∨ q)

Note. DNF is not unique.

(p ∧ q) ∨ r ≡ (p ∨ r) ∧ (q ∨ r)
≡ [(p ∨ r) ∧ q] ∨ [(p ∨ r) ∧ r]
≡ (p ∧ q) ∨ (r ∧ q) ∨ (p ∧ r) ∨ (r ∧ r)

Example. Obtain CNF of ¬(p ∧ q) ↔ (p ∨ q)

Observation.
(1). An elementary product is identically false (a contradiction) iff the product contains at least
one pair of complementary literals.
Eg. (i) p ∧ q ∧ r ∧ ¬p ≡ 0
(ii) p ∧ · · · ∧ ¬p ∧ · · · ≡ 0

1
(2). An elementary sum is identically true (a tautology) iff the sum contains at least one pair
of complementary literals.
Eg. (i) p ∨ q ∨ s ∨ ¬q ≡ 1
(ii) q ∨ · · · ∨ ¬q ∨ · · · ≡ 1
Reference
1. Kenneth H Rosen. Discrete Mathematics and Its Applications with Combinatorics and
Graph Theory, 7th Edition, Tata McGraw Hill, 2017.

2
 MA4201: Mathematical Foundations of Computer Science MSc (M&SC), I Sem
Lecture-11
Department of Mathematics, NIT Warangal Scribe: Dr. Y. Sreenivasa Rao

1. Principal Normal Forms

(1) Principal DNF.

Let p and q be two propositional variables.

Minterm. A conjunction in which each variable occurs once either in the negated form or
in the non-negated form.

Note. (i) Minterms containing p and q variables: p ∧ q, p ∧ ¬q, ¬p ∧ q, ¬p ∧ ¬q.

(ii) For n variables, we can write 2n minterms.

Principal DNF. For a given formula, an equivalent formula consisting of disjunctions of

minterms only is known as its principal DNF. Such a normal form is also called sum-of-
products canonical form.

Eg. p ↔ q ≡ (p ∧ q) ∨ (¬p ∧ ¬q)

∑
Eg. p ∨ ¬q ≡ (p ∧ q) ∨ (p ∧ ¬q) ∨ (¬p ∧ ¬q) ≡ 0, 2, 3

Note. Minterms are binary representation of the numbers from 0 to 2n − 1, for n variables.

Converting wff into Principal DNF.

• Replace →, ↔ by using ∨, ∧, ¬

• Use DeMorgans’ laws, distribution laws etc. (if necessary)

• Drop an elementary product that is a contradiction

• Introduce missing variables in each conjunction as follows.

p = p ∧ 1 = p ∧ (q ∨ ¬q)

• Delete duplications

Example. Convert p ∨ (¬p → (¬q → r)) into Principal DNF.

(2) Principal CNF

Maxterm. Dual of a minterm.
Eg. p ∨ q, p ∨ ¬q, ¬p ∨ q, ¬p ∨ ¬q, for two variables p and q.

1
 Principal CNF. Conjunction of maxterms. (Product of sums canonical form)
∏
Eg. p ↔ q ≡ (¬p ∨ q) ∧ (p ∨ ¬q) ≡ 1, 2

Example. Find the principal CNF of (p → q) → (q → p).

Example. Find the principal DNF of (p → q) → (q → p).

Example. Find the principal CNF of p ∨ (¬p → (¬q → r)).

Reference
1. Kenneth H Rosen. Discrete Mathematics and Its Applications with Combinatorics and
Graph Theory, 7th Edition, Tata McGraw Hill, 2017.

2
 MA4201: Mathematical Foundations of Computer Science MSc (M&SC), I Sem
Lecture-12
Department of Mathematics, NIT Warangal Scribe: Dr. Y. Sreenivasa Rao

1. Normal Forms in First Order logic

Prenex Normal Form

F ≡ (Q1 x1 )(Q2 x2 ) · · · (Qn xn ) (M )

| {z } |{z}
pref ix matrix

where M is aformula containing no quantifiers, called matrix of the formula F.


∀xi
Each Qi xi =

∃xi
Eg. (∃z)(∀x)(∃y)(P (x, y) ∨ Q(y, z))
Conversion of a given formula to prenex normal form.
During conversion, we use the following rules if necessary.
(1) ∀x F1 (x) ∨ ∀x F2 (x) ̸= ∀x (F1 (x) ∨ F2 (x))
Technique:

∀x F1 (x) ∨ ∀x F2 (x) = ∀x F1 (x) ∨ ∀y F2 (y) renaming variables

= ∀x∀y (F1 (x) ∨ F2 (y))

(2) ∃x F1 (x) ∧ ∃x F2 (x) ̸= ∃x (F1 (x) ∧ F2 (x))

Technique:

∃x F1 (x) ∧ ∃x F2 (x) = ∃x F1 (x) ∧ ∃y F2 (y)

= ∃x∃y (F1 (x) ∧ F2 (y))

If G does not contain x, then we have the following rules.

(3) ∀xF (x) ∧ G ≡ ∀x(F (x) ∧ G)
(4) ∀xF (x) ∨ G ≡ ∀x(F (x) ∨ G)
(5)∃xF (x) ∧ G ≡ ∃x(F (x) ∧ G)
(6) ∃xF (x) ∨ G ≡ ∃x(F (x) ∨ G)

1
 Problem solving procedure.

• Replace →, ↔ using ∨, ∧, ¬

• Use ¬¬, DeMorgans’ laws etc. repeatedly (if necessary)

• Rename variables (if necessary)

• Use the above rules (1) to (6) to bring the quantifiers to the left

Example. Convert the wff

∀x P (x) → ∃x Q(x)

into prenex normal form.

Example. Convert the wff
( )
∀x (∃yR(x, y) ∧ ∀y¬S(x, y)) → ¬(∃yR(x, y) ∧ p)

into prenex normal form.

Reference
1. Kenneth H Rosen. Discrete Mathematics and Its Applications with Combinatorics and
Graph Theory, 7th Edition, Tata McGraw Hill, 2017.

2
 MA4201: Mathematical Foundations of Computer Science MSc (M&SC), I Sem
Lecture-17
Department of Mathematics, NIT Warangal Scribe: Dr. Y. Sreenivasa Rao

1. Basic Counting Techniques

Recall: For a finite set A, |A| is the cardinality of A that is the number of elements of A.
For a pair of sets A and B, A × B is their cartesian product:

A × B = {(a, b) | a ∈ A ∧ b ∈ B}

Product rule (in sets): If A and B are finite sets, then |A × B| = |A| · |B|.
If one event can occur in n1 ways and another event can occur in n2 ways, then there are
n1 × n2 ways in which these two events can occur.
General product rule: For any m ∈ N, if A1 , A2 , . . . , Am are finite sets, then

|A1 × A2 × · · · × Am | = |A1 | · |A2 | · · · |Am |

Example 1. How many bit strings of length seven are there?

Example 2. How many different car license plates can be made if each plate contains a sequence
of three uppercase English letters followed by three digits?
Example 3 (Counting functions). Let A and B be two finite sets. Let B A be the set of all
 
functions from A to B. Then, B A  = |B||A|
Example 4 (Counting injective functions). Let A and B be finite sets with |A| = n and
|B| = m. Then, the number of injective functions from A to B is

m · (m − 1) · (m − 2) · · · (m − n + 1)

Sum Rule: If A and B are finite sets that are disjoint (meaning A ∩ B = ∅), then

|A ∪ B| = |A| + |B|

If a task can be done either in one of |A| = m ways or in one of |B| = n ways, where none of
the set of m ways is the same as any of the set of n ways, then there are m + n ways to do the
task.
Example 5. Suppose variable names in a programming language can be either a single up-
percase letter or an uppercase letter followed by a digit. Find the number of possible variable
names.
1
Example 6. Each user on a computer system has a password which must be six to eight
characters long.
Each character is an uppercase letter or digit.
Each password must contain at least one digit.
How many possible passwords are there?
Principle of Inclusion-Exclusion for Two Sets (Subtraction Rule): For any two finite
sets A and B (not necessarily disjoint), |A ∪ B| = |A| + |B| − |A ∩ B|.
Example 7. How many bit strings of length 8 either start with a 1 bit or end with the two bits
00 ?
Theorem 1 (The Pigeonhole Principle). For any positive integer k, if k+1 objects (pigeons)
are placed in k boxes (pigeonholes), then at least one box contains two or more objects. The
Pigeonhole Principle (rephrased more formally): If a function f : A → B maps a finite
set A with |A| = k + 1 to a finite set B with |B| = k, then f is not injective.
Example 8. Among any group of 367 people, there must be at least two with the same birthday,
because there are only 366 possible birthdays.
Question 1. How many students must be in a class to guarantee that at least two students
receive the same score on the final exam, if the exam is graded on a scale from 0 to 100 points?
Application. Given a sequence of n integers a1 , a2 , . . . , an , there exist consecutive a’s in the
sequence whose sum is divisible by n,
i.e., ∃ i,j with 1 ≤ i ≤ j ≤ n such that ai+1 + ai+2 + · · · + aj is divisible by n.
Application. A man hiked for 10 hours and covered a total distance of 45kms. It is known
that he hiked 6kms in the first hour and only 3kms in the last hour. Show that he must have
hiked at least 9kms within a certain period of two consecutive hours.
Application. Show that among any n + 1 positive integers not exceeding 2n there must be an
integer that divides one of the other integers.
Application. Show that given any n + 2 integers there exist two of them whose sum or differ-
ence is divisible by 2n.
Generalized pigeonhole principle. If N objects are placed into k boxes, then there is at
least one box containing at least ⌈N/k⌉ objects.
Example 9. Assume 100 people. Can you tell something about the number of people born in
the same month?

Reference
1. Kenneth H Rosen. Discrete Mathematics and Its Applications with Combinatorics and
Graph Theory, 7th Edition, Tata McGraw Hill, 2017.
2
 MA4201: Mathematical Foundations of Computer Science MSc (M&SC), I Sem
Lecture-18
Department of Mathematics, NIT Warangal Scribe: Dr. Y. Sreenivasa Rao

1. The Pigeonhole Principle

Theorem 1 (The Pigeonhole Principle). For any positive integer k, if k+1 objects (pigeons)
are placed in k boxes (pigeonholes), then at least one box contains two or more objects. The
Pigeonhole Principle (rephrased more formally): If a function f : A → B maps a finite
set A with |A| = k + 1 to a finite set B with |B| = k, then f is not injective.
Example 8. Among any group of 367 people, there must be at least two with the same birthday,
because there are only 366 possible birthdays.
Question 1. How many students must be in a class to guarantee that at least two students
receive the same score on the final exam, if the exam is graded on a scale from 0 to 100 points?
Application. Given a sequence of n integers a1 , a2 , . . . , an , there exist consecutive a’s in the
sequence whose sum is divisible by n,
i.e., ∃ i,j with 1 ≤ i ≤ j ≤ n such that ai+1 + ai+2 + · · · + aj is divisible by n.
Application. Show that among any n + 1 positive integers not exceeding 2n there must be an
integer that divides one of the other integers.
Application. Show that given any n+2 integers there exist two of them whose sum or difference
is divisible by 2n.
Generalized pigeonhole principle. If N objects are placed into k boxes, then there is at
least one box containing at least ⌈N/k⌉ objects.
Example 9. Assume 100 people. Can you tell something about the number of people born in
the same month?
Reference
1. Kenneth H Rosen. Discrete Mathematics and Its Applications with Combinatorics and
Graph Theory, 7th Edition, Tata McGraw Hill, 2017.

1
 MA4201: Mathematical Foundations of Computer Science MSc (M&SC), I Sem
Lecture-19
Department of Mathematics, NIT Warangal Scribe: Dr. Y. Sreenivasa Rao

1. Permutations

Definition 1. Let S be a set of distinct objects. Any ordered arrangement of the objects of
S is called a permutation. An ordered arrangement of r elements of S is called an r-permutation.

Example 10. Let S = {a, b, c}. The ordered arrangement b, a, c is a permutation of S. The
ordered arrangement c, b is a 2-permutation of S. The ordered arrangement c is a 1 permutation
of S.

Fact 1. Let n, r ∈ N such that r ≤ n. Then the number of r-pernutations of a set with n
elements is denoted by P (n, r) and is given by P (n, r) = n(n − 1)(n − 2) · · · (n − r + 1).

n!
Fact 2. P (n, r) =
(n − r)!

Note: Now, we can define P (n, r) for r = 0. P (n, 0) = 1. Also, note that P (n, n) = n!.

Example 11. Suppose that a salesman has to visit eight different cities. He must begin
his trip in a specified city, but he can visit the other seven cities in any order he wishes. How
many possible orders can the salesman use when visiting these cities?

Example 12. How many permutations of the letters A, B, C, D, E, F, G, H contain the

string ABC? (when all the letters are used)

2. Combinations

Definition 2. Let S be a set with n elements and 0 ≤ r ≤ n. An r-combination of elements

of S is an unordered selection of r elements from S. Thus, an r-combination is simply a subset
with r elements.
(n)
The number of r-combinations of a set with n distinct elements is denoted by C(n, r) or r .

1
Example 13. Let S = {1, 2, 3, 4}. All possible 3-combinations of the elements of S are
{1, 2, 3}, {1, 2, 4}, {2, 3, 4} and {1, 3, 4}.
The following theorem will give you the relation between P (n, r) and C(n, r).

Theorem 2. Let n and r be two non-negative integers with r ≤ n. Then,

P (n, r) n!
C(n, r) = =
P (r, r) r!(n − r)!

Example 14. How many poker hands of five cards can be dealt from a standard deek of 52
cards? Also, how many ways are there to select 47 cards from a standard deck of 52 cards?

Theorem 3. Let n and r be two non-negative integers with r ≤ n. Then, C(n, r) = C(n, n − r).

Example 15 . How many bit strings of length n contain exactly r1 s?

Example 16. Suppose that there are 9 faculty members in the mathematics department and
11 in the computer science department. How many ways are there to select a committee to
develop a discrete mathematics course at a school if the committee is to consist of three faculty
members from the mathematics department and four from the computer science department?

Reference
1. Kenneth H Rosen. Discrete Mathematics and Its Applications with Combinatorics and
Graph Theory, 7th Edition, Tata McGraw Hill, 2017.

2
 MA4201: Mathematical Foundations of Computer Science MSc (M&SC), I Sem
Lecture-20
Department of Mathematics, NIT Warangal Scribe: Dr. Y. Sreenivasa Rao

1. Pascal’s Identity and Vandermonde’s Identity

A binomial expression is simply the sum of two terms, such as x + y. The binomial theorem
( )
gives the coefficients of the expansion of powers of binomial expressions. The number nr is
called a binomial coefficient because these numbers occur as coefficients in the expansion of
powers of binomial expressions such as (x + y)n .

Theorem 4 (The Binomial Theorem). Let x and y be variables, and let n be a nonneg-
ative integer. Then
( ) ( ) ( ) ( ) ( )
n n n n−1 n n−2 2 n n n
n
(x + y) = x + x y+ x y + ··· + xy n−1
+ y
0 1 2 n−1 n
∑n ( )
n n−r r
= x y
r
r=0

Example 17. What is the coefficient of x12 y 13 in the expansion of (x + y)25 ?

Example 19. What is the coefficient of x12 y 13 in the expansion of (2x − 3y)25 ?

Corollaries
1. Let n be a non-negative integer. Then
n ( )
∑ n
= 2n
r
r=0

2. Let n be a positive integer. Then

∑
n ( )
n
r
(−1) =0
r
r=0

That is, ( ) ( ) ( ) ( ) ( ) ( )
n n n n n n
+ + + ··· = + + + ···
0 2 4 1 3 5
3. Let n be a non-negative integer. Then

∑
n ( )
r n
2 = 3n
r
r=0
1
 Figure 1: Pascal’s Triangle.

Theorem 6 (Pascal’s Identity). Let n and r be positive integers with n ≥ r. Then

( ) ( ) ( )
n+1 n n
= +
r r−1 r

Two different combinatorial proofs of the Pascal’s identity will be discussed in the class.

(n )
Exercise 1. Prove the Pascal’s identity by algebraic manipulation from the formula for r .

(n )
Remark 1. Pascal’s identity, together with the initial conditions r can be used to recur-
sively define binomial coefficients. This recursive definition is useful in the computation of
binomial coefficients because only addition (and not multiplication ) of integers is needed to use
this recursive definition.
Pascal’s identity is the basis for a geometric arrangement of the binomial coefficients in a
triangle, as shown in Figure 1. This triangle is known as Pascal’s triangle. The nth row in the
( )
triangle consists of the binomial coefficients nr , r = 0, 1, 2, . . ..

2
Theorem 7 (Vandermonde’s Identity). Let m, n, and r be non-negative integers with
r not exceeding either m or n. Then
( ) ∑r ( )( )
m+n m n
=
r r−k k
k=0

Corollary 8. If n is a non-negative integer, then

( ) ∑ n ( )2
2n n
=
n k
k=0

Proof. Use Vandermonde’s identity with m = r = n.

Reference
1. Kenneth H Rosen. Discrete Mathematics and Its Applications with Combinatorics and
Graph Theory, 7th Edition, Tata McGraw Hill, 2017.

3
 MA4201: Mathematical Foundations of Computer Science MSc (M&SC), I Sem
Lecture-21
Department of Mathematics, NIT Warangal Scribe: Dr. Y. Sreenivasa Rao

Example (Pigeonhole Principle). During a month with 30 days, a baseball team plays at
least one game a day, but no more than 45 games. Show that there must be a period of some
number of consecutive days during which the team must play exactly 14 games.

1. Generalized Permutations and Combinations

In many counting problems, elements may be used repeatedly. For instance, a letter or digit
may be used more than once on a license plate. In this section, we will show how to solve
counting problems where elements may be used more than once.

Theorem 9 (Permutations with Repetition). The number of r-permutations of a set

of n objects with repetition allowed is nr .

Example. How many strings of length r can be formed from the uppercase letters of the
English alphabet?

Theorem 10 (Combinations with Repetition). When repetition of elements is allowed, we

( )
can generate n−1+r
r number of r-combinations from a set with n elements.

Example. How many ways are there to select four fruits from a bowl containing apples,
oranges, and pears if the order in which the fruits are selected does not matter, only the type
of fruit matters, and there are at least four fruits of each type of fruit in the bowl?

Example. How many ways are there to select five coins from a cash box containing 1 ru-
pee coins, 2 rupee coins, 5 rupee coins, 10 rupee coins, 20 rupee coins, 50 rupee coins, and 100
rupee coins? Assume that the order in which the coins are chosen does not matter, that the
coins of each denomination are indistinguishable, and that there are at least five coins of each
type.

Example. Let x1 , x2 and x3 be three non-negative integers. How many solutions does the
equation x1 + x2 + x3 = 11 have?
1
Example. Let x1 , x2 and x3 be integers with x1 ≥ 1, x2 ≥ 2 and x3 ≥ 3. How many so-
lutions does the equation x1 + x2 + x3 = 11 have?

Reference
1. Kenneth H Rosen. Discrete Mathematics and Its Applications with Combinatorics and
Graph Theory, 7th Edition, Tata McGraw Hill, 2017.

2
 MA4201: Mathematical Foundations of Computer Science MSc (M&SC), I Sem
Lecture-22
Department of Mathematics, NIT Warangal Scribe: Dr. Y. Sreenivasa Rao

Some elements may be indistinguishable (i.e., identical) in counting problems. When this is
the case, care must be taken to avoid counting things more than once.
Theorem 11 (Permutations with Identical Objects). There are n objects in which n1
indistinguishable objects of type-1, n2 indistinguishable objects of type-2, . . ., and nk indistin-
guishable objects of type-k such that n1 + n2 + · · · + nk = n. Then the number of different
n!
permutations of the n objects is .
n1 ! n2 ! · · · nk !

Example. How many different strings can be made by reordering the letters at the word
SUCCESS?

1. Principle of Inclusion-Exclusion for n sets

Let S be a set and A1 , A2 , . . . , An be its subsets. Then,

|A1 ∪ A2 ∪ · · · ∪ An |
∑n ∑ ∑
= |Ai | − |Ai ∩ Aj | + |Ai ∩ Aj ∩ Ak | − · · · + (−1)n−1 |A1 ∩ A2 ∩ · · · ∩ An |
i=1 1≤i<j≤n 1≤i<j<k≤n

Example. Find the number of positive integers n such that 1 ≤ n ≤ 100 and n is not divisible
by 2, 3, or 5.

Exercise. How many integers between 1 and 300 (inclusive) are

(i) divisible by at least one of 5, 6, 8?
(ii) divisible by none of 5, 6, 8?

Example. Find the number of non-negative integer solutions of the equation

x1 + x2 + x3 + x4 = 18

satisfying the conditions x1 ≤ 7, x2 ≤ 7, x3 ≤ 7, x4 ≤ 7.

1
Exercise. Find the number of integer solutions of the equation

x1 + x2 + x3 = 20

satisfying the conditions 2 ≤ x1 ≤ 5, 4 ≤ x2 ≤ 7, −2 ≤ x3 ≤ 9.

Reference
1. Kenneth H Rosen. Discrete Mathematics and Its Applications with Combinatorics and
Graph Theory, 7th Edition, Tata McGraw Hill, 2017.

2
 MA4201: Mathematical Foundations of Computer Science MSc (M&SC), I Sem
Lecture-23
Department of Mathematics, NIT Warangal Scribe: Dr. Y. Sreenivasa Rao

Terminology. distinguishable = different = labeled

indistinguishable = same = unlabeled

1. Balls-to-Bins Problem

Many counting problems can be solved by enumerating the ways balls (a.k.a. objects) can be
placed into bins (where the order these balls are placed into the bins does not matter). The balls
can be either distinguishable (i.e., different from each other) or indistinguishable (i.e., identical).
Similarly, bins can be distinguishable, or indinguishable.
When you solve a counting problem using the model of distributing balls into bins, you need
to determine whether the balls are distinguishable and whether the bins are distinguishable.
We have four cases:

1. distinguishable balls, distinguishable bins

2. indistinguishable balls, distinguishable bins

3. distinguishable balls, indistinguishable bins

4. indistinguishable balls, indistinguishable bins

1.1. distinguishable balls, distinguishable bins

• The number of ways to distribute k distinguishable balls into n distinguishable bins (each
bin receives at most 1 ball) = n Pk = n(n − 1)(n − 2) · · · (n − k + 1).

• The number of ways to distribute k distinguishable balls into n distinguishable bins (with-
out condition) = nk

• The number of ways to distribute n distinguishable balls into k distinguishable bins so

n!
that ni balls are placed into bin-i, i = 1, 2, . . . , k, equals
n1 ! n2 ! . . . nk !

Example 1. How many ways are there to distribute hands of 5 cards to each of four
players from the standard deck of 52 cards?

1
1.2. indistinguishable balls, distinguishable bins
• The number of ways to distribute k indistinguishable balls into n distinguishable bins (each
( )
bin receives at most 1 ball) = n Ck = nk .

• The number of ways to distribute k indistinguishable balls into n distinguishable bins

( )
(without condition) = n−1+k Ck = n−1+k
k .

1.3. distinguishable balls, indistinguishable bins

Counting the ways to place n distinguishable balls into k indistinguishable bins is more diffi-
cult. There is no simple closed formula for the number of ways to distribute n distinguishable
balls into k indistinguishable bins. However, there is a formula involving a summation that is
given in the following Theorem. First, let us illustrate this with an example.

Example 2. How many ways are there to put four different employees into three indistin-
guishable offices, when each office can contain any number of employees?

Result. The number of ways to distribute n distinguishable balls into k indistinguishable

bins (without condition) =
∑
k
S(n, j)
j=1

where S(n, j) = number of ways to distribute n distinguishable balls into j indistinguishable

bins so that no bin is empty
and
( )
1 ∑
j−1
j
S(n, j) = (−1)t (j − t)n
j! t
t=0

Note: The numbers S(n, j) are called Stirling numbers of the second kind.

Solution of Example 2: the number of ways to put 4 different employees into 3 indistinguishable
offices = S(4, 1) + S(4, 2) + S(4, 3) = 1 + 7 + 6 = 14.

1.4. indistinguishable balls, indistinguishable bins

We illustrate this principle with an example.
Example 3. How many ways are there to pack 6 copies of the same book into 4 identical boxes,
where a box can contain as many as 6 books?

2
Remark. Distributing n indistinguishable balls into k indistinguishable bins is the same as
writing n as the sum of at most k positive integers in non-increasing order.
If a1 + a2 + · · · + aj = n, where a1 , a2 , . . . , aj are positive integers with a1 ≥ a2 ≥ · · · ≥ aj ,
we say that ⟨a1 , a2 , . . . , aj ⟩ is a partition of the positive integer n into j positive integers.
Result. The number of ways to distribute n indistinguishable balls into k indistinguishable
∑
bins (without condition) = kj=1 P (n, j)
where P (n, j) = the number of partitions of n into exactly j parts/integers.
Note. But no simple closed formula exists for this number.

Reference
1. Kenneth H Rosen. Discrete Mathematics and Its Applications with Combinatorics and
Graph Theory, 7th Edition, Tata McGraw Hill, 2017.

3
 MA4201: Mathematical Foundations of Computer Science MSc (M&SC), I Sem
Lecture-24
Department of Mathematics, NIT Warangal Scribe: Dr. Y. Sreenivasa Rao

Balls-to-Bins Problem Examples

1. How many ways are there to distribute 5 balls into 7 boxes if each box must have at most one
ball in it if
a) both the balls and boxes are distinguishable?
b) the balls are indistinguishable, but the boxes are distinguishable?
c) the balls are distinguishable, but the boxes are indistinguishable?
d) both the balls and boxes are indistinguishable?

2. How many ways are there to distribute 5 balls into 3 boxes if each box must have at least one
ball in it if
a) both the balls and boxes are distinguishable?
b) the balls are indistinguishable, but the boxes are distinguishable?
c) the balls are distinguishable, but the boxes are indistinguishable?
d) both the balls and boxes are indistinguishable?

1
 MA4201: Mathematical Foundations of Computer Science MSc (M&SC), I Sem

Lecture 25
Department of Mathematics, NIT Warangal Scribe: Dr. Y. Sreenivasa Rao

Balls-to-Bins Problem
In how many ways can we distribute 𝒌 balls in to 𝒏 bins?
Condition on the number of balls received
𝒌 balls 𝒏 bins No condition Each bin receives Each bin receives at Each bin receives
at most 1 ball least 1 ball exactly 1 ball
different different 𝑛𝑘 , 𝑛𝑃𝑘 if 𝑘 ≤ 𝑛, 𝑛! ∙ 𝑆(𝑘, 𝑛) if 𝑘 ≥ 𝑛, 𝑛! if 𝑘 = 𝑛,
for any 𝑛, 𝑘 0 if 𝑘 > 𝑛 0 if 𝑘 < 𝑛 0 if 𝑘 ≠ 𝑛
𝑛
same different (𝑛−1+𝑘), (𝑘 ) if 𝑘 ≤ 𝑛, 𝑘−1
(𝑛−1) if 𝑘 ≥ 𝑛, 1 if 𝑘 = 𝑛,
𝑘
for any 𝑛, 𝑘 0 if 𝑘 > 𝑛 0 if 𝑘 < 𝑛 0 if 𝑘 ≠ 𝑛
different same ∑𝑛𝑗=1 𝑆(𝑘, 𝑗) 1 if 𝑘 ≤ 𝑛, 𝑆(𝑘, 𝑛) if 𝑘 ≥ 𝑛, 1 if 𝑘 = 𝑛,
for any 𝑛, 𝑘 0 if 𝑘 > 𝑛 0 if 𝑘 < 𝑛 0 if 𝑘 ≠ 𝑛
same same ∑𝑛𝑗=1 𝑃(𝑘, 𝑗) 1 if 𝑘 ≤ 𝑛, 𝑃(𝑘, 𝑛) if 𝑘 ≥ 𝑛, 1 if 𝑘 = 𝑛,
for any 𝑛, 𝑘 0 if 𝑘 > 𝑛 0 if 𝑘 < 𝑛 0 if 𝑘 ≠ 𝑛

𝑆(𝑘, 𝑛) is the number of partitions of the set {1, 2, … , 𝑘} into exactly 𝑛 parts,
𝑃(𝑘, 𝑗 ) is the number of partitions of 𝑘 into 𝑗 parts.
 MA4201: Mathematical Foundations of Computer Science MSc (M&SC), I Sem
Lecture-26
Department of Mathematics, NIT Warangal Scribe: Dr. Y. Sreenivasa Rao

Recurrence Relations
Recurrence relations play an important role in many aspects of the study of algorithms and
their complexity. You will see in your Design and analysis of algorithms course how recurrence
relations can be used to analyze the complexity of divide-and-conquer algorithms, such as the
merge sort algorithm.
First, we see how we can use recurrence relations to model certain problems. Consider the
following famous puzzle.
The Tower of Hanoi Puzzle: A popular puzzle of the late nineteenth century invented
by the French mathematician Édouard Lucas, called the Tower of Hanoi, consists of three pegs
mounted on a board together with disks of different sizes. Initially these disks are placed on the
first peg in order of size, with the largest on the bottom (as shown in the following Figure 1).
The rules of the puzzle allow disks to be moved one at a time from one peg to another as long
as a disk is never placed on top of a smaller disk. The goal of the puzzle is to have all the disks
on the second peg in order of size, with the largest on the bottom.

Figure 1: A model of the Tower of Hanoi

Question. How many moves does it take to transfer n disks from peg 1 to peg 2 , following the
rules of the Tower of Hanoi puzzle?
1
Exercise. A young pair of rabbits (one of each sex) is placed on an island. A pair of rabbits
does not breed until they are 2 months old. After they are 2 months old, each pair of rabbits
produces another pair each month. Find the number of pairs of rabbits on the island after 10
months, assuming that no rabbits ever die.

Recurrence Relations: Informally, a recurrence relation is an alternative definition of a se-

quence that specifies one or more initial terms and a rule for finding subsequent terms from
those that precede them. Such relations can be used in studying and solving certain counting
problems. A formal definition of a recurrence relation is given in the following definition.

Definition. A recurrence relation for the sequence {an }∞

n=0 is an equation that expresses an in
terms of one or more of the previous terms a0 , a1 , . . . , an−1 of the sequence, for all n ≥ N , where
N is a non-negative integer.
A sequence is called a solution of a recurrence relation if its terms satisfy the recurrence
relation.

Example. f0 = 0, f1 = 1, fn = fn−1 + fn−2 , ∀n ≥ 2

The solution for this recurrence relation is the Fibonacci sequence 0, 1, 1, 2, 3, 5, 8, 13, . . .

Linear Homogeneous Recurrence Relations

Definition. A linear homogeneous recurrence relation of degree k with constant coefficients is
a recurrence relation of the form

an = c1 an−1 + c2 an−2 + · · · + ck an−k , ∀n ≥ k

where c1 , c2 , . . . , ck are real numbers and ck ̸= 0

The recurrence relation in this definition is

• linear: previous terms appear with exponent 1 (not squares, cubes etc.)
• homogeneous: no terms occur that are not multiples of the aj ’s
• degree k: an is expressed in terms of previous k terms
• constant coefficients: coefficients are real numbers, instead of functions of n.

2
 Recurrence relation Is linear? Is homogeneous? Degree
an = 3.5an−1 X X 1
fn = fn−1 + fn−2 X X 2
an = an−3 + an−6 X X 6
2
an = an−1 + an−2 × − −
hn = 2hn−1 + 1 X × 1

Remark. More than one sequence can be a solution for the same recurrence relation. For
instance,
an = 2an−1 − an−2

The following sequences are solutions of this recurrence relation:

• 0, 3, 6, 9, 12, . . . (an = 3n, ∀n ≥ 0)
• 5, 5, 5, 5, 5, . . . (an = 5, ∀n ≥ 0)
Note that the k initial conditions a0 = d0 , a1 = d1 , . . . , ak−1 = dk−1 for a sequence specify the
first k terms of the sequence.
The recurrence relation

an = c1 an−1 + c2 an−2 + · · · + ck an−k , ∀n ≥ k

together with the initial conditions a0 = d0 , a1 = d1 , . . . , ak−1 = dk−1 uniquely determine the
sequence.
In the above example, the initial conditions a0 = 0, a1 = 3 represent the first sequence and
a0 = 5, a1 = 5 represent the second sequence.

Reference
1. Kenneth H Rosen. Discrete Mathematics and Its Applications with Combinatorics and
Graph Theory, 7th Edition, Tata McGraw Hill, 2017.

3
 MA4201: Mathematical Foundations of Computer Science MSc (M&SC), I Sem
Lecture-27
Department of Mathematics, NIT Warangal Scribe: Dr. Y. Sreenivasa Rao

Solving Second Degree Linear Homogeneous Recurrence Relations with Constant

Coefficients
Consider second degree linear homogeneous recurrence relations with constant coefficients

an = c1 an−1 + c2 an−2 , ∀n ≥ 2 (1)

Suppose the sequence {an = rn } is a solution of (1).

{an = rn } is a solution of (1)

iff r2 = c1 r + c2 or r2 − c1 r − c2 = 0
iff r is a solution of x2 − c1 x − c2 = 0

r2 − c1 r − c2 = 0 is called the characteristic equation of the recurrence relation (1).

The solutions of this equation are called the characteristic roots of the recurrence relation (1).

The explicit formula for the solution sequence {an }: Let r1 and r2 be two roots. We have
three cases:

1. If r1 ̸= r2 , then an = α1 r1n + α2 r2n ,

where α1 , α2 are constants

2. If r1 = r2 = r, then an = (α1 + α2 n)rn

3. If r1 = α + iβ and r2 = α − iβ (α, β are real), then

an = (α2 + β 2 )n/2 (A cos nθ + B sin nθ)

where θ = tan−1 (β/α) and A, B are complex constants.

Example A. Find an explicit formula for the Fibonacci numbers. The corresponding recurrence
relation is
fn = fn−1 + fn−2 , f0 = 0, f1 = 1.

Exercise. Solve the following recurrence relations

1
 1. an + an−1 − 6an−2 = 0 and a0 = −1, a1 = 8

2. an − 6an−1 + 9an−2 = 0 and a0 = 5, a1 = 12

3. an = 2an−1 − 2an−2 and a0 = 1, a1 = 2

Exercise The Lucas numbers satisfy the recurrence relation Ln = Ln−1 + Ln−2 and L0 =
2, L1 = 1.

1. Show that Ln = fn−1 + fn+1 , ∀n ≥ 2, where fn is the nth Fibonacci number.

Hint: Use strong induction

2. Find an explicit formula for the Lucas numbers.

Hint: Use the procedure of example A.

Solving Third Degree Linear Homogeneous Recurrence Relations with Constant

Coefficients
The equation is
an = c1 an−1 + c2 an−2 + c3 an−3 , ∀n ≥ 3 (2)

The characteristic equation of the recurrence relation (2) is r3 − c1 r2 − c2 r − c3 = 0

Solution {an }: We have four cases.

1. Roots are r1 , r2 , r3 (three different roots), then an = α1 r1n + α2 r2n + α3 r3n

where α1 , α2 , α3 are constants

2. Roots are r1 , r1 , r2 (one pair of equal roots), then an = (α1 + α2 n)r1n + α3 r2n

3. Roots are r1 , r1 , r1 (three equal roots), then an = (α1 + α2 n + α3 n2 )r1n

4. Roots are r1 = α + iβ, r2 = α − iβ and r3 , α, β are real (one pair of complex roots), then

an = (α2 + β 2 )n/2 (A cos nθ + B sin nθ) + α3 r3n

where θ = tan−1 (β/α) and A, B are complex constants

Example. Find the solution to the recurrence relation

an = 6an−1 − 11an−2 + 6an−3

with initial conditions a0 = 2, a1 = 5, a2 = 15.

Exercise Find the solution to the recurrence relation

an = −3an−1 − 3an−2 − an−3

2
with initial conditions a0 = 1, a1 = −2, a2 = −1.
Remark. One can solve the higher degree linear homogeneous recurrence relations with con-
stant coefficients in a manner similar to the second degree and third degree recurrence relations.
Example. Suppose that the roots of the characteristic equation of a linear homogeneous re-
√ √
currence relation are 2, 2, 2, 2, 5, 5, 5, 1 + i 3, 1 − i 3 and 9. What is the form of the general
solution?
Exercise. Find the solution of the recurrence relation an −an−4 = 0 with a0 = 1, a1 = 0, a2 = −1
and a3 = 1
Example. Let an denote the number of bit-strings of length n, that do not contain two con-
secutive 0’s.
(a) Deduce a recurrence relation for an . Also determine the requisite initial conditions.
(b) Solve the recurrence relation of Part (a) to obtain an explicit formula for an .
Exercise. Let an denote the number of strings of length n over Σ = {0, 1, 2}, that do not
contain two consecutive 2’s.
(a) Deduce a recurrence relation for an . Also determine the requisite initial conditions.
(b) Solve the recurrence relation of Part (a) to obtain an explicit formula for an .

Reference
1. Kenneth H Rosen. Discrete Mathematics and Its Applications with Combinatorics and
Graph Theory, 7th Edition, Tata McGraw Hill, 2017.

3
 MA4201: Mathematical Foundations of Computer Science MSc (M&SC), I Sem
Lecture-28
Department of Mathematics, NIT Warangal Scribe: Dr. Y. Sreenivasa Rao

Linear non-homogeneous recurrence relation with constant coefficients

• A linear non-homogeneous recurrence relation with constant coefficients (LNonHomoRRwCC)
is a recurrence relation of the form

an = c1 an−1 + c2 an−2 + · · · + ck an−k + g(n) (1)

where c1 , c2 , . . . , ck are real numbers and g(n) is a function not identically zero, depending only
on n.
• The recurrence relation an = c1 an−1 +c2 an−2 +· · ·+ck an−k is called the associated homogeneous
recurrence relation.
Examples

1. an = 3an−1 + 2n

2. an = 5an−1 − 6an−2 + 7n

3. an = 6an−1 + 10an−2 + (n2 + 1)3n

4. an = −11an−1 − 6an−2 + n2 2n

Theorem. If {a′n } is a particular solution of the linear non-homogeneous recurrence relation

with constant coefficients (1) and {a′′n } is a general solution of the associated homogeneous re-
currence relation. Then, {a′n + a′′n } is a general solution of (1).

Finding particular solution of an = c1 an−1 + c2 an−2 + · · · + ck an−k + g(n)

• If g(n) = p(n)sn , where p(n) is a polynomial of degree t and the real number s is a root of the
characteristic equation
rk − c1 rk−1 − c2 rk−2 − · · · − ck = 0

of the associated homogeneous recurrence relation, with multiplicity ℓ,

• then the LNonHomoRRwCC has a particular solution of the form

nℓ (b0 + b1 n + b2 n2 + · · · + bt nt )sn

Question. What form does a particular solution of LNonHomoRRwCC with characteristic

equation (r − 1)3 (r − 3)2 (r − 6) = 0 have when
1
 1. g(n) = (n2 + 2n + 1)3n ?

2. g(n) = n6n ?

3. g(n) = 1?

4. g(n) = n4 ?

Example. (i) Find all solutions of the recurrence relation

an+2 − 4an+1 + 3an = −200, ∀n ≥ 0.

(ii) Find the solution of the above recurrence relation with initial conditions a0 = 3000, a1 =
3300.

Exercise. (i) Find all solutions of the recurrence relation an + 5an−1 + 6an−2 = 42 · 4n .
(ii) Find the solution of this recurrence relation with a1 = 56 and a2 = 278.
Exercise. Find the solution of the recurrence relation an = 4an−1 − 3an−2 + 2n + n + 3 with
a0 = 1 and a1 = 4.

Reference
1. Kenneth H Rosen. Discrete Mathematics and Its Applications with Combinatorics and
Graph Theory, 7th Edition, Tata McGraw Hill, 2017.

2
 MA4201: Mathematical Foundations of Computer Science MSc (M&SC), I Sem
Lecture-29
Department of Mathematics, NIT Warangal Scribe: Dr. Y. Sreenivasa Rao

Solving Recurrence Relations using Substitution

Example. (using range transformation)
Solve the recurrence relation a2n − 2a2n−1 = 1 for n ≥ 1 where a0 = 1.
Example. (using range transformation)
Find all solutions of the recurrence relation

a0 = 1
a1 = 2
an+2 = (an+1 )(an ), ∀n ≥ 0

Example. (using range transformation)

Find all solutions of the recurrence relation

a0 = 1
an = 3a2n−1 , ∀n > 0

Example. (using domain transformation)

Example Solve the divide and conquer relation

 1, n = 1;
T (n) =
 3T (n/2) + n, n > 1.

where n is a power of 2.
Example. (using domain transformation)
Solve the recurrence relation T (n) = nT 2 (n/2) with initial condition T (1) = 6 when n = 2k .

Reference
1. Kenneth H Rosen. Discrete Mathematics and Its Applications with Combinatorics and
Graph Theory, 7th Edition, Tata McGraw Hill, 2017.

1
 MA4201: Mathematical Foundations of Computer Science MSc (M&SC), I Sem
Lecture-30
Department of Mathematics, NIT Warangal Scribe: Dr. Y. Sreenivasa Rao

Solving Recurrence Relations using Generating Function

Definition The generating function for the sequence a0 , a1 , a2 , . . . , an , . . . of real numbers is the
infinite series

∞
∑
G(x) = a0 + a1 x + a2 x2 + · · · + an xn + · · · = an xn
n=0
∑
Example (i) For the sequence 1, 2, 4, 8, 16, . . ., the generating function is ∞ n n
n=0 2 x .
∑∞
(ii) For the sequence an = n + 1, ∀n ≥ 0, the generating function is n=0 (n + 1)xn .
Remark We can define generating functions for finite sequences of real numbers by extending
a finite sequence a0 , a1 , a2 , . . . , an into an infinite sequence by setting an+1 = 0, an+2 = 0, . . ..
The generating function G(x) of this infinite sequence {an }∞
n=0 = {an } is a polynomial of degree
n as
G(x) = a0 + a1 x + a2 x2 + · · · + an xn

Properties: The following are a couple of properties of generating functions.

1. If f (x) is a generating function for the sequence {an } and g(x) is a generating function for
the sequence {bn }, then pf (x)+rg(x) is a generating function for the sequence {pan + rbn },
where p and r are any two real numbers.

2. If f (x) is a generating function for the sequence {an }, then xf ′ (x) is a generating function
for the sequence {nan }.

1
 Sequence Generating function
1 ∑
{1n } = 1, 1, 1, . . . = ∞ n=0 x = 1 + x + x + · · ·
n 2
1−x

1 ∑
{(−1)n } = 1, −1, 1, −1, . . . = ∞n=0 (−1) x = 1 − x + x − x + · · ·
n n 2 3
1+x

1 ∑
{cn } = ∞n=0 c x = 1 + cx + c x + · · ·
n n 2 2
1 − cx

1 ∑
{n + 1} = 1, 2, 3, 4, . . . = ∞
n=0 (n + 1)x = 1 + 2x + 3x + 4x + · · ·
n 2 3
(1 − x) 2

x ∑
{n} = 0, 1, 2, 3, . . . = ∞
n=0 nx = 0 + 1x + 2x + 3x + · · ·
n 2 3
(1 − x) 2

{ } 1+x ∑
(n + 1)2 = 12 , 22 , 32 , 42 , . . . = ∞
n=0 (n + 1) x = 1 + 2 x + 3 x + 4 x + · · ·
2 n 2 2 2 2 2 3
(1 − x) 3

{ } x(1 + x) ∑∞ 2 n
n2 = 02 , 12 , 22 , 32 , 42 , . . . = n=0 n x = 02 + 12 x + 22 x2 + 32 x3 + · · ·
(1 − x)3

(m+n−1) 1 ∑∞ (m+n−1) n
{ } = x
n (1 − x)m n=0 n

Example Find the generation function of the following sequences.

(i) 0, 2, 6, 12, 20, 30, 42, . . .
(ii) 8, 26, 54, 92, . . .
Example Use generating functions to solve the recurrence relation

a0 = 6
a1 = 30,
an = 5an−1 − 6an−2 , ∀n ≥ 2

Ans: an = −12 · 2n + 18 · 3n , ∀n ≥ 0
Exercise Solve the following recurrence relation using generating functions.

a0 = 1
a1 = 9
an = 8an−1 + 10n−1 , ∀n ≥ 2

Ans: an = 1
2 (8n + 10n ) , ∀n ≥ 0

2
Example Use generating functions to solve the recurrence relation

an+1 − an = n2 , a0 = 1 (n ≥ 0)

Ans: an = 1 + 16 n(n − 1)(2n − 1)

Exercise. Solve the following recurrence relation using generating functions.

an = 4an−1 − 4an−2 + n2 , n>2

with initial conditions a0 = 2, a1 = 5

Ans: an = n2 + 8n + 20 + 2n (6n − 18)

Reference
1. Kenneth H Rosen. Discrete Mathematics and Its Applications with Combinatorics and
Graph Theory, 7th Edition, Tata McGraw Hill, 2017.

3
 MA4201: Mathematical Foundation of Computer Science MSc (M&SC),I Sem

re LECTURE – 32
Department of Mathematics NIT Warangal

Binary Relation :- Let A and B be two non – empty sets.

A × B = {(a, b) | a ∈ A , b ∈ B}
A binary relation from A to B is a subset of A × B. It is written as R ⊆ A × B.

Where, (a, b) is an ordered pair, i.e., (a, b) ≠ (b, a).

| A × B | = |A| |B|
No. of relations = 2|A||B|

aRb means (a, b) ∈ R , a is related to b by relation R.

a Rb means (a, b) ∉ R , a is not related to b by relation R.

Example:- let A = {1,2,3} and B = {2,3} then A × B = { (1,2), (1,3), (2,2), (2,3), (3,2), (3,3) }.
Define a relation R such that aRb when a<b then R = { (1,2), (1,3), (2,3)}.
 Let A is a non-empty set then a relation from A to A is a subset of A × A.
A × A = {(a, b) | a ∈ A , b ∈ A}
If |A| = n then no. of relations on A = 2n*n.

Representation of a relation

1. Boolean Matrix (0-1 matrix) representation.

2. Directed Graph (Digraph) representation.

1. Boolean Matrix (0-1 matrix) representation

Let A = { a1, a2 ,……………,an } and B = { b1, b2 ,……………,bn } and R ⊆ A × B.

R can be represented by the 0-1 matrix denoted as MR

MR = ( mij) 1 ≤ i ≤ n, 1 ≤ j ≤ m
where,

1, if (𝑎𝑖 , 𝑏𝒋 ) ∈ 𝑅
𝑚𝑖𝑗 = {
0, if (𝑎𝑖 , 𝑏𝒋 ) ∉ 𝑅

Example :- let A = {1,2,3} and B = {a,b,c}, R = { (1,a), (2,b), (2,c), (3,c)}.

Then,
𝑎 𝑏 𝑐
1 1 0 0
MR = 2 [0 1 1]
3 0 0 1

3. Digraph representation of a relation :-

A digraph consists of
 a set A of vertices (nodes) together with
 a set R of ordered pairs of A × A called as directed edges or (arcs).

 (a,b) = ab, here ab is called as edge(directed edge) and represented as arrow and

a and b are called as vertecies represented as solid dot “ ” .

a b
 Self loop or loop

a
Let A = {1,2,3,4}, R = {(1,1), (3,1), (3,2), (4,4)}
(A,R) = ( {1,2,3,4}, {(1,1), (3,1), (3,2), (4,4)} )
Example: A={1,2,3,4} and relation is R ≤ R={(1,2),(1,3),(1,4)(2,3),(2,4),(3,4),(4,4)}

Digraph representation:

1 2

4 3

R1={(1,2),(1,1),(2,1)} Digraph Representation:

1 2

Reference :-

1. Kenneth H Rosen. Discrete Mathematics and It’s Applications with Combinatoies and
Graph Theory, 7th edition, Tata McGraw Hill,2017
2 . Lecture Notes - Dr. Y. Sreenivasa Rao
MA4201: Mathematical Foundations of Computer Science MSc(M&SC), 1st Sem
Lecture-33
Department of Mathematics, NIT Warangal

Types of Relation
Let R be a relation on A.

1. Reflexive relation
A relation R is reflexive if for all y ∈ A, (y, y) ∈ R.
All the diagonal entries in MR are 1.
Every node in DR has a loop.
∀ a ∈ A, a R a
∀ a ∈ A, (a, a) ∈ 𝑅

Example of reflexive relation

Consider a set A = {a, b, c}
R = {(a, a), (a, b), (a, c), (b, c), (b, b), (c, c)}
∆ = {(a, a), (b, b), (c, c)}
Here, ∆ = Smallest reflexive relation.

2. Irreflexive Relation
A relation on a set A is irreflexive if no element is related to itself, in other words.
All the diagonal entries in MR are 0.
Every node in DR should not have any loop.
∀ a ∈ A, a ℟ a
∀ a ∈ A, (a, a) ∉ 𝑅
Note: Irreflexive ≠ Not reflexive

1 2 Not reflexive but not irreflexive

3
3. Symmetric Relation
A relation on a set A is symmetric relation if the first element is related to the second
element, then the second element is also related to the first element.

(a, b) ∈ 𝑅 (b, a) ∈ 𝑅
 ∀ a ∀ b (a R b b R a)

(I)
1 2

aa = (a, a)
ab = (a, b)
ba = (b, a)

Note: For every edge in DR, there is an edge in opposite direction.

(II) mij = 1 then mji = 1
mij = 0 then mji = 0
mij = mji , if i ≠ j (MR is a symmetric matrix.)

4. Antisymmetric Relation
A relation on a set A is said to be antisymmetric if for all a, b in A if a related to b and
b is related to a, then a=b.

∀ a ∀ b (a R b ʌ b R a a=b)
∀ a, b ∈ A, (a, b) ∈ 𝑅 & (b, a) ∈ R a=b
(a, b) ∈ 𝑅, a ≠ 𝑏 (b, a) ∉ R

a b

mij , i ≠ 𝑗

Where, mij = 1 ʌ mji = 0

(Or) mij = 0 ʌ mji = 1
(Or) mij = 0 ʌ mji = 0

5. Asymmetric Relation
A relation is said to be asymmetric if for all a, b in A if a is related to b, then b does not
related to a.
∀ a ∀ b (a R b b ℟ a)
∀ a, b ∈ A, (a, b) ∈ 𝑅 (b, a) ∉ 𝑅
(a, a) ∈ 𝑅 (a, a) ∉ 𝑅 (Not have any loop)
 a b

MR = (mij)ij , where, i ≠ j
mij = 1 ʌ mji = 0
(Or) mij = 0 ʌ mji = 1
(Or) mij = 0 ʌ mji = 0
(Or) mij = 0 , i = j

6. Transitive Relation
A relation is said to be transitive if for all a, b, c in A, if a is related to b and b is related to
c, then a is related c.
∀ a, b, c ∈ A, (a, b), (b, c) ∈ R (a, c) ∈ R
∀ a ∀ b ∀ c, (a R b ʌ b R c a R c)

a c

Combining Relations
Let R1, R2 be two relations on A.
Union
R1 U R2= {(a, b) | (a, b) R1 V (a, b) R2}
𝑀R1 U R2 = MR1 V MR2 = (aij V bij)

Example

1 0 V 1 1 = 1 1
0 0 0 1 0 1

Difference of two sets

R1-R2 = {(a, b) : (a, b) ∈ R1 ⋀ (a, b) ∉ R2}
Symmetric Relation
R1⊕R2 = (R1 – R2) ∪ (R2 – R1)
R1⊕R2 = (R1 ∪ R2) − (R1 ∩ R2)

R¯1 = {(a, b) : (b, a) ∈ 𝑅}

 Mʀ¯1 = MʀT

Composition of Relation

In the mathematics of binary relations, the formation of a new binary relation R∘S
from two given binary relations R and S is known as the composition of relations.

1: R1⊆ 𝐴 × 𝐵, R2 ⊆ 𝐵 × 𝐶, Then R2oR1 ⊆ A × C

(a, b) ∈ R2oR1 ∃c∈B
such that (a, c) ∈ 𝑅1 ⋀ (𝑐, 𝑏) ∈ 𝑅2
2: R1,R2 ⊆ 𝐴 × 𝐴
(a, b) ∈ 𝑅2𝑜𝑅1 ∃ 𝑐∈ A
such that (a, c) ∈ 𝑅1 ⋀(𝑐, 𝑏) ∈ 𝑅2
3: R ⊆ 𝐴 × 𝐴

(a, b) ∈ RoR = R2 ↔ ∃ c ∈ A, ∃ (a, c), (c, b) ∈ R

𝑅1 = 𝑅

𝑅 2 = 𝑅𝑜𝑅

𝑅 3 = 𝑅 2 𝑜𝑅
𝑅 4=𝑅 3oR
:
:
𝑅 𝑛+1 = 𝑅 𝑛 𝑜𝑅
MA4201: Mathematical Foundation of Computer Science MSc (M&SC),I Sem
LECTURE – 34
Department of Mathematics NIT Warangal

PROPERTY R1∪R2 R1∩R2

1. Reflexive ✔ ✔
2. Irreflexive ✔ ✔
3. Symmetric ✔ ✔
4. Antisymmetric × ✔
5. Asymmetric × ✔
6. Transitive × ✔

Composition
Let A,B,C be sets and let R1 and R2 be two relations such that R1 ⊆ A × B and R2 ⊆
B × C. Then R1 and R2 given rise to a relation from A to C indicated by R2oR1 and defined by
(a,c) ∈ R2oR1 , iff ヨ b ∈ B such that (a,b) ∈ R1 & (b,c) ∈ R2 .

The relation R2oR1 is known as the composition of R1 and R2 .

Example:- A = {a,b,c}

B = {1,2,3,4}

C = { x,y,z}

R1={(a,2),(a,3),(b,3),(b,4),(c,2),(c,4)}

R2={(1,x),(1,z),(2,y),(3,y),(3,z),(4,y)}

R2oR1={(a,y),(a,z),(b,z),(b,y),(c,y)}

Let R be a relation on a set A that is R is a relation from the set A to itself.

i.e R ⊆A×A & it is defined as , (a,c) ∈ RoR iff ヨ b∈ A such that (a,b) , (b,c) ∈ R
Example:- A = {1,2,3,4}

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

RoR={(1,1),(2,1),(3,1),(4,2)}

Boolean product (⊙)of matrices

A Boolean Matrix(also called a 0-1 matrix)has its entries either 0 or 1. Three operators
defined on them are ∨,∧and¯. Let A = [aij] and B = [bij ] be m × n Boolean Matrices.

• Let C = A ∨ B = [Cij ]. C is then said to be the join of A and B. C is also an m × n Matrix.

• Let D = A∧B = [dij]. D is then said to be the meet of A and B. D is also an m×n Matrix.

• The Boolean Product represented by A⊙B is quite different from the above two
operations. Let A be a Boolean matrix of order a1 × a2 and B a Boolean matrix of order
b1 × b2. A⊙B is defined only if a2 = b1. So let A have an order of m×p and B have an
order of p×n Let E = A⊙B = [eij ]. E is then said to be the Boolean Product of A and B.

E is an m × n Matrix.
For eij we select the ith row of A and jth column of B. If even one of the corresponding
entries are both 1, the result is 1, else the result is 0(as illustrated in the figure below).

Example:-

M1 =

M2 =

M1 ⊙ M2 =

● MR2 o MR1 = MR1 ⊙ MR2

Reference :-
1. Kenneth H Rosen. Discrete Mathematics and It’s Applications with Combinatorics
andGraph Theory, 7th edition, Tata McGraw Hill,2017

2 . Lecture Notes - Dr. Y. Sreenivasa Rao

 Lecture 35

Paths in Diagraph (Directed Graphs) and Closure of Relations

November 18, 2022

Fact:
Suppose R be a relation on A. Then R is Transitive relation if and only if Rn ⊆ R

Proof:
Part 1:
Suppose R is Transitive relation on A.
let us prove by Mathematical Induction
For n = 1, Clearly, R1 ⊆ R
Assume that, Rk ⊆ R
claim: Rk+1 ⊆ R
We know that (a, b) ∈ Rk+1 = Rk ◦ R
∃ c ∈ A such that (a, c) ∈ Rk and (c, b) ∈ Rk
since Rk ⊆ R =⇒ (a, c) ∈ R
∴ ∃ c ∈ A such that (a, c) ∈ R and (c, b) ∈ R
∴ (a, b) ∈ R
Hence, Rk+1 ⊆ R
By Mathematical Induction, Rn ⊆ R

Part 2:
Suppose Rn ⊆ R ,∀n = 1, 2, ...
To prove that R is Transitive
(i.e. To prove that (a, c) ∈ R and (c, b) ∈ R =⇒ (a, b) ∈ R)
Let (a, c) ∈ R and (c, b) ∈ R
(a, c) ∈ R2 = R ◦ R = R2
But R2 ⊆ R
∴ (a, c) ∈ R
Hence, R is Transitive

1
Paths in Diagraphs (Directed Graphs)

Def:- A path from u to v in a diagraph D = (V,E) is a sequence of edges (x0 , x1 ) (x1 , x2 ) ...
(xn−1 , xn ) where n ≥ 0 and n ∈ Z satisfying the terminal node of an edge equal to initial node in
the next edge in the sequence

NOTATIONS:

1. This path is denoted by u, x1 , x2 , ..., xn−1 , v and it has length n

2. Any path u, x1 , x2 , ..., xn−1 , v is called a circuit or cycle if u = v

NOTE:

1. A Path can be passed through a node more than once.

2. An edge can occur more than once in a path.

3. An edge (a, b) where a ̸= b is a path of length 1

Theorem:
If there is a path of length 2 from u to v in DR if and only if (u, v) ∈ R2

Proof:
Part 1:
Let R be a relation on A
Suppose There is a path of length 2 from u to v in DR
Then ∃ a node a ∈ A such that (u, a), (a, v) are edges in DR i.e.(u, a), (a, v) ∈ R
∴ (u, v) ∈ R ◦ R
Hence, (u, v) ∈ R2

Part 2:
Suppose (u, v) ∈ R2
Then ∃ c ∈ A such that (u, c) ∈ R and (c, v) ∈ R
=⇒ (u, c), (c, v) ∈ R
=⇒ u, c, v is a path of length 2 in DR between u and v
Hence, There exists a path of length 2 in DR between u and v

Conclusion: In general, There is a path of length n from u to v in DR if and only if (u, v) ∈ Rn

2
e.g. A = { 1, 2, 3, 4 }
R = { (1, 1), (2, 1), (3, 2), (4, 3) }
R2 = { (1, 1), (2, 1), (3, 1), (4, 2) }
R3 = { (1, 1), (2, 1), (3, 1), (4, 1) }

Closure of Relations

Reflexive closure: Let R be a relation on A which is not reflexive. Now the smallest reflexive
relation containing R is called the Reflexive closure of R.

S is said to be a reflexive closure of R if:

1. S is reflexive
2. R ⊆ S
3. If T is a reflexive relation containing R then S ⊆ T

Example1: If R = {(1,2),(2,1),(1,1),(2,2)} be a relation on A = {(1,2,3.4)}. Find the reflexive

closure of R.
Solution:
Reflexive closure(R′ ) = R ∪ { (a, a) | a ∈ R}
Therefore, R′ = {(1,2),(2,1),(1,1),(2,2),(3,3),(4,4)}

Observation:
T
1. S = Ri , R ⊆ Ri where each Ri is reflexive
i
2. R is not reflexive Then S = R ∪ ∆
3. MS = MR∪∆ = MR ∨ M∆ = MR ∨ I

Symmetric closure: Let R be a relation on A which is not symmetric. Now the smallest sym-
metric relation containing R is called the symmetric closure of R.

S is said to be a symmetric closure of R if:

1. S is symmetric
2. R ⊆ S
3. If T is a symmetric relation containing R then S ⊆ T

Example1: If R = {(1,2),(2,1),(3,1),(2,2),(4,3)} be a relation on A = {(1,2,3.4)}. Find the sym-

metric closure of R.
Solution:
Symmetric closure(R′ ) = R ∪ { (b, a) | (a, b) ∈ R}
Therefore, R′ = {(2,1),(4,3),(2,2),(1,2),(1,3),(3,4),(3,1)}

3
Observation:
T
1. S = Ri , R ⊆ Ri where each Ri is symmetric
i
2. R is not symmetric Then S = R ∪ R−1
3. MS = MR∪R−1 = MR ∨ MR−1 = MR ∨ MRT

[1]

References

[1] Kenneth H Rosen. Discrete mathematics & applications. McGraw-Hill, 2017.

4
MA4201: Mathematical Foundation of Computer Science MSc (M&SC),I Sem

LECTURE – 36

Department of Mathematics NIT Warangal

Scribe: Dr. Y. Sreenivasa Rao

Transitive closure -

Definition -
*
Let R be a relation on a set A. The connectivity relation 𝑅 consists of the
pairs (a,b) such that there is a path of length at least one from a to b in R.

The transitive closure of R =

Proof –
Suppose R is not transitive
*
Claim - 𝑅 is “smallest “ “transitive” relation “containing R”

(I) “containing R “
∞
𝑛 *
R = R’ ⊆ ⋃ 𝑅 = 𝑅
𝑛=1
(II) “transitive”
∞
𝑛
(a,b) , (b,c) ∈ R* = ⋃ 𝑅
𝑛=1
𝑛1 𝑛2
⇒ (a,b) ∈ 𝑅 𝑎𝑛𝑑 (𝑏, 𝑐) ∈ 𝑅
∞
𝑛2 𝑛1 𝑛2+𝑛1 𝑛 *
⇒ (a, c) ∈ 𝑅 ◦𝑅 =𝑅 ⊆ ⋃ 𝑅 = 𝑅
𝑛=1
∴ R* is transitive
 (III) “smallest “

Let S be a transitive relation such that :

R⊆S

Claim : – R* ⊆ S
𝑛
Since S is transitive 𝑆 ⊆ S ∀ n = 1, 2 ….
∞
𝑛
⋃ 𝑆 ⊆S
𝑛=1
2 2 3 3
since R ⊆ S , 𝑅 ⊆ 𝑆 ,𝑅 ⊆ 𝑆 …
∞ ∞
* 𝑛 𝑛
𝑅 = ⋃ 𝑅 ⊆ ⋃ 𝑆 ⊆S
𝑛=1 𝑛=1
so, R* ⊆ S
∞
𝑛 1 2 𝑛
R* = ⋃ 𝑅 = 𝑅 ∪ 𝑅 …… ∪ 𝑅
𝑛=1

Ex. R = { (1,1) (1,3) (2,2) (3,1) (3,2) }

R=

R* = { (1,1) (1,2) (1,3) (2,2) (3,1) (3,2) (3,3) }

1 2 𝑛
• Trcl(R) = 𝑅 ∪ 𝑅 … . ∪ 𝑅 if R is a relation on A with n elements

• Let A be a set with n elements, and let R be a relation on A.

If there is a path of length at least one in R from a to b, then there is
such a path with length not exceeding n.
Moreover, when a = b, if there is a path of length at least one in R from
a to b, then there is such a path with length not exceeding n − 1.
 1 2 𝑛
Now, S = 𝑅 ∪ 𝑅 … . ∪ 𝑅
𝑀𝑆 = 𝑀 1 2 3 𝑛
𝑅 ∪ 𝑅 ∪𝑅 .....∪𝑅

= 𝑀𝑅 ⋁ 𝑀 2⋁ ..... ⋁ 𝑀 𝑛
𝑅 𝑅
(1) (2) (𝑛)
= 𝑀𝑅 ∨ 𝑀𝑅 ∨ 𝑀𝑅 ……… ∨ 𝑀𝑅

Algorithm :
1. Write MR
2. Initialize : A=MR
B=A
3. For i =1 to n-1
A = A ⊙ MR
B=B⋁A
*
4. Write R for B
*
5. Return R

Complexity :
O(n3) · n
O(n4)
Example:
A = { (a, a), (b,b), (a,c), (c, a), (c,b) }

given set A is not transitive, so using the above algorithm to get

transitive closure
𝐾 [1] [2] [3]
𝑀𝑅 = M 𝑅 ⋁ 𝑀𝑅 𝑉 𝑀𝑅

Trcl(A) = { (a,a), (b,b), (a,c), (c,a), (c,b), (a,b) }

 [LECTURE 37] 2022

WARSHALL’S ALGORITHM

Warshall’s algorithm, named after Stephen Warshall, who described this algorithm I 1960
is an efficient method for computing the transitive closure of a relation. Algorithm 1 can find the
transitive closure of a relation on a set with n elements using 2n3(n-1) bit operations. However,
the transitive closure can be found by Warshall’s algorithm using only 2n 3 bit operations.
Warshall’s algorithm is sometimes called the Roy-Warshall algorithm, because Bernard
Roy described this algorithm in 1959.
Suppose that R is a relation on a set with n elements. Let v1,v2,………..vn be an arbitrary
listing of these n elements. The concept of the interior vertices of a path is used in Warshall’s
algorithm. If a, x1, x2, …., xm-1, b is a path, its interior vertices are x1, x2,……, xm-1, that is, all the
vertices of the path that occur somewhere other than as the first and last vertices in the path.
For instance, the interior vertices of a path a, c, d, f, g, h, b, j in a directed graph are c, d, f, g, h
and b. The interior vertices of a, c, d, a, f, b are c, d, a, and f. (Note that the first vertex in the
path is not an interior vertex unless it is visited again by the path, except as the last vertex.
Similarly, the last vertex in the path is not an interior vertex unless it was visited previously by
the path, except as the first vertex).

Warshall’s algorithm is based on the construction of a sequence zero-one matrices. These

matrices are W0, W1 ,…, Wn, where W0 = MR is the zero-one matrix of this relation, and WK =
[wij(k)], where wi j(k) = 1 if there is a path from vi to vj such that all the interior vertices of this path
are in the set {v1, v2,,…..,vk} (the first k vertices in the list) and is 0 otherwise. (The first and last
vertices in the path may be outside the set of the first k vertices in the list.) Note that Wn = MR*,
because the (i, j)th entry of MR* is 1 if and only if there is a path from vi to vj, with all interior
vertices in the set {v1, v2,….,vn} (but these are the only vertices in the directed graph). In the
below example what the matrix Wk represents.

EXPLANATION
Let R be the relation with directed graph shown in figure 3. Let a, b, c, d be a listing of the
elements of the set. Find the matrices W0, W1, W2, W3 and W4. The matrix W4 the transitive
closure of R.

1
 [LECTURE 37] 2022

Solution: Let v1 = a, v2 = b, v3 = c, and v4 = d. W0 is the matrix of the

relation. Hence,

0 0 0 1
1 0 1 0
W 0= [ ]
1 0 0 1
0 0 1 0

W1 has 1 as it (i, j)th entry if there is a path from vi to vj that has only
v1 = an interior vertex. Note that all paths of length one can still be used since they have interior
vertices. Also, there is now an allowable path from b to d namely, b, a, d. Hence,

0 0 0 1
1 0 1 1
W1= [ ]
1 0 0 1
0 0 1 0

W2 has 1 as its (i, j)th entry if there is a path from vi to vj that has only v1 = a and v2 = b as an
interior vertices, if any. Since there are no edges that have b as a terminating vertex, no new
paths are obtained when we permit b to be an interior vertex. Hence, W2 = W1
W3 has 1 as its (i, j)th entry if there is a path from vi to vj that has only v1 = a and v2 = b and /or v3
= c as its interior vertices, if any. We now have paths from d to a namely, d, c, a, and from d to d,
namely, d, c, d. Hence,

0 0 0 1
1 0 1 1
W3=[ ]
1 0 0 1
1 0 1 1

Finally, W4 has 1 as its (i, j)th entry if there is a path from vi to vj that has v1 = a, v2 = b, v3 = c
and/or v4 = d as interior vertices, if any. Since there are all the vertices of the graph, this entry is
1 if and only if there is path from vi and vj. Hence,

1 0 1 1
1 0 1 1
W4 = [ ]
1 0 1 1
1 0 1 1

This last matrix, W4, is the matrix of the transitive closure.

Warshall’s algorthrim computes MR* by efficiently computing W0 = MR, W1, W2, …., Wn = MR*.
This observation shows that we can compute Wk directly from Wk-1: There is a path from vi to vj

2
 [LECTURE 37] 2022

with no vertices other than v1, v2, …, vk as interior vertices if and only if either there is a path
from vi to vj with its interior vertices among the first k-1 vertices in the list, or there are paths
from vi to vk and from vk to vi have interior vertices only among the first k-1 vertices in the list
that is, either as path from vi to vj already existed before vk was permitted as an interior vertex,
or allow vk as an interior vertex produces a path that goes from vi and v k and then from vk to v k-1.
These two cases are shown in Figure 4.

Case 1 Case 2

Figure 4: Adding vk to the set of allowable Interior vertices

(𝑘−1)
The first type of path exists if and only if 𝑤𝑖𝑗 = 1, and the second type of path exists if
(𝑘−1) (𝑘−1) (𝑘−1) (𝑘−1)
and only if both 𝑤𝑖𝑘 and 𝑤𝑘𝑗 are 1. Hence 𝑤𝑖𝑗 is 1 if and only if either 𝑤𝑖𝑗 is 1
(𝑘−1) (𝑘−1)
or both 𝑤𝑖𝑘 and 𝑤𝑘𝑗 are 1 . This gives us Lemma 2.

(𝑘)
LEMMA2 Let 𝑊𝑘 = [𝑤𝑖𝑗 ] be the zero -one matrix that has a 1 in its (𝑖, 𝑗)th position if and
only if there is a path from 𝑣𝑖 to 𝑣𝑗 with interior vertices from the set{𝑣1 , 𝑣2 , … , 𝑣𝑘 }. Then
(𝑘) (𝑘) (𝑘−1) (𝑘−1)
𝑤𝑖𝑗 = 𝑤𝑖𝑗 ⋁(𝑤𝑖𝑘 ⋀𝑤𝑘𝑗 )

Whenever 𝑖, 𝑗 𝑎𝑛𝑑 𝑘 are positive integers not exceeding n.

Lemma 2 gives us the means to efficiently the matrices 𝑊𝑘 , 𝑘 = 1,2, … , 𝑛. We display the
psedocode for Warshall`s algorithm, using Lemma 2, as Algorithm 2.

3
 [LECTURE 37] 2022

ALGORITHM-2:Warshall Algorithm.
procedure Warshall (MR : n × n zero- one matrix)
W := MR
for k := 1 to n
begin
for i := 1 to n
begin
for i := 1 to n
wij := wij V (wik ˄ wkj)
end
end{ W = [wij] is MR*}

Example: By using Warshall’s algorithm, find the transitive closure of the relation

R = {(2,1),(2,3),(3,1),(3,4),(4,1),(4,3)} on set A = {1, 2, 3, 4}

Solution: First, we will represent the relation R in matrix form.
0 0 0 0
Understand that there are 4 elements in set.
1 0 1 0
R= [ ] Therefore, 4 steps are required in order to find the
1 0 0 1
1 0 1 0 transitive closure of relation R (According to Warshall’s
Algorithm).

>>In step 1, we will consider 1st column and 1st row of the above matrix i.e., C1 and R1.

 Write all positions where 1 is present in column 1. C1 = {2,3,4}

 Also, write all position where 1 is present in row 1 R1 = ф
 Now, take the cross product of C1 and R1 = ф
Therefore, no new additions.
>>In step 2, we will consider 2nd column and 2nd row of the above matrix
C2 R2 C2×R2 = Ф
Ф {1, 3} Therefore, no new additions
>>In step 3, we will consider 3rd column and 3rd row.
C3 R3 C3×R3 = {(2, 1), (2, 4), (4, 1), (4, 1)}
{2, 4} {1, 4}

4
 [LECTURE 37] 2022

0 0 0 0
1 0 1 1
New matrix = [ ]
1 0 0 1
1 0 1 1
>>In step 4, we will consider 4th column and 4th row of the above matrix.
C4 R4
{2, 3, 4} {1, 3, 4}
C4×C4 = {(2,1),(2,3),(2,4),(3,1),(3,3),(3,4),(4,1),(4,3),(4,4)}
0 0 0 0
1 0 1 1
New matrix [Rt*] = [ ]
1 0 1 1
1 0 1 1
Rt* = {(2,1),(2,3),(2,4),(3,1),(3,3),(3,4),(4,1),(4,3),(4,4)}
Rt* is the transitive closure of relation R.

REFERENCE:
 Lecture on 21.11.2022 - Dr. Y. Sreenivasa Rao
 ICS 241 Discrete Mathematics II (Spring 2015) by Edsger W. Dijkstra

*****

5
MA4201:
Mr Mathematical Foundation of Computer Science MSc (M&SC),I Sem

LECTURE – 38
Department of Mathematics NIT Warangal By – Manish Dharmani, Neeraj Patnayak, Mainak Banerjee

Warshall’s Algorithm for Computing Transitive Closure:

Warshall's algorithm computes MR by efficiently computing W₁ , W2 ,……, Wn = MR .This observation shows
that we can compute Wk, directly from Wk-1: There is a path from vi to vj with no vertices other than v1, v2,
..., vk interior vertices if and only if either there is a path from vi to vj with its interior vertices among the first
k-1 vertices in the list, or there are paths from vi to vk and from vk to vj, that have interior vertices only among
the first k-1 vertices in the list. That is, either a path from vi to vj already existed before vk was permitted as
an interior vertex, or allowing vk as an interior vertex produces a path that goes from vi to vk and then from
vk to vj. These two cases are shown in bellow Figure.
The first type of path exists if and only if wij[k] =1, and the and second type of path exists if and only if both
wik[k-1]and wkj[k-1] . Hence, wij[k] is 1 if and only if either wij [k-1] is 1 or both wik[k-1] and wkj[k-1] are 1.

LEMMA: Let Wk = [wij[k]] be the zero-one matrix that has a 1 in its (I,j)th position if and only if there is a path
from vi to vj with interior vertices from the set {v1,v2,………,vn}. Then
wij[k]= wij [k-1] ˅(wik[k-1] ˄ wkj[k-1])
whenever i, j, and k are positive integers not exceeding n.
Counting of relations:
1.Reflexive Relation and Irreflexive Relation:

A reflexive relation on set A must contain the n elements (a,a) for every a∈A. The remaining number of pairs
is n2−n. So we can choose only among n2−n elements to build reflexive relations. Hence, there are
2 −𝑛
2𝑛 = 2𝑛(𝑛−1)
reflexive relations on a set with cardinality n.
An irreflexive relation is the opposite of a reflexive relation. It contains no identity elements (a,a) for
all a∈A. It is clear that the total number of irreflexive relations is given by the same formula as for reflexive
relations.

2.Symmetric relation:
We can determine the number of symmetric relations on a set A. A relation R defined on a set A with n
elements has ordered pairs of the form of (a, b). Now, we know that element 'a' can be chosen in n ways
and similarly, element 'b' can be chosen in n ways. This implies we have n2 ordered pairs (a, b) in R. Also, if
(a, b) is in R, then for a symmetric relation, (b, a) is forced to be in R. Therefore, we have 2 n(n-1)/2 such ordered
pairs. For a reflexive relation, we have ordered pairs of the form (a, a) which are also symmetric. We have
2n such ordered pairs. Hence, the number of symmetric relations is 2n. 2n(n-1)/2 = 2n(n+1)/2.
Antisymmetric relation and Asymmetric relation:

Consider an antisymmetric relation R on set A, say a, b ∈A with a≠b, then relation R must not contain
both (a, b) and (b, a). it may contain one of the ordered pairs or neither of them. Thus, there
are three possible choices for pairs. Therefore, the count of all combinations of these
𝑛(𝑛−1)
choices is equal to 3 2 . The number of subsets of pairs of the form (a, a) is equal to 2𝑛 .
𝑛(𝑛−1)
Therefore, total number of possible antisymmetric relations is equal to 2𝑛 ⋅ 3 2 .
For asymmetric relation almost everything is same as antisymmetric relation only the pairs
of the form (a, a) are not allowed. Thus, total number of possible asymmetric relation is
𝑛(𝑛−1)
equal to 3 2 .
**There is no particular counting technique for Transitive Relation**
Question:
1.how many possible relations are there on a set s={1,2,3,……,n} which are both reflexive and symmetric?
2.how many possible relations are there on a set s={1,2,3,……,n} which are both symmetric and
antisymmetric?
1. Kenneth H Rosen. Discrete Mathematics and It’s Applications with Combinatoies and Graph Theory, 7th edition,
Tata McGraw Hill,2017
2 .Lecture Notes - Dr. Y. Sreenivasa Rao
 MA4201: Mathematical Foundations of Computer Science MSc (M&SC), I Sem

Lecture-39
Department of Mathematics, NIT Warangal Date: 26.11.2022

Department
Definition of Mathematics,
(Equivalence NIT Warangal Scribe: Dr. Y. Sreenivasa RaoMA4201: Mathematical
Relation):
Foundations of Computer Science MSc (M&SC), I Sem
A relation 𝑅 on 𝐴 is called Equivalence Relation if 𝑅 satisfied the following condition:
1. 𝑅 is Reflexive (that is ∀𝑎 ∈ 𝐴 ⟹ 𝑎𝑅𝑎)
Lecture-5
2. 𝑅 is Symmetric (that is ∀𝑎∀𝑏(𝑎𝑅𝑏 ⟹ 𝑏𝑅𝑎))
3. 𝑅 is Transitive (that is ∀𝑎∀𝑏∀𝑐(𝑎𝑅𝑏 ∧ 𝑏𝑅𝑐 ⟹ 𝑎𝑅𝑐))
Definition
Department(Partition of a set):
of Mathematics, NIT Warangal Scribe: Dr. Y. Sreenivasa Rao
The class sets {𝐵𝑖 }𝑖∈𝐼 forms a partition for the set 𝐴 if
1. 𝐵𝑖 ≠ ∅
Lecture-5
2. 𝐵𝑖 ∩ 𝐵𝑗 = ∅, ∀𝑖 ≠ 𝑗
3. ⋃𝑖∈𝐼 𝐵𝑖 = 𝐴
Department of Mathematics, NIT Warangal Scribe: Dr. Y. Sreenivasa Rao

Statement 1: For every equivalence relation on a set 𝑨, there is a partition for 𝑨.

Proof. Let us consider 𝐴 be a set and ~ be an equivalence relation on 𝐴. Then the set of all
equivalence classes 𝐴/~ = {[𝑎]|𝑎 ∈ 𝐴}, where [𝑎] = {𝑏 ∈ 𝐴|𝑏~𝑎}. Our claim is that 𝐴/~
forms a partition for 𝐴.
(i) Let [𝑎] ∈ 𝐴/~ . Since ~ is reflexive and 𝑎 ∈ 𝐴, then 𝑎~𝑎. Implies that 𝑎 ∈ [𝑎] and
[𝑎] ≠ ∅.
(ii) Let [𝑎], [𝑏] ∈ 𝐴/~ , where [𝑎] ≠ [𝑏]. Let it consider [𝑎] ∩ [𝑏] ≠ ∅. Then there exist
some 𝑝 ∈ 𝐴 such that 𝑝 ∈ [𝑎] ∩ [𝑏]. Therefore 𝑎~𝑝 and 𝑏~𝑝. Now 𝑏~𝑝 ⟹ 𝑝~𝑏
(∵ ∼ is symmetric). Again (𝑎~𝑝 ) ∧ (𝑝 ∼ 𝑏) ⟹ 𝑎~𝑏. That contradicts [𝑎] ≠ [𝑏].
Hence [𝑎] ∩ [𝑏] ≠ ∅.
(iii) Here [𝑎] ⊆ 𝐴, ∀𝑎 ∈ 𝐴. That follows ⋃[𝑎]∈𝐴/~[𝑎] ⊆ 𝐴.
Again let 𝑥 ∈ 𝐴. Then 𝑥 ∈ 𝐴 ⟹ 𝑥 ∈ [𝑥]
⟹ 𝑥 ⊆ ⋃[𝑎]∈𝐴/~[𝑎].

Therefore ⋃[𝑎]∈𝐴/~[𝑎] = 𝐴.

That follows for the equivalence relation ∼ forms the partition 𝐴/∼ for 𝐴.

Statement 2: For every partition for 𝑨 induces an equivalence relation on 𝑨.

Proof. Let {𝐵1 , 𝐵2 , … , 𝐵𝑛 } be a partition for 𝐴. Define 𝑎, 𝑏 ∈ 𝐴 and 𝑎 ∼ 𝑏 if and only if 𝑎, 𝑏 ∈
𝐵𝑖 , for some 𝑖. Our claim is that ~ is an equivalence relation on 𝐴.

1
 (i) Let 𝑎 ∈ 𝐴. Then 𝑎 ∈ 𝐴
⟹ 𝑎 ∈ 𝐵1 ∪ 𝐵2 ∪ … ∪ 𝐵𝑛
⟹ 𝑎 ∈ 𝐵𝑖 , 𝑓or some 𝑖
⟹ 𝑎, 𝑎 ∈ 𝐵𝑖
⟹ 𝑎~𝑎. That follows 𝐴 is Reflexive.
(ii) Let 𝑎, 𝑏 ∈ 𝐴 and 𝑎~𝑏. Then 𝑎~𝑏 ⟹ 𝑎, 𝑏 ∈ 𝐵𝑖 , for some 𝑖
⟹ 𝑏, 𝑎 ∈ 𝐵𝑖
⟹ 𝑏~𝑎. That follows 𝐴 is Symmetric.
(iii) Let 𝑎, 𝑏, 𝑐 ∈ 𝐴 and 𝑎~𝑏, 𝑏~𝑐. Then 𝑎, 𝑏 ∈ 𝐵𝑖 and 𝑏, 𝑐 ∈ 𝐵𝑗 for some 𝑖, 𝑗. That
follows 𝑏 ∈ 𝐵𝑖 ∩ 𝐵𝑗 . But either 𝐵𝑖 ∩ 𝐵𝑗 = ∅ or 𝐵𝑖 = 𝐵𝑗 . Now 𝐵𝑖 ∩ 𝐵𝑗 ≠ ∅ that
follows 𝐵𝑖 = 𝐵𝑗 . Therefore 𝑎, 𝑐 ∈ 𝐵𝑖 = 𝐵𝑗 implies that 𝑎~𝑐. That show 𝐴 is
Transitive.
Hence ~ is an equivalence relation on 𝐴.

Note:
(i) The number of different equivalence relation on 𝐴 with |𝐴| = 𝑛
=The number of different partitions for 𝐴 with |𝐴| = 𝑛
= ∑𝑛𝑘=1 𝑆(𝑛, 𝑘) = 𝐵𝑛 (Bell Number)
(ii) If 𝑎 ∈ 𝐴 and 𝑎 ∈ 𝐵𝑖 for some 𝑖, then [𝑎] = 𝐵𝑖 .
Let any 𝑥 ∈ [𝑎]. Then 𝑥 ∈ [𝑎] ⟹ 𝑥~𝑎
⟹ 𝑥, 𝑎 ∈ 𝐵𝑖
⟹ 𝑥 ∈ 𝐵𝑖 .
That follows [𝑎] ⊆ 𝐵𝑖 .
Let any 𝑦 ∈ 𝐵𝑖 . Then 𝑦 ∈ 𝐵𝑖 ⟹ 𝑦, 𝑎 ∈ 𝐵𝑖
⟹ 𝑦~𝑎
⟹ 𝑦 ∈ [𝑎].
That follows 𝐵𝑖 ⊆ [𝑎]. Therefore [𝑎] = 𝐵𝑖 .

Example: Let 𝐴 = {1,2,3,4,5,6} and 𝐵1 = {1,2,3}, 𝐵2 = {4,5}, 𝐵3 = {6} are the partition for
A. Find the equivalence relation induces from {𝐵1 , 𝐵2 , 𝐵3 }.
The partition includes 3 subsets correspond to 3 equivalence classes of the relation
𝑅(say). We can denote these classes by 𝐸1 , 𝐸2 , 𝐸3 . They contain the following points:
𝐸1 = {(1,1), (2,2), (3,3), (1,2), (2,1), (1,3), (3,1), (2,3), (3,2)}
𝐸2 = {(4,4), (5,5), (4,5), (5,4)}
𝐸3 = {(6,6)}
Therefore, the relation 𝑅 roster form is given by
𝑅 = 𝐸1 ∪ 𝐸2 ∪ 𝐸3
= {(1,1), (2,2), (3,3), (4,4), (5,5), (6,6), (1,2), (2,1), (1,3), (3,1), (2,3), (3,2)(4,5), (5,4)}

2
Note:
From the above example, we noticed that 𝐸1 is nothing but 𝐵1 × 𝐵1. In the similar
way 𝐸2 = 𝐵2 × 𝐵2 and 𝐸3 = 𝐵3 × 𝐵3. Therefore, the equivalence relation 𝑅 on 𝐴 is
𝐸1 ∪ 𝐸2 ∪ 𝐸3 = (𝐵1 × 𝐵1 ) ∪ (𝐵2 × 𝐵2 ) ∪ (𝐵3 × 𝐵3 ).
Conclusion:
If {𝐵1 , 𝐵2 , … , 𝐵𝑛 } is a partition for 𝐴. Then the equivalence relation corresponding
to the partition is (𝐵1 × 𝐵1 ) ∪ (𝐵2 × 𝐵2 ) ∪ … ∪ (𝐵𝑛 × 𝐵𝑛 ).

Reference
1. Kenneth H Rosen. Discrete Mathematics and Its Applications with Combinatorics and
Graph Theory, 7th Edition, Tata McGraw Hill, 2017.
2. Lecture Notes: Dr. Y. Sreenivasa Rao

3
 MA4201: Mathematical Foundations of Computer Science MSc (M&SC), I Sem
Lecture-40
Department of Mathematics, NIT Warangal Scribe: Dr. Y. Sreenivasa Rao

Equivalent Relation: -
Let R be a relation on A that satisfies –
Reflexive Property
Symmetric Property
Transitive Property
is called equivalence relation.
E.g., 1 A=ℤ, m € ℤ+, R= ‘/ ‘
aRb  m/(a-b)
1) REFLEXIVE –
aRa  m/(a-a) = m/0
⇒ (a, a) € R, for all a € ℤ

2) SYMMETRIC-
(a, b) € R
 aRb  m/(a-b)
 m/(b-a)
 (b-a) € R

3) TRANSITIVE
(a, b) € R and (b, c) € R
m/(a-b) and m/(b-c)
Then m/(a-b)-(b-c)
⇒ m/(a-c)
Hence R is an equivalence relation
A=ℤ, m € ℤ+ (a, b) € R  m/(a-b)  a ≡ b (mod m)

E.g., A=ℤ/ {0} & R= /

aRb  a/b

This is reflexive, transitive but not symmetric that’s why it is not equivalence relation.

𝐿1 𝑅𝐿2 𝐿1 ||𝐿2 → not reflexive ⇒ not equivalent

EQUIVALENCE CLASSES
[a] = {b € A | (a, b) € R}
 = {b € A | m/(a-b)} a-b=m*q ⇒b=a-m*q where q € ℤ
= {a-m*q | q € ℤ}
a=3 and m=5
[3]5 = {3-5*q | q € ℤ}
= {-7, -2 ,3, 8, 13}
=The equivalence class containing 3
[0]5 = {0-5*q | q € ℤ}

= [5]5
The set of all equivalent classes
𝑍 ≡ 5 = {[0]5 , [1]5 , [2]5 , [3]5 , [4]5 }

A/R= {[𝑎]𝑅 | 𝑎 € A} → Forms partition of A

For any a, b € A
(i) [𝑎]𝑅 ∩ [𝑏]𝑅 =𝜙
(ii) [𝑎]𝑅 ≠ 𝜙
(iii) ∪a€ A [𝑎]𝑅 =A

Partition Let S be a non-empty set. Let {𝐵𝑖 }𝑘𝑖=1 be a family of subsets of S, and satisfies the following
conditions
(i) 𝐵𝑖 ≠ 𝜙,∀𝑖
(iv) 𝐵𝑖 ∩ 𝐵𝑗 = 𝜙
(ii) ∪𝑛𝑖=1 𝐵𝑖 = 𝑆

Then, {𝐵𝑖 }𝑘𝑖=1 is a partition on S

Every equivalence relation on S gives a partition for S.
𝑍 ≡ m = {[0]𝑚 , [1]𝑚 , [2]𝑚 , [3]𝑚 , … [𝑚 − 1]𝑚 }→General Form

Every equivalence relation on R, ∆⊆ 𝑅 ⊆ 𝐴𝑋𝐴

If R1 and R2 are equivalence relation then R1∩ R2 are also an equivalence relation, but R1∪ R2 may or
may not be
E.g. A= {1,2,3}

R1 1 2

3
 R2
1 2 3

1 2 3

R1∪R2
R1 and R2 are equivalence relation but R1∪R2 is not

since (1,2) , (2,3) € R1∪R2

but (1,3) does not belongs to R1∪R2

CLOSER OF AN EQUIVALENCE RELATION

Suppose R is not an equivalence relation on A
Trcl(Symcl | (Refcl(R)))
Algorithm
I/P : R is not an equivalence relation on A
1. Write MR
2. MR = MR V I
3. N=N V MT
4. T=Worskins(N)
5. Return T
MA4201 : Mathematical Foundations of Computer Science MSc(M&SC).I Sem

Department of mathematics, NIT Warangal Scribe- Dr. Y. Sreenivas Rao

𝐏𝐚𝐫𝐭𝐢𝐚𝐥𝐥𝐲 𝐎𝐫𝐝𝐞𝐫𝐞𝐝 𝐒𝐞𝐭 (𝐏𝐨𝐬𝐞𝐭):

Definition. A relation on a set 𝐴 is called a partial ordering or partial order if it is
• Reflexive

• Antisymmetric

• Transitive

Definition. If 𝐴 is a set and 𝑅 is a partial order on A, then the pair (𝐴, 𝑅)is called a partially ordered set
or poset

Notation. The partial order is denoted by ≼

Example:
(Z + ,≼= | ) is a poset.
But (Z/{0},≼=|) is not a poset.
Definition. Let (𝐴, ≼) be a poset and 𝑎, 𝑏 be two elements in 𝐴. If either 𝑎 ≼ 𝑏 or 𝑏 ≼ 𝑎, we say
that 𝑎 and 𝑏 are comparable. Otherwise, they are incomparable.
Example: A={1,2,3,4,5,6},≼=≤
Here all element are comparable to each other .

Totally Ordered Set.

Let (𝐴, ≼)be a poset. If every two elements of 𝐴 are comparable with respect to ≼, then ≼ is
called a total order or a linear order. In this case, (𝐴, ≼) is called a totally ordered set or chain.
Example: A={1,2,3,4,5,6},≼=≤
1≼ 2 ≼ 3 ≼ 4 ≼ 5 ≼ 6.
So here (𝐴, ≼) is called a totally ordered set or chain.

Least Element of a Poset.

Let (𝐴, ≼)be a poset such that 𝐵 ⊆ 𝐴. An element 𝑎 ∈ 𝐵 is a least element of 𝐵 if 𝑎 ≼ 𝑏 for all 𝑏
∈𝐵
Example:
(𝑍, ≼) ,where a≼b iff [|a|< |b| or (|a| = |b|) and (a≤b) ]
So (𝑍, ≼)is a poset.
0≼-1≼1≼-2≼2≼………..
Here 0 is the least element.
But (Z- ,≼=≤) does not have the least element.

Definition. A relation 𝑅 on a set 𝐴 is a well-order if

• (𝐴, 𝑅) is a chain
• Every non-empty subset of 𝐴 has a least element with respect to 𝑅.
In this case, (𝐴, 𝑅) is a well-ordered set and 𝑅 is a well-ordering of 𝐴.

Hasse Diagram of a Poset

Steps to construct a Hasse diagram:
• Construct a diagraph so that all arcs point up (except loops)
• Remove all self-loops
• Remove all transitive edges
• Eliminate the arrows by assuming that all arcs are oriented upwords
• The resulting diagram is a Hasse diagram
Example:
A={1,2,3,4} , ≼=≤
Ignore the self loop ignore transitive loop

4
3

2
1
a≼b ,that is a and b are comparable

a a a

b b b
if a and b are not comparable then ,
a b

Example:
let A={1,2,4,5,10,20}, ≼=| or (D20,|),i.e divisor of 20 with ≼=|
Hasse Diagram:
20
4 10

2 5
1

Exercise. Draw Hasse diagrams for the following posets

• 𝐴 = {1,2,3,4,5,6,7,8,9,10}, ≼ = divides
• 𝐴 = {2,3,4,5,6,30,60}, ≼ = divides
• 𝐴 = {2,4,6,12,24,36}, ≼ = divides

Maximal and Minimal element of a Poset: Let (𝐴, ≼)be a poset .

• 𝑎 ∈ 𝐴 is a minimal element iff there is no 𝑏 ∈ 𝐴 such that

• 𝑏 ≺ 𝑎 (i. e. , 𝑏 ≼ 𝑎 and 𝑏 ≠ 𝑎)
• 𝑎 ∈ 𝐴 is a maximal element iff there is no 𝑏 ∈ 𝐴 such that
• 𝑎 ≺ 𝑏 (i. e. , 𝑎 ≼ 𝑏 and 𝑎 ≠ 𝑏)
Note. There can be more than one minimal and maximal element in a poset.

Ex: a
x o y

C p q z

S t
In 1 no. picture maximal elements are b and a ,minimal element is c.
In 2 no. picture minimal elements are o , z and maximal element are x,o,y.
In 3 no. picture minmal elements are s,t and maximal elements are p,q.

Topological Sorting:
Motivation. Suppose that a project is made up of 100 different tasks. Some tasks can be
completed only after others have been finished. How can an order be found for these tasks?
To model this problem we setup a partial order on the set of tasks as follows:
𝑥 ≼ 𝑦 iff 𝑦 cannot be started until 𝑥 has been completed
Find a topological sorting.
Definition. Constructing a (compatible) total ordering from a given partial ordering is called
topological sorting (or linearization of a partial order)

Lemma. Every non-empty finite poset has at least one minimal element.
Topological Sorting Algorithm
Let (𝐴, ≼) be a non-empty finite poset.
• Choose a minimal element 𝑎 from (𝐴, ≼)
• Remove 𝑎 from 𝐴
Consider (𝐴 − {𝑎 }, ≼) which is a non-empty finite poset
• Choose a minimal element 𝑎 from (𝐴 − {𝑎 }, ≼)
Write 𝑎 ≺ 𝑎
• Remove 𝑎 from A
Consider (𝐴 − {𝑎 , 𝑎 }, ≼) which is a non-empty finite poset
• Choose a minimal element 𝑎 from (𝐴 − {𝑎 , 𝑎 }, ≼)
Write 𝑎 ≺ 𝑎 ≺ 𝑎
• Continue this process until no elements remain, i.e., 𝐴 is empty
𝑎 ≺ 𝑎 ≺ 𝑎 ≺ ⋯ ≺ 𝑎 is the required total ordering

Example :
A is non empty, |A| = n
A1

A2

A3

A4

An --------------------> Minimal element

Example. A development project at a computer company requires
the completion of seven tasks, numbered from 1 to 7.
The task 1 must be completed before 2 and 3 begin.
Task 4 cannot be started until 2 has been completed.
Tasks 2 and 3 are pre-requisite tasks fro 5.
Tasks 4 and 5 are pre-requisite tasks fro 7.
The task 6 can proceed only after 4 has completed.
We can only perform one task at a time.
Find a feasible order in which the tasks can be executed in order to
completed the project.
Solution :

6 7

4 5

2 3
1
Hasse Diagram

Exercise. Find a compatible total ordering for the poset ( {1, 2, 4, 5, 12, 20} , | ) .

Definition. Let (𝐴, ≼)be a poset.

• An element 𝑎 ∈ 𝐴 is a least element if 𝑎 ≼ 𝑏 for all 𝑏 ∈ 𝐴
• An element 𝑎 ∈ 𝐴 is a greatest element if 𝑏 ≼ 𝑎 for all 𝑏 ∈ 𝐴.
Example :
1 2 3 1 2
3
4
4 5
5
no least element, no greatest element

one least element, no greatest element

Theorem. Least and greatest elements are unique (if they exist).

Definition. Let (𝐴, ≼)be a poset and 𝑆 ⊆ 𝐴.

• An element 𝑎 ∈ 𝐴 is an upper bound of 𝑆 if 𝑠 ≼ 𝑎 for all 𝑠 ∈ 𝑆.
• An element 𝑎 ∈ 𝐴 is a lowerbound of 𝑆 if 𝑎 ≼ 𝑠 for all 𝑠 ∈ 𝑆.
Example :

4 5

2 3 4

1 2

1 Two lower bound, one upper bound

One upper bound , one lower bound

Theorem. glb and lub of 𝑆 are unique (if they exist).

Example: Find greatest lower bound and least upper bound, ( Z+ , | )
(a) A = {3,9,12} (b) B = {1,2,4,5,10}

a) b) 4 10

9 12

3 2 5

Glb = 3 , lub = 36 1 glb = 1 , lub = 20

Lattices
Definition. A poset is a lattice if every pair of elements has a lub and glb
Notation. 𝑙𝑢𝑏(𝑎, 𝑏) = 𝑎 ∨ 𝑏 (read 𝑎 join b)
𝑔𝑙𝑏(𝑎, 𝑏) = 𝑎 ∧ 𝑏 (read 𝑎 meet b)

Example : A={ {1, 2, 3, 4, 5} , | }  Not lattice

Definition. Let (𝐿, ≼)be a lattice such that S ⊆ 𝐿.

(𝑆, ≼) is a lattice (sublattice of 𝐿 iff 𝑎 ∨ 𝑏, 𝑎 ∧ 𝑏 for all 𝑎, 𝑏 ∈ 𝑆.

Application. Information flow is modeled as lattice.

Distributive Laws
Let 𝑥, 𝑦, 𝑧 ∈ 𝐿.
• 𝑥 ∧ (𝑦 ∨ 𝑧) = (𝑥 ∧ 𝑦) ∨ (𝑥 ∧ 𝑧)
• 𝑥 ∨ (𝑦 ∧ 𝑧) = (𝑥 ∨ 𝑦) ∧ (𝑥 ∨ 𝑧)
Example : e

c
a wee d

b
a ( c۷d ) = a۸e = a --------①
( a۸c ) ۷( a۸d ) = b۷b = b -------②
① and ② are not equal, therefore not a distributive class

Definition. A lattice satisfying distributive laws is called distributive lattice

Result. In a lattice (𝐿, ≼), for 𝑥, 𝑦, 𝑧 ∈ 𝐿, we have
𝒙∨𝒙=𝒙 𝒙∧𝒙=𝒙
𝒙≼𝒙∨𝒚 𝒙∧𝒚≼𝒙
𝒚≼𝒙∨𝒚 𝒙∧𝒚≼𝒚
𝒙∨𝒚= 𝒚∨𝒙 𝒙∧𝒚=𝒚∧𝒙
𝒙 ∨ (𝒚 ∨ 𝒛) = (𝒙 ∨ 𝒚) ∨ 𝒛 𝒙 ∧ (𝒚 ∧ 𝒛) = (𝒙 ∧ 𝒚) ∧ 𝒛
𝒙 ∨ (𝒙 ∧ 𝒚) = 𝒙 𝒙 ∧ (𝒙 ∨ 𝒚) = 𝒙
1. 𝒙 ∨ 𝒙 = 𝒙
𝑎 ∨ 𝑏 = 𝑙𝑢𝑏{𝑎, 𝑏}
𝒙 ∨ 𝒙 = 𝑙𝑢𝑏{𝑥, 𝑥}
𝒙≤𝒙 𝒙 is upper-bound for x

Definition. A lattice is said to be bounded lattice if it has the greatest element 1 and a least
element 0.
0≤x≤1
Definition. Let (𝐿, ≼, 0,1) be a bounded lattice.
For any 𝑎 ∈ 𝐿, there exists 𝑏 ∈ 𝐿 such that
𝑎 ∧ 𝑏 = 0, 𝑎 ∨ 𝑏 = 1
𝑏 is called a complement of 𝑎, denoted by 𝑎 or 𝑎
1

a b

Definition. A lattice 𝐿 is said to be complemented lattice if

• it is bounded and
• If every element in 𝐿 has a complement
1

a b

Question. Give an example of a finite lattice where at least one element has more than
one complement.

a ccc b

0
Question. Give an example of a finite lattice where at least one element has

NO complement.

Result. In a bounded distributive lattice, complement is unique (if it exists).

Boolean Algebra

The tuple is (B, ۷ ۸,--,0,1) is a Boolean algebra if it satisfy the following:

Result. A complemented, distributive lattice is a Boolean algebra

Example : The set of propositions of n varaibles with the ۷ and ۸ operators, F and T,

and the negation operator.