Introduction

What is Discrete Mathematics?

Discrete mathematics is the part of mathematics devoted to the study of discrete objects
i.e. distinct or unconnected objects.

Why we need to study discrete mathematics?

There are several important reasons to study discrete mathematics:
First, through this course we can develop our mathematical maturity i.e. the ability to understand
and create mathematical arguments. Getting to the depth of knowledge of mathematical sciences
will remain vague without these skills.
Second, discrete mathematics provides the mathematical foundations for many computer science
courses including data structures, algorithms, database theory, automata theory, formal
languages, compiler theory, computer security and operating systems.

The materials included in discrete mathematics are logic, set theory, number theory, linear
algebra, abstract algebra, combinatorics, graph theory and probability theory (discrete part).

Logic
Proposition: A proposition or statement is a declarative sentence which is true or false but not both.

Example: 1. Today is Monday.

2. Today is not Monday.

3. 1 + 1 = 2

4. 2 + 2 = 5

5. Puri is the capital of Odisha.

Truth Value: Something that adds sense or meaning to the proposition is called truth value.

Example: 1. Today is Monday. (True)

2. Today is not Monday. (False)

3. 1 + 1 = 2 (True)

4. 2 + 2 = 5 (False)

5. Puri is the capital of Odisha. (False)

Compound Proposition: Many propositions are composite, i.e. composed of sub propositions and
various connectives, such propositions are called compound propositions.

1
Primitives: Propositions that cannot be broken into simpler propositions are called primitives.

Connectives: Two or more primitives are joined into compound propositions by means of certain
words called connectives. Basically there are five connectives, they are and, or, not, if…then, if and
only if.

Truth Table: The truth value of a compound proposition is obtained y truth table.

Basic Logical Operations:

1. Negation (p or p):

Axiom: If ‘p’ is true, then ‘p’ is false and if ‘p’ is false then ‘p’ is true.
Truth Table:
p p
T F
F T

2. Conjunction (pq) (-‘and’ operator):

Axiom of Conjunction: If p and q both are true then, pq is true.
Truth Table:
p q pq
T T T
T F F
F T F
F F F
3. Disjunction (p  q) ( -‘or’ operator):
Axiom of Disjunction: If p and q both are false then, pq is true.
Truth Table:
p q pq
T T T
T F T
F T T
F F F
4. Implication (Conditional) ( →or ⇒ ----“Implies”, “if…then”):
Axiom of Implication: Let ‘p’ and ‘q’ be propositions. The conditional
statement p → q is false only in the case that, p is true but q is false and true
otherwise.
Truth Table:

2
 p q P→q
T T T
T F F
F T T
F F T
Here, p: hypotheses or antecedent or premise.
q: conclusion or consequence.
Note: The statement p → q is called conditional statement because p → q
asserts that ‘q’ is true on the condition that ‘p’ holds.
p is the condition (holds). First Statement (antecedent/hypothesis)
q is the statement (to be executed). Second Statement (consequent/conclusion)

5. Biconditional (⇔ or , “if and only if”):

Biconditional means conjunction of two conditional statements, here pq
means ( p → q) ( q → p). Thus, truth table of p  q is

Truth Table:
p Q p→q q→p pq
T T T T T
T F F T F
F T T F F
F F T T T

Some other logical statements:

Converse, contrapositive and Inverse: If p and q are propositions,
1) converse of p→ q is the implication q → p.
2) contrapositive of p→ q is the implication q→ p.
3) inverse of p→ q is the implication p → q.

Truth Table:
p q p→ q q→ p p q q→ p p→ q
(Conditional) (Converse) (Contrapositive) (Inverse)
T T T T F F T T
T F F T F T F T

3
 F T T F T F T F
F F T T T T T T

Exclusive Or (XOR)():
Truth table for the “exclusive or” of two propositions:
p Q pq
T T F
T F T
F T T
F F F

Precedence of logical operators:

Operator Precedence
 First
 Second
 Third
→ Fourth
 Fifth

Equivalent Propositions: When two composite propositions, say p and q, have the
same truth value, then they are called equivalent propositions. It is written as pq.
In other words, pq iff pq.

Eg: p( (p)), pq(pq), (pq) p q.

Construction of truth table: If the number of prime components is 2, then the table
contains 22=4 horizontal rows. Similarly, if the number of prime components is ‘n’
then there are ‘2n’ horizontal rows.

Question: Show that p(qr)  (pq)  (pr).

Solution: Constructing the truth table, we have,

p q r qr p(qr) (pq) (pr) (pq)  (pr)

T T T T T T T T
T T F F T T T T
T F T F T T T T
T F F F T T T T

4
 F T T T T T T T
F T F F F T F F
F F T F F F T F
F F F F F F F F

Tautology: A compound proposition whose truth value is always true, no matter,

whatever e the truth values of its respective propositions (primitives), is called a
tautology.

Contradiction: A compound proposition that is always false is called a contradiction or

an absurdity.

Contingency: A proposition that is neither a tautology nor a contradiction is called a

contingency.

Questions:

1. What are the contrapositive, the converse and the inverse of the conditional statement
“The home team wins whenever it is raining”?
2. For a given conditional statement, which statement is equivalent to it: converse,
contrapositive and inverse? Explain.
3. Out of converse, contrapositive and inverse which two statements are equivalent.
Give a proof.
4. Construct a truth table for each of the following:
i )  p  q     q  p 
ii )  p  q    q  p 
iii )  p  q    p   q 
iv )   p   q    q  r 
v)  p  q    r  s 
5. Show that: pp is a tautology.
6. Show that: pp is a contradiction.
7. Prove that ppp is a tautology.
8. Prove that (pq) (p q)  (q p) is a tautology.
9. Prove that “If the sky is cloudy then it will rain and it will not rain” is a contradiction.
10. Show that [(p q) q] p is a tautology.
11. Show that pq and (p q)  (q p) are equivalent.

5
12. Using truth table prove the following:
i) p   q  r   q   p  r 
ii)  p  q    p  q 
iii )  p  q    p  r    q  r  is a tautology.
iv)   p  q    p  q 
v)   p  q    p  q 
13. There are two hotels. One says “Good food is not cheap” and the other says “Cheap
food is not good”. Are they saying the same thing?
14. Verify that the two propositions ((pq) (pr)) s and (p(qr)) s are
equivalent.

Laws of Algebra of propositions:

(I) Logical Equivalences:

1. Identity Laws: pT=p, pF=p

2. Domination Laws: pT=T, pF=F
3. Idempotent Laws: pp=p, pp=p
4. Involution(or double negation):  (p)
5. Commutative Laws: pq qp, pq qp
6. Associative Laws: (pq) rp(q r), pq) rp (qr)
7. Distibutive Laws: p(qr) (pq)  (pr), p (qr) (pq)  (pr)
8. De Morgan’s Laws:  (pq)  pq,  (pq)  pq
9. Absorption Laws: p(pq) p, p (pq) p
10. Negation Laws: ppT, ppF (Law of excluded middle)

(II) Logical Equivalences involving implications:

1. p→ qpq (Contrapositive Law)

2. p→ q q→ p (Contrapositive Law)
3. p  q p→ q
4. p  q (p→ q)
5. (p → q)  pq
6. (p → q) (p→ r) p → (qr)
7. (p → r) (q→ r) (pq) → r
8. (p → q)  (p→ r) p→ (qr)
9. (p → r) (q→ r) (pq) → r
10. (p →q) (p→ q) → p (Contrapositive Law)
6
(III) Logical Equivalences involving bimplications(biconditionals):

1. p  q( p→ q) ( q→ p)
2. p  q pq
3. p  q (pq) (pq)
4. ( pq) p q

Questions:

1. Without using truth table show that (p(pq)) and pq are logically
equivalent.
2. Show that (pq) →(pq) is a tautology without using truth table.
3. Using laws show that (pq) (pq) p without using truth table.
4. Show that (p→q)  (r→q) (pr) →q without using truth table.
5. Show that {[(pq) →r] (p )} →( q → r) is a tautology without using truth
tables.
6. Is the statement ((p→q) (q→r)) → (p→r) a tautology? Prove it without using
truth table.

Predicates and Quantifiers (Predicate Calculus):

Predicates: Predicate is a generalization of proposition. It contains all the
components of propositional calculus, including propositional variables and constants.
Note: The part of the statement that follows the subject is called a ‘predicate’.
Consider the following statements:
x  3, x  y  3, x y  z
The above statements are neither true nor false when the values of the variables are
not specified.
The statement x  3 i.e. “x is greater than 3” has two parts:
1) The first part, variable ‘x’ is the subject of the statement, and
2) The second part which is the predicate i.e. “is greater than 3” refers to the property
that the subject of the statement can have.
Such statement is denoted as p(x) where, p denotes the predicate “is greater than 3”
and ‘x’ the variable is the subject.
Once a value has been assigned to the variable ‘x’, the statement p(x) becomes a
proposition and has a truth value.

Quantifiers:

7
1) One way predicates can be statements is by assigning specific values to their
variables.
2) Another way is by adding quantifiers.

Definition: Quantifiers are words that refer to quantities such a “some” or “all” and
indicate how frequently a certain statement is true.
Quantifiers are classified into two types:
1. Universal Quantifier
2. Existential Quantifier

1. Universal Quantifier or Universe of Discourse ( - ‘for all’): The universal

quantification of a predicate is the set of all possible values that may be substituted in
place of variables, i.e. “for all values of x, p(x) is true”.
The universal quantifier or universe of discourse is also called as domain or simply
‘universe’.
Symbolically we write: x p ( x ), p ( x ), x  A, x  A : p( x)
Example: 1. x  : x  5  5 is true. Since,  x : x  5  5  1, 2,3,  .
2. x  : x 2  1 is false. Since,  x : x 2  1    .
Note:
1. p(x) is an open statement and therefore has no truth value but x p( x) does have a
truth value.
2. x p( x) is same as p  x1   p  x2   p  x3     p  xn  .

2. Existential Quantifier (): Many mathematical statements assert that there is an

element with a certain property. Such statements are expressed using existential
quantification. It is denoted as x : p ( x ) or p(x) is true for some x  A.
Note:
1. With existential quantification, we form a proposition that is true if and only if p(x)
is true for at least one value of x in the universe of discourse.
2. x p( x) is same as p  x1   p  x2   p  x3     p  xn  .
Example: 1) The proposition x  : 1  x  1 is true. Since,
 x : 1  x  1  1, 0,1   (True).
2) The proposition x  : x  8  2 is false. Since,  x  : x  8  2   (False).

3. Negating Quantifiers:

8
Consider the statement: 1. “All the students in this class are intelligent.”
Negation:
2. It is not the case that all the students in the class are intelligent.
3. There is a student in the class who is not intelligent.
Let, P(x): x is intelligent and S denotes the set of all students in a class.
Then, Statement-1 implies x  S : p( x) .
Statement-2 and 3 can be expressed as   x  S : p  x   and x  S : p ( x ) .
Since, statement-2 and 3 are equivalent so,   x  S : p  x    x  S : p( x)

Table for Negating Quantifiers:

Negation Equivalent When is negation When False?
Statement true?
x p  x  x p  x  For every x, p(x) is There is an x for
false. which p(x) is true.
x p  x  x p  x  There is an x for p(x) is true for
which p(x) is false. every x.

Summary:
Value Statement Negation
All True x p  x  x p  x   at least one false.
At least one false x p  x  x p  x  all true.
All False x  p  x    x P  x  at least one true
At least one true  x P  x  x P  x   all false

Nested Quantifiers or Multiple Quantifiers:

Nested quantifiers are quantifiers that occur within the scope of other quantifiers. E.g.
For all x there exist y such that x + y = 0 is true or  x  y  x  y  0  .
Note: The order of quantifiers is very important. The statement xyP  x, y  and
yxP  x, y  are not logically equivalent.
There are 8 ways to apply the two quantifiers to the two variables. According to the
order:
1. x y 2. yx 3. xy 4. yx 5. x y 6. y x 7. y x 8. x y
Meaning:
P(x,y): x is related to y or x meets y
1. x y P  x, y  : Everyone meets Everybody.

9
 2. yx P  x, y  Everyone meets Somebody.
3. xy P  x, y  : Someone meets Somebody.
4. yx P  x, y  : Someone meets Everybody
5. x y P  x, y  : Everybody is met by Everyone.
6. y x P  x, y  : Everybody is met by someone.
7. y x P  x, y  : There is somebody whom everyone meets.
8. x y P  x, y  : There is somebody whom someone meets.
Note: 1 & 2, 7 & 8 are logically equivalent.
********

Methods of Proof
Rules of Inferences:
1. Hypotheses: The propositions that are assumed to be true are called premises
or hypotheses.
2. Conclusion: The propositions derived by using the rules of inferences is called
conclusion.
3. Valid Argument: The process of deriving conclusions based on the assumption
of premises is called a valid argument.
Note: In valid argument we are concerned with the process of arriving at the
conclusion rather than obtaining the conclusion.
Table:
Rule of Inference Tautological Form Name
p p   p  q Addition
1.
pq
pq  p  q  p Simplification
2.
p
p Conjunction
 ( p)  ( q)   p  q
3. q
pq
pq  p  q   p   q Modus Ponens
p
4.
 q
pq  p  q   q   p Modus Tollens
q
5.
 p

10
 pq  p  q    q  r    ( p  r ) Hypothetical Syllogism
qr
6.
pr
pq  p  q   p   q Disjunction Syllogism
p
7.
 q
p  q  (r  s) ( p  q )  (r  s)  ( p  r )  (q  s) Constructive Dilemma
pr
8.
 q s
p  q  (r  s) ( p  q )  ( r  s )  ( q   s ) Destructive Dilemma
q  s  ( p  r )
9.
 p  s
pq  p  q   (p  r )   (q  r ) Resolution
p  r
10.
q  r

Examples:
1. Modus Ponens or The Law of Detachment:
Find the conclusion of the following statements:
i. “If it snows today, then we will go skiing.” “It is snowing today.”
Conclusion: We will go skiing.
ii. “If n is greater than 3, then n2 is greater than 9.” “ n is greater than 3.”
Conclusion: “ n2 is greater than 9.”
iii. “If John has a B in calculus, he will graduate.” “John does have a B in
calculus.”
Conclusion: “ Therefore he will graduate.”
2. Modus Tollens or Method of Denying:
i. Harvey is a dentist, then Harvey drills teeth. Harvey does not drill teeth.
Conclusion: Harvey is not a dentist.
3. Disjunction Syllogism:
i. Either elephants are blue or monkeys are green. Elephants are grey.
Conclusion: Monkeys are green.
4. Hypothetical Syllogism:
P: Mary is senior, Q: Mary wears a pin, R: Mary will graduate.
Conclusion: If Mary is a senior , then Mary will graduate.

Examples:

Question: State which rule of inference is the basis of the following argument:

11
 1. “It is below freezing now.” Therefore, it is either below freezing or raining now.”
Solution: Addition Rule. Explanation: p p  q
2. “It is below freezing and raining now.” “Therefore, it is below freezing now.”
Solution: Simplification Rule.
Question:
3. Show that the hypotheses “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”, and “If we take a canoe trip, then we
will be home by sunset” lead to the conclusion “We will be home by sunset”.

Solution:
p: It is sunny this afternoon. q: It is colder than yesterday. r: We will go
swimming. s: We will take a canoe trip. t: We will be home by sunset.
So, we have the following,
hypotheses: p  q, r  p, r  s, s  t and
conclusion: t (To Prove)
Proof: No. Step Reason
1. p  q Hypothesis
2. p Simplification by 1
3. r p Hypothesis
4. r Modus tollens by 2 & 3
5. r  s Hypothesis
6. s Modus ponens by 4 & 5
7. s t Hypothesis
8. t Modus ponens by 6 & 7

4. Show that the hypotheses “If you send me an e-mail message, then I will finish
writing the program”, “If you do not send me an e-mail message, then I will go to
sleep early”, and “If I go to sleep early, then I will wake up feeling refreshed” lead
to the conclusion “If I do not finish writing the program, then I will wake up
feeling refreshed”.

Solution:
p: You send me an e-mail message. q: I will finish writing the program.
r: I will go to sleep early. s: I will wake up feeling refreshed.
So, we have the following,
hypotheses: p  q ,  p  r , r  s . and
conclusion: q  s (To Prove)
12
 Proof: No. Step Reason
1. pq Hypothesis
2. q  p Contrapositive
3. p  r Hypothesis
4. q  r Hypothetical Syllogism
2&3
5. rs Hypothesis
6. q  s Hypothetical Syllogism
4 & 5 (required
conclusion)
***********

Sequences and Summations

Sequence: A sequence is a function from a subset of the set of integers
usually either or W to a set S.
Note:
1. The notation an is used to denote the image of the integer ‘n’.
2. ‘an’is called term of the sequence.
3. The notation { an }is used to describe the sequence.
1
Example: List the terms of the sequence { an }, where an  .
n
1 1 1
Answer: an   1, , , ,
2 3 4
Arithmetic Progression: An arithmetic progression is a sequence of the form
a, a+d, a+2d,…,a+nd, where the initial term ‘a’ and the common difference
‘d’ are real numbers.
It is denoted by the function f ( x )  dx  a. Eg: {sn} where sn= 1+4n, n  .
Geometric Progression: A geometric progression is a sequence of the form a,
ar, ar2,…,arn, where the initial term ‘a’ and the common ratio ‘r’ are real
numbers. It is denoted by the function f  x   ar x . Eg: {bn} with bn=(1)n.
Strings: Sequences of the form a1, a2,…, an are finite sequences also called
strings. A string is denoted by a1a2…an.
Note:
1. The length of the string S is the number of terms in the string.

13
 2. The empty string is the string that has no terms. It is denoted by λ. Its
length is zero.

Example: The string abcd is a string of length four.

Questions: find formulas for the following sequences:

1 1 1 1
1. 1, , , , ,
2 4 8 16
Ans: This is a G.P. with first term a = 1 and common ratio =1/2. The
1
required sequence is {an} with an  .
2 n 1
2. 1,3,5, 7,9,
Ans: This is a A.P. with first term a=1 and common difference d=2. The
required sequence is {an} with an= 2n1.
3. 1, 1,1, 1,1, 1,
Ans: This is a G.P. with first term a = 1 and common ratio = 1. The
n 1
required sequence is {an} with an   1 .
4. Obtain the next 10 terms of the sequence 1, 2, 2,3,3,3, 4, 4, 4, 4,
Ans: 5,5, 5,5,5, 6, 6, 6, 6, 6.

Summations: The partial sum of the terms of a sequence is called series or

summations.

Thus, if {an}is a sequence with the terms a1 , a2 , a3 , , an , , then the sum of the
terms a1  a2  a3    an   (say), is termed series or summation of the sequence
{an}.
n
It is denoted as S n  a1  a2  a3    an or by the notation S n   am , where ‘m’ is
m 1

arbitrary and is called the index of summation, ‘1’ is the lower limit, ‘n’ is the
upper limit.

Examples:
1
1. Express the sum of the first 100 terms of the sequence {an}, where an  .
n
5
2
2. What is the value of j
j 1
?

14
 100
2
3. Find the value of k
k 50
.

4 3
4. Evaluate:  ij.
i 1 j 1

 ar n 1  a n
 , if r  1
Theorem: If ‘a’ and ‘r’ are real numbers and r  0, then  ar j   r  1 .
j 0   n  1 a , if r  1

n
Proof: Let, S   ar j
j 0
n n n1
 rS  r  ar j   ar j 1   ar k (byshiftingindex, k  j  1)
j 0 j 0 k 1
n
 n  n
  ar k  ar n1    ar k  ar 0   ar n1  ar 0   ar k   ar n1  a 
k 1  k 1  k 0

 n 
 rS  S   ar n1  a   S   ar j , j beingarbitrary 
 j 0 
  r 1 S   ar n1  a 

S 
 ar n1
 a
, r  1.
 r 1
and for r = 1, we have,
n n 1
S  
j 0
a   a (by sh iftin g in dex )
j 1

 a  a  a   ( n  1) tim es
 ( n  1) a .

Note: Some useful summation formulae:

Sum Closed Form

n n 1
k ar  a
1.  ar
k 0 r 1
,r 1
n
n( n  1)
2.  k 1
k
2
3. 
n
k2 n  n  1 2n  1
k 1
6

15
 n 2
4.  k 1
k3 n 2  n  1
4

xk , x  1 1
5.  k 0
1 x

*********

Mathematical Induction

Statement: A sentence or description which can be judged to e true or false is

called a statement.

Example:

1. 2 divides 6. True
2. Jaipur is the capital of Rajasthan. True
3. There are five days in a week. False
4. (x+1) is a factor of x 2  3 x  2. False
5. A B  B A True

Mathematical Statements: Statements involving mathematical relations are known

as mathematical statements.

Principle of Mathematical Induction:

1. First Principle of Mathematical Induction:

Let P(n) be a statement involving the natural number ‘n’, such that

(I) P(1) is true, i.e. P(n) is true for n = 1.

(II) P(m+1) is true, whenever P(m) is true, i.e. P(m) is true P(m+1) is true.

Then, P(n) is true for all natural numbers ‘n’.

2. Second Principle of Mathematical Induction:

Let P(n) be a statement involving the natural number ‘n’, such that

(I) P(1) is true, i.e. P(n) is true for n = 1.

(II) P(m+1) is true, whenever P(n) is true for all n, where 1 ≤ n ≤ m

16
 Then, P(n) is true for all natural numbers.

2. Prove by the principle of mathematical induction that for all ∈ N, ‘ n 2  n ’is even
natural number.

Solution: Basis Step: Step-I:

We have, P(n): ‘ n 2  n ’is even natural number.

For n=1, P(1): 12+1=2, which is an even natural number.

Therefore, P(1) is true.

Inductive Step: Step-II:

Let, P(m) be true for m ∈ .

Then, m2+m is even m2+m=2λ, for some λ ∈ . --------(1)

Now, we shall show, P(m+1) is true.

i.e. To prove: (m+1)2+(m+1) is an even natural number.

2
 m  1   m  1   m 2  2 m  1   m  1
  m 2  m    2m  2 
Now,
 2  2( m  1)
 2(  m  1)  2  , where     m  1  .

17
 2
  m  1   m  1 is an even natural number
 P(m  1)is true.

Thus, P(m) is true P(m+1) is true. Hence, by the principle of mathematical

induction, P(n) is true for all n  , i.e. n2+n is even for all n  .

3. Prove by the principle of mathematical induction that, n(n+1)(2n+1) is divisible y 6

for all n  .

Solution: LetP(n) be the statement “n(n+1)(2n+1) is divisible by 6”

i.e. P(n): n(n+1)(2n+1) is divisible by 6.

Step-I: For n=1, P(1): 1(1+1)(2.1+1)=6, which is divisible by 6.

Therefore, P(1) is true.

Step-II: Let, P(m) be true.

i.e. P(m): m(m+1)(2m+1) is divisible by 6.

m(m+1)(2m+1) = 6λ, for some   . -------(1)

Now we shall show that P(m+1) is true.

i.e. to prove P(m+1): (m+1)(m+1+1)[2(m+1)+1] is divisible by 6.

Consider , P(m 1) :  m  1 m 11 2  m  1 1   m 1 m  2 2m  2  1

  m 1 m  2  2m 1  2   m 1 m  2 2m 1  2  m 1 m  2

 m  m 1 2m 1  2  m 1 2m 1  2  m 1 m  2
 m  m 1 2m 1  2  m 1 2m 1 m  2
 m  m 1 2m 1  2  m 1 3m  3
2 2
 m  m 1 2m 1  6  m 1  6  6  m 1 (Using (1))
2
 6    m 1  , whichisdivisibleby6
 
 P  m 1 is true.

Thus, P(m) is true P(m+1) is true.

18
 Hence, by the principle of mathematical induction, the given statement is
true for all n  .
4. Prove that 4n  15n  1 is divisible by 9 for all natural numbers ‘n’.
Solution: Let P(n) be the statement given by
P(n): 4n  15n  1 is divisible y 9.
Step-I: For n=1, P(1):

5. Prove by induction that the sum S n  n3  3n 2  5n  3 is divisible by 3 for all

n .
6. Prove by the principle of mathematical induction that the sum of the first ‘n’
n  n  1
natural numbers is .
2
7. Prove by the principle of mathematical induction that the sum of square of the
n  n  1 2n  1
first ‘n’ natural numbers is .
6
8. Prove by the principle of mathematical induction that the sum of cube of the
2
 n  n  1 
first ‘n’ natural numbers is   .
 2 
9. Prove that for n  ,10n  3.4n 2  5 is divisible by 9.
10. Prove that for n  ,3n  n.
11. Use mathematical induction to prove that n3  n is divisible by 3 whenever n is
a positive integer.
12. Prove by induction that 11n  2  122 n1 is divisible by 133, n  .
1 1 1 1
13. 1      2
 2  for all n  2, ∈ .
4 9 n n
1 1 1 1
Solution: Let, P(n): 1      2  2  for all n  2, n  .
4 9 n n
1 1 1
Basis Step: For n=2, we have 1  2  1   1.25  1.50  2 
2 4 2
1 1
 1 2  2 
2 2
Therefore, P(n) is true for n=2.
Inductive Hypothesis: Let us assume that P(k) be true for all k  2, k  .
Inductive Step: To prove P(k+1) is true, on the basis that P(k) is true.
Now, since P(k) is true

19
 1 1 1 1
 1    2  2 
4 9 n n
1 1 1 1 1 1  1 
 1    2   2    adding the term on both sides 
4 9 n  n  1 2 n  n  1 2   n  1
2


1 1 1 1 1 1 
 1    2   2    
4 9 n  n  1 2  n  n  1 2 
 
1 1 1 1  n 2  2n  1  n 
 1    2   2   
4 9 n  n  1 2  n  n  1 2 
 
1 1 1 1   n2  n   1 
 1    2   2 
4 9 n  n  1 2  n  n  12 
 
1 1 1 1  n  n  1 1   n  n  1 
 1    2  2
 2 2
 2
  2 
4 9 n  n  1  n  n  1 n  n  1   n  n  1 2 
   
1 1 1 1 1
 1    2  2
 2
4 9 n  n  1 n 1
⇒ P(k+1) is true.
Therefore, P(n) is true for all n  2, n  N.
14. 3n  n ! if n  and n  6.
15. 2n  n 2 if n  and n  4.
16. 1+3+5+…+(2k1)=k2.
17. 1+2+22+…+2n =2n+11.
n
ar n 1  a
18.  ar i  , r  1.
i 0 r 1
19. n  2n , n  .
20. 2n  n !, n  , n  4.
21. Prove by induction that any positive integer n greater than or equal to 2 is either a
prime or product of primes.

Solution: Let, P(n): ‘n’ is a prime or product of primes, where ‘n’ is an integer and
n 2.
Basis step: For n  2, P  2   2.1  2, which is a prime.
For n  3, P  3  3.1  3, which is a prime.
For n  4, P  4   2.2  4, which is product of prime.
Inductive Hypothesis: Assume that P  j  is true for all positive integer j with j  k .
Inductive step: To Prove: P  k  1 is true.

20
 There are two cases:
Case  I : k  1 is prime.
If k  1 is prime, then this is obviously true and hence nothing to prove.
Case  II : k  1 is composite, then k  1 can be written as product of two integers. a
and b with 2  a  b  k  1.
Now by induction hypothesis, both a and b can be written as the product of
primes.
Thus, if k  1 is composite, it can be written as the product of primes, that is, those
primes in the factorization of a and those primes in the factorization of b .
Hence, P  k  is true  P  k  1 is true.
Therefore, P  n  is true.
************

Recursion And Structural Induction

Recursion: Defining an object in terms of itself is called recursion.

Eg: The sequence an  2n , n  0,1, 2, , can also be expressed in recursive method as
a0  1, an 1  2an , n  0,1, 2,3,...

Structural Induction: To prove results about recursively defined sets we use a

method called structural induction.

Now how to find recursively defined functions?

Basis Step: Specify the value of the function at zero.

Recursive Step: Give a rule for finding its value at an integer from its values at
smaller integers.

Examples:

1. Give an inductive definition of the factorial function F (n)  n ! .

Solution: Basis Step: F(0)=1
Inductive Step: F(n+1)=(n+1)F(n), n=0,1,2,3,…
2. Give a recursive definition of an, where ‘a’ is a non-zero real number and
‘n’ is a non-negative integer.
n
3. Give a recursive definition of a
k 0
k .
n
Solution: Let, F(m): a
m0
m

21
 0
Basis Step: F(0)=  am  a0 .
m 0
n 1 n
 
Inductive Step: F(m+1)=  am    am   an1
m 0  m 0 

Fibonacci Numbers: The sequence of numbers 1,1,2,3,5,8,13,… are called

Fibonacci numbers.

4. Express the Fibonacci numbers as a recursive formulae.

Solution: Basis Step: f0=0, f1=1
Inductive Step: fn=fn-1+fn-2, n=2,3,4,…
5. Show that whenever n  3, f n   n  2 , where   1  5  2.
Solution: Let P(n): f n   n  2 .
Basis Step: For n  3,   1.618  2  f3 .
Again for n  4,   2.618  3  f 4 .
So, P(3) and P(4) are true.
Inductive Step: Let P(j) be true, i.e. f j   j 2 for all integers j with 3  j  k ,
where k  4 .
To Prove: P(k+1) to be true. i.e. f k 1   k 1
1 5
We observe that ,   is a Solution of the quadratic equation
2
x 2  x  1  0.
Hence, we have  2    1. Therefore,
 k 1   2 . k 3    1  k 3   . k 3  1. k 3   k 2   k 3 .
Now, by induction hypothesis, for k  4 , we have,
f k 1   k 3 and f k   k  2 .
Therefore, we have f k 1  f k  f k 1   k  2   k 3   k 1
f(k+1) is true.

********

Solutions to Recurrence Relation

A sequence is called a Solution of a recurrence relation if its terms satisfy
the recurrence relation.
Example:

22
 1. Determine whether the sequence {an} is a Solution of the recurrence
relation an  2an1  an 2 for n=2,3,4,…, where
i) an=3n,
ii) an=2n
iii) an=5, for every nonnegative integer ‘n’.
Solution:
i) Suppose, an=3n for every non-negative integer ‘n’. Then, for n  2, we
have 2an 1  an 2  2 3  n  1  3  n  2    3n  an . Hence, {an}, where an=3n is a
Solution of the recurrence relation.
ii) Suppose, an=2n for every non-negative integer ‘n’. Then, for n  2, we
1 3
have 2an 1  an2  2  2n1   2n 2  2 n  2n 2  2n 1  2 
 2n.  an . Hence, {an},
 2  4
where an=2n is not a Solution of the recurrence relation.
iii) Let, an=5 for every non-negative integer ‘n’. Then, for n  2, we have
2an 1  an  2  2 5  5  10  5  5  an . Therefore, {an}, where an=5 is a Solution of
the recurrence relation.

Solving Recurrence Relation:

A linear homogeneous recurrence relation of degree ‘k’ with constant
coefficients is a recurrence relation of the form an  c1an1  c2 an 2    ck ak 1 ,
where c1 , c2 , , ck are real numbers and ck  0.
Examples:
1. What is the Solution of the recurrence relation an  an 1  2an2 with a0 =2 and
a1 = 7 ?
Solution:
Let, an = rn, where ‘r’ is a constant, n=0,1,2,3,…
Given, an  an 1  2an2 ----------(1) with a0=2 and a1=7.
Putting, an = rn in equn(1), we get
r n  r n 1  2r n  2
 r2  r  2  0
 r  0 and r  -1
Hence, the sequence {an} is a Solution to the recurrence relation iff
n
an  1 2n   2  1 , for some constants 1 and  2 .
Now from the initial condition, we have,

23
 a0  2  1   2 and
a1  7  21   2  1
On solving the above simultaneous linear equations, we get,
 1  3 and  2   1
Hence, the Solution to the recurrence relation and initial conditions is {an}
with an=3.2n - (-1)n.
2. Find an explicit formula for the Fibonacci numbers.
Solution: The sequence of numbers 1,1,2,3,5,8,13,… is called Fibonacci
numbers which is given by the recurrence relation f n  f n1  f n 2 -------(1)
with initial conditions f 0  0 and f1  1 whose Solution is obtained by putting
an  r n where r is a constant and n = 0,1,2,3,… in (1),
1 1
i.e. r n  r n 1  r n  2  1 
 2  r 2  r 1  0
r r
1 5 1 5
 r1  and r1 
2 2
Thus the Fibonacci numbers can also be given by
n n
 1 5  1 5 
Fn  1     2        (2) for some constants 1 and  2 .
 2   2 
Using the initial conditions f 0  0 and f1  1 in (2), we obtain,
f 0  1   2  0 and
1 5  1 5 
f1  1     2    1
 2   2 
On solving the above two simultaneous linear equations, we obtain,
1 1
1  and  2  
5 5
n n
1  1 5  1 1 5 
Hence, the Fibonacci numbers are given by Fn       .
5 2  5  2 
Formula-2: Let C1 and C2 be real numbers with C2  0 and r 2  C1r  C2  0
has only one root r0. Then the relation an  C1an1  C2an 2 has a solution
obtained by an  1r0 n   2 nr0 n , n = 0,1,2,3,…, 1 &  2 are constants.
3. What is the solution of the recurrence relation an  6an1  9an 2 with initial
condition a0  1 and a1  6 ?

24
Solution: Putting an=rn where r is a constant, n=0,1,2,3,… in an  6an1  9an 2
we have, r n  6r n1  9r n 2  r 2  6r  9  0  r  3 (repeated).
Hence, the solution to this recurrence relation is an  1 3n   2 n3n for some 1
and  2 .
Now, from the initial conditions, we have,
a0  1  1 and
a1  6  1 .3   2 .3
On solving the above two simultaneous equations, we get, 1  1 and  2  1
Hence, the solution is {an} with an=3n+n3n.

Formula-3: Let C1 , C2 , C3 ,  , Ck be real numbers. Suppose

r k  C1r k 1    Ck  0 has ‘k’ distinct roots. Then the recurrence relation
an  C1an 1  C2 an  2    Ck an  k has a Solution obtained by
an  1r1n   2 r2 n     k rk n , n=0,1,2,3,…, 1, 2,… are constants.

4. Find the Solution to the recurrence relation an  6an1  11an 2  6an3 with the
initial conditions a0 = 2, a1 = 5 and a2 =15.
Solution: Given, recurrence relation is an  6 an 1  11a n  2  6 a n  3 ------(1) with
initial conditions a0 = 2, a1 = 5 and a2 =15.
Putting, an= rn in (1), we get,
r n  6 r n  1  1 1 r n  2  6 r n  3  r 3  6 r 2  1 1 r  6  0  r  1, r  2 , r  3 .
Hence, the Solution to the recurrence relation is an  1 1n   2 2n   3 3n , ---
(2), for some constants 1, 2, 3.
Using the initial conditions, we obtain,
a0  2  1   2   3 ,
a1  5  1  2 2  3 3 ,
a2  15  1  4 2  9 3 .
On solving the above three simultaneous linear equations, we get,
1  1,  2  1and  3  2.
Hence, the unique Solution to this recurrence relation and the given initial
conditions is the sequence {an} with an  1  2 n  2  3n .

25
Formula-4: Let C1 , C2 , C3 , , Ck be real numbers. Suppose the characteristic
equation r k  C1r k 1    Ck  0 has ‘t’ distinct roots r1 , r2 , , rt with
multiplicities m1 , m2 , , mt respectively, so that mi1 for i=1, 2, …,t and
m1+m2+…+mt = k. Then a sequence {an} is a Solution of the recurrence
relation an  C1an 1  C2 an  2    Ck an  k if and only if

an   1,0   1,1n     1, m1 1n m1 1  r  
n
1 2,0   2,1 n     2, m2 1n m2 1 r n
2



  t ,0   t ,1 n     t , mt 1 n mt 1 r n
t
for n  0,1, 2,  , where  i , j are constants
for 1  i  t and 0  j  mi  1.

5. Find the Solution to the recurrence relation an  3an1  3an2  an3 with
initial conditions a0 = 1, a1= -2, a2 = -1.
Solution: Given, an  3an1  3an2  an3 -------- (1) with initial conditions a0
= 1, a1= -2, a2 = -1.
Let, an=rn, where ‘r’ is a constant, n=0,1,2,3,… . So (1) becomes,
r n   3 r n 1  3 r n  2  r n  3
 r 3  3r 2  3r  1  0
3
 r  1  0
i.e. r = -1 is a root of multiplicity 3 of the characteristic equation. Hence, the
Solution of the recursive relation (1) is of the form
n n n n
an  1,0  1,1n  1,2 n 2   1  1,0  1  1,1n  1  1,2 n 2  1 ------- (2), where

1,0, 1,1, 1,2 are constants.

To find the constants using the initial conditions, we have,
a 0  1   1, 0
a 1   2    1, 0   1,1   1, 2
a 2   1   1, 0  2  1 ,1  4  1 , 2
On solving the above linear simultaneous equations, we get,
1,0 = 1, 1,1 = 3, 1,2=2.
Hence, the unique Solution to this recurrence relation and the given initial
condition is the sequence {an} with an=(1+3n2n2)( 1)n.

26
Linear Non-Homogeneous Recurrence Relation With
Constant Coefficients:
The recurrence relation of the form an=C1 an-1+ C2 an-2+…+ Ck an-k+F(n)
where C1 ,C2 ,…, Ck are real numbers and F(n) is a function not identically
zero depending only on ‘n’ is called linear non-homogeneous recurrence
relation with constant coefficients.
E.g.: (i ) a  3a  2n
n n 1

(ii ) an  3an 1  n3n

(iii) an  an 1  an  2  an 3  n !
Note: The recurrence relation an=C1 an-1+ C2 an-2+…+ Ck an-k is called the
associated homogeneous recurrence relation, which plays an important role
in the Solution of the non-homogeneous recurrence relation.

Formula-5: If { an p  } is a particular Solution of the non-homogeneous linear

recurrence relation with constant coefficients an = C1 an-1+ C2 an-2+…
+Ck an-k+F(n), then every Solution is of the form { an p  an h }, where { an h }
is a Solution of the associated homogeneous recurrence relation an = C1 an-
1+ C2 an-2+…+Ck an-k.
Formula-6: Suppose that {an} satisfies the linear non-homogeneous
recurrence relation an  c1an1  c2 an 2    ck an k  F  n  , where c1, c2, …, ck are
real numbers and F  n    bt nt  bt 1nt 1    b1n  b0  s n , where b0, b1, …, bt and s
are real numbers.
Case-I: When ‘s’ is not a root of an( h ) then particular Solution is of the form
pnt
t
 pt 1nt 1    p1n  p0  s n .
Case-I: When ‘s’ is a root of an( h ) and its multiplicity is ‘m’ then particular
Solution is of the form n m  pt n t  pt 1n t 1    p1n  p0  s n .

6. What form does a particular Solution of the linear non homogeneous

recurrence relation an  6an1  9an 2  F (n) have when

27
i) F (n)  3n
ii ) F (n)  n3n
iii ) F (n)  n 2 2 n
iv) F ( n)   n 2  1 3n ?

Solution:
Associated linear homogeneous recurrence relation is a n  6 a n 1  9 a n  2 .
2
Characteristic equation is r 2  6r  9  0   r  3  0  r  3 (multiplicity 2).
Particular Solution:
i. F  n   3n , so particular Solution will be of the form an  P0 n 2 3n (Since, s=3
is a root of characteristic equation with multiplicity 2.)
ii. F  n   n3n , so particular Solution will be of the form an  n 2  p1n  p0  3n.
iii. F  n   n 2 2n , so particular Solution will be of the form
an   p2 n 2  p1n  p0  2n (since, s=2 is not a root of the characteristic
equation.)
iv. F  n    n 2  1 3n , so particular Solution will be of the form
an  n 2  p2 n 2  p1n  p0  3n .

7. Find all Solutions of the recurrence relation an  3an1  2n. What is the
Solution with a1=3?

Solution: The Solution to the associated linear homogeneous equation

an  3an 1 , with initial condition a1=3 is,
3
Let, an=rn, r=constant, n=0,1,2,3,… . So, r n  3r n 1  1   r  3.
r
Hence, the Solution to the homogeneous part is an h   3n. [ Now, from the
initial condition a1=3 we have 3  3      1. ]
Particular Solution: Since, F(n)=2n is a linear polynomial in ‘n’ i.e. of
degree one.
So, the particular Solution will also be in linear form, i.e. say, an=cn+d
 an  an( p )  .
Putting in the given equation,

28
 cn  d  3 c  n  1  d   2n
 cn  d  3cn  3c  3d  2n
  2c  2  n   3c  2d   0  0  n  0.
On comparing, we get,
2c  2  0 and 3c  2d  0
3
 c  1 and d .
2
3
Thus, a particular Solution is of the form an p    n  .
2
3
Hence, the general Solution or total Solution  an  an h  an p    n     3n ,
2
where ‘’ is constant.
To find the Solution with a1  3 , let n=1, we have,
3
a1  3  1     31
2
   11 .
6
3
So, the required Solution with a1  3 is an   n   11 6 3n.
2
 
8. Find all Solutions of the recurrence relation an  5an 1  6an  2  7n .

Solution: The given equation an  5an 1  6an  2  7n (1) is a linear non

homogeneous recurrence relation.
The Solution of the associated homogeneous recurrence relation
an  5an 1  6an 2 is obtained as,
Let, an  r n , r= constant, n=0,1,2,3,… so,
r n  5r n 1  6r n 2
5 6
1  2
r r
2
 r  5r  6  0
 r  3, 2.
Hence, the Solution to the homogeneous part is an h   1 3n   2 2n , for some
constants 1 and  2 .
Particular Solution: Since F  n   7 n , so the particular Solution will be of the
form an  c  7 n , where c=constant. So putting in (1), we have,

29
 c  7 n  5  c  7 n 1  6  c  7 n  2  7 n
7n 7n
 c  7 n  5c
 6c 2  7 n
7 7
5 6
 c  c  c 1
7 49
49
c .
20
49  n
Hence, the particular Solution is an p    7 .
 20 
49  n
Hence the total Solution is an  an h  an p  1 3n   2 2n   7 .
 20 

9. Let an be the sum of the first ‘n’ positive integers. Form a recurrence
relation with an initial condition. Determine a formula for an by solving this
recurrence relation.

Solution:

*********

Generating Function

The generating function for the sequence a0, a1,…, ak,... of real numbers is

the infinite series G  x   a0  a1 x    ak x k     ak x k .
k 0

Generating functions are used to represent sequences efficiently by coding

the terms of a sequence as coefficients of powers of a variable ‘x’ in a
formal power series.
E.g.: The generating functions for the sequences {ak} with

k
(i) ak = 3 is  3x
k 0

k
(ii) ak = k+1 is  3x
k 0

k
(iii) ak = 2k is  3x
k 0

Questions:

30
1. What is the generating function for the sequence 1, 1, 1, 1, 1, 1 ?
6
k x6 1
2 3 4 6
Solution: Here, ak=1. So,  ak x  1  x  x  x  x  x   G  x
k 0 x 1
2. What is the generating function for the sequence 1, 1, 1, … ?
Solution: Here, ak=1. So,
 
1
G  x    ak x k   x k  1  x  x 2  x 3    for x  1.
k 0 k 0 1 x

Examples (Answer the following questions):

1. Use generating function to find the Solution of the recurrence relation
ak  3ak 1 for k = 1, 2, 3, … and initial condition a0 = 2.

Solution: Let, G  x    ak x k , ----------- (1) be the generating function for the
k 0

sequence {ak}.
Given, recurrence relation is ak  3ak 1 for k = 1, 2, 3, … with initial
condition a0 = 2.   
k k 1
Now, from (1), xG ( x )  x  ak x   ak x  a j 1 x j  by shifting index 
k 0 k 0 j 1 0
 
  a j 1 x j   a k 1 x k  ' k ' being arbitrary 
j 1 k 1

31
Now given,
ak  3ak 1  ak  3ak 1  0    (1)
Now,Consider G  x   3xG(x)
 
 ak x 3ak 1xk k

k 0 k 1
 
 a0  ak xk 3ak 1xk
k 1 k 1

 a0   ak  3ak 1  xk
k 1

 a0  0 xk  a0  2(fromthegiveninitialcondition)
k 1

 1  3x G  x  2

2  1  
 G  x   23k xk   1 ax  a2 x2  a3 x3   k 0 ak xk 
1 3x k 0  1 ax 

 G  x   2 3k xk . Thus, ak  2 3k.
k 0

2. For the recurrence relation an  8an 1  10n 1 and the initial condition a0  1 ,
find an explicit formula for an, using generating functions.

n
Solution: Let, G  x    an x be the generating function of the sequence a0, a1,
n 0

… -------(1)
n 1
The given recurrence relation is an  8an 1  10 ------(2) with initial condition
a1 = 9.
 a n x n  8 a n 1 x n  10 n 1 x n
  
  an x n   8an 1 x n   10 n 1 x n  Taking summation on both sides 
n 1 n 1 n 1
  
 
   an x  a 0   a 0   8 a n 1 x   10 n 1 x n
n n

 n 1  n 1 n 1

32
  
 G  x   1  8 x  an 1 x n 1  x 10n 1 x n 1
n 1 n 1
 
 8 x  an x n  x 10n x n
n 0 n 0

x
 8 xG  x  
1  10 x
x 1  9x
 G  x   8 xG  x   1  
1  10 x 1  10 x
1  9x 1 1 1 
 G  x    
1  10 x 1  8 x  2  1  8 x 1  10 x 
1  
  1
   8n x n   10n x n     8n  10 n x n
2  n 0 n 0  n 0 2

1 n
Hence, the Solution is {an}, with an 
2
 8  10n  .
n
3. Use generating function to show that  C (n, k ) 2  C (2n, n) , where ‘n’ is a positive
k 0

integer.
Solution: By the binomial theorem, we have,
2n
1  x   2 nC0  2 nC1  2 nC2    2 nCn    2 nC2 n ----------- (1)
From, (1) we have coefficient of x n  C  2n, n  --------- (2)
Again,
2n n 2 2
1  x   1  x    C  n, 0   C  n,1 x  C  n, 2  x 2    C  n, n  x n 
 
 C  n, 0   C  n,1 x  C  n, 2  x 2    C  n, n  x n  C  n, 0   C  n,1 x  C  n, 2  x 2    C  n, n  x n 

In particular, the coefficient of xn is

C  n, 0  C  n, n   C  n,1 C  n, n  1  C  n, 2  C  n, n  2     C  n, n  C  n, 0 
 C  n, 0  C  n, 0   C  n,1 C  n,1  C  n, 2  C  n, 2     C  n, n  C  n, n   C  n, r   C  n, n  r  
2 2 2 2
 C  n, 0   C  n,1  C  n, 2     C  n, n 
n
2
  C  n, k         (3)
k 0

From, (2) and (3), we have,

n
2
 C  n, k 
k 0
 C 2n, n .

4. Use generating function to solve the recurrence relation ak  7 ak 1 with the initial
condition a0  5 .

33
5. Use generating function to solve the recurrence relation ak  3ak 1  2 with the initial
condition a0  1 .
6. Use generating function to solve the recurrence relation ak  3ak 1  4 k 1 with the initial
condition a0  1 .
7. Use generating function to solve the recurrence relation ak  5ak 1  6ak  2 with the
initial condition a0  6 and a1  30.

***************

Inclusion-Exclusion Principle

1. For two elements A, B, A  B  A  B  A  B .

2. For three elements, A, B, C,
A B C  A  B  C  A B  AC  B C  A B C
3. In general, for finite sets A1, A2,…, An,
n 1
A1  A2    An   Ai   Ai  A j   Ai  A j  Ak     1 A1  A2    An
1 i  n 1 i  j  n 1 i  j  k  n

Examples:
1. Let A and B be two sets such that, n( A)  20, n( A  B )  42 and n( A  B )  4.
Find i) n(B), ii) n(A-B), iii) n(B-A).

Solution:

2. A survey shows that 76% of the Indians like oranges, where as 62% like bananas.
What percentage of the Indians like both oranges and bananas?

Solution: A  76, B  62, A  B  100, A  B  A  B  A  B  76  62  100  38.

3. Out of the members of three athletic teams in a certain school, 21 are in the
basketball team, 26 in hockey team and 29 in the football team. 14 play hockey
and basketball, 15 play hockey and football, 12 play football and basketball and 8
play all the three games. How many members are there in all?

Solution: Let, A, B and C be the sets of members of basketball, hockey and

football teams respectively. Then,
A  21, B  26, C  29, A  B  14, B  C  15, A  C  12, A  B  C  8.
Now, by inclusion-exclusion principle, we have,
A B C  A  B  C  A B  B C  AC  A B C

34
 4. In a group of 1000 people, there are 750 who can speak Hindi and 400 who can
speak Telugu. How many can speak Hindi only? How many can speak Telugu
only? How many can speak both Hindi and Telugu?

Solution:

5. How many bit strings of length eight either start with a ‘1’ bit or end with the two
bits ‘00’?

Solution: We know, by inclusion-exclusion principle: A  B  A  B  A  B .

Let, A  Strings of length 8 starting with 1.
1 0 /10 /10 /10 /10 /10 /10 /1  1.2.2.2.2.2.2.2  2 7  128 ways, so A  128.
  
27

B  Strings of length 8 ending with 00.

0 /10 /10 /10 /10 /10 /10 /1 0 0  26  64 ways, so B  64.
Now, AB= All those bit strings which begin with 1 bit and end with 00
i.e. A and B  1 0 /10 /10 /10 /10 /10 /1 00  25 ways, so A  B  32.
So, by the inclusion-exclusion principle, number of strings of length eight
starting with a 1 bit or end with two bits 00  A  B  128  64  32  160.

6. How many bit strings of length seven either begin with two 0’s or end with three
1’s ?

Solution:

***************

Relations on a Set

Cartesian Product: Let A and B be two non-empty sets. The Cartesian product of A and B is
defined and denoted as A  B   x, y  x  A and y  B. Eg: A  1, 2,3 , B  2,5. Then,
A  B  1, 2  ,  2, 2  ,  3, 2  , 1,5  ,  2, 5 ,  3,5 .

Relation:

Properties:
1. Reflexive: A relation on a set ‘A’ is called reflexive if (a,a)R for every element
aA.
2. Symmetric: (b,a)  R whenever (a,b)  R, for all a,b  A.

35
3. Anti-Symmetric: A relation ‘R’ on a set ‘A’ is defined such that (a,b)  R and (b,a)
 R only if a = b, for all a,b A is called anti symmetric.
4. Transitive: A relation R on a set ‘A’ is called transitive if whenever (a,b) R and
(b,c) R, then (a,c) R for all a,b,cA.
2
Note: There are 2n relations on a set with ‘n’ elements.

5. Composite: Let ‘R’ be a relation from a set A to a set B and ‘S’ is a relation from
set ‘B’ to set ‘C’. The composite of ‘R’ and ‘S’ is the relation consisting of
ordered pairs (a,c) where a  A and c  C and for which there exists an element b 
B such that (a,b) R and (b,c)  S. The composite of ‘R’ and ‘S’ is denoted by
S  R.
6. Powers of a Relation ‘R’: Let ‘R’ be a relation on the set A. The powers
R n , n  1, 2, 3,  are defined recursively by R1  R and R n 1  R n  R.
So, R 2  R  R , R 3  R 2  R   R  R   R and so on.

Example: Let R  1,1 ,  2,1 ,  3, 2  ,  4,3. Find the powers R n , n  2, 3, .

Solution: R 2  R  R  1,1 ,  2,1 ,  3,1 ,  4, 2 
R3  R 2  R  1,1 ,  2,1 ,  3,1 ,  4,1 , R 4  R3  R  1,1 ,  2,1 ,  3,1 ,  4,1 ,
R5  R 4  R  1,1 ,  2,1 ,  3,1 ,  4,1 , continuing in this manner we see that
R n  R 3 for n=2,3,4,…

Note: The relation ‘R’ on a set ‘A’ is transitive iff R n  R for n = 1,2,3,…

Closures of Relation:

i) Reflexive: Set A  1, 2,3 , Let a relation be defined by

R  1,1 , 1, 2  ,  2,1 ,  3, 2  . The given relation is not a reflexive relation as the
elements of the form (a, a) are missing i.e. the elements (2,2), (3,3) are
missing.
The set    a, a  | a  A is called diagonal relation on A as they are the
elements along the main diagonal of a matrix.
ii) Symmetric: Set A  1, 2,3 , Let a relation be defined by
R  1,1 , 1, 2  ,  2, 2  ,  2,3 3,1 ,  3, 2  . The given relation is not a symmetric
relation as for the elements (a, b) the elements of the form (b, a) are missing
i.e. the elements (2, 1), (1, 3) are missing.
The set R 1   b, a  |  a, b   R is called the inverse relation of A as they are the
elements obtained by reversing the order of the elements of ‘R’.
iii) Transitive closure and its construction:

36
 Consider a Set A={1,2,3,4}. Let a relation be defined by R={(1,3), (1,4), (2,1),
(3,2)}. The given relation is not a transitive relation as the following elements
(1, 2), (2, 3), (2, 4), (3, 1) are missing in ‘R’. However including them still the
relation ‘R’ is not transitive because (3, 4) cannot be included.

Definition: Let R be a relation on a set A. The connectivity relation R * consists of the

pairs (a,b) such that there is a path of length atleast one from ‘a’ to ‘b’ in R. Infact the
transitive closure of a relation R equals the connectivity relation R *.

Warshall’s Algorithm:

It is an efficient method for computing the transitive closure of a relation, which uses
the concept of the interior vertices of a path.
We know an algorithm is a step-by-step specification on how to perform a certain
task. Here we basically deal with the applications of the theory of digraphs and
relations to the study of algorithms. There are many aspects of an algorithm. One of
the most basic aspects is the correctness of an algorithm. An algorithm is considered
to be correct if, when performed on input that satisfies its input requirements, the
algorithm terminates and yields output that satisfies its output requirements.

Algorithm for computing the transitive closure:

1. Input: The adjacency matrix ‘M’ of digraph (V, E), where V={v1, v2, …, vn}.
2. Output: A new adjacency matrix ‘M’, which is the adjacency matrix of (V, E +).
3. Method: For each ‘k’ from 1 upto ‘n’ (sequentially) do the following:
For each pair (i, j) such that 1i,jn (in any order) do the following:
(*) If M(i, k)=1, M(k, j)=1, and M(i, j)=0 then change M(i, j) to 1.

Basic Idea:
For each vertex ‘vk’ and all the paths through it, the main loop of the algorithm
considers all of the possible two step paths from vi to vj that go into and out of vk and
if any are found, the algorithm builds a bypass (vi, vj), provided such a bypass doesn’t
already exist.
Ultimately, each vertex is by passed, which means that for each path in the original
graph there will be a direct connection (edge) in the result.

Application:
Start with M0, the adjacency matrix of the relation ‘R’, and then successively
construct the matrices M1, M2, …, Mn, where ‘n’ is the number of vertices for the
relation ‘R’.
Moreover, for each k1, we can construct Mk in terms of the previously constructed
matrices Mk-1.
Mk(i, j) can be obtained from the condition (*) (mentioned above)

37
 Warshall observed that Mk[i, j]=1 can occur only if one of the following two cases
occurs:
i. There is a simple path from vi to vj which does not use any other vertices except
possibly v1, v2, …, vk-1; Mk-1[i, j]=1.
ii. There is a simple path from vi to vk and a simple path from vk to vj where each
simple path does not use any other vertices except possibly v1, v2, …, vk-1, hence
Mk-1[i, j] = 1 and Mk-1[k, j] = 1

These two cases are pictured as follows:

(1) vi … vj (2) vi … vk … vj

Here, “ … ” denotes part of a simple path which does not use any other vertices
except possibly v1, v2, …, vk-1.
Accordingly, the elements of Mk can be obtained by
M k  i, j   M k 1 i, j    M k 1 i, k   M k 1  k , j  ,
where ‘’ & ‘’ are the usual logical operators ‘AND’ and ‘OR’, respectively.
In other words, we can obtain each entry in the matrix Mk by looking at only three
entries in the matrix Mk-1.

Example: If a, b, c, d, e, f, g is a path then its interior vertices are b, c, d, e, f. Similarly

if a, x1, x2, x3,… , xm-1, b is a path, its interior vertices are x1, x2, x3,… , xm-1 i.e. the
vertices except the first and last vertices.

Note: Warshall’s algorithm is based on the construction of a sequence of zero-one

matrices. These matrices are W0, W1,…, Wn, where W0=MR is the zero-one matrix of
1,if there is a path from vi to v j
this relation and Wk   wij( k )   
 0, otherwise

7. Matrix of a Relation (0-1 Matrix): Another way of representing a relation R from A to

B is with a matrix.
Rows = Elements of A, Columns = Elements of B. If a  A and b  B then we write ‘1’
in row ‘a’ column ‘b’ if aRb, otherwise we write ‘0’.
Example: The relation R={(a,1), (b,1), (c,2), (c,3)} form A={a, b, c, d} to B={1, 2, 3,
4} has the following matrix:
1 2 3 4
a 1 0 0 0
b 1 0 0 0
 
c 0 1 1 0
 
d 0 0 0 0

38
 Answer the following questions:
1. Let R be the relation with directed graph as shown in the figure below. Let a, b, c, d
be a listing of the elements of the set. By Warshall’s algorithm find the matrices W0,
W1, W2, W3, and W4, where W4 is the transitive closure of R.

Solution: Let v1  a, v2  b, v3  c, v4  d .
v1 v2 v3 v4
v1  0 0 0 1
v 1
The matrix of the relation= W0 = 2 
0 1 0

v3  1 0 0 1
 
v4  0 0 1 0
a b c d
a 0 0 0
1 
1
First transitive matrix with only ‘a’ as interior=W1= b 
0 1 
1 b,a,d
c 1 0 0 1 
 
d 0 0 1 0 
a b c d
a 0 0 0 1
1 1
Second transitive matrix with ‘b’ as interior element=W2= b 
0 1

c 1 0 0 1
 
d 0 0 1 0
a b c d
a 0 0 0 1 
 1 0 1 1 
b
Third transitive matrix with ‘a’ & ‘b’ as interior=W3=  
c 1 0 0 1 
 
d  1  0 1 1  
Fourth transitive matrix with ‘a’, ‘b’, ‘c’ as interior and/or ‘d’ as interior = W4 =
a b c d
a  1  0 1  1
b  1 0 1

1
c 1 0 1 1
 
d 1 0 1 1

39
The last matrix i.e. W4 is the matrix of the transitive closure because all the vertices a, b,
c, d are interior vertices as such there is entry ‘1’ if and only if there is a path from vi to
vj.

2. Find the transitive closure of the relation R   a, a  ,  a, b  ,  b, c  ,  c, d  ,  c, e  ,  d , e  for

the set A  a, b, c, d , e , using Warshall’s algorithm.
Solution: The given set is A  a, b, c, d , e
Let the corresponding vertices be v1  a, v2  b, v3  c, v4  d , v5  e.
The given relation of the elements of set A is
R   a, a  ,  a, b  ,  b, c  ,  c, d  ,  c, e  ,  d , e 
The corresponding digraph of the given relation is

or

v1 v2 v3 v4 v5
v1  1 1 0 0 0
v2  0 0 1 0 0
 
The matrix of the relation = MR = W0 = v 3  0 0 0 1 1
 
v4  0 0 0 0 1
v 5  0 0 0 0 0 
v1 v2 v3 v4 v5
v1  1 1 0 0 0
v2  0 0 1 0 0
 
First transitive matrix with only ‘a’ as interior = W1 = v 3  0 0 0 1 1
 
v4  0 0 0 0 1
v 5  0 0 0 0 0 
This matrix is same as the original matrix i.e. W0 = W1 because with the vertex ‘a’ as the
interior vertex no new edge is formed.

40
 Second transitive matrix with ‘a’ and/or ‘b’ as interior element = W2 =
v1 v2 v3 v4 v5
v1  1 1 1 0 0
v2  0 0 1 0 0
  ab 
v3  0 0 0 1 1   abc i.e.The path ac.
bc 
 
v4  0 0 0 0 1
v 5  0 0 0 0 0 
Third transitive matrix with ‘a, b’ and/or ‘c’ as interior =W3=
v1 v2 v3 v4 v5
v1  1 1 1 1 1 v3
v2   v4  v2 v4 
v2  0 0 1 1 1 
  v2 ,v3
v1   v4  v1v4 
v3  0 0 0 1 1 v3   Paths
  v2   v5  v2 v5 
v4  0 0 0 0 1  
v3
v1   v5  v1v5 
v 5  0 0 0 0 0 
Fourth transitive matrix with ‘a, b, c’ and/or ‘d’ as interior = W 4 =
v1 v 2 v 3 v 4 v 5
v1  1 1 1 1 1
v2  0 0 1 1 1 

v3  0 0 0 1 1 
 
v4  0 0 0 0 1 
v 5  0 0 0 0 0 
We observe that W3 = W4 i.e. with the above stated vertices as interior vertices, no new
edge is formed.

Fifth transitive matrix: Finally with ‘a, b, c, d’ and /or ‘e’ as the interior vertices still there
will be no changes. Viewing in another way we see W4 has 1 in several positions of
column 5 but no 1’s in row 5. Thus, no new 1’s need be added to W4.

Therefore, W5 = W4 = W3 is the adjacency matrix of the transitive closure.

3. Using Warshall’s algorithm, compute the adjacency matrix of the transitive closure of the
digraph given below:
a b c d
● ● ● ●
Solution:

41
4. Using Warshall’s algorithm, compute the adjacency matrix of the transitive closure of
the digraph given below:

5. Using Warshall’s algorithm, compute the adjacency matrix of the transitive closure of
the digraph G  a, b, c, d , e ,  a, b  ,  b, c  ,  c, d  ,  d , e  ,  e, d  .
Solution:

6. Let ‘R’ be a relation on A  a, b, c, d , e whose adjacency matrix is given. Compute the
adjacency matrix of the transitive closure  R   using Warshall’s algorithm.
0 1 0 0 1 0 0 1 1 1 0 0
1 0 1 0 1 1 0 0 1 0 0 0
 a    , b    , c  ,
0 0 0 1 0 0 0 0 0 0 0 0
     
0 0 0 0 0 0 1 0 0 0 1 0
1 0 0 1 0 1 0 0 1 0 0 1
0 0 1 1 0 0 0 1 0 1 1 0
 d   ,  e  ,  f 
0 0 1 1 0 1 0 0 0 1 1 0
     
1 0 0 1 0 0 1 0 1 0 0 1

************

Equivalence Relation: A relation on a set ‘A’ is called an equivalence relation if it is

reflexive, symmetric and transitive.

42
 Examples:
Answer the following questions:
1. Let ‘m’ be a positive integer with m  1 . Show that the relation R   a, b  a  b  mod m 
is an equivalence relation on the set of integers.

Solution: We know, a  b  mod m   m divides a  b.

Reflexive: Clearly, a-a is divisible by m aa(mod m). So, congruence modulo is
reflexive.
Symmetric: a  b  mod m   a  b is divisible by m.
 a  b  km, where k is an integer.
 b  a  km    k  m, where   k  is an integer.
 b  a  mod m  .
So, congruence modulo is symmetric.
Transitive: Let, a  b  mod m  and b  c  mod m 
 a  b  km and b - c  lm, where k and l are integers.
Now, consider a  c   a  b    b  c   km  lm   k  l  m, where  k  l  is an integer.
 a  c  mod m  .
So, congruence modulo ‘m’ is transitive.
Since, the congruence modulo ‘m’ is reflexive, symmetric and transitive, so it is an
equivalence relation.

2. Let ‘R’ be the relation on the set of real numbers such that aRb if and only if ab is an
integer. Is ‘R’ an equivalence relation?
3. Suppose that ‘R’ is the relation on the set of strings of English letters such that aRb if
and only if l  a   l  b  , where l  x  is the length of the string x. Is ‘R’ an equivalence
relation?
4. Show that the “divides” relation on the set of positive integers is not an equivalence
relation.
5. Let ‘R’ be the relation on the set of real numbers such that xRy if and only if x and y are
real numbers that differ by less than 1, that is x  y  1. Show that ‘R’ is not an
equivalence relation.

**************

Equivalence Class: Let ‘R’ be an equivalence relation on a set ‘A’. The set of all elements
that are related to an element ‘a’ of ‘A’ is called the eqiovalence class of ‘a’. The
equivalence class of ‘a’ with respect to ‘R’ is denoted by [a]R or [a].

Equivalence Classes and Partition: An equivalence class of an equivalence relation on A

partitions the set A into mutually disjoint subsets of A. In other words, let ‘R’ be an

43
equivalence relation on a set ‘A’. The following statements are equivalent:
(i ) a R b
(ii ) [a]  [b]
(iii )[a]  [b]  

Partitions:
A partition or quotient set of a nonempty set A is a collection P of nonempty subsets of A
such that
1. Each element of A belongs to one of the sets in P.
2. If A1 and A2 are distinct elements of P, then A1  A2   .
The sets in P are called the blocks or cells of the partition. Figure 4.2 shows a partition P
  A1 , A2 , A3 , A4 , A5 , A6 , A7  into seven blocks.

Figure-1

Example-1: Let A  a, b, c, d , e, f , g , h . Consider the following subsets of A :

A1  a, b, c , d  , A2  a, c, e, f , g , h , A3  a, c, e, g , A4  b, d  , A5   f , h .
Then  A1 , A2  is not a partition A1  A2   . Also,  A1 , A5 is not a partition since e  A1
and e  A5 . The collection P   A3 , A4 , A5  is a partition of A.
Example: The set { 1, 2, 3 } has these five partitions:
{ {1}, {2}, {3} }, sometimes written 1|2|3.
{ {1, 2}, {3} }, or 12|3.
{ {1, 3}, {2} }, or 13|2.
{ {1}, {2, 3} }, or 1|23.
{ {1, 2, 3} }, or 123 (in contexts where there will be no confusion with the number).
Example: The following are not partitions of { 1, 2, 3 }:
{ {}, {1, 3}, {2} } is not a partition (of any set) because one of its elements is the empty
set.
{ {1, 2}, {2, 3} } is not a partition (of any set) because the element 2 is contained in more
than one block.
{ {1}, {2} } is not a partition of {1, 2, 3} because none of its blocks contains 3; however,
it is a partition of {1, 2}.
Example: Let

44
 Z  set of all integers,
A1 = set of all even integers, and
A2 =set of all odd integers.
Then  A1 , A2  is a partition of Z .
Since the members of a partition of a set A are subsets of A , we see that the partition is a
subset of P  A , the power set of A . That is, partitions can be considered as particular
kinds of subsets of P  A .

Equivalence Relations and Partitions:

The following result shows that if P is a partition of a set A, then P can be used to
construct an equivalence relation on A.

Theorem-1: Let P be a partition of a set A. The sets in P are called the blocks of P.
Define the relation R on A as follows: a R b if and only if a and b are members of the
same block. Then R is an equivalence relation on A.

Proof: (1) If a  A, then clearly a is in the same block as itself; so a R a.

(2) if a R b, then a and b are in the same block; so b R a.
(3) If a R b and b R c, then a, b and c must all lie in the same block of P,
thus a R c.
Since R is reflexive, symmetric and transitive, R is an equivalence relation. R will be
called the equivalence relation determined by P.

Example : Let A  1, 2,3, 4 and consider the partition P  1, 2, 3, ,4 of A. Find the
equivalence relation R on A determined by P.
Solution: The blocks of P are 1, 2,3 and 4 . Each element in a block is related to
every other element in the same block and only to those elements. Thus, in this case,
R  1,1 , 1, 2  , 1, 3 ,  2,1 ,  2, 2  ,  2,3 ,  3,1 ,  3, 2  ,  3, 3 ,  4, 4 

If P is a partition of A and R is the equivalence relation determined by P then the

blocks of P can easily be described in terms of R. If A1 is a block of P and a  A1 , we see
by definition that A1 consists of all elements x of A with a R x. That is, A1  R  a  . Thus
the partition P is R  a  | a  A. In words, P consists of all distinct R  relative sets that
arise from elements of A. For instance, in the example above the blocks 1, 2,3 and 4
can be described, respectively, as R 1 and R  4  . Of course, 1, 2,3 could also be
described as R  2  or R  3 , so this way of representing the blocks is not unique.
All equivalence relations on A can be produced from partitions.

45
Lemma-1: Let R be an equivalence relation on a set A, and let a  A and b  A. Then
a R b if and only if R  a   R  b  .
Proof: First suppose that R  a   R  b  . Since R is reflexive, b  R  b  ; therefore,
b  R  a  , so a R b. Conversely, suppose that a R b. Then note that
1. b  R  a  by definition. Therefore, since R is symmetric,
2. a  R  b  , since a relation R on a set A is symmetric means that a  R  b  if and only if
b  R  a .
We must show that R  a   R  b  . First, choose an element x  R  b  . Since R is
transitive, the fact that x  R  b  , together with (1), implies by the transitivity of R means
that if b  R  a  and c  R  b  , then c  R  a  , that x  R  a  . Thus R  b   R  a  . Now
choose y  R  a  . This fact and (2) imply, as before, that y  R  b  . Thus R  a   R  b  , so
we must have R  a   R  b  .
Theorem-: Let R be an equivalence relation on A, and let P be the collection of all
distince relative sets R  a  for a in A. Then P is a partition of A, and R is the
equivalence relation determined by P.

Proof: According to the definition of a partition, we must show the following two
properties:
(a) Every element of A belongs to some relative set.
(b) If R  a  and R  b  are not identical, then R  a   R  b    .
Now property (a) is true, since a  R  a  by reflexivity of R. To show property (b) we
prove the following equivalent statement:
If R  a   R  b    , then R  a   R  b  .
To prove this, we assume that c  R  a   R  b  . Then a R c and b R c.
Since R is symmetric, we have c R b. Then a R c and c R b, so, by transitivity of R, a R b.
The above lemme tells us that R  a   R  b  . We have now proved that P is a partition,
Hence by the above lemma we see that a R b if and only if a and b belong to the same
block of P. Thus P determines R , and hence the theorem is proved.

If R is an equivalence relation on A, then the sets R  a  are traditionally called

equivalence classes of R. The equivalence class R  a  is also denoted by  a  .
The partition P constructed in the above theorem therefore consists of all equivalence
classes of R , and this partition will be denoted by A / R. The partitions of A are also called
quotient sets of A, and the notation A / R reminds us that P is the quotient set of A that
is constructed from and determines R.

46
 Example: Let A  1, 2,3, 4 and let R  1,1 , 1, 2  ,  2,1 ,  2, 2  ,  3, 4  ,  4, 3 ,  3,3 ,  4, 4 
be the relation on A. Determine A / R.
Solution: Since R 1  1, 2  R  2  . Also R  3  3, 4  R  4  . Hence
A / R  1, 2 , 3, 4.
Example: Let A  Z and let
R   a, b   A  A | a and b yield the same remainder when divided by 2.
Solution: Here R is in fact the congruence mod 2 relation which is an equivalence
relation.
Now first, R  0    , 6, 4, 2, 0, 2, 4, 6,8, , the set of even integers, since the
remainder is zero when each of these numbers is divided by
2. R 1   , 5, 3, 1,1,3, 5, 7, , the set of odd integers, since each gives a remainder of
1 when divided by 2. Hence A / R consists of the set of even integers and the set of odd
integers.
Thus we can extract a general procedure for determining partitions A / R for A finite or
countable.
Procedure:
Step 1: Choose any element of A and compute the equivalence class R  a  .
Step 2: If R  a   A, choose an element b, not included in R  a  , and compute the
equivalence class R  b  .
Step 3: If A is not the union of previously computed equivalence classes, then choose
an element x of A that is not in any of those equivalence classes and compute R  x  .
Step 4: Repeat step 3 until all elements of A are included in the computed equivalence
classes. If A is countable, this process could continue indefinitely. In that case, continue
until a pattern emerges that allows you to describe or give a formula for all equivalence
classes.

Partial Ordering: A relation on a set ‘A’ is called a partial ordering if it is reflexive, anti-
symmetric and transitive. A set ‘S’ together with a partial ordering ‘R’ is called a
partially ordered set or poset and is denoted by (S,R).

Example:
Answer the following question:
1. Show that the “greater than or equal” relation () is a partial ordering on the set of
integers.
Solution: Reflexive: Since, a  a, for every integer ‘a’. so,  is reflexive.
Anti-Symmetric: If a  b and b  a a = b. Thus,  is anti-Symmetric.
Transitive: Since, a  b and b  c a  c. Thus,  is transitive.
Hence,  is a partial ordering on the set of integers and (Z, ) is a poset.

Note: A poset is also denoted by  S ,   where  denotes the relation in any poset.

47
 Comparable: The elements ‘a’ and ‘b’ of a poset  S ,   are called comparable if either a 
b or b  a.
When ‘a’ and ‘b’ are elements of S such that neither ab nor ba , then ‘a’ and ‘b’ are
called incomparable.

Lexicographic Order: The words in a dictionary are listed in alphabetic order or

lexicographic order, which is based on the ordering of the letters in the alphabet.

Examples:
Answer the following questions:
1. Investigate the lexicographic ordering constructed from the relation ‘’on , of the
following 1,3, 5, 7   1,3, 7,9  .
2. Investigate the lexicographic ordering on the set of strings:
a. discreet  discrete
b. discreet  discreetness

Hasse Diagrams: The partial ordering on a finite set can be represented using graphical
representation, without showing loops and which is non-directed. Such a diagram
contains sufficient information to find the partial ordering. This diagram is called Hasse
diagram.

Examples:
Answer the following questions:
1. Draw the Hasse diagram representing the partial ordering  a, b  a divides b on
1, 2,3, 4,6,8,12.
2. Draw the Hasse diagram for the partial ordering  A, B  | A  B on the power set P(S)
where S={a,b,c}.
3. Draw the Hasse diagram for the partial ordering  a, b  | a  b on the set {1, 2, 3, 4}.

Maximal and Minimal Elements:

Maximal Element: An element of a poset is called maximal if it is not less than any
element of the poset.
Minimal Element: An element of a poset is called minimal if it is not greater than any
element of the poset.

Examples:
Answer the following questions:
1. Which elements of the poset 2, 4, 5,10,12, 20, 25, ,| are maximal and which are
minimal?

Greatest and Least Element:

48
 Greatest Element: An element ‘a’ is the greatest element of the poset  S ,   if ba for all
b  S . The greatest element is unique when it exists.

Least Element: An element ‘a’ is the least element of  S ,   if ab for all b  S . The least
element is unique when it exists.

Lower Bound and Upper Bound:

Lower Bound: If ‘l’ is an element of ‘S’ such that l  a for all elements a  A , then ‘l’ is
called a lower bound of A.

Upper Bound: If ‘u’ is an element of ‘S’ such that a u for all elements a  A , then ‘u’ is
called an upper bound of A.

Least Upper Bound: The element ‘x’ is called the least upper bound of the subset ‘A’ if
‘x’ is an upper bound that is less than every other upper bound of A.

Greatest Lower Bound: The element ‘y’ is called the greatest lower bound of the subset
‘A’ if ‘y’ is greater than all other lower bounds of ‘A’.

Example:
Answer the following questions:
1. Find the greatest lower bound and the least upper bound of the sets 3,9,12 and
1, 2, 4,5,10 if they exist in the poset  
,| .

Lattice: A partially ordered set in which every pair of elements has both a least upper
bound and a greatest lower bound is called a lattice.

Uses: Models of information flow, play an important role in Boolean algebra.

Examples:
Answer the following questions:
1. Determine whether the posets 1, 2,3, 4, 5 ,| and 1, 2, 4,8,16 ,| are lattices.
Solution: In the poset S  1, 2,3, 4,5 ,| though they have ‘1’ as the g.l.b of any two
elements of the set lying in the set, but 2 and 3 have no upper bounds in the given poset.
The LCM of 2 and 3 is 6 which is not in the given poset. So, ‘S’ is not a lattice.
Again, in the poset P  1, 2, 4,8,16 ,| the g.l.b of any two elements of P is smaller of the
elements and the l.u.b of two elements in this poset is the larger of the elements which
lies in the set too. Since, the given poset contains both g.l.b and l.u.b, so the given poset
is a lattice.

49
*****End of Module-I*****

50