DM

Units Topics Page
No
1 Mathematical Logic 1-33
2 Set Theory 34-52
3 Algebraic Structure 53-69
4 Combinatorics 70-87
5 Graph Theory 88-109

UNIT-I
Mathematical Logic
Syllabus
Mathematical Logic: Introduction, Statements and Notation, Connectives, Truth tables, Well-
formed formulas, Tautology, Contradiction, Contingency, Logical equivalence, Normal Forms,
Theory of Inference for the Statement Calculus, The Predicate Calculus, Inference Theory of the
Predicate Calculus
Introduction to Discrete Mathematics
• Discrete Mathematics is the study of discrete structures which mathematical models

dealing with discrete objects and relationships between them.
• Examples of discrete objects are like Sets, Permutations, graphs and etc.
Why it is important for computer science
 In the world of computers, all the information is stored in bits, units of information that can
take the value of either 0 or 1. It’s not like in nature, where something can take all the values
in between 0 and 1 as well. Instead, everything is binary.
 Since the bits are the building blocks of everything that happens in computer software,
everything becomes discrete. For instance, the hard drive on the laptop I’m using right now
can store 1 845 074 329 600 bits of information.
 The study of algorithms is also firmly in the discrete world. An algorithm is a step-by- step
list of instructions to the computer and it’s what makes computer programs possible. When
determining how much time an algorithm needs to run, you count the number of operations
it needs to perform. Notice the word count. Again, discrete mathematics.
• In continuous mathematics (the opposite of discrete), the calculation would go like this:
• ∫50 𝑥 dx=[1/2∗x2]50=52 /2−0=12.5

• In discrete mathematics, the equivalent calculation would go like this:
∑40 𝑋𝑖 = 0 + 1 + 2 + 3 + 4 = 10
1
Applications of discrete mathematics with computer applications
• 1)Computer networks
• 2)Programming languages
• 3)Finite state automata or compilers
• 4)Databases
Symbolic logic is used in framing algorithms and their verification and in automatic theorem
proving. Set theory, Graph Theory, trees etc. are used in storage and retrieval of information (data
structures), Algorithms and their complexity studies also uses tools from discrete mathematics.
Formal Languages, Automata theory, Turing machines etc. are themselves part of discrete
mathematics and so is Recursive Function Theory. Undecidability of many problems are
established using Turing machines which is the Mathematical model for studying theoretical
limitations of Computation. Lattices and Boolean Algebra are used in Computer Science as well
as in communications and networking.
Mathematical Logic
Logic
It is the study of the principles and methods that distinguishes between valid and invalidargument.
1. Proposition Logic
Proposition or Statement
A proposition or a statement can defined as a declarative sentence to which we can assign one
and only one of the truth values either true (or) false but not both is called a proposition.
The true or false of a proposition is called truth value of a proposition
These two values true and false are denoted by the symbols T and F respectively. Sometimes
these are also denoted by the symbols 1 and 0 respect.
2
Proposition truth value
Ex: 1) India capital is new Delhi True
2) 2*3=5 false
3) 5 is a prime number true
These are propositions (or statements) because they are either true or false.
Next consider the following sentences:
4) How beautiful are you?

5) Wish you a happy new year
6) x + y = z
7) Take one book.
These are not propositions as they are not declarative in nature, that is, they do not declare a
definite truth value T or F.
Types of Propositions
1) Atomic proposition
2)Compound Proposition
1)Atomic proposition
• A Proposition which cannot be divided further is called an atomic proposition.
• Examples:
• 1)India’s capital is New Delhi
• 2)2*3=5
2) Compound Proposition
• Two or more atomic propositions can be combined to form a compound proposition with
help of Connectives. Compound Proposition also called as Propositional function.
3
• Examples of Compound statements
• ―3+2=-1 and Delhi is the capital of India.
• grass is green or ―it is hot today.
• Discrete mathematics is not difficult to me.
And, Or ,Not are called connectives.
Notations
• Statements are symbolically represented as A,B,C,..P,Q,R,S… Those are called

propositional variables or notations.
• Examples:
• P→Delhi is the capital of India.
• Q→17 is divisible by 3.
Logical Connectives
The words or phrases or symbols which are used to make a compound proposition by two
or more atomic propositions are called logical connectives or simply connectives.
There are five basic connectives called negation, conjunction, disjunction, conditional
and biconditional.
Connectivity Symbol Word

Negation ¬ Not
Disjunction ∨ OR
Conjunction 𝖠 AND
Conditional → IF AND THEN
Biconditional ↔ If and only if
Negation (~) or(¬)
The negation of a statement is generally formed by writing the word ‘not’ at a proper
place in the statement (proposition) or by prefixing the statement with the phrase (¬).It is not
the case that. If p denotes a statement then the negation of p is written as¬ p and read as not p.
If the truth value of p is T then the truth value of ¬p is F. Also if the truth value of p is F then
the truth value of ¬p is T.
Truth table for Negation
P ¬P
F T
Disjunction (OR)( V)
• If P and Q are any two propositions then ‘P OR Q’ symbolically written as P V Q .

• P V Q is a proposition whose truth values is false only when both P and Q are false
otherwise True.˄
Truth table for Disjunction
P Q PVQ
F F F
F T T
T F T
T T T
P: I shall go to the game.
Q : I shall watch the game on television.
P V Q: I shall go to the game OR I shall watch the game on television.

Conjunction (AND(˄))
IF P and Q are any two propositions then P and Q Symbolically written as P ˄ Q.

P ˄ Q is a proposition whose truth value is true only when both are P and Q are true.
Whole truth value is false when either P or Q are false and both are false.
Truth table for Conjunction
P Q P˄Q
F F F
F T F
T F F
T T T
P : It is raining today.
Q: There are 10 chairs in the room.
P 𝖠 Q: It is raining today AND There are 10 chairs

in the room.
Conditional (or) Implication (→)
If P and Q are any two statements (or propositions) then the statement P → Q which is read
as, If P, then Q‗ is called a conditional statement (or proposition) or implication and the
connective is the conditional connective.
Truth table for conditional
P Q P→ Q
F F T
F T T
T F F
T T T
In this conditional statement, P is called the hypothesis or premise or antecedent and Q is

called the consequence or conclusion.
Biconditional (If and only if)
• If P and Q are any two propositions then P if and only if Q Written as P ↔Q.
• It‘s truth value is true only when both P & Q have same truth values.
P q p↔q
T T T
T F F
F T F
F F T
TAUTOLOGY AND CONTRADICTION
Tautology: A proposition is said to be a tautology if its truth value is T for any assignment
of truth values to its components.
Example: The proposition P V ¬P is a tautology.

Contradiction
A proposition is said to be a contradiction if its truth value is F for any assignment of truth
values to its components. Example: The proposition P ˄ ¬P is a contradiction.
Contingency: A statement formula which is neither a tautology nor a contradiction is known as
a contingency.
Example: P->Q
Tautology: A statement formula which is true regardless of the truth values of the
statements which replace the variables in it is called a universally valid formula or a logical
truth or a tautology.
How to prove given compound proposition is tautology
1)By Constructing truth table
2)By using substitution method
1)Constructing truth table
Show that following function is tautology
a)(PVQ) V ¬P
Solution
P Q ¬P PVQ (PVQ)V¬P
F F T F T
F T T T T
T F F T T
T T F T T
In the above table (PVQ) V ¬P is giving all truth values are true so it is a tautology.
Show that given proposition is a tautology ((P → Q) ˄ (Q→R)) →(P→ R)
P Q R P → Q→R ((P → Q) ˄ (Q→R) P→ R ((P → Q) ˄ (Q→R)) →(P→ R)

Q
F F F T T T T T
F F T T T T T T
F T F T F F T T
T F F F T F F T
F T T T T T T T
T F T F T F T T
T T F T F F F T
T T T T T T T T
Implication:
• If P and Q are any two propositions then P->Q ie, If P then Q
• P->Q is proposition whose truth value is false only when P is true and Q is false.
• Here P is antecedent and Q is Consequent..
P Q P→ Q
F F T
F T T
T F T
T T T
• When ever P is false P->Q is true

• Ie, false antecedent P implies any proposition Q
• When ever Q is true P->Q is also true
• Ie, a true consequent Q implied by any propositional ‗P‘.
from the implication statement we can write another three statements which are
converse, inverse and contrapositive
Converse, Inverse and Contrapositive
If P → Q is a conditional statement, then (1).
Q → P is called its converse (2).
¬P → ¬Q is called its inverse
(3). ¬Q → ¬P is called its contrapositive.
Example:
• P: Today is Sunday
• Q: It is a holiday
• Converse Statement: If it is a holiday, then today is Sunday.
• Inverse Statement: If today is not Sunday, then it is not a holiday.
• Contrapositive Statement- If it is not a holiday, then today is not Sunday.

Here Implication and Contrapositive are equal.
Converse and inverse are opposite propositions.
Well formed formulas(wff):

Not all strings can represent propositions of the predicate logic. Those which produce a
proposition when their symbols are interpreted must follow the rules given below, and they are
called wffs (well-formed formulas) of the first order predicate logic.
Rules for constructing Wffs
A predicate name followed by a list of variables such as P(x, y), where P is predicate name, and x
and y are variables, is called an atomic formula.
A well formed formula of predicate calculus is obtained by using the following rules.
1. An atomic formula is a wff.
2. If A is a wff, then 7A is also a wff.
3. If A and B are wffs, then (A V B), (A ˄ B), (A → B) and (A D B).
4. If A is a wff and x is any variable, then (x)A and ($x)A are wffs.
5. Only those formulas obtained by using (1) to (4) are wffs.
Since we will be concerned with only wffs, we shall use the term formulas for wff. We shall
follow the same conventions regarding the use of parentheses as was done in the case of statement
formulas.
Wffs are constructed using the following rules:
1. True and False are wffs.

2. Each propositional constant (i.e. specific proposition), and each propositional variable
(i.e. a variable representing propositions) are wffs.
3. Each atomic formula (i.e. a specific predicate with variables) is a wff.
4. If A, B, and C are wffs, then so are A, (A B), (A B), (A B), and (A B).
5. If x is a variable (representing objects of the universe of discourse), and A is a wff, then
so are x A and x A .For example, "The capital of Virginia is Richmond." is a specific
proposition. Hence it is a wffby Rule 2.
Let B be a predicate name representing "being blue" and let x be a variable. Then B(x) is an atomic
formula meaning "x is blue". Thus it is a wff by Rule 3. above. By applying Rule 5. to B(x),
xB(x) is a wff and so is xB(x). Then by applying Rule 4. to them x B(x) x B(x) is seen to be a
wff. Similarly, if R is a predicate name representing "being round". Then R(x) is an atomic
formula. Hence it is a wff. By applying Rule 4 to B(x) and R(x), a wff B(x) R(x) is obtained. In
this manner, larger and more complex wffs can be constructed following the rules given above.
Note, however, that strings that cannot be constructed by using those rules are not wffs. For
example, xB(x)R(x), and B( x ) are NOT wffs, NOR are B( R(x) ), and B( x R(x) )
.
More examples: To express the fact that Tom is taller than John, we can use the atomic formula
taller (Tom, John), which is a wff. This wff can also be part of some compound statement such
as taller (Tom, John) taller(John, Tom), which is also a wff. If x
is a variable representing people in the world, then taller(x,Tom), x taller(x,Tom), x
taller(x,Tom), x y taller(x,y) are all wffs among others. However, taller ( x,John) and
taller(Tom Mary, Jim), for example, are NOT wffs.
Logical Equivalence
Two formulas A and B are said to equivalent to each other if and only if A↔ B
is a tautology. If A↔B is a tautology, we write A ⇔ B which is read as A is
equivalent to B.
Note : 1. ⇔ is only symbol, but not connective.
A ↔ B is a tautology if and only if truth tables of A and B are the same. Equivalence relation is
symmetric and transitive.
(or)
Let P and Q are two propositional functions P is Equivalent to Q.
Symbolically written as P⇔ Q or P ≡ Q if P and Q have same truth table.

Ex: P->Q ⇔ ~P V Q.
Method I. Truth Table Method: One method to determine whether any two statement formulas
are equivalent is to construct their truth tables.
Example: Prove (P → Q) ⇔ (¬P ∨ Q).
P Q P→Q ¬P ¬P∨Q
T T T F T
T F F F F
F T T T T
F F T T T
In the above table both P → Q and ¬P∨Q are have same truth values.
So that (P → Q) ⇔ (¬P ∨ Q).
Equivalence Formulas:
1. Idempotent laws:
(a) P ∨ P ⇔ P (b) P ∧ P ⇔ P
2. Associative laws:
(a) (P ∨ Q) ∨ R ⇔ P ∨ (Q ∨ R) (b) (P ∧ Q) ∧ R ⇔ P ∧ (Q ∧ R)
3. Commutative laws:
(a) P ∨ Q ⇔ Q ∨ P (b) P ∧ Q ⇔ Q ∧ P
4. Distributive laws:
P∨(Q∧R)⇔(P∨Q)∧(P∨R) P∧(Q∨R)⇔(P∧Q)∨(P∧R)
Identity laws (or)

5. Domination Law
(a) (i) P ∨ F ⇔ P (ii) P ∨ T ⇔ T
Page 13
(b) (i) P ∧ T ⇔ P (ii) P ∧ F ⇔ F
6. Component laws:
(a) (i) P ∨ ¬P ⇔ T (ii) P ∧ ¬P ⇔ F .

(b) (i) ¬¬P ⇔ P (ii) ¬T ⇔ F , ¬F ⇔ T
7. Absorption laws:
(a) P ∨ (P ∧ Q) ⇔ P (b) P ∧ (P ∨ Q) ⇔ P
8. De Morgan‘s Laws
(a) ¬(P ∨ Q) ⇔ ¬P ∧ ¬Q (b) ¬(P ∧ Q) ⇔ ¬P ∨ ¬Q
Page 14
Tautological Implications.
A statement formula A is said to tautologically imply a statement B if and only if A → B is a

tautology. In this case we write A ⇒ B, which is read as ‗A implies B‗.
Note: ⇒ is not a connective, A ⇒ B is not a statement formula.
A ⇒ B states that A → B is tautology.
Clearly A ⇒ B guarantees that B has a truth value T whenever A has the truth value T . One can
determine whether A ⇒ B by constructing the truth tables of A and B in the same manner as was
done in the determination of A ⇔ B.
Example: Prove that (P → Q) ⇒ (¬Q → ¬P ).
P Q ¬P ¬Q P→Q ¬Q→¬P (P→Q)→(¬Q→¬P)
T T F F T T T
T F F T F F T
F T T F T T T
F F T T T T T
Since all the entries in the last column are true, (P → Q) → (¬Q → ¬P ) is a
tautology.
Hence (P → Q) is Tautological Implications to (¬Q → ¬P ).
So that (P → Q) ⇒ (¬Q → ¬P ).
In order to show any of the given implications, it is suﬃcient to show that an assignment of the
truth value T to the antecedent of the corresponding conditional leads to the truth value T for the
Page 15
consequent. This procedure guarantees that the conditional becomes tautology, thereby proving
the implication.
Example: Prove that ¬Q ∧ (P → Q) ⇒ ¬P .
Solution: Assume that the antecedent ¬Q ∧ (P → Q) has the truth value T, then both ¬Q and P
→Q have the truth value T, which means that Q has the truth value F, P → Q has the truth
value T .
Hence P must have the truth value F. Therefore, the consequent ¬P must have the truth value T.
¬Q∧(P→Q) ➙¬P.
Another method to show A ⇒ B is to assume that the consequent B has the truth value F and then
show that this assumption leads to A having the truth value F. Then A → B must have the truth
value T.
Example: Show that ¬(P → Q) ⇒ P .
Solution: Assume that P has the truth value F . When P has F , P → Q has T , then ¬(P → Q)
has F. Hence ¬(P → Q) → P has T .
So that ¬(P→Q)⇒P.
Normal Forms
If a given statement formula A(p1, p2, ...pn) involves n atomic variables, we have 2n possible
combinations of truth values of statements replacing the variables.
The formula A is a tautology if A has the truth value T for all possible assignments of the truth
values to the variables p1, p2, ...pn and A is called a contradiction if A has the truth value F for all
possible assignments of the truth values of the n variables. A is said to be satisfiable if A has the
truth value T for at least one combination of truth values assigned to p1, p2, ...pn.
The problem of determining whether a given statement formula is a Tautology, or a Contradiction

is called a decision problem.
Page 16
The construction of truth table involves a finite number of steps, but the construction may not be
practical. We therefore reduce the given statement formula to normal form and find whether a
given statement formula is a Tautology or Contradiction or at least satisfiable. It will be convenient
to use the word product in place of conjunction and sum in place of disjunction .
A product of the variables and their negations in a formula is called an elementary Product.
Similarly, a sum of the variables and their negations in a formula is called an elementary sum. Let
P and Q be any atomic variables Then P, ~P ˄ Q, ¬Q ˄ P ˄ ~P, Q ˄ ~P are some example
ofelementary products.
On the other hand P, ¬P∨ Q, ¬Q∨ P∨ ¬P, Q∨ ¬P. are some examples of elementary sums.
Types of Normal forms
1) Disjunctive Normal forms
2) Conjunctive Normal forms.
Disjunctive Normal Form (DNF)
A formula which is equivalent to a given formula and which consists of a sum of elementary
products is called a disjunctive normal form of the given formula.
Example: Obtain disjunctive normal forms of
(a) P 𝖠 (P → Q)
P𝖠(P→Q)⇔P𝖠(¬P∨Q) (apply distributive law P∧(Q∨R)⇔(P∧Q)∨(P∧R)
- (P𝖠¬P)∨(P𝖠Q)
b)¬(P ∨ Q) ↔(P ∧ Q)
¬(P ∨ Q) ↔(P ∧ Q)⇔ (¬(P ∨ Q) 𝖠 (P ∧ Q)) ∨ ((P ∨ Q) 𝖠 ¬(P ∧ Q)) [using

R↔S⇔(R∧S)∨(¬R∧¬S)]
⇔((¬P ∧ ¬Q) 𝖠 (P∧Q)) ∨ ((P ∨ Q) ∧ (¬P ∨ ¬Q)).
⇔(¬P∧¬Q∧P∧Q)∨((P∨Q) ∧¬P)∨((P∨Q) ∧¬Q).
⇔(¬P∧¬Q∧P∧Q)∨(P∧¬P)∨(Q∧¬P)∨(P∧¬Q)∨(Q∧¬Q).
Which is the required disjunctive normal form. Note: The DNF of a given formula is not unique.
Page 17
Conjunctive Normal Form (CNF)
A formula which is equivalent to a given formula and which consists of a product of elementary
sums is called a conjunctive normal form of the given formula.
The method for obtaining conjunctive normal form of a given formula is similar to the one
given for disjunctive normal form. Again, the conjunctive normal form is not unique.
(a) P∧ (P → Q) obtain the conjunctive normal form

P ∧ (P → Q) ⇔ P ∧ (¬P ∨ Q)
(b) ¬(P ∨ Q)↔ (P ∧ Q)
- (¬(P∨Q)→(P∧Q))𝖠((P∧Q)→¬(P∨Q))
- ((P∨Q)∨(P∧Q)) ∧ (¬(P∧Q)∨¬(P∨Q))
- [(P∨Q∨P) ∧ (P∨Q∨Q)] ∧ [(¬P∨¬Q)∨(¬P∧¬Q)]
- (P∨Q∨P) ∧ (P∨Q∨Q) ∧ (¬P∨¬Q∨¬P) ∧ (¬P∨¬Q∨¬Q)
Principal Disjunctive Normal Form
In this section, we will discuss the concept of principal disjunctive normal form (PDNF).
Minterm: For a given number of variables, the minterm consists of conjunctions in which each
statement variable or its negation, but not both, appears only once.
Let P and Q be the two statement variables. Then there are 22 minterms given by
P ∧ Q, P ∧ ¬Q,
¬P ∧ Q, and ¬P 𝖠∧¬Q
Minterms for three variables P , Q and R are P∧Q ∧ R, P ∧ Q ∧ ¬R, P ∧¬Q ∧

R, P∧ ¬Q ∧ ¬R, ¬P∧ Q ∧ R, ¬P ∧ Q ∧ ¬R, ¬P ∧ ¬Q ∧ R and ¬P ∧ ¬Q ∧ ¬R.
Page 18
From the truth tables of these minterms of P and Q, it is clear that.
P Q P∧Q P∧¬Q ¬P∧Q ¬P∧¬Q
T T T F F F
T F F T F F
F T F F T F
F F F F F T
(i). No two minterms are equivalent
(ii). Each minterm has the truth value T for exactly one combination of the truth values of the
variables P and Q.
PDNF
Definition: For a given formula, an equivalent formula consisting of disjunctions of minterms

only is called the Principal disjunctive normal form of the given formula. The principle
disjunctive normal formula is also called the sum-of-products canonical form.
Methods to obtain the PDNF of a given formula.
(a). By Truth table:
(b). without constructing the truth table
(a). By Truth table:
(i). Construct a truth table of the given formula.
(ii). For every truth value T in the truth table of the given formula, select the minterm which
also has the value T for the same combination of the truth values of P and Q.
(iii). The disjunction of these minterms will then be equivalent to the given formula
Page 19
Example: Obtain the PDNF of P → Q.
Solution: From the truth table of P → Q
P Q P→Q Minterm
T T T P∧Q
T F F P∧¬Q
F T T ¬P∧Q
F F T ¬P∧¬Q
The PDNF of P → Q is (P ∧ Q) ∨ (¬P ∧ Q) ∨ (¬P ∧ ¬Q).
Obtain the PDNF for (P ∧ Q) ∨ (¬P ∧ R) ∨ (Q ∧ R).

Solution:
P Q R Minterm P∧Q ¬P∧R Q∧R (P∧Q)∨(¬P∧R)∨(Q∧R)
T T T P∧Q∧R T F T T
T T F P∧Q∧¬R T F F T
T F T P∧¬Q∧R F F F F
T F F P∧¬Q∧¬R F F F F
F T T ¬P∧Q∧R F T T T
F T F ¬P∧Q∧¬R F F F F
F F T ¬P∧¬Q∧R F T F T
F F F ¬P∧¬Q∧¬R F F F F
The PDNF of (P ∧ Q) ∨ (¬P ∧ R) ∨ (Q ∧ R) is (P∧Q∧R)∨(P∧Q∧¬R)∨(¬P∧Q∧R)∨(¬P∧¬Q∧R).

(b). Without constructing the truth table:
In order to obtain the principal disjunctive normal form of a given formula is con-
structed as follows:
Page 20
(1). First replace →, by their equivalent formula containing only 𝖠, ∨ and ¬.
(2). Next, negations are applied to the variables by De Morgan‗s laws followed by the application
of distributive laws.
(3). Any elementarily product which is a contradiction is dropped. Minterms are obtained in the
disjunctions by introducing the missing factors. Identical minterms appearing in the disjunctions
are deleted.
Example: Obtain the principal disjunctive normal form of
(a) ¬P∨ Q
(b) (P ∧ Q) ∨ (¬P ∧ R) ∨ (Q ∧ R).
(a) ¬P∨ Q
¬P∨Q ⇔ (¬P∧T) ∨ (Q∧T)
- (¬P∧ (Q∨¬Q)) ∨ (Q∧ (P∨¬P)) [∵P∨¬P⇔T]
- (¬P∧Q) ∨ (¬P∧¬Q) ∨ (Q∧P) ∨ (Q∧¬P)

- (¬P𝖠Q) ∨ (¬P𝖠¬Q) ∨ (P𝖠Q) [∵P∨P⇔P]
(b) (P ∧ Q) ∨ (¬P ∧ R) ∨ (Q ∧ R)
(P ∧ Q) ∨ (¬P ∧ R) ∨ (Q ∧ R) ⇔ (P∧Q∧T) ∨ (¬P∧R∧T) ∨ (Q∧R∧T)

- (P∧Q∧(R∨¬R)) ∨ (¬P∧R∧(Q∨¬Q)) ∨ (Q∧R∧(P∨¬P))
-(P∧Q∧R) ∨ (P∧Q∧¬R) ∨ (¬P∧R∧Q)∨(¬P∧R∧¬Q)∨
(Q∧R∧P) ∨ (Q∧R∧¬P)
- (P∧Q∧R) ∨ (P∧Q∧¬R) ∨ (¬P∧Q∧R) ∨ (¬P∧¬Q∧R)
Principal Conjunctive Normal Form
The dual of a minterm is called a Maxterm. For a given number of variables, the maxterm consists
of disjunctions in which each variable or its negation, but not both, appears only once. Each of the
maxterm has the truth value F for exactly one combination of the truth values of the variables.
Now we define the principal conjunctive normal form.
For a given formula, an equivalent formula consisting of conjunctions of the max-terms only is
known as its principle conjunctive normal form. This normal form is also called the product-of-
sums canonical form. The method for obtaining the PCNF for a given formula is similar to the
one described previously for PDNF.
Page 21
Example: Obtain the principal conjunctive normal form of the formula (¬P→R) ∧ (Q↔P)
Solution:
(¬P→R) ∧ (Q↔P) ⇔[¬(¬P)∨R] ∧ [(Q→P) ∧ (P→Q)]
- [(P∨R) ∧ [(¬Q∨P) ∧ (¬P∨Q)]
- ( P∨R∨F) ∧ [(¬Q∨P∨F) ∧ (¬P∨Q∨F)]
- [(P∨R)∨(Q∧¬Q)]𝖠[¬Q∨P)∨(R∧¬R)]𝖠[(¬P∨Q)∨(R∧¬R)]
⇔
(P∨R∨Q) ∧ (P∨R∨¬Q) ∧ (P∨¬Q∨R) ∧ (P∨¬Q∨¬R) ∧ (¬P∨Q∨R) ∧ (¬P∨Q∨¬R)
Page 22
Rules of inference:
The two rules of inference are called rules P and T.
Rule P: A premise may be introduced at any point in the derivation.
Rule T: A formula S may be introduced in a derivation if s is tautologically implied by

any one or more of the preceding formulas in the derivation.
Before proceeding the actual process of derivation, some important list

of implications and equivalences are given in the following tables.
Implications
I1 P٨Q =>P } Simplification

I2 PQ٨ =>Q
I3 P=>PVQ } Addition
I4 Q =>PVQ
I5 7P => P→ Q
I6 Q => P→ Q
I7 7(P→Q) =>P
I8 7(P → Q) => 7Q
I9 P, Q => P ٨ Q
I10 7P, PVQ => Q ( disjunctive syllogism)
I11 P, P→ Q => Q ( modus ponens )
I12 7Q, P → Q => 7P (modus tollens )
I13 P → Q, Q → R => P → R ( hypothetical syllogism)
I14 P V Q, P → Q, Q → R => R (dilemma)
Equivalences
Page 23
E1 77P <=>P
E2 P ٨ Q <=> Q ٨ P } Commutative laws
E3 P V Q <=> Q V P
E4 (P ٨ Q) ٨ R <=> P ٨ (Q ٨ R) } Associative laws
E5 (P V Q) V R <=> PV (Q V R)
E6 P ٨ (Q V R) <=> (P ٨ Q) V (P ٨ R) } Distributive laws
E7 P V (Q ٨ R) <=> (P V Q) ٨ (PVR)
E8 7(P ٨ Q) <=> 7P V7Q
De Morgan‘s laws
E9 7(P V Q) <=>7P ٨ 7Q }
E10 P V P <=> P
E11 P ٨ P <=> P
E12 R V (P ٨ 7P) <=>R
E13 R ٨ (P V 7P) <=>R
E14 R V (P V 7P) <=>T
E15 R ٨ (P ٨ 7P) <=>F
E16 P → Q <=> 7P V Q
E17 7 (P→ Q) <=> P ٨ 7Q
E18 P→ Q <=> 7Q → 7P
E19 P → (Q → R) <=> (P ٨ Q) → R
E20 7(PD Q) <=> P D 7Q
E21 PDQ <=> (P → Q) ٨ (Q → P)
E22 (PDQ) <=> (P ٨ Q) V (7 P ٨ 7Q)
Page 24
Example 1.Show that R is logically derived from P → Q, Q → R, and P
Solution. {1} (1) P→Q Rule P

{2} (2) P Rule P
{1, 2} (3) Q Rule (1), (2) and I11
{4} (4) Q→R Rule P
{1, 2, 4} (5) R Rule (3), (4) and I11.
Example 2.Show that S V R tautologically implied by ( P V Q) ٨ ( P → R) ٨ ( Q → S ).
Solution . {1} (1) PVQ Rule P

{1} (2) 7P → Q T, (1), E1 and E16
{3} (3) Q→S P
{1, 3} (4) 7P → S T, (2), (3), and I13
{1, 3} (5) 7S → P T, (4), E13 and E1
{6} (6) P→R P
{1, 3, 6} (7) 7S → R T, (5), (6), and I13
{1, 3, 6) (8) SVR T, (7), E16 and E1
Example 3. Show that 7Q, P→ Q => 7P
Solution . {1} (1) P → Q Rule P

{1} (2) 7P → 7Q T, and E 18
{3} (3) 7Q P
{1, 3} (4) 7P T, (2), (3), and I11 .
Example 4 .Prove that R ٨ ( P V Q ) is a valid conclusion from the premises PVQ , Q

→ R, P → M and 7M.
Solution . {1} (1) P→M P

{2} (2) 7M P
{1, 2} (3) 7P T, (1), (2), and I12
{4} (4) PVQ P
Page 25
{1, 2 , 4} (5) Q T, (3), (4), and I10.
{6} (6) Q→R P
{1, 2, 4, 6} (7) R T, (5), (6) and I11
{1, 2, 4, 6} (8) R ٨ (PVQ) T, (4), (7), and I9.
There is a third inference rule, known as rule CP or rule of conditional proof.
Rule CP: If we can derive s from R and a set of premises, then we can derive R → S from theset
of premises alone.
Note. 1. Rule CP follows from the equivalence E10 which states that
( P ٨ R ) → S óP → (R → S).
2. Let P denote the conjunction of the set of premises and let R be any formula
The above equivalence states that if R is included as an additional premise and
S is derived from P ٨ R then R → S can be derived from the premises P alone.
3. Rule CP is also called the deduction theorem and is generally used if the
conclusion is of the form R → S. In such cases, R is taken as an additional
premise and S is derived from the given premises and R.
Example 5 . Show that R → S can be derived from the premises

P → (Q → S), 7R V P , and Q.
Solution. {1} (1) 7R V P P

{2} (2) R P, assumed premise
{1, 2} (3) P T, (1), (2), and I10
{4} (4) P → (Q → S) P
{1, 2, 4} (5) Q→ S T, (3), (4), and I11
{6} (6) Q P
{1, 2, 4, 6} (7) S T, (5), (6), and I11
{1, 4, 6} (8) R→S CP.
Page 26
Example 6 Show that P → S can be derived from the premises, 7P V Q, 7Q V R,
and R → S .
Solution.
{1} (1) 7P V Q P
{2} (2) P P, assumed premise
{1, 2} (3) Q T, (1), (2) and I11
{4} (4) 7Q V R P
{1, 2, 4} (5) R T, (3), (4) and I11
{6} (6) R→S P
{1, 2, 4, 6} (7) S T, (5), (6) and I11
{2, 7} (8) P→S CP
Example 7. ” If there was a ball game , then traveling was difficult. If they arrived on time,
then traveling was not difficult. They arrived on time. Therefore, there was no ball game”.
Show that these statements constitute a valid argument.
Solution. Let P: There was a ball game

Q: Traveling was difficult.
R: They arrived on time.
Given premises are: P → Q, R → 7Q and R conclusion is: 7P
{1} (1) P → Q P
{2} (2) R → 7Q P
{3} (3) R P
{2, 3} (4) 7Q T, (2), (3), and I11
{1, 2, 3} (5) 7P T, (2), (4) and I12
Page 27
Consistency of premises:
Consistency
A set of formulas H1, H2, …, Hm is said to be consistent if their conjunction has the truth
value T for some assignment of the truth values to be atomic appearing in H1, H2, …, Hm.
Inconsistency
If for every assignment of the truth values to the atomic variables, at least one of the formulas
H1, H2, … Hm is false, so that their conjunction is identically false, then the formulasH1, H2, …,
Hm are called inconsistent.
A set of formulas H1, H2, …, Hm is inconsistent, if their conjunction implies a

contradiction, that is H1٨ H2٨ … ٨ Hm => R ٨ 7R
Where R is any formula. Note that R ٨ 7R is a contradiction and it is necessary and
sufficient that H1, H2, …,Hm are inconsistent the formula.
Indirect method of proof

In order to show that a conclusion C follows logically from the premises H1, H2,…, Hm,
we assume that C is false and consider 7C as an additional premise. If the new set of premises is
inconsistent, so that they imply a contradiction, then the assumption that 7C is true does not hold
simultaneously with H1٨ H2٨ ..… ٨ Hm being true. Therefore, C is true whenever H1٨
H2٨ ..… ٨ Hm is true. Thus, C follows logically from the premises H1, H2 ….., Hm.
Example 8 Show that 7(P ٨ Q) follows from 7P٨ 7Q. Solution.
We introduce 77 (P٨ Q) as an additional premise and show that this additional premise
leads to a contradiction.
{1} (1) 77(P٨ Q) P assumed premise
{1} (2) P٨ Q T, (1) and E1
{1} (3) P T, (2) and I1
Page 28
{1} {4) 7P٨7Q P
{4} (5) 7P T, (4) and I1
{1, 4} (6) P٨ 7P T, (3), (5) and I9
Here (6) P٨ 7P is a contradiction. Thus {1, 4} viz. 77(P٨ Q) and 7P٨ 7Q leadsto
a contradiction P ٨ 7P.
Example 9Show that the following premises are inconsistent.
1. If Jack misses many classes through illness, then he fails high school.
2. If Jack fails high school, then he is uneducated.
3. If Jack reads a lot of books, then he is not uneducated.
4. Jack misses many classes through illness and reads a lot of books.
Solution.
P: Jack misses many classes.
Q: Jack fails high school.
R: Jack reads a lot of books.
S: Jack is uneducated.
The premises are P→ Q, Q → S, R→ 7S and P٨ R
{1} (1) P→Q P

{2} (2) Q→ S P
{1, 2} (3) P→S T, (1), (2) and I13
{4} (4) R→ 7S P
{4} (5) S → 7R T, (4), and E18
{1, 2, 4} (6) P→7R T, (3), (5) and I13
{1, 2, 4} (7) 7PV7R T, (6) and E16
{1, 2, 4} (8) 7(P٨R) T, (7) and E8
{9} (9) P٨ R P
{1, 2, 4, 9) (10) (P٨ R) ٨ 7(P٨ R) T, (8), (9) and I9
The rules above can be summed up in the following table. The "Tautology" column shows how
to interpret the notation of a given rule.
Page 29
Rule of inference Tautology Nam
e
Addition
Simplification
Conjunction
Modus ponens
Modus tollens
Hypothetical
syllogism
Disjunctive syllogism
Resolution
Page 30
Predicative logic:
A predicate or propositional function is a statement containing variables. For instance ―x + 2 =

7‖, ―X is American‖, ―x < y‖, ―p is a prime number‖ are predicates. The truth value of the
predicate depends on the value assigned to its variables. For instance if we replace x with 1 in the
predicate ―x + 2 = 7‖ we obtain ―1 + 2 = 7‖, which is false, but if we replace it with 5 we get ―5
+ 2 = 7‖, which is true. We represent a predicate by a letter followed by the variables enclosed
between parenthesis: P (x), Q(x, y), etc. An example for P (x) is a value of x for which P (x) is
true. A counterexample is a value of x for which P (x) is false. So, 5 is an example for ―x + 2 =
7‖, while 1 is a counterexample. Each variable in a predicate is assumed to belong to a universe
(or domain) of discourse, for instance in the predicate ―n is an odd integer‖ ‘n‘ represents an
integer, so the universe of discourse of n is the set of all integers. In ―X is American‖ we may
assume that X is a human being, so in this case the universe of discourse is the set of all human
beings.
Free & Bound variables:
Let's now turn to a rather important topic: the distinction between free variables and bound
variables.
Have a look at the following formula:
The first occurrence of x is free, whereas the second and third occurrences of x are bound,
namely by the first occurrence of the quantifier . The first and second occurrences of the variable
y are also bound, namely by the second occurrence of the quantifier .
Informally, the concept of a bound variable can be explained as follows: Recall that quantifications
are generally of the form:
or
where may be any variable. Generally, all occurrences of this variable within the quantification
are bound. But we have to distinguish two cases. Look at the following formula to see why:
Page 31
1. may occur within another, embedded, quantification or , such as the in
in our example. Then we say that it is bound by the quantifier of this
embedded quantification (and so on, if there's another embedded quantification over
within ).
2.Otherwise, we say that it is bound by the top-level quantifier (like all other occurrences of
in our example).
Here's a full formal simultaneous definition of free and bound:
1.Any occurrence of any variable is free in any atomic formula.

2.No occurrence of any variable is bound in any atomic formula.
3. If an occurrence of any variable is free in or in , then that same occurrence is free in
, , , and .
4. If an occurrence of any variable is bound in or in , then that same occurrence is
bound in , , , . Moreover, that same occurrence is bound in
and as well, for any choice of variable y.
5. In any formula of the form or (where y can be any variable at all in this case) the
occurrence of y that immediately follows the initial quantifier symbol is bound.
6. If an occurrence of a variable x is free in , then that same occurrence is free in and
, for any variable y distinct from x. On the other hand, all occurrences of x that are
free in , are bound in and in .
If a formula contains no occurrences of free variables we call it a sentence
Page 32
Quantifiers
The variable of predicates is quantified by quantifiers. There are two types of quantifier in
predicate logic − Universal Quantifier and Existential Quantifier.
Universal Quantifier
Universal quantifier states that the statements within its scope are true for every value of the
specific variable. It is denoted by the symbol ∀
∀xP(x) is read as for every value of x, P(x) is true..

Example − "Man is mortal" can be transformed into the propositional form
∀xP(x)∀xP(x) where P(x) is the predicate which denotes x is mortal and the universe of discourse
is all men.
Existential Quantifier
Existential quantifier states that the statements within its scope are true for some values of the
specific variable. It is denoted by the symbol ∃.
∃xP(x) is read as for some values of x, P(x) is true.
Example − "Some people are dishonest" can be transformed into the propositional form
∃xP(x) where P(x) is the predicate which denotes x is dishonest and the universe of discourse is
some people.
Page 33
UNIT-II
Relations
Syllabus
Introduction, Basic Concepts of Set Theory, Representation of Discrete Structures, Relations, Types of
relations, Partial order relation, POSET, External elements in POSET, Lattices, Functions, Types of
functions, inverse of functions, invertible functions and Composition of functions
Introduction
The elements of a set may be related to one another. For example, in the set of natural numbers
there is the ‘less than or equal to’ relation between the elements. The elements of one set may also
be related to the elements another set.
Binary Relation
A binary relation between two sets A and B is a rule R which decides, for any elements, whether
a is in relation R to b. If so, we write a R b.
If a is not in relation R to b, then we shall write a R b.
We can also consider a R b as the ordered pair (a, b) in which case we can define a binary
relation from A to B as a subset of A X B. This subset is denoted by the relation R.
In general, any set of ordered pairs defines a binary relation.
For example, the relation of father to his child is F = {(a, b) / a is the father of b}
In this relation F, the first member is the name of the father and the second is the name of the
child.
The definition of relation permits any set of ordered pairs to define a relation.
For example, the set S given by

S = {(1, 2), (3, a), (b, a),(b, Joe)}
Definition
The domain D of a binary relation S is the set of all first elements of the ordered pairs in the
relation. (i.e) D(S)= {a / ∃ b for which (a, b) Є S}
Page 34
The range R of a binary relation S is the set of all second elements of the ordered
pairs in the relation.(i.e) R(S) = {b / ∃a for which (a, b) Є S}.
For example
For the relation S = {(1, 2), (3, a), (b, a) ,(b, Joe)}
D(S) = {1, 3, b, b} and
R(S) = {2, a, a, Joe}
Let X and Y be any two sets. A subset of the Cartesian product X * Y defines a relation, say C.
For any such relation C, we have D( C ) Í X and R( C) Í Y, and the relation C is said to from X
to Y. If Y = X, then C is said to be a relation form X to X. In such case, c is called a relation in
X. Thus any relation in X is a subset of X * X . The set X * X is called a universal relation in X,
while the empty set which is also a subset of X * X is called a void relation in X.
For example
Let L denote the relation ―less than or equal to‖ and D denote the relation
―divides‖ where x D y means ― x divides y‖. Both L and D are defined on the
set {1, 2, 3, 4}
L = {(1, 1), (1, 2), (1, 3), (1, 4), (2, 2), (2, 3), (2, 4), (3, 3), (3, 4), (4, 4)}
D = {(1, 1), (1, 2), (1, 3), (1, 4), (2, 2), (2, 4), (3, 3), (4, 4)}
L Ç D = {(1, 1), (1, 2), (1, 3), (1, 4), (2, 2), (2, 4), (3, 3), (4, 4)}
=D
Properties of Binary Relations:

1. reflexive
Definition: A binary relation R in a set X is reflexive if, for every x Є X, x R x,
That is (x, x) Є R.
For example
 The relation £ is reflexive in the set of real numbers.

 The set inclusion is reflexive in the family of all subsets of a universal set.
 The relation equality of set is also reflexive.
 The relation is parallel in the set lines in a plane.
Page 35
 The relation of similarity in the set of triangles in a plane is reflexive.
Examples: (i). If R1 = {(1, 1), (1, 2), (2, 2), (2, 3), (3, 3)} be a relation on A = {1, 2, 3}, then R1 is
 a reflexive relation, since for every x ∈ A, (x, x) ∈ R1.
(ii). If R2 = {(1, 1), (1, 2), (2, 3), (3, 3)} be a relation on A = {1, 2, 3}, then R2 is not a
reflexive relation, since for every 2 ∈ A, (2, 2) R2.
Symmetric
Definition: A relation R in a set X is symmetric if for every x and y in X, wheneverx

R y, then y R x.
For example
 The relation equality of set is symmetric.

 The relation of similarity in the set of triangles in a plane is symmetric.
 The relation of being a sister is not symmetric in the set of all people.
 However, in the set females it is symmetric.
Example. If R3 = {(1, 1), (1, 2), (1, 3), (2, 2), (2, 1), (3, 1)} be a relation on A = {1, 2, 3}, then
R3 is a symmetric relation.
Transitive
Definition: A relation R in a set X is transitive if, for every x, y, and z are in X,

whenever x R y and y R z , then x R z.
For example
 The relations < and > are transitive in set of real numbers
 The relation of similarity in the set of triangles in a plane is transitive.
 Definition: A relation R in a set x is antisymmetric if for every x and y in X,

whenever x R y and y R x, then x = y.
Page 36
Example: If R4 = {(1, 2), (2, 2), (2, 3)} on A = {1, 2, 3} is an anti symmetric relation.
Equivalence Relation:
Definition Type equation here.:A relation R in a set A is called an equivalence relation if
 a R a for every i.e. R is reflexive
 a R b => b R a for every a, b Є A i.e. R is symmetric
 a R b and b R c => a R c for every a, b, c Є A, i.e. R is transitive.
For example
 The relation equality of numbers on set of real numbers.
 The relation being parallel on a set of lines in a plane.
Problem1: Let us consider the set T of triangles in a plane. Let us define a relation
R in T as R= {(a, b) / (a, b Є T and a is similar to b}
We have to show that relation R is an equivalence relation
Solution :
 A triangle a is similar to itself. a R a
 If the triangle a is similar to the triangle b, then triangle b is similar to the triangle a then
a R b => b R a
 If a is similar to b and b is similar to c, then a is similar to c (i.e) a R b and b R c => a R

c.
Hence R is an equivalence relation.
Problem 2: Let x = {1, 2, 3, … 7} and R = {(x, y) / x – y is divisible by 3}

Show that R is an equivalence relation.
Solution: For any a Є X, a- a is divisible by 3,

Hence a R a, R is reflexive
For any a, b Є X, if a – b is divisible by 3, then b – a is also divisible by 3,
Page 37
R is symmetric.
For any a, b, c Є, if a R b and b R c, then a – b is divisible by 3 and b–
c is divisible by 3. So that (a – b) + (b – c) is also divisible by 3,
hence a – c is also divisible by 3. Thus R is transitive.
Hence R is equivalence.
Problem3 Let Z be the set of all integers. Let m be a fixed integer. Two integers a and b are said
to be congruent modulo m if and only if m divides a-b, in which case we write a ≡b (mod m).
This relation is called the relation of congruence modulo m and we can show that is an equivalence
relation.
Solution :
 a - a=0 and m divides a – a (i.e) a R a, (a, a) Є R, R is reflexive .

 a R b = m divides a-b
m divides b - a
b ≡a (mod m)
bRa
that is R is symmetric.
 a R b and b R c => a ≡b (mod m) and b≡ c (mod m)

o m divides a – b and m divides b-c
o a – b = km and b – c = lm for some k ,l Є z
o (a – b) + (b – c) = km + lm
o a – c = (k +l) m
o a≡ c (mod m)
o aRc
o R is transitive
Hence the congruence relation is an equivalence relation.
Page 38
Equivalence Classes:
Let R be an equivalence relation on a set A. For any a ЄA, the equivalence class generated by a
is the set of all elements b Є A such a R b and is denoted [a]. It is also called the R – equivalence
class and denoted by a Є A.
i.e., [a] = {b Є A / b R a}
Let Z be the set of integer and R be the relation called ―congruence modulo 3
defined by R = {(x, y)/ x∈ Z and y∈ Z , (x-y) is divisible by 3}
Then the equivalence classes are
[0] = {… -6, -3, 0, 3, 6, …}
[1] = {…, -5, -2, 1, 4, 7, …}
[2] = {…, -4, -1, 2, 5, 8, …}
Composition of binary relations:
Definition:Let R be a relation from X to Y and S be a relation from Y to Z. Then the relation R

o S is a relation from X to Z given by R o S = {(x, z) / x∈ 𝑋, 𝑧 ∈ 𝑍S)} is called the composite
relation of R and S.
The operation of obtaining R o S is called the composition of relations.
Example: Let R = {(1, 2), (3, 4), (2, 2)} and

S = {(4, 2), (2, 5), (3, 1),(1,3)}
Then R o S = {(1, 5), (3, 2), (2, 5)} and S o R = {(4, 2), (3, 2), (1, 4)}
It is to be noted that R o S ≠ S o R.
Also Ro(S o T) = (R o S) o T = R o S o T
Note: We write R o R as R2; R o R o R as R3 and so on.
Definition
Let R be a relation from X to Y, a relation R from Y to X is called the converse of R,
where the ordered pairs of Ř are obtained by interchanging the numbers in each of the ordered
pairs of R. This means for x ∈ X and y ∈ Y, that x R y ó y Ř x.
Page 39
Then the relation Ř is given by R = {(x, y) / (y, x) ∈ R} is called the converse of R
Example:
Let R = {(1, 2),(3, 4),(2, 2)}
Then Ř = {(2, 1),(4, 3),(2, 2)}
Note: If R is an equivalence relation, then Ř is also an equivalence relation.
Page 40
Partial Ordering Relations:
Definition
A binary relation R in a set P is called a partial order relation or a partial ordering in
P if R is reflexive, ant symmetric, and transitive.
i.e.,
 aRa for all a ∈ P
 aRb and bRa ➙ a = b
 aRb and bRc ➙ aRc
A set P together with a partial ordering R is called a partial ordered set or poset. The relation R
is often denoted by the symbol ≤ which is different from the usual less than equal to symbol.
Thus, if ≤ is a partial order in P , then the ordered pair (P, ≤) is called a poset.
Example: Show that the relation ‖greater than or equal to‖ is a partial ordering on the set of
integers.
Solution: Let Z be the set of all integers and the relation R =≥
(i). Since a ≥ a for every integer a, the relation ≥ is reflexive.
(ii). Let a and b be any two integers.
Let aRb and bRa ➙ a ≥ b and b ≥ a
➙a=b
∴ The relation≥ is antisymmetric.
(iii).Let a, b and c be any three integers.
Let aRb and bRc ➙ a ≥ b and b ≥ c
➙a≥c
∴ The relation Let aRb and bRc ➙ a ≥ b and b ≥ c
➙a≥c
∴ The relation≥ is transitive.
Since the relation ≥ is reflexive, antisymmetric and transitive,≥ is partial ordering on the set of
integers. Therefore, (Z, ≥) is a poset.
Page 41
Hasse Diagram:
A Hasse diagram is a digraph for a poset which does not have loops and arcs implied by the
transitivity.
Example 10: For the relation {< a, a >, < a, b >, < a, c >, < b, b >, < b, c >, < c, c >} on set {a,
b,c}, the Hasse diagram has the arcs {< a, b >, < b, c >} as shown below.
Ex: Let A be a given finite set and r(A) its power set. Let Í be the subset relation on the elements
of r(A). Draw Hasse diagram of (r(A), Í) for A = {a, b, c}
Page 42
Qn. From the Hasse diagram, find the maximal, Minimal, Greatest element, Least element, Upper bound,
Least upper bound, Lower bound and Greatest lower bound of {𝑎, 𝑏, 𝑐 }
Functions:
Introduction
A function is a special type of relation. It may be considered as a relation in which each
element of the domain belongs to only one ordered pair in the relation. Thus a function from A
to B is a subset of A X B having the property that for each a ЄA, there is one and only one b Є B
such that (a, b) Î G.
Definition
Let A and B be any two sets. A relation f from A to B is called a function if for every a Є A
there is a unique b Є B such that (a, b) Є f .
Note that the definition of function requires that a relation must satisfy two additional
conditions in order to qualify as a function.
The first condition is that every a Є A must be related to some b Є B, (i.e) the domain of f must
be A and not merely subset of A. The second requirement of uniqueness can be expressed as (a,
b) Є f ٨ (b, c) Є f => b = c
Intuitively, a function from a set A to a set B is a rule which assigns to every element of A, a
Page 43
unique element of B. If a ЄA, then the unique element of B assigned to a under f is denoted by f
(a).The usual notation for a function f from A to B is f: A® B defined by a ® f (a) where a Є A,
f(a) is called the image of a under f and a is called pre image of f(a).
 Let X = Y = R and f(x) = x2 + 2. D(f) = R and R(f) ⊆ R.

 Let X be the set of all statements in logic and let Y = {True, False}.
A mapping f: X®Y is a function.
 A program written in high level language is mapped into a machine language by a

compiler. Similarly, the output from a compiler is a function of its input.
 Let X = Y = R and f(x) = x2 is a function from X ® Y,and g(x2) = x is not a function
from X ® Y.
A mapping f: A ® B is called one-to-one (injective or 1 –1) if distinct elements

of A are mapped into distinct elements of B. (i.e) f is one-to-one if
a1 = a2 => f (a1) = f(a2) or equivalently f(a1) ¹ f(a2) => a1 ¹ a2
For example, f: N ® N given by f(x) = x is 1-1 where N is the set of a natural numbers.
A mapping f: A® B is called onto (surjective) if for every b Є B there is an a Є A suchthat
f (a) = B. i.e. if every element of B has a pre-image in A. Otherwise it is called into.
For example, f: Z®Z given by f(x) = x + 1 is an onto mapping. A

mapping is both 1-1 and onto is called bijective
.
For example f: R®R given by f(x) = X + 1 is bijective
Definition: A mapping f: R® b is called a constant mapping if, for all a Є A, f (a) =

b, a fixed element.
For example f: Z®Z given by f(x) = 0, for all x Є Z is a constant mapping.
Page 44
.
Definition
A mapping f: A®A is called the identity mapping of A if f (a) = a,
for all a Є A. Usually it is denoted by IA or simply I.
Composition of functions:
If f: A®B and g: B®C are two functions, then the composition of functions f and g, denoted
by g o f, is the function is given by g o f : A®C and is given by
g o f = {(a, c) / a Є A ٨ c Є C ٨ b Є B ': f(a)= b ٨ g(b) = c}
and (g of)(a) = ((f(a))
Example 1: Consider the sets A = {1, 2, 3},B={a, b} and C = {x, y}.

Let f: A® B be defined by f (1) = a ; f(2) = b and f(3)=b and
Let g: B® C be defined by g(a) = x and g(b) = y
(i.e) f = {(1, a), (2, b), (3, b)} and g = {(a, x), (b, y)}.
Then g o f: A®C is defined by
(g of) (1) = g (f(1)) = g(a) = x
(g o f) (2) = g (f(2)) = g(b) = y
(g o f) (3) = g (f(3)) = g(b) = y
i.e., g o f = {(1, x), (2, y),(3, y)}
If f: A® A and g: A®A, where A= {1, 2, 3}, are given by

f = {(1, 2), (2, 3), (3, 1)} and g = {(1, 3), (2, 2), (3, 1)}
Then g of = {(1, 2), (2, 1), (3, 3)}, fog= {(1, 1), (2, 3), (3, 2)}
f of = {(1, 3), (2, 1), (3, 2)} and gog= {(1, 1), (2, 2), (3, 3)}
Page 45
Example 2: Let f(x) = x+2, g(x) = x – 2 and h(x) = 3x for x Î R, where R is the set of
real numbers.
Then f o f = {(x, x+4)/x Є
R} f o g = {(x, x)/ x Є
X}
g o f = {(x, x)/ x Є X}
g o g = {(x, x-4)/x Є X}
h o g = {(x,3x-6)/ x Є X}
h o f = {(x, 3x+6)/ x Î Є
X}
Inverse functions:
Let f: A® B be a one-to-one and onto mapping. Then, its inverse, denoted by f -1 is given by f -
1 = {(b, a) / (a, b) Є f} Clearly f-1: B® A is one-to-one and onto.
Also we observe that f o f -1 = IB and f -1o f = IA. If

f -1 exists then f is called invertible.
For example: Let f: R ®R be defined by f(x) = x + 2

Then f -1: R® R is defined by f -1 (x) = x - 2
Page 46
Theorem: Let f: X ®Y and g: Y ® Z be two one to one and onto functions. Then gof is also one
to one and onto function.
Proof
Let f:X ® Y g : Y ® Z be two one to one and onto functions. Let x1, x2 Є X
 g o f (x1) = g o f(x2),
 g (f(x1)) = g(f(x2)),
 g(x1) = g(x2) since [f is 1-1]
x1 = x2 since [ g is 1-1}
so that gof is 1-1.
By the definition of composition, gof : X ® Z is a function.

We have to prove that every element of z Є Z an image element for some x Є
Xunder gof.
Since g is onto $ y Є Y ': g(y) = z and f is onto from X to Y,
$ x Є X ': f(x) = y.
Now, gof (x) = g ( f ( x))
= g(y) [since f(x) = y]
= z [since g(y) = z]
which shows that gof is onto.
Theorem (g o f) -1 = f -1o g -1
(i.e) the inverse of a composite function can be expressed in terms of the
composition of the inverses in the reverse order.
Proof.
f: A ® B is one to one and onto.
g: B ® C is one to one and onto.
gof: A ® C is also one to one and onto.
Þ (gof) -1: C ® A is one to one and onto.
Page 47
Let a Є A, then there exists an element b Є B such that f (a) = b Þ a = f-1 (b).
Now b Є B Þ there exists an element c Є C such that g (b) = c Þ b = g-1 (c).
Then (gof)(a) = g[f(a)] = g(b) = c Þ a = (gof) -1(c). .............(1)
(f -1 o g-1) (c) = f -1(g -1 (c)) = f -1(b) = a Þ a = (f -1 o g -1)( c ) ….(2)
Combining (1) and (2), we have
(gof) -1 = f -1 o g -1
Theorem: If f: A ® B is an invertible mapping , then

f o f -1 = I B and f-1 o f = IA
Proof: f is invertible, then f -1 is defined by f(a) = b ó f-1(b) = a
where a Є A and b Є B .
Now we have to prove that f of -1 = IB .
Let b Є B and f -1(b) = a, a Î A
then fof-1(b) = f(f-1(b))
= f(a) = b
therefore f o f -1 (b) = b " b Î B => f o f -1 = IB
Now f -1 o f(a) = f -1 (f(a)) = f -1 (b) = a therefore
f -1 o f(a) = a " a Є A => f -1 o f = IA.
Lattice and its Properties:
Introduction:
A lattice is partially ordered set (L, £) in which every pair of elements a, b ÎL has a greatest
lower bound and a least upper bound.
The glb of a subset, {a, b} Í L will be denoted by a * b and the lub by a Å b.
.
Usually, for any pair a, b Î L, GLB {a, b} = a * b, is called the meet or product and LUB{a,
b} = a Å b, is called the join or sum of a and b.
Example1 Consider a non-empty set S and let P(S) be its power set. The relation Í ―contained
in‖ is a partial ordering on P(S). For any two subsets A, B P(S)
GLB {A, B} and LUB {A, B} are evidently A Ç B and A È B respectively.
Page 48
Example2 Let I+ be the set of positive integers, and D denote the relation of ‘division’ in
I+ such that for any a, b Є I+ , a D b iff a divides b. Then (I+, D) is a lattice in which
the join of a and b is given by the least common multiple(LCM) of a and b, that is,
a Å b = LCM of a and b, and the meet of a and b, that is , a * b is the greatest common divisor
(GCD) of a and b.
A lattice can be conveniently represented by a diagram.

For example, let Sn be the set of all divisors of n, where n is a positive integer. Let D denote the
relation ―division‖ such that for any a, b cdi654p[]
Fda21 A Sn, a D b iff a divides b.

Then (Sn, D) is a lattice with a * b = gcd (a, b) and a Å b = lcm(a, b).
Take n=6. Then S6 = {1, 2, 3, 6}. It can be represented by a diagram in Fig(1).
Take n=8. Then S8 = {1, 2, 4, 8}
Two lattices can have the same diagram. For example if S = {1, 2, 3} then (p(s), Í ) and (S6,D)
have the same diagram viz. fig(1), but the nodes are differently labeled .
We observe that for any partial ordering relation £ on a set S the
converse relation ³ is also partial ordering relation on S. If (S, £) is a lattice
With meet a * b and join a Å b , then (S, ³ ) is the also a lattice with meet
a Å b and join a * b i.e., the GLB and LUB get interchanged . Thus we have
the principle of duality of lattice as follows.
Any statement about lattices involving the operations ^ and V and the relations £
and ³ remains true if ^, V, ³ and £ are replaced by V, ^, £ and ³ respectively.
The operation ^ and V are called duals of each other as are the relations £ and ³..
Also, the lattice (L, £) and (L, ³) are called the duals of each other.
Properties of lattices:
Let (L, £) be a lattice with the binary operations * and Å then for any a, b, c Î L,
 a*a=a aÅa =a (Idempotent)

 a*b=b*a , aÅ b = bÅ a (Commutative)
Page 49
 (a * b) * c = a * (b * c) , (a Å ) Å c = a Å (b Å c)
Page 50
o (Associative)
 a * (a Å b) = a , a Å (a * b ) = a (absorption)
For any a ÎL, a £ a, a £ LUB {a, b} => a £ a * (a Å b). On the other hand, GLB
{a, a Å b} £ a i.e., (a Å b) Å a, hence a * (a Å b) = a
Theorem 1
Let (L, £) be a lattice with the binary operations * and Å denote the operations of meet and join
respectively For any a, b Î L,
a£b óa*b=aóaÅb=b
Proof
Suppose that a £ b. we know that a £ a, a £ GLB {a, b}, i.e., a £ a * b.

But from the definition of a * b, we get a * b £ a.
Hence a £ b => a * b = a ………………………… (1)
Now we assume that a * b = a; but is possible only if a £ b,
that is a * b = a => a £ b ………………………… (2)
From (1) and (2), we get a £ b ó a * b = a.
Suppose a * b = a.
then b Å (a * b) = b Å a = a Å b ……………………. (3)
but b Å ( a * b) = b ( by iv) …………………….. (4)
Hence a Å b = b, from (3) => (4)
Suppose aÅ b = b, i.e., LUB {a, b} = b, this is possible only if a£ b, thus(3) => (1)
(1) => (2) => (3) => (1). Hence these are equivalent.
Let us assume a * b = a.
Now (a * b) Å b = a Å b
We know that by absorption law , (a * b) Å b = b
so that a Å b = b, therefore a * b = a Þ a Å b = b (5)
similarly, we can prove a Å b = b Þ a * b = a (6)
From (5) and (6), we get
Page 51
a*b=aÛaÅb =b
Hence the theorem.
Theorem2 For any a, b, c Î L, where (L, £) is a lattice.

b £ c => { a * b £ a * c and
{ aÅb£ aÅc
Proof Suppose b £ c. we have proved that b £ a ó b * c = b… ..... (1)

Now consider
(a * b ) * (a * c) = (a * a) * (b * c) (by Idempotent)
= a * (b * c)
= a*b (by (1))
Thus (a * b) * (a * c ) = a * b which => (a * b ) £ (a * c)
Similarly (a Å b) Å ( a Å c) = (a Å a) Å (b Å c)
= a Å (b Å c)
=aÅ c
which => (a Å b ) £ (a Å c )
note: These properties are known as isotonicity.
Page 52
Unit-III:
Algebraic Structures
Syllabus:
Algebraic structures: Algebraic systems with examples and general properties, semi groups and
monoids, groups & its types, Introduction to homomorphism and Isomorphism (Proof of theorems
are not required)
Algebraic systems
N = {1,2,3,4,….. } = Set of all natural numbers.
Z = { 0, ± 1, ± 2, ± 3, ± 4 , ….. } = Set of all integers. Q=

Set of all rational numbers.
R = Set of all real numbers.
Binary Operation: The binary operator * is said to be a binary operation (closed operation)
on anon- empty set A, if a * b ∈ A for all a, b ∈ A (Closure property).
Ex: The set N is closed with respect to addition and multiplication but
not w.r.t subtraction and division.
Algebraic System: A set A with one or more binary(closed) operations defined on it is

called an algebraic system.
Ex: (N, + ), (Z, +, – ), (R, +, . , – ) are algebraic systems.
Properties
Associativity: Let * be a binary operation on a set

A.The operation * is said to be associative in A .
if (a * b) * c = a *( b* c) for all a, b, c in A
Page 53
Identity: For an algebraic system(A,*), an element e in A is said to be an identity element of
A if a * e = e * a = a for all a ∈ A.
Note: For an algebraic system (A, *), the identity element, if exists, is unique.
Inverse: Let(A,*) be an algebraic system with identity ‗e‘. Let a be an element in A. An

element b is said to be inverse of A .
if a * b = b * a = e
Semi groups
Semi Group: An algebraic system (A, *) is said to be a semi group if
1. * is closed operation on A.
2. * is an associative operation, for all a, b, c in
A. Ex. (N, +) is a semi group.
Ex. (N, .) is a semi group.
Ex. (N, – ) is not a semi group.
Page 54
Monoid
An algebraic system (A, *) is said to be a monoid if the following conditions are satisfied.
1) * is a closed operation in A.
2) * is an associative operation in A.
3) There is an identity in A.
Ex. Show that the set N is a monoid with respect to
multiplication. Solution: Here, N = {1,2,3,4,……}
Closure property:1We know that product of two natural numbers is again a natural number.
i.e., a.b=b.a for all a,b∈ N
∴ Multiplication is a closed operation.
Associativity : Multiplication of natural numbers is associative.
i.e., (a.b).c = a.(b.c) for all a,b,c ∈ N
Identity : We have, 1 ∈ N such that
a.1 = 1.a = a for all a ∈ N.
∴ Identity element exists, and 1 is the identity element.
Hence, N is a monoid with respect to multiplication
Page 55
Examples
Ex. Let (Z, *) be an algebraic structure, where Z is the set of integers
and the operation * is defined by n * m = maximum of (n, m).
Show that (Z, *) is a semi group. Is (Z, *) a monoid ?. Justify your answer.
Solution: Let a , b and c are any three integers.
Closure property: Now, a * b = maximum of (a, b) ∈ Z for all a,b ∈Z
Associativity : (a * b) * c = maximum of {a,b,c} = a * (b * c)
∴ (Z, *) is a semi group.

Identity : There is no integer x such that
a * x = maximum of (a, x) = a for all a ∈Z

∴ Identity element does not exist. Hence, (Z, *) is not a monoid.
Ex. Show that the set of all strings S is a monoid under the operation concatenation
of strings‘.
Is S a group w.r.t the above operation? Justify your answer.
Page 56
Solution: Let us denote the operation
‗concatenation of strings‘ by +.
Let s1, s2, s3 are three arbitrary strings in S.
Closure property: Concatenation of two strings is again a string. i.e.,
s1+s2 ∈ S
Associativity: Concatenation of strings is associative.
(s1+ s2 ) + s3 = s1+ (s2 + s3 )
Identity: We have null string , l ∈ S such that s1 + l = S.

∴ S is a monoid.
Note: S is not a group, because the inverse of a nonempty string does not exist under
concatenation of strings.
Groups
Group: An algebraic system (G, *) is said to be a group if the following conditions are satisfied.
1) * is a closed operation.
2) * is an associative operation.
3) There is an identity in G.
4) Every element in G has inverse in G.
Abelian group (Commutative group): A group (G, *) said

to be abelian (or commutative) if
a*b=b*a for all a, b ∈ G.
Page 57
Properties
In a Group (G, * ) the following properties hold good
1. Identity element is unique.
2. Inverse of an element is unique.
3. Cancellation laws hold good
a * b = a * c => b = c (left cancellation law)
a * c = b * c => a = b (Right cancellation
law)
4. (a * b) -1 = b-1 *a-1
In a group, the identity element is its own inverse.
Order of a group :The number of elements in a group is called order of the
group. Finite group: If the order of a group G is finite, then G is called a finite
group.
Ex1 . Show that, the set of all integers is an abelian group with respect to addition.
Solution: Let Z = set of all integers.
Let a, b, c are any three elements of Z.
1. Closure property: We know that ,Sum of two integers is again an
integer. i.e., a + b ∈ Z for all a,b ∈ Z
2. Associativity: We know that addition of integers is
Page 58
associative. i.e., (a+b)+c = a+(b+c) for all a,b,c ∈
Z.
3. Identity : We have 0 ∈ Z and a + 0 = a for all a ∈ Z .

∴ Identity element exists, and ‗0‘ is the identity element.
4. Inverse: To each a ∈ Z , we have – a ∈ Z such that
a+(–a)=0
Each element in Z has an inverse.
5. Commutativity: We know that addition of integers is
commutative. i.e., a + b = b +a for all a,b ∈ Z.
Hence, ( Z , + ) is an abelian group.
Page 59
Ex2 . Show that set of all non zero real numbers is a group with respect to multiplication.
Solution: Let R* = set of all non zero real numbers.
Let a, b, c are any three elements of R* .
1. Closure property:Weknowthat,productoftwononzerorealnumbersisagainanonzeroreal
number .
i.e., a . b ∈ R* for all a,b ∈ R* .
2. Associativity: We know that multiplication of real numbers is
associative.
i.e.,(a.b).c=a.(b.c) for all a,b,c ∈ R* .
3. Identity : We have 1 ∈ R* and a .1 = a for all a ∈ R* .

∴ Identity element exists, and ‗1’ is the identity element.
4. Inverse: To each a ∈ R* , we have 1/a ∈ R* such that

a .(1/a) = 1 i.e., Each element in R* has an inverse.
5.Commutativity: We know that multiplication of real
numbers is commutative.
i.e., a . b = b . a for all a,b∈R*.
Hence, ( R* , . ) is an abelian group.
Note: Show that set of all real numbers ‗Ris not a group with respect to multiplication.
Solution: We have 0 ∈ R .
The multiplicative inverse of 0 does not exist.
Hence. R is not a group.
Page 60
Example: Let S be a finite set, and let F(S) be the collection of all functions f:S→S
under the operation of composition of functions, then show that F(S) is a monoid.
Is S a group w.r.t the above operation? Justify your answer.
Solution: Let f1, f2, f3 are three arbitrary functions on S.
Closure property: Composition of two functions on S is again a function on S.
i.e., f1of2 ∈ F(S)

Associativity: Composition of functions is associative.
i.e., (f1 o f2 ) o f3 = f1 o (f2 o f3 )

Identity: We have identity function I : S→S
such that f1 o I = f1.
∴ F(S) is a monoid.
Note: F(S) is not a group, because the inverse of an bijective function on S does not exist.
Ex. If M is set of all non singular matrices of order ‗n x n‘. thenshow that M is a
groupw.r.t. matrix multiplication. Is (M,*) an abelian group?. Justify your
answer.
Solution: Let A,B,C ∈M.

1. Closure property : Product of two non-singular matrices is again a non-singular matrix,
because |𝐴𝐵| = |𝐴| |𝐵| ≠ 0 (Since, A and B are nonsingular)
i.e., AB ∈ M for all A,B ∈ M .

2. Associativity: Matrix multiplication is associative.
i.e., (AB)C=A(BC) for all A, B, C ∈ M .
3. Identity : We have In ∈ M and A In = A for all A ∈ M .
∴ Identity element exists, and ‗In‘ is the identity element.
4. Inverse: To each A ∈ M, we have A-1 ∈ M such that
AA-1 = In i.e., Each element in M has an inverse.
∴ M is a group w.r.t. matrix multiplication.

We know that, matrix multiplication is not commutative. Hence, M is not an abelian group.
Page 61
Ex. Show that the set of all positive rational numbers form s an abelian groupunder the composition
* defined by
a * b = (ab)/2 .
Solution: Let A = set of all positive rational numbers.
Let a, b, c be any three elements of A.
1. Closure property: We know that , Product of two positive rational numbers is again a
rational number.
i.e., a *b ∈ A for all a,b ∈ A .

2. Associativity: (a*b)*c = (ab/2) * c = (abc) / 4
a*(b*c) = a * (bc/2) = (abc) / 4
3. Identity : Let e be the identity element.
We have a*e=(ae)/2 …(1) , By the definition of again,
a*e = a …..(2),Since e is the identity.
From (1) and (2), (a e)/2 =a ⇒ e = 2 and 2 ∈ A

∴ Identity element exists, and 2 is the identity element in A.
4. Inverse: Let a ∈ A let us suppose b is inverse of a
. Now, a * b= (ab)/2 ….(1) (By definition of inverse.)

Again, a* b= e = 2 …..(2) (By definition of inverse)
From (1) and (2), it follows that (a b)/2 = 2
=> b = (4 / a) ∈ A
∴ (A ,*) is a group.
Commutativity: a * b = (ab/2) = (ba/2) = b * a
Hence, (A,*) is an abelian group.
Page 62
Finite groups
Ex. Show that G = {1, -1} is an abelian group under multiplication.
Solution: The composition table of G is
* 1 -1
1 1 -1
-1 -1 1
1. Closure property: Since all the entries of the composition table are the elements of the
given set, the set G is closed under multiplication.
2. Associativity: The elements of G are real numbers, and we know that multiplication of real
numbers is associative.
3. Identity : Here, 1 is the identity element and 1∈ G.
4. Inverse: From the composition table, we see that the inverse elements of
1 and – 1 are 1 and – 1 respectively.
Hence, G is a group w.r.t multiplication.
5. Commutativity: The corresponding rows and columns of the table are identical.
Therefore the binary operation . is commutative.
Hence, G is an abelian group w.r.t. multiplication..
Ex. Show that G = {1, w, w2} is an abelian group under multiplication.

Where 1, w, w2 are cube roots of unity.
* 1 w w2
1 1 w w2
w w w2 1
w2 w2 1 w
Page 63
1. Closure property: Since all the entries of the composition table are the elements of thegiven
set, the set G is closed under multiplication.
2. Associativity: The elements of G are complex numbers, and we know that

multiplication of complex numbers is associative.
3. Identity : Here, 1 is the identity element and 1∈ G.
4. Inverse: From the composition table, we see that the inverse elements of 1 w, w2are
1, w2, w respectively.
Hence, G is a group w.r.t multiplication.
5. Commutativity: The corresponding rows and columns of the table are identical.
Therefore the binary operation . is commutative.
Hence, G is an abelian group w.r.t. multiplication.
Modulo systems
Addition modulo m ( +m )
let m is a positive integer. For any two positive integers a and b
a +m b = a + b if a + b < m
a +m b = r if a + b > m where r is the remainder obtained

by dividing (a+b) with m.
Multiplication modulo p ( *m)
let p is a positive integer. For any two positive integers a and b a
*mb = a b if a b < p
a *mb = r if a b ³ p where r is the remainder obtained
by dividing (ab) with p.
Ex. 3 *5 4 = 2 , 5 *5 4 = 0 , 2 *5 2 = 4
Page 64
Example : The set G = {0,1,2,3,4,5} is a group with respect to addition modulo 6.
+6 0 1 2 3 4 5
0 0 1 2 3 4 5
1 1 2 3 4 5 0
2 2 3 4 5 0 1
3 3 4 5 0 1 2
4 4 5 0 1 2 3
5 5 0 1 2 3 4
1. Closure property: Since all the entries of the composition table are the elements of the givenset,
the set G is closed under +6 .
2. Associativity: The binary operation +6 is associative in G.
for ex. (2 +6 3) +6 4 = 5 +6 4 = 3 and
2 +6 ( 3 +6 4 ) = 2 +6 1 = 3
3. Identity : Here, The first row of the table coincides with the top row. The element
heading that row , i.e., 0 is the identity element.
4. .Inverse: From the composition table, we see that the inverse elements of 0,1,2,3,4.5 are 0,
5,4, 3, 2, 1 respectively
5.Commutativity: The corresponding rows and columns of the table are identical. Therefore the
binary operation +6 is commutative.
Hence, (G, +6 ) is an abelian group.
Page 65
Example : The set G= {1,2,3,4,5,6} is a group with respect to multiplication modulo 7.
*7 1 2 3 4 5 6
1 1 2 3 4 5 6
2 2 4 6 1 3 5
3 3 6 2 5 1 4
4 4 1 5 2 6 3
5 5 3 1 6 4 2
6 6 5 4 3 2 1
1. Closure property: Since all the entries of the composition table are the elements of the givenset,
the set G is closed under *7 .
2. Associativity: The binary operation *7 is associative in G.
for ex. (2 *7 3) *7 4 = 6 *7 4 = 3 and
2 * 7 ( 3 *7 4 ) = 2 *7 5 = 3
3. Identity : Here, The first row of the table coincides with the top row. The element
heading that row , i.e., 1 is the identity element.
4. . Inverse: From the composition table, we see that the inverse elements of 1, 2, 3, 4. 56 are 1, 4,
5, 2, 5, 6 respectively.
5. Commutativity: The corresponding rows and columns of the table are identical. Therefore thebinary
operation *7 is commutative.
Hence, (G, *7 ) is an abelian group.
More on finite groups
In a group with 2 elements, each element is its own inverse
Page 66
In a group of even order there will be at least one element (other than identity element) which is itsown inverse
The set G = {0,1,2,3,4,…..m-1} is a group with respect to addition modulo m.
The set G = {1,2,3,4,….p-1} is a group with respect to multiplication

modulo p, where p is a prime number.
Sub groups
Def. A non empty sub set H of a group (G, *) is a sub group of G,
if (H, *) is a group.
Note: For any group {G, *}, {e, * } and (G, * ) are trivial sub groups.
Ex. G = {1, -1, i, -i } is a group w.r.t multiplication.
H1 = { 1, -1 } is a subgroup of G . H2 = { 1 } is a trivial subgroup of G.
Ex. ( Z , + ) and (Q , + ) are sub groups of the group (R +). Theorem: A non-empty sub set H of a group
(G, *) is a sub group of G iff
i) a*b ∈ H V a, b∈ H
i) a-1∈ H Va∈ H
Homomorphism and Isomorphism
Homomorphism : Consider the groups ( G, *) and ( G1, ⊕)
A function f : G → G1 is called a homomorphism if f( a * b) = f(a) ⊕f (b)
Isomorphism : If a homomorphism f : G→G 1 is a bijection then f is called isomorphism between G

and G1 .
Then we write G ≡ G1
Page 67
Example : Let R be a group of all real numbers under addition and R+ be a group of all positive real
number sunder multiplication. Show that the mapping f : R → R+ defined byf(x) = 2x for all x ∈ R
is an isomorphism.
Solution: First, let us show that f is a homomorphism. Let a ,b ∈ R.
Now, f(a+b) = 2a+b
= 2a 2b
= f(a).f(b)
∴ f is an homomorphism.
Next, let us prove that f is a Bijection. For
any a , b ∈ R, Let, f(a) = f(b)

=> 2a = 2b
=> a = b
∴ f is one.to-one.
Next, take any c ∈ R+.
Then log2 c ∈ R and f (log2 c ) = 2 log2 c = c.
⇒ Every element in R+ has a pre image in R. i.e., f is
onto.
∴ f is a bijection.
Hence, f is an isomorphism.
Ex. Let R be a group of all real numbers under addition and R+ be a group of all positive real
Numbers under multiplication. Show that the mapping f : R+ → R defined by f(x) = log10 xfor
all x ∈ R is an isomorphism.
Solution: First, let us show that f is a homomorphism. Let
a , b ∈ R+ .
Now, f(a.b) = log10 (a.b)
= log10 a + log10 b
= f(a) + f(b)
∴ f is an homomorphism.
Page 68
Next, let us prove that f is a
Bijection. For any a , b ∈ R+ , Let,
f(a) =f(b)
=> log10 a = log10 b
=> a = b
∴ f is one.to-one.
Next, take any c ∈ R.
Then 10c ∈ R and f (10c) = log10 10c = c.
⇒ Every element in R has a pre image inR+ .
i.e., f is onto.
∴ f is a bijection.
Hence, f is an isomorphism.
Page 69
UNIT-IV
COMBINATORICS
Basis of counting:
If X is a set, let us use |X| to denote the number of elements in X.
Two Basic Counting Principles
Two elementary principles act as ―building blocks< for all counting problems. The
first principle says that the whole is the sum of its parts; it is at once immediate and
elementary.
Sum Rule: The principle of disjunctive counting :
If a set X is the union of disjoint nonempty subsets S1, ….., Sn, then | X | = | S1 | + | S2 | + ….. +
| Sn |.
We emphasize that the subsets S1, S2, …., Sn must have no elements in common.
Moreover, since X = S1 U S2 U ……U Sn, each element of X is in exactly one of the
subsets Si. In other words, S1, S2, …., Sn is a partition of X.
If the subsets S1, S2, …., Sn were allowed to overlap, then a more
profound principle will be needed--the principle of inclusion and exclusion.
Frequently, instead of asking for the number of elements in a set perse, someproblems
ask for how many ways a certain event can happen.
The difference is largely in semantics, for if A is an event, we can let X be the set of ways
that A can happen and count the number of elements in X. Nevertheless, let us state the sum rule
for counting events.
If E1, ……, En are mutually exclusive events, and E1 can happen e1 ways, E2 happen
e2 ways,…. ,En can happen en ways, E1 or E2 or …. or En can happen e1 + e2 +
…….. + en ways.
Again we emphasize that mutually exclusive events E1 and E2 mean that E1 or E2 can
happen but both cannot happen simultaneously.
The sum rule can also be formulated in terms of choices: If an object can be selected
from a reservoir in e1 ways and an object can be selected from a separate reservoir in e2 ways
and an object can be selected from a separate reservoir in e2 ways, then the selection of one
object from either one reservoir or the other can be made in e1 + e2 ways.
Page 70
Product Rule: The principle of sequencing counting
If S1, ….., Sn are nonempty sets, then the number of elements in the Cartesian product
S1 x S2 x ….. x Sn is the product ∏in=1 |S i |. That is,
| S1 x S2 x ............. x Sn | = ∏in=1| S i |.
Observe that there are 5 branches in the first stage corresponding to the 5 elements of S1
and to each of these branches there are 3 branches in the second stage corresponding to the 3
elements of S2 giving a total of 15 branches altogether. Moreover, the Cartesian product S1 x S2
can be partitioned as (a1 x S2) U (a2 x S2) U (a3 x S2) U (a4 x S2) U (a5 x S2), where (ai x S2)
= {( ai, b1), ( ai i, b2), ( ai, b3)}. Thus, for example, (a3 x S2) corresponds to the third branch in
the first stage followed by each of the 3 branches in the second stage.
More generally, if a1,….., an are the n distinct elements of S1 and b1,….,bm are the m
distinct elements of S2, then S1 x S2 = Uin =1 (ai x S2).
For if x is an arbitrary element of S1 x S2 , then x = (a, b) where a Î S1 and b Î

S2. Thus, a = ai for some i and b = bj for some j. Thus, x = (ai, bj) Î(ai x S2) and
therefore x Î Uni =1(ai x S2).
Conversely, if x Î Uin =1(ai x S2), then x Î (ai x S2) for some i and thus x = (ai, bj) where
bj is some element of S2. Therefore, x Î S1 x S2.
Next observe that (ai x S2) and (aj x S2) are disjoint if i ≠ j since if
x Î (ai x S2) ∩ (aj x S2) then x = ( ai, bk) for some k and x = (aj, b1) for some l.
But then (ai, bk) = (aj, bl) implies that ai = aj and bk = bl. But since i ≠ j , ai ≠ a j.
Thus, we conclude that S1 x S2 is the disjoint union of the sets (ai x S2).
Furthermore |ai x S2| = |S2| since there is obviously a one-to-one correspondence between
the sets ai x S2 and
S2, namely, (ai, bj) → bj.
Then by the sum rule |S1 x S2| = ∑nni=1 | ai x S2|

7.(n summands) |S2| + |S2| +… .... + |S2|
8.n |S2|
9.nm.
Therefore, we have proven the product rule for two sets. The general rule follows by
mathematical induction.
MFCS
Page 71
We can reformulate the product rule in terms of events. If events E1, E2 , …., En
can happen e1, e2,…., and en ways, respectively, then the sequence of events E1 first,
M F C followed by E2,…., followed by En can happen e1e2 …en ways.
S In terms of choices, the product rule is stated thus: If a first object can be chosen
e1ways, a second e2 ways , …, and an nth object can be made in e1e2….en ways.
Combinations & Permutations

Definition.
A combination of n objects taken r at a time (called an r-combination of n objects)
is an unordered selection of r of the objects.
A permutation of n objects taken r at a time (also called an r-permutation of n
objects) is an ordered selection or arrangement of r of the objects.
Note that we are simply defining the terms r-combinations and r-permutations
here and have not mentioned anything about the properties of the n objects.
For example, these definitions say nothing about whether or not a given element
may appear more than once in the list of n objects.
In other words, it may be that the n objects do not constitute a set in the normal usage of
the word.
General formulas for enumerating combinations and permutations will now be

presented. At this time, we will only list formulas for combinations and permutations without
repetitions or with unlimited repetitions. We will wait until later to use generating functions to
give general techniques for enumerating combinations where other rules govern the selections.
Let P (n, r) denote the number of r-permutations of n elements without repetitions.
Theorem 5.3.1.( Enumerating r-permutations without repetitions).
P(n, r) = n(n-1)……. (n – r + 1) = n! / (n-r)!
Proof. Since there are n distinct objects, the first position of an r-permutation may be filled in
n ways. This done, the second position can be filled in n-1 ways since no repetitions are allowed
and there are n – 1 objects left to choose from. The third can be filled in n-2 ways. By applying
the product rule, we conduct that
P (n, r) = n(n-1)(n-2)……. (n – r + 1).

From the definition of factorials, it follows that
P (n, r) = n! / (n-r)!
Page 72
C
When r = n, this formula becomes

P (n, n) = n! / 0! = n!
When we explicit reference to r is not made, we assume that all the objects are to be arranged;
thus we talk about the permutations of n objects we mean the case r=n. Corollary 1. There are
n! permutations of n distinct objects.
Number of permutations that can be formed from a collection of ‘n’ objects of which n 1 are of
one type, n2 are of second type …….nk are of kth type with n1+n2+……+nk = n. Then the
𝑛!
number of permutations of the of the n objects is 𝑛1!+𝑛2!+⋯+𝑛𝑘!.
Example 1.
There are 3! = 6 permutations of {a, b, c}.
There are 4! = 24 permutations of (a, b, c, d).
The number of 2-permutations {a, b, c, d, e} is P(5, 2) = 5! /(5

- 2)! = 5 x 4 = 20.
The number of 5-letter words using the letters a, b, c, d, and e at most once
is P (5, 5) = 120.
Example 2 There are P (10, 4) = 5,040 4-digit numbers that contain no repeated digits since
each such number is just an arrangement of four of the digits 0, 1, 2, 3 , …., 9 (leading zeroes
are allowed). There are P (26, 3) P(10, 4) license plates formed by 3 distinct letters followed
by 4 distinct digits.
Example3. In how many ways can 7 women and 3 men be arranged in a row ifthe 3
men must always stand next to each other?
There are 3! ways of arranging the 3 men. Since the 3 men always stand next to each other, we
treat them as a single entity, which we denote by X. Then if W1, W2, ….., W7 represents the
women, we next are interested in the number of ways of arranging {X, W1, W2, W3,……., W7}.
There are 8! permutations these 8 objects. Hence there are (3!) (8!) permutations altogether. (of
course, if there has to be a prescribed order of an arrangement on the
3 men then there are only 8! total permutations).
MFCS 47
Page 73
Example 4. In how many ways can the letters of the English alphabet be arranged so that there
are exactly 5 letters between the letters a and b?
There are P (24, 5) ways to arrange the 5 letters between a and b, 2 ways to place a and b, and
then 20! ways to arrange any 7-letter word treated as one unit along with the remaining 19
letters. The total is P (24, 5) (20!) (2).
Note: If instead of arranging objects in a line, we arrange them in a circle, then the number
of permutations decreases.
Example 5. In how many ways can 5 children arrange themselves in a ring?
Solution: Here, the 5 children are not assigned to particular places but are only arranged relative
to one another. Thus, the arrangements (see Figure 2-3) are considered the same if the children
are in the same order clockwise. Hence, the position of child C1 is immaterial and it isonly the
position of the 4 other children relative to C1 that counts. Therefore, keeping C1 fixed in
position, there are 4! arrangements of the remaining children.
Example 6. A certain question paper contains 3 parts A,B,C with 4 questions in part A, 5
questions in part B and 6 questions in part C. it is required to answer 7 questions selecting at
least 2 question from each part. In how many different ways can a student select his seven
question for answering?
Solution: The different possible ways in which a student can make a selection are
(1) 2 questions from part A, 2 from part B and 3 from part C
Selection (1) can be made in C(4,2)xC(5,2)xC(6,3)=1200 ways
Therefore number of possible selection is 1200+900+600=2700
1. How many different strings (sequences) of length 4ncan be formed using the letters of the word FLOWER.
Sol: The given word FLOWER has 6 letters where all of which are distinct.
6! 6!
The required number of strings is P(6,4) = (6−4)! = 2! = 360
2. Find the number of permutations of the letters of the word SUCCESS.

Sol: The given word SUCCESS has 7 letters , of which 3 are S’s, 2 are C’s and
1 each are U and E.
7!
The required number of permutations is 3!2!1!1! = 420
3. Find the number of permutations of the letters of the word MASSASAUGA. In how many
Of these, all four A’s are together? How many of them begin with S?
Sol: The given word MASSASAUGA has 10 letters of which 4 are A’s, 3 are S’s
and 1 each are M,U and G.
10!
Required number of permutations is 4!3!1!1!1! = 25,200
If all A’s are together, we treat all A’s as one single letter. Page 74
7!
Then required number of permutations is 1!3!1!1!1! = 840
If the word begin with letter S, there occurs 9 open positions to fill, where 2 are S’s,
4 are A’s and one each are M,U,G
9!
Then required number of permutations is = 7560
2!4!1!1!1!
4. How many positive integers n can we form using the digits 3,4,4,5,5,6,7 if we want n to exceed 5,000,000
Sol: Here n must be of the form n = x1 x2 x3 x4 x5 x6 x7
Where x1,x2,x3,x4,x5,x6,x7 are the given digits with x1 = 5 or 6 or 7
Suppose we take x1 = 5 then x2,x3,x4,x5,x6,x7 is an arrangement of the remaining 6 digits which contains
two 4’s and one each of 3,5,6,7
6!
The number of such arrangements is 2!1!1!1!1! = 360
Next, Suppose we take x1 = 6 then x2,x3,x4,x5,x6,x7 is an arrangement of the remaining 6 digits which
contains two each of 4 and 5 and one each of 3,7
6!
The number of such arrangements is 2!2!1!1! = 180
Similarly, we take x1 = 7 then x2,x3,x4,x5,x6,x7 is an arrangement of the remaining 6 digits which contains
two each of 4 and 5 and one each of 3,6
6!
The number of such arrangements is 2!2!1!1! = 180
According to Sum Rule,
The number of n’ s of desired type is = 360+180+180 = 720
5. Four different Mathematics books, five different computer science books and two
Different control theory books are to be arranged in a shelf. How many different arrangements are
possible if
a) the books in each particular subject must all be together?
b) Only the Mathematics books must be together?
Sol: a) The Mathematics books can be arranged among themselves in 4! ways, the
Computer science book in 5! ways, the control theory books in 2! ways and the three groups
in 3! Ways
the number of possible arrangements is 4! X 5! X 2! X 3! = 34,560
b) Consider the four mathematics books as one single book. Then we have 8 books which
Can be arranged in 8! Ways. In all of these ways the mathematics books are together.
But the mathematics books can be arranged among themselves in 4! Ways.
Hence, the number of arrangements is 8! X 4! = 967,680
6. Find the value of n such that 2P(n,2)+50 = P(2n,2)
Sol: 2P(n,2) + 50 = P(2n,2)
n! (2n)!
2 X (n−2)! + 50 = (2n−2)!
2n(n−1) + 50 = 2n(2n-1)
n2 = 25
n = 5 or -5
since n cannot be negative, the value of n =5
Page 75
THE PRINCIPLE OF INCLUSION-EXCLUSION:
Consider a finite set S containing p number of elements. Here, the number p is called order,
size or the cardinality of the set S and is denoted by 𝑜(𝑆), or 𝑛(𝑆) or |𝑆|.
For example, if 𝐴 = {1,2,6} and 𝐵 = {𝑎, 𝑏, 𝑐, 𝑑 } then 𝑜(𝐴) = |𝐴| = 3 and 𝑜(𝐵) = |𝑏| = 4
It is obvious that |∅| = 0, and |𝑆| ≥ 1 for every non-empty finite set S. Further for any two
finite sets A and B, if 𝐴 ⊆ 𝐵 then |𝐴| ≤ |𝐵| and if A 𝐴 ⊂ 𝐵 then |𝐴| < |𝐵|
If A is a subset of a finite universal set U, then the number of elements in the complement 𝐴̅(of
A in U) is given by-
|𝐴̅| = |𝑈| − |𝐴| (1)
Suppose we consider the union of two finite sets A and B and wish to determine the number of
elements in 𝐴 ∪ 𝐵. Since, the elements of 𝐴 ∪ 𝐵 consist of all elements which are in A or in B
or both A and B, the number of elements in 𝐴 ∪ 𝐵 is equal to the number of elements in A plus
the number of elements in B minus the number of elements (if any) that are common to A and
B. That is,
|𝐴 ∪ 𝐵 | = |𝐴 | + |𝐵 | − |𝐴 ∩ 𝐵 | (2)
A more explicit (visual) way of obtaining this result is through the use of a Venn Diagram.
𝑃1 𝑃2 𝑃3
Consider the Venn diagram shown above. In this diagram, the set A is made up of two parts 𝑃1 and 𝑃2 and
the set B is made up of two parts 𝑃2 and 𝑃3 , where 𝑃2 = 𝐴 ∩ 𝐵, and 𝐴 ∪ 𝐵 is made up of parts 𝑃1 , 𝑃2 and 𝑃3 .
Therefore,
|𝐴| = Number of elements in 𝑃1 + Number of elements in 𝑃2
= |𝑃1 | + |𝑃2 |
Similarly, |𝐵| = |𝑃2 | + |𝑃3 |, |A ∪ B| = |𝑃1 | + |𝑃2 |+|𝑃3 |
From these, we get

|A ∪ B| = |𝑃1 | + |𝑃2 |+|𝑃3 | = ( |𝑃1 | + |𝑃2 |) + ( |𝑃2 | + |𝑃3 |) − |𝑃2 |
= |𝐴 | + |𝐵 | − |𝐴 ∩ 𝐵 |
Thus, for determining the number of elements in 𝐴 ∪ 𝐵, we first include all elements in A and all elements in
B, and then exclude all elements that are common to A and B.
If U is a finite universal set of which A and B are subsets, then, by virtue of a De’ Morgan Law and the
expression (1) above, we have-
Page 76
|𝐴̅ ∩ 𝐵̅| = |̅̅̅̅̅̅̅
𝐴 ∪ 𝐵 | = |𝑈 | − | 𝐴 ∪ 𝐵 |
With the use of formula (2) above, this becomes
|𝐴̅ ∩ 𝐵̅| = |̅̅̅̅̅̅̅
𝐴 ∪ 𝐵| = |𝑈| − {|𝐴| + |𝐵| − |𝐴 ∩ 𝐵|}
= |𝑈 | − |𝐴 | − |𝐵 | + |𝐴 ∩ 𝐵 | (3)
Expressions (2) and (3) are equivalent to one another. Either of these is referred to as the Addition Principle
(Rule) or the Principle of inclusion-exclusion for two sets.
In the particular case where A and B are disjoint sets so that 𝐴 ∩ 𝐵 = ∅, the addition rule (2) becomes-
|𝐴 ∪ 𝐵| = |𝐴| + |𝐵| − |∅| = |𝐴| + |𝐵| (4)
This is known as the Principle of disjunctive counting for two sets.
Binomial Coefficients: In mathematics, the binomial coefficient is the coefficient of the

n
term xn in the polynomial expansion of the binomial power (1 + x) .
In combinatorics, is interpreted as the number of k-element subsets (the k-combinations) of

an n-element set, that is the number of ways that k things can be "chosen" from a set of n things.
Hence, is often read as "n choose k" and is called the choose function of n and k. The
notation was introduced by Andreas von Ettingshausen in 182, although the numbers were
already known centuries before that (see Pascal's triangle). Alternative notations include C(n, k),
n
n k Ck,
C , , in all of which the C stands for combinations or choices.
For natural numbers (taken to include 0) n and k, the binomial coefficient can be defined as
k n
the coefficient of the monomial X in the expansion of (1 + X) . The same coefficient also
Page 77
occurs (if k ≤ n) in the binomial formula
(valid for any elements x,y of a commutative ring), which explains the name "binomial
coefficient".
Another occurrence of this number is in combinatorics, where it gives the number of

ways, disregarding order, that a k objects can be chosen from among n objects; more
formally, the number of k-element subsets (or k-combinations) of an n-element set. This
number can be seen to be equal to the one of the first definition, independently of any of the
formulas below to compute n
it: if in each of the n factors of the power (1 + X) one temporarily labels the term X with an index i
(running from 1 to n), then each subset of k indices gives after expansion a contribution
k
X , and the coefficient of that monomial in the result will be the number of such subsets. This
shows in particular that is a natural number for any natural numbers n and k. There are many
other combinatorial interpretations of binomial coefficients (counting problems for which
theanswer is given by a binomial coefficient expression), for instance the number of words
formedof n bits (digits 0 or 1) whose sum is k, but most of these are easily seen to be
equivalent to counting k-combinations.
Several methods exist to compute the value of without actually expanding a binomial power
or counting k-combinations.
Method of generating functions for First-Order Recurrence Relations:-
Suppose the recurrence relation to be solved is of the form
an = c an-1 + F(n) for n ≥ 1
or an+1 = c an + 𝜑(𝑛) for n ≥ 0
generating function is f(x) = ∑∞ 𝑛=0 𝑎0 𝑥
𝑛
𝑎 +𝑥𝑔(𝑥)
then we get f(x) = 01−𝑐𝑥 𝑤ℎ𝑒𝑟𝑒 𝑔(𝑥) = ∑∞ 𝑛=0 𝜑 (𝑛 )𝑥
𝑛
Problems:
1. Find a generating function for the recurrence relation a n+1 –an = 3n, n≥0
and a0 = 1. Hence solve the relation.
Sol: Given an+1 – an = 3n
= > an+1 = an + 3n
this is of the form an+1 = c an + 𝜑(𝑛) for n ≥ 0
Here c = 1 , a0=1 and 𝜑(𝑛) = 3n
Page 78
Generating function is f(x) = 01−𝑐𝑥 𝑤ℎ𝑒𝑟𝑒
∞
𝑔(𝑥 ) = ∑𝑛=0 𝜑(𝑛)𝑥 𝑛
= ∑∞ 𝑛 𝑛
𝑛=0 3 𝑥
= ∑∞ 𝑛
𝑛=0(3𝑥) = (1-3x)
-1
1+𝑥(1−3𝑥)−1
f(x) = 1−𝑥
𝑥
1+
1−3𝑥
= 1−𝑥
1−2𝑥
= (1−3𝑥)(1−𝑥)
is the required G.F
1−2𝑥 𝐴 𝐵
Let (1−3𝑥)(1−𝑥)
= +
1−𝑥 1−3𝑥
1-2x = A(1-3x) + B(1-x)
On solving A = B = ½
1−2𝑥 1 1 1
f(x) = (1−3𝑥)(1−𝑥) = 2 (1−𝑥 + )
1−3𝑥
1
= 2
(∑∞ 𝑛
𝑛=0 𝑥 +
∞
∑𝑛=0(3𝑥)𝑛 )
1
= 2 ∑∞ 𝑛
𝑛=0(1 + 3 )𝑥
𝑛
= ∑∞
𝑛=0 𝑎0 𝑥
𝑛
1
Hence required solution is an = 2 (1 + 3𝑛 )
2.Find the generating function foe the recurrence relation a n+1 – an = n2 , n≥0 and a0=1
Hence solve it.
Sol: Given an+1-an = n2 => an+1 = an+n2 , n≥0
this is of the form a n+1 = c an + 𝜑(𝑛) for n ≥ 0
Here c = 1 , a0=1 and 𝜑(𝑛) = n2
Generating function is f(x) = 01−𝑐𝑥 𝑤ℎ𝑒𝑟𝑒
∞
𝑔(𝑥 ) = ∑𝑛=0 𝜑(𝑛)𝑥 𝑛
= ∑∞ 𝑛=0 𝑛 𝑥
2 𝑛
2 2 2 2
i.e., g(x) is the G.F for <n > = 0 ,1 ,2 ,......................
𝑥(1+𝑥)
then g(x) = (1−𝑥)3
1 𝑥 2 (1+𝑥)
f(x) = 1−𝑥 (1 + (1−𝑥)3
)
1−3𝑥+4𝑥 2
f(x) = is the required G.F
(1−𝑥)4
f(x) = (1-3x+4x2) (1-x)-4
= (1-3x+4x2)[ ∑∞ 𝑟
𝑟=0 4 + 𝑟 − 1𝑐𝑟 𝑥 ]
= (1-3x+4x2)[ ∑∞ 𝑟
𝑟=0 3 + 𝑟𝑐𝑟 𝑥 ]
3+𝑟 𝑟 3 + 𝑟 𝑟+1 3 + 𝑟 𝑟+2
= ∑∞𝑟=0( )𝑥 - 3∑∞ 𝑟=0( )𝑥 + 4∑∞
𝑟=0( )𝑥
𝑟 𝑟 𝑟
Since f(x) = ∑∞
𝑛=0 𝑎𝑛 𝑥
𝑛
Coeff. Of xn is
Page 79
𝑛+3 3+𝑛−1 3+𝑛−2
an = ( ) – 3( ) + 4( )
𝑛 𝑛−1 𝑛−2
𝑛+3 𝑛+2 𝑛+1
=( ) -3( ) + 4( )
𝑛 𝑛−1 𝑛−2
(𝑛+3)! (𝑛+2)! (𝑛+1)!
= −3 + 4 (𝑛−2)!3!
𝑛!3! (𝑛−1)!3!
(𝑛+1)
= {(𝑛 + 5𝑛 + 6) − 3(𝑛2 + 2𝑛) + 4(𝑛2 − 𝑛)}
2
6
(𝑛+1)
= (2𝑛2 − 5𝑛 + 6) is the required solution.
6
Method of generating functions for second-order Recurrence relations:-

Consider the second order recurrence relation
an + A an-1 + Ban-2 = F(n) for n ≥2
or an+2 + A an+1 + Ban = 𝜑 (n) for n ≥0
Generating function is f(x) = ∑∞

𝑛=0 𝑎0 𝑥
𝑛
𝑎0 +(𝑎1 +𝑎0 𝐴)𝑥+𝑥 2𝑔(𝑥)
then we get f(x) = 𝑤ℎ𝑒𝑟𝑒 𝑔(𝑥 ) = ∑∞
𝑛=0 𝜑 (𝑛 )𝑥
𝑛
1+𝐴𝑥+𝐵𝑥 2
𝑎0+(𝑎1 +𝑎0 𝐴)𝑥

Note: If 𝜑 (n) = 0 then generating function is f(x) = 1+𝐴𝑥+𝐵𝑥 2
1. Find a generating function for the recurrence relation an+an-1-6an-2 = 0 for n≥2
Given a0 = -1, a1 = 8
Sol: Given an+an-1-6an-2 = 0 for n≥2
an+2+an+1-6an = 0 for n≥0
and a0 = -1, a1 = 8, A =1, B = -6, 𝜑 (n) = 0
𝑎0 +(𝑎1+𝑎0 𝐴)𝑥
then generating function f(x) =
7𝑥−1
f(x) = 1+𝑥−6𝑥 2 is the required generating function.
2. Find a generating function for the recurrence relation a n+2-2an+1+an = 2n for n≥0
Given a0 = 1, a1 = 2 Hence solve it.
Sol: Given an+2-2an+1+an = 2n for n≥0
Here a0=1, a1 =2 , A=-2, B=1 and 𝜑 (n) = 2n
𝑎0 +(𝑎1+𝑎0 𝐴)𝑥+𝑥 2𝑔(𝑥)
then generating function f(x) = 𝑤ℎ𝑒𝑟𝑒
∞
𝑔 (𝑥 ) = ∑ 𝜑 (𝑛 )𝑥 𝑛
𝑛=0
∞ ∞
𝑛 𝑛
𝑔 (𝑥 ) = ∑ 2 𝑥 = ∑(2𝑥)𝑛 = (1 − 2𝑥)−1
𝑛=0 𝑛=0
Page 80
1+ x2 (1−2x)−1 1−2𝑥+𝑥 2 1
Thus, f(x) = = (1−𝑥)2(1−2𝑥) =
(1−𝑥)2 1−2𝑥
f(x) = (1-2x)-1
= ∑∞ 𝑛 ∞
𝑛=0(2𝑥 ) = ∑𝑛=0 2 𝑥
𝑛 𝑛
n
an = 2 is the required solution.
3. Find a generating function for the recurrence relation a n+2-5an+1+6an = 2 for n≥0
Given a0 = 3, a1 = 7 Hence solve it.
Sol: Given an+2-5an+1+6an = 2 for n≥0
Here a0 =3, a1 =7, A =-5, B=6 and 𝜑 (n) = 2
𝑎0 +(𝑎1 +𝑎0 𝐴)𝑥+𝑥 2𝑔(𝑥)
then generating function f(x) = 𝑤ℎ𝑒𝑟𝑒
∞
𝑔 (𝑥 ) = ∑ 𝜑 (𝑛 )𝑥 𝑛
𝑛=0
= ∑∞
𝑛=0 2 𝑥
𝑛
-1
= 2(1-x)
3−8𝑥+2𝑥 2(1−𝑥)−1
Thus f(x) = 1−5𝑥+6𝑥 2
10𝑥 2−11𝑥+3
= (1−2𝑥)(1−3𝑥)(1−𝑥)
is the required generating function.
10𝑥 2 −11𝑥+3 𝐴 𝐵 𝐶
Now, Let (1−2𝑥)(1−3𝑥)(1−𝑥)
= + 1−2𝑥 + 1−3𝑥
1−𝑥
10x2-11x+3 = A(1-2x)(1-3x) + B(1-x)(1-3x) + C(1-x)(1-2x)
On solving A=1, B=0,C=2
10𝑥 2 −11𝑥+3 1 2
f(x) = (1−2𝑥)(1−3𝑥)(1−𝑥) = + 1−3𝑥
1−𝑥
= (1-x)-1 + 2(1-3x)-1
= ∑∞ 𝑛 ∞
𝑛=0 𝑥 + 2 ∑𝑛=0(3𝑥)
𝑛
= ∑∞ 𝑛
𝑛=0(1 + 2. 3 )𝑥
𝑛
n
Hence an = 1+2.3 is the required solution.
4.Find a generating function for the Fibonacci sequence <Fn> and hence obtain an expression
for Fn
Sol: Recurrence relation for Fibonacci sequence is
Fn+2 = Fn+1 + Fn for n≥0 with F0=0, F1=1
 Fn+2 - Fn+1 - Fn = 0 for n≥0
Here F0=0, F1=1, A= -1,B = -1 and 𝜑 (n) = 0
𝑎0 +(𝑎1+𝑎0 𝐴)𝑥
then generating function f(x) = 1+𝐴𝑥+𝐵𝑥 2
Page 81
−𝑥
= 𝑥 2 +𝑥−1
−𝑥 𝐴 𝐵
Now, f(x) = 𝑥 2 +𝑥−1 = + 𝑥−𝛽 𝑤ℎ𝑒𝑟𝑒 𝑥 2 + 𝑥 − 1 = (𝑥 − 𝛼 )(𝑥 − 𝛽)
𝑥−𝛼
1
𝛼 ,𝛽 = (−1 ± √5)
2
-x = A (x- β) + B(x- α)
𝐴 1 𝐵 1
= 𝛽−𝛼 , 𝛽 = 𝛼−𝛽
𝛼
𝐴 𝐵
Now f(x) = − 𝛼−𝑥 − 𝛽−𝑥
𝐴 𝑥 𝐵 𝑥
= − 𝛼 (1 − 𝛼 )−1 − 𝛽 (1 − 𝛽)−1
𝐴 𝑥 𝐵 𝑥
= − 𝛼 ∑ (𝛼 )𝑛 − ∑( )𝑛
𝛽 𝛽
𝐴 𝐵
= − ∑∞
𝑛=0 (𝛼𝑛+1 + 𝛽 𝑛+1 ) 𝑥
𝑛
𝐴 𝐵
Thus Fn = − 𝛼𝑛+1 − 𝛽𝑛+1
1 𝐴 𝐵
= − (𝛼𝛽)𝑛 [ 𝛼 𝛽 𝑛 + 𝛼𝑛]
𝛽
1 1 1 −1+√5 −1−√5
= − (−1)𝑛 [ 𝛽−𝛼 𝛽 𝑛 + 𝛼−𝛽 𝛼 𝑛 ] 𝑠𝑖𝑛𝑐𝑒 𝛼 = ,𝛽 =
2 2
1 1 𝑛 1 𝑛]
= − (−1)𝑛 [−√5 𝛽 + 𝛼 𝛼. 𝛽 = −1, 𝛼 − 𝛽 = √5
√5
1
= (−1)𝑛 [𝛽 𝑛 − 𝛼 𝑛 ]
√5
Second order linear homogeneous Recurrence relations BY CHARACTERESTIC ROOTS

Consider the second order RR
Cnan + Cn-1an-1 + Cn-2an-2 = 0 for n≥2 → (1)
Cn, cn-1, cn-2 are constants with cn ≠ 0.
We want to get the solution of (1) in the form an = ckn
C ≠ 0 & k ≠ 0, put an = ckn in (1)
Cn (Ckn) + Cn-1 Ckn-1 + Cn-2(Ckn-2) = 0
Ckn-2 [Cnk2 + Cn-1k + Cn-2] = 0
Cnk2 + Cn-1k + Cn-2 = 0 → (2)
an = Ckn is the solution of (1) if (2) is true. This quadratic equation (2) in k is called
auxiliary equation or Characteristic equation of RR (1). Then ∃ three cases
1) The two roots k1 & k2 are real and distinct then solution is an = Ak1n + B k2n.
2) The two roots k1 & k2 are real but equal then solution is an = (A + Bn) kn.
3) K1 & k2 are complex conjugates like k1 = p+iq & k2 = p-iq
Page 82
𝑞
An = rn(A cos n𝜃 + B sin n𝜃) where r = √𝑝2 +𝑞 2 & 𝜃 = 𝑡𝑎𝑛−1 (𝑝)
Q1: Solve the recurrence relation an+an-1-6an-2 = 0 for n≥2, ao=-1,a1=8
Sol: General form of second order RR is cnan + cn-1an-1 + cn-2an-2 = 0
∴ Cn= 1, cn-1= 1, cn-2=-6
Now the characteristic equation is k2+k-6=0, on solving it k1=-3, k2=2
(real and distinct).
an=A(-3)n + B(2)n where A & B are constants.
Now using the initial condition find a & B
a0 = A+B =» A+B = -1
a1 = -3A+2B =» -3A+ 2B = 8 then A=-2, B=1
∴ Solution is an = -2(-3)n + (2n)
Q2: Solve an=2(an-1 – an-2) for n≥ 2/a0=1 & a1=2

Sol : an-2an-1+2an-2 = 0 , cn=1, c2= -2, c3 =2
characteristic equation is k2-2k+2 = 0, k = 1±i
∴ General solution an = rn [A cos n𝜃 + B sin n𝜃]
r = √𝑝2 + 𝑞 2 , 𝑝 = 1 𝑞 = 1
𝑞 1 𝜋
= √2 , 𝜃 = 𝑡𝑎𝑛−1 (𝑝) = 𝑡𝑎𝑛−1 (1) =≫ 𝑡𝑎𝑛−1 (1) =≫ 𝜃 = 4
𝑛𝜋 𝑛𝜋
∴ an=(√2)n [A cos 4 + B sin 4 ]
To get A & B using initial conditions, a0=1 =≫ A cos 0 + B sin 0=≫ 𝐴 = 1
𝑛𝜋 𝑛𝜋
a1=2 =≫ (√2)[ A cos 4 + B sin 4 ]
1 1
= √2 [A +B ]
√2 √2
𝑛𝜋 𝑛𝜋
A + B = 2 then B=1 =≫ an = (√2)n [A cos 4 + B sin 4 ]
Q3: Solve Fn+2 = Fn+1 + Fn for n ≥ 0, F0 = 0, F1 = 1
Sol: Fn+2 - Fn+1 – Fn = 0 , cn=1, cn-1 =-1, cn-2 = 1
𝑛 𝑛
1+√5 1−√5
Characteristic equation Fn = A ( ) +B( )
2 2
Using critical values, A+B = 0 → (1) =≫ B = -A

𝑛 𝑛
1+√5 1−√5
1= A( ) +B( )
2 2
𝑛 𝑛
1+√5 1−√5
=A( ) -A( )
2 2
√5 1 −1
1= 2 * A * =≫ A = , B=
2 √5 √5
𝑛 𝑛
1 1+√5 1−√5
Fn = [( ) − ( ) ] is the solution.
√5 2 2
Third and Higher Order Linear Homogeneous Recurrence Relation:
Page 83
Q1. Solve 2an3  an2  2an1  an for n  0 given a0  0, a1  1, a2  2
Sol: Let 2an3  an 2  2an1  an  0 for n  0
We have Cn  2, Cn1  1, Cn2  2, Cn3  1
1
Characteristic equation is 2k 3  k 2  2k  1  0  k1  , k2  1, k3  1
2
The roots are real and distinct.
n
1
 an  A    B 1  C  1
n n
2
To find A, B & C:
a0  0  A  B  C -----------(1)
1
a1  1  A  B  C ---------(2)
2
1
a2  2  A  B  C --------(3)
4
Adding (1) + (2) gives 3A  4B  2 --------(4)
Adding (2) + (3) gives 3A  8B  12 --------(5)
8 5 1
Now, solving (4) & (5) we get A  , B  ,C 
3 2 6
8  1  5 n 1
n
 an     1   1
n
3 2 2 6
This is the required solution.
Q2. Solve the recurrence relation an  an1  8an2  12an3  0 , given a0  1, a1  5, a2  1 .
Sol: Given an  an1  8an2  12an3  0
We have C1  1, C2  1, C3  8, C4  12
Characteristic equation is k 3  k 2  8k  12  0  k1  k2  2, k3  3
The roots are real and repeated.
Hence the solution is an   A  Bn  2   C  3
n n
a0  1  A  C -----------(1)
a1  5  2  A  B   C ---------(2)
a2  1  4  A  2B   9C --------(3)
Solving (1), (2) and (3), we get A  0, B  1, C  1

 an  (n)(2)n  3n is the required solution.
Non-Homogeneous Recurrence Relation of Second and Higher Order:
Recurrence relation is of the form,
cn an  cn1an1  cn2 an2  ...  f (n) where n  k  2 & cn  0 ----------(1)
A general solution for this RR be an  an( h )  an( p ) where an( h ) is the solution of the LHS part.
Page 84
To get an( p ) consider the following cases:
Case (i): Suppose f(n) is a polynomial of degree q & 1 is not a root of the characteristic equation of the homogeneous
part (LHS) of relation in equation (1). In this case an( p ) can be taken as
an( p )  A0  A1n  A2n2  ...  Aq nq . Then A0 , A1 , A2 ,..., Aq should be evaluated.
Case (ii): Suppose f(n) is a polynomial of degree q & 1 is a root of multiplicity m, an( p ) can be taken as
an( p )  n m  A0  A1n  A2 n 2  ...  Aq n q  . Then A0 , A1 , A2 ,..., Aq should be evaluated.
Case (iii): Suppose f (n)   bn where  is constant and b is not a root of the characteristic equation then an( p )  A0b n
Case (iv): Suppose f (n)   bn where  is constant and b is a root of multiplicity m of the characteristic equation
then an( p )  A0 n mb n
Problems:
Q1. Solve the recurrence relation an  4an1  4an2  8 for n  2 and a0  1, a1  2
Sol: Given recurrence relation is an  4an1  4an2  8 ---------(1)
Consider the homogeneous part, an  4an1  4an2  0
We have Cn  1, Cn1  4, Cn2  4
The characteristic equation is k 2  4k  4  0  k1  k2  2 --------(2)
The roots are real and repeated, so the required solution is an( h )  ( A  Bn)(2) n --------(3)
Consider the RHS, it is a constant 8, consider it as a polynomial with degree 0. (ie., n=0) and 1 is not a root for LHS.
By case (i), an( p )  A0 --------(4)
8 8
Put (4) in (1), we get A0  4 A0  4 A0  8  A0  . So we have an( p )  A0 
9 9
Therefore, the general solution of (1) is an  an  an .
(h) ( p)
8
 an  ( A  Bn)(2) n  . -------(5)
9
8 8 1
Now, for finding values of A & B, a0  1  A   A  1   -----------(6)
9 9 9
8 8
a1  2  2  A  B    2 A  2 B  2  ---------(7)
9 9
6
Solving (6) & (7), we get B 
9
1 2  8
Substituting the values of A & B in (5), we have an    n  (2) n  .
9 3  9
Q2. Solve the recurrence relation an2  4an1  3an  200 for n  0 and given a0  3000, a1  3300
Sol: Given an2  4an1  3an  200 for n  0 --------(1)

We have Cn  1, Cn1  4, Cn2  3
Page 85
Characteristic equation is k 2  4k  3  0  k1  1, k2  3
The roots are real and distinct, so we have an( h )  A(1)n  B(3)n
Since 1 is the root of the characteristic equation with multiplicity m=1, we can write
an( p )  n1  A0  , now substituting this in eqn. (1) we get,
(n  2) A0  4(n  1) A0  3nA0  200  2 A0  200  A0  100
Hence, we have an( p )  100n
We know that the general solution is given by an  an( h )  an( p )
 an  A  B  3  100n ---------(2)
n
Also, we have
a0  3000  A  B  B  3000  A -----------(1)
a1  3300  A  B(3)1  100(1) ---------(2)
Solving (1) & (2) we get A  2900, B  100
Hence the particular solution is given by an  2900  100  3  100n
n
Q3. Solve the recurrence relation an  2  10an 1  21an  3n 2  2 , n  0 .

Sol: Given an  2  10an 1  21an  3n 2  2 , n  0 --------(1)
We have Cn  1, Cn1  10, Cn2  21
Characteristic equation is k 2  10k  21  0  k1  3, k2  7
The roots are real and distinct, so we have an( h )  A(3)n  B(7) n -------(2)
Since RHS is a polynomial of degree 2 and 1 is not a root of the characteristic equation, we can write
an( p )  A0  A1n  A2 n 2 ----------(3)
now substituting (3) in eqn. (1) we have,
 A0  A1 (n  2)  A2 (n  2) 2   10  A0  A1 (n  1)  A2 (n  1) 2   21  A0  A1n  A2 n 2   3n 2  2
13 1 1
On solving this equation we get A0  , A1  , A2 
72 3 4
13 1 1
Hence, we have an( p )   n  n2
72 3 4
13 1 1
 an  A  3  B  7    n  n 2 is the required solution.
n n
72 3 4
Q4. Solve an  4an 1  4an 2  5  (2) n
Sol: Given an  4an 1  4an 2  5  (2) n -------------(1)
We have Cn  1, Cn1  4, Cn2  4
Characteristic equation is k 2  4k  4  0  k1  k2  2
The roots are real and repeated, so we have an( h )  ( A  Bn)(2) n -------(2)
Page 86
Here RHS is of the form 5  (2)n   bn where b  2 is a root of the characteristic equation with multiplicity,
m=2. So an( p ) is of the form an( p )  A0 n mb n  an( p )  A0 n 2 (2) n ----------(3)
Now substitute (3) in (1) to get  A0 n 2 (2)n   4  A0 (n  1) 2 (2) n 1   4  A0 (n  2) 2 (2) n  2   5  (2) n
 
(2)n2  A0 n2 (2)2   4  A0 (n  1)2 (2)1   4  A0 (n  2)2   5  (2) n
 4 A0 n 2  8 A0 (n  1) 2  4 A0 (n  2) 2  5  (2) 2
 4 A0 n 2  8 A0 (n 2  2n  1)  4 A0 (n 2  4n  4)  20
5
 8 A0  20  A0 
2
5
Substituting this value in (3), we get an( p )  n 2 (2) n
2
5
 an  ( A  Bn)(2) n  n 2 (2) n is the required solution.
2
Page 87
UNIT-V
Graph Theory
Syllabus
Graph Theory: Representation of Graph, DFS, BFS, Spanning Trees, planar Graphs.
Representation of Graphs:
There are two different sequential representations of a graph. They are
 Adjacency Matrix representation

 Path Matrix representation
Adjacency Matrix Representation

Suppose G is a simple directed graph with m nodes, and suppose the nodes of G have been
ordered and are called v1, v2, . . . , vm. Then the adjacency matrix A = (aij) of the graph G is the
m x m matrix defined as follows:
1, if vi is adjacent to Vj, that is, if there is an edge (Vi, Vj)

aij =
0 otherwise
Suppose G is an undirected graph. Then the adjacency matrix A of G will be a symmetric
matrix, i.e., one in which aij = aji; for every i and j.
Drawbacks
1. It may be difficult to insert and delete nodes in G.
2. If the number of edges is 0(m) or 0(m log2 m), then the matrix A will be sparse, hence a
great deal of space will be wasted.
Path Matrix Representation

Let G be a simple directed graph with m nodes, v1,v2, . . . ,vm. The path matrix of G is the
m-square matrix P = (pij) defined as follows:
Page 88
1 if there is a path from Vi to Vj
Pij =
0 otherwise
Graphs and Multigraphs

A graph G consists of two things:
1.A set V of elements called nodes (or points or vertices)
2.A set E of edges such that each edge e in E is identified with a unique
(unordered) pair [u, v] of nodes in V, denoted by e = [u, v]

Sometimes we indicate the parts of a graph by writing G = (V, E).
Suppose e = [u, v]. Then the nodes u and v are called the endpoints of e, and u and v are said to
be adjacent nodes or neighbors. The degree of a node u, written deg(u), is the number of edges
containing u. If deg(u) = 0 — that is, if u does not belong to any edge—then u is called an
isolated node.
Path and Cycle

A path P of length n from a node u to a node v is defined as a sequence of n + 1 nodes. P =
(v0, v1, v2, . . . , vn) such that u = v0; vi-1 is adjacent to vi for i = 1,2, . . ., n and vn = v.
Types of Path
1. Simple Path
2. Cycle Path
(i) Simple Path

Simple path is a path in which first and last vertex are different (V0 ≠ Vn)
(ii) Cycle Path

Cycle path is a path in which first and last vertex are same (V0 = Vn).It is also called as
Closed path.
Connected Graph
A graph G is said to be connected if there is a path between any two of its nodes.
Page 89
Complete Graph
A graph G is said to be complete if every node u in G is adjacent to every other node v in G.
Tree
A connected graph T without any cycles is called a tree graph or free tree or, simply, a tree.
Labeled or Weighted Graph

If the weight is assigned to each edge of the graph then it is called as Weighted or
Labeled graph.
The definition of a graph may be generalized by permitting the following:
1. Multiple edges: Distinct edges e and e' are called multiple edges if they connect the same
endpoints, that is, if e = [u, v] and e' = [u, v].
2. Loops: An edge e is called a loop if it has identical endpoints, that is, if e = [u, u].
Page 90
3. Finite Graph:A multigraph M is said to be finite if it has a finite number of nodes and
a finite number of edges.
Directed Graphs
A directed graph G, also called a digraph or graph is the same as a multigraph except that each
edge e in G is assigned a direction, or in other words, each edge e is identified with an ordered
pair (u, v) of nodes in G.
Outdegree and Indegree

Indegree: The indegree of a vertex is the number of edges for which v is head
Example
Indegree of 1 = 1
Indegree pf 2 = 2
Outdegree:The outdegree of a node or vertex is the number of edges for which v is tail.
Example
Page 91
Outdegree of 1 =1
Outdegree of 2 =2
Simple Directed Graph
A directed graph G is said to be simple if G has no parallel edges. A simple graph G may
have loops, but it cannot have more than one loop at a given node.
Basic Concepts Isomorphism:
Let G1 and G1 be two graphs and let f be a function from the vertex set of G1 to the vertex set of
G2. Suppose that f is one-to-one and onto & f(v) is adjacent to f(w) in G2 if and only if v is adjacent
to w in G1.
Then we say that the function f is an isomorphism and that the two graphs G1 and G2 are
isomorphic. So two graphs G1 and G2 are isomorphic if there is a one-to-one correspondence
between vertices of G1 and those of G2 with the property that if two vertices of G1 are adjacent
then so are their images in G2. If two graphs are isomorphic then as far as we concerned they are
the same graph though the location of the vertices may be different. To show you how the program
can be used to explore isomorphism draw the graph in figure 4 with the program (first get the null
graph on four vertices and then use the right mouse to add edges).
Page 92
Save this graph as Graph 1 (you need to click Graph then Save). Now get the circuit graph with 4
vertices. It looks like figure 5, and we shall call it C(4).
Example:
The two graphs shown below are isomorphic, despite their different looking drawings.
Graph G Graph H An isomorphism

between G and H
Page 93
ƒ(a) = 1
ƒ(b) = 6
ƒ(c) = 8
ƒ(d) = 3
ƒ(g) = 5
ƒ(h) = 2
ƒ(i) = 4
ƒ(j) = 7
Subgraphs:
A subgraph of a graph G is a graph whose vertex set is a subset of that of G, and whose adjacency
relation is a subset of that of G restricted to this subset. In the other direction, a super graph of a
graph G is a graph of which G is a subgraph. We say a graph G contains another graph H if some
subgraph of G is H or is isomorphic to H.
A subgraph H is a spanning subgraph, or factor, of a graph G if it has the same vertex set as G.
We say H spans G.
A subgraph H of a graph G is said to be induced if, for any pair of vertices x and y of H, xy is an
edge of H if and only if xy is an edge of G. In other words, H is an induced subgraph of G if it
has all the edges that appear in G over the same vertex set. If the vertex set of H is the subset S of
V(G), then H can be written as G[S] and is said to be induced by S.
A graph that does not contain H as an induced subgraph is said to be H-free.
A universal graph in a class K of graphs is a simple graph in which every element in K can be
embedded as a subgraph.
Page 94
K5, a complete graph. If a subgraph looks like this, the vertices in that subgraph form a clique of
size 5.
Multi graphs:
In mathematics, a multigraph or pseudograph is a graph which is permitted to have multiple

edges, (also called "parallel edges"), that is, edges that have the same end nodes. Thus two vertices
may be connected by more than one edge. Formally, a multigraph G is an ordered pair G:=(V, E)
with
 V a set of vertices or nodes,

 E a multiset of unordered pairs of vertices, called edges or lines.
Multigraphs might be used to model the possible flight connections offered by an airline. In this
case the multigraph would be a directed graph with pairs of directed parallel edges connecting
cities to show that it is possible to fly both to and from these locations.
Page 95
A multigraph with multiple edges (red) and a loop (blue). Not all authors allow multigraphs to
have loops.
Euler circuits:
In graph theory, an Eulerian trail is a trail in a graph which visits every edge exactly once.
Similarly, an Eulerian circuit is an Eulerian trail which starts and ends on the same vertex. They
were first discussed by Leonhard Euler while solving the famous Seven Bridges of Königsberg
problem in 1736. Mathematically the problem can be stated like this:
Given the graph on the right, is it possible to construct a path (or a cycle, i.e. a path starting and
ending on the same vertex) which visits each edge exactly once?
Euler proved that a necessary condition for the existence of Eulerian circuits is that all vertices in
the graph have an even degree, and stated without proof that connected graphs with all vertices
of even degree have an Eulerian circuit. The first complete proof of this latter claim was
published in 1873 by Carl Hierholzer.
The term Eulerian graph has two common meanings in graph theory. One meaning is a graph
with an Eulerian circuit, and the other is a graph with every vertex of even degree. These
definitions coincide for connected graphs.
Page 96
For the existence of Eulerian trails it is necessary that no more than two vertices have an odd
degree; this means the Königsberg graph is not Eulerian. If there are no vertices of odd degree, all
Eulerian trails are circuits. If there are exactly two vertices of odd degree, all Eulerian trails start
at one of them and end at the other. Sometimes a graph that has an Eulerian trail but not an Eulerian
circuit is called semi-Eulerian.
An Eulerian trail, Eulerian trail or Euler walk in an undirected graph is a path that uses each
edge exactly once. If such a path exists, the graph is called traversable or semi-Eulerian.
An Eulerian cycle, Eulerian circuit or Euler tour in an undirected graph is a cycle that uses each
edge exactly once. If such a cycle exists, the graph is called unicursal. While such graphs are
Eulerian graphs, not every Eulerian graph possesses a Eulerian cycle.
For directed graphs path has to be replaced with directed path and cycle with directed cycle.
The definition and properties of Eulerian trails, cycles and graphs are valid for multigraphs as well.
This graph is not Eulerian, therefore, a solution does not exist.
Page 97
Every vertex of this graph has an even degree, therefore this is an Eulerian graph. Following the
edges in alphabetical order gives an Eulerian circuit/cycle.
Hamiltonian graphs:
In the mathematical field of graph theory, a Hamiltonian path (or traceable path) is a path in
an undirected graph which visits each vertex exactly once. A Hamiltonian cycle (or Hamiltonian
circuit) is a cycle in an undirected graph which visits each vertex exactly once and also returns to
the starting vertex. Determining whether such paths and cycles exist in graphs is the Hamiltonian
path problem which is NP-complete.
Hamiltonian paths and cycles are named after William Rowan Hamilton who invented the Icosian
game, now also known as Hamilton's puzzle, which involves finding a Hamiltonian cycle in the
edge graph of the dodecahedron. Hamilton solved this problem using the Icosian Calculus, an
algebraic structure based on roots of unity with many similarities to the quaternions (also invented
by Hamilton). This solution does not generalize to arbitrary graphs.
A Hamiltonian path or traceable path is a path that visits each vertex exactly once. A graph that
contains a Hamiltonian path is called a traceable graph. A graph is Hamilton-connected if for
every pair of vertices there is a Hamiltonian path between the two vertices.
A Hamiltonian cycle, Hamiltonian circuit, vertex tour or graph cycle is a cycle that visits each
vertex exactly once (except the vertex which is both the start and end, and so is visited twice). A
graph that contains a Hamiltonian cycle is called a Hamiltonian graph.
Similar notions may be defined for directed graphs, where each edge (arc) of a path or cycle can
only be traced in a single direction (i.e., the vertices are connected with arrows and the edges traced
"tail-to-head").
A Hamiltonian decomposition is an edge decomposition of a graph into Hamiltonian circuits.
Examples
 a complete graph with more than two vertices is Hamiltonian
 every cycle graph is Hamiltonian
 every tournament has an odd number of Hamiltonian paths
 every platonic solid, considered as a graph, is Hamiltonian
Page 98
Planar Graphs:
In graph theory, a planar graph is a graph that can be embedded in the plane, i.e., it can be drawn
on the plane in such a way that its edges intersect only at their endpoints.
A planar graph already drawn in the plane without edge intersections is called a plane graph or
planar embedding of the graph. A plane graph can be defined as a planar graph with a mapping
from every node to a point in 2D space, and from every edge to a plane curve, such that the extreme
points of each curve are the points mapped from its end nodes, and all curves are disjoint except
on their extreme points. Plane graphs can be encoded by combinatorial maps.
It is easily seen that a graph that can be drawn on the plane can be drawn on the sphere as well,
and vice versa.
The equivalence class of topologically equivalent drawings on the sphere is called a planar map.
Although a plane graph has an external or unbounded face, none of the faces of a planar map
have a particular status.
Applications
 Telecommunications – e.g. spanning trees
 Vehicle routing – e.g. planning routes on roads without underpasses
 VLSI – e.g. laying out circuits on computer chip.
 The puzzle game Planarity requires the player to "untangle" a planar graph so that none
of its edges intersect.
Example graphs:
Planar Nonplanar
Graph Graph
Butterfly graph
Page 99
Chromatic Numbers:
In graph theory, graph coloring is a special case of graph labeling; it is an assignment of labels
traditionally called "colors" to elements of a graph subject to certain constraints. In its simplest
form, it is a way of coloring the vertices of a graph such that no two adjacent vertices share the
same color; this is called a vertex coloring. Similarly, an edge coloring assigns a color to each
edge so that no two adjacent edges share the same color, and a face coloring of a planar graph
assigns a color to each face or region so that no two faces that share a boundary have the same
color.
Vertex coloring is the starting point of the subject, and other coloring problems can be transformed
into a vertex version. For example, an edge coloring of a graph is just a vertex coloring of its line
graph, and a face coloring of a planar graph is just a vertex coloring of its planar dual. However,
non-vertex coloring problems are often stated and studied as is. That is partly for perspective, and
partly because some problems are best studied in non-vertex form, as for instance is edge coloring.
Graph Colouring:
Graph coloring enjoys many practical applications as well as theoretical challenges. Beside the
classical types of problems, different limitations can also be set on the graph, or on the way a color
is assigned, or even on the color itself. It has even reached popularity with the general public in
the form of the popular number puzzle Sudoku. Graph coloring is still a very active field of
research.
A proper vertex coloring of the Petersen graph with 3 colors, the minimum number possible.
Page 100
Vertex coloring
When used without any qualification, a coloring of a graph is almost always a proper vertex
coloring, namely a labelling of the graph‘s vertices with colors such that no two vertices sharing
the same edge have the same color. Since a vertex with a loop could never be properly colored, it
is understood that graphs in this context are loop less.
The terminology of using colors for vertex labels goes back to map coloring. Labels like red and
blue are only used when the number of colors is small, and normally it is understood that the labels
are drawn from the integers {1,2,3,...}.
A coloring using at most k colors is called a (proper) k-coloring. The smallest number of colors
needed to color a graph G is called its chromatic number, χ(G). A graph that can be assigned a
(proper) k-coloring is k-colorable, and it is k-chromatic if its chromatic number is exactly k. A
subset of vertices assigned to the same color is called a color class, every such class forms an
independent set. Thus, a k-coloring is the same as a partition of the vertex set into k independent
sets, and the terms k-partite and k-colorable have the same meaning.
This graph can be 3-colored in 12 different ways.

The following table gives the chromatic number for familiar classes of graphs.
graph
complete graph
cycle graph ,
star graph , 2
Page 101
wheel graph ,
Trees and its basic properties:
A graph G is called a tree if it is connected and has no cycles.

A pendant vertex (a vertex has degree one) of a tree is called a leaf.
Theorem 1: Prove that of T is a tree if and only if there is one and only one path between every pair of
vertices.
Proof: Let T be a tree. Then T is a simple graph. Since T is connected there is at least one path between each
pair of vertices. If there are two paths between one pair of vertices, the union of these two paths will make a
cycle in T contradicting the fact that T is a tree. There for in a tree there is one and only one path between
every pair of vertices.
Now conversely assume that in T there is one and only one path between every pair of vertices. Then it is
connected. Since there is one and only one path between every pair of vertices in T, T cannot have a cycle.
Therefore T is a tree.
Theorem 2: A tree with n vertices has n-1 edges.
Proof: Proof is done by induction on number of vertices n. The theorem is true for n=1,n=2 and n=3(we can see this
using graphs). Assume the theorem is true for n=k vertices. Consider a tree T with k+1 vertices. Let e=uv be an edge in
T. now T-e is a disconnected graph(since T is tree). There exist 2 components of T-e , say T1 and T2. T1 contains say
k1 vertices and T2 contains say k2 vertices: k1+k2=k+1. Since T1 and T2 has number of vertices less than or equal to
k by our assumption T1 and T2 contain k1-1 and k2-1 edges respectively. Then T-e contains ( k1+k2)-2 edges, that is (
k+1)-2 edges, k-1 edges. Therefore T contains k-1+e edges, which implies k edges. The theorem is proved for n=k+1
vertices. Therefore the theorem is true for all positive integer n.
Result: Any connected graph with n vertices and n-1 edges is a tree.
Page 102
Problems:
a. S.T the complete graph 𝐾𝑛 is not a tree for n>2.
Solution: Let, 𝑣1 , 𝑣2 , 𝑣3 be any three vertices of 𝐾𝑛 . Since, 𝐾𝑛 is a complete graph there exists an adjacency
between each pair of vertices.
⸫ 𝑣1 is adj 𝑣2 , 𝑣2 will be adj to 𝑣3 and 𝑣1 is adj to 𝑣3 also.

⸫ 𝑣1 𝑣2 𝑣3 creates a cycle inside 𝐾𝑛 implies 𝐾𝑛 is not a cycle.
b. S.T the complete graph bipartite graph 𝐾𝑚,𝑛 is not a tree when 𝑚 ≥ 2
Solution: Let, 𝑣1 , 𝑣2 be any two vertices in the first vertex set & 𝑣1′ , 𝑣2′ be two vertices of second set of the given
complete bipartite graph 𝐾𝑚,𝑛 with 𝑚 ≥ 2. Since, 𝐾𝑚,𝑛 is complete there exists adj from 𝑣1 ⟶ 𝑣1′ & 𝑣2′ ,
𝑣2 ⟶ 𝑣1′ & 𝑣2′
∴ 𝑣1 𝑣1′ 𝑣2 𝑣2′ 𝑣1 is a cycle in 𝐾𝑚,𝑛 which implies 𝐾𝑚,𝑛 is not a tree.
Minimally Connected Graph:

A connected graph is said to be minimally connected if the removal of any one edge from it disconnects the graph.
*All trees are minimally connected.
Theorem: A connected graph is a tree iff it is minimally connected.

Proof: G is a connected graph which is not a tree implies there exists a cycle. From the cycle remove one edge ‘e’
implies G-e is still connected implies G is not minimally connected.
If a graph is not a tree, then it is not minimally connected. By contrapositivity we proved that, if a connected
graph is minimally connected then it is a tree.
Conversely, let G be non-minimally connected graph then ∃ ‘e’ such that G-e is connected.
⸫ e must be a part of a cycle i.e. G contains a cycle i.e. G is not a tree.
By contrapositivity if G is a tree then it is minimally connected.
Rooted Tree:
A directed tree is a directed graph whose underlying graph is a tree. A directed tree T is called a rooted tree T
contains - 1) a unique vertex, called the root (r) whose indegree is zero
2)the indegrees of all other vertices of T are 1
Eg.
A vertex 𝑣 of the rooted tree is said to be at the 𝑘 𝑡ℎ level if the path from 𝑟 → 𝑣 is of length 𝑘.
In the above figure, 𝑣 is at the 3𝑟𝑑 level.
If 𝑣1 &𝑣2 are two vertices: 𝑣1 has a lower level than 𝑣2 and there is path from 𝑣1 to 𝑣2 then we say that 𝑣1 is an
Page 103
ancestor of 𝑣2 and 𝑣2 is a descendant of 𝑣1 . If 𝑣1 &𝑣2 are adjacent i.e. there exists an edge from 𝑣1 → 𝑣2, then 𝑣1
is called parent of 𝑣2 and 𝑣2 is the child of 𝑣1 . Two vertices with a common parent are called siblings. A vertex
whose outdegree zero is called a leaf. A vertex which is not a leaf is called as an internal vertex.
Eg
Page 104
1) 𝑟 is the root.
2) 𝑣1 𝑎𝑛𝑑 𝑣2 are in 1st level.
3) 𝑣3 𝑎𝑛𝑑 𝑣4 are in 2nd level.
4) 𝑣1 is the ancestor of 𝑣3 , 𝑣8 𝑎𝑛𝑑 𝑣9 and 𝑣1 is the parent of 𝑣3 .
5) 𝑣8 𝑎𝑛𝑑 𝑣9 are children of 𝑣3 and are called siblings.
6) 𝑣8 , 𝑣9 , 𝑣6 , 𝑣7 are leaves.
Binary Tree
A rooted tree T is called a binary rooted tree, if every internal vertex is of out degree 1 or 2. That is every vertex has
at most 2 children. It is called a complete binary tree, if each vertex is of out degree 2.
Spanning Trees
Let TG be a connected graph. A subgraph T of G is called a spanning tree of G if
(1) T is a tree
(2) T contains all vertices of G
The edges of the spanning tree are called branches.
Example:
Chords and Co tree

Let T be a spanning tree of G. Then the Edges of G that are not in Tare called chords of G with respect to T. The set
̅ Therefore G = TU𝑇̅
of all chords of G is called a chord set or a co tree of T in G and is represented by 𝑇.
DFS (depth first search) Algorithm to find the spanning tree of a graph:
Let 𝐺 = (𝑉, 𝐸 ) be a connected graph of order ‘n’, with vertices labelled 𝑣1 , 𝑣2 , … . 𝑣𝑛 in some specified order.
Step I: Assign the vertex ‘𝑣1 ’ to the variable 𝑣 and initials T as the tree consisting of just this vertex. (this vertex will
become the root of the tree T)
Step II: Select the smallest subscript k, for 2≤ k ≤ n: {𝑣, 𝑣𝑘 }𝜖 𝐸 & 𝑣𝑘 has not already been selected in T.
If no such subscript is found go to Step III, otherwise:
(i) Attach the edge {𝑣, 𝑣𝑘 } to the tree T

(ii) Assign 𝑣𝑘 to v
(iii) Return to Step II.
Page 105
Step III: If 𝑢 = 𝑣1 , the tree T is the spanning tree.
Step IV: For 𝑣 ≠ 𝑣1 , back track from 𝑣. If 𝑢 is the parent of the vertex assigned to 𝑣 in T, then assign 𝑢 to 𝑣
and return to Step II.
BFS (breadth first search) Algorithm to find the spanning tree of a graph:
Let G = ( V,E) be a connected graph of order n with vertices labelled v1,v2,…..vn.in some specified order. We refer to
an ordered list Q of vertices of G as a queue in G. Vertices are inserted in this list at one end (called the rear of the
queue) and deleted from the list at the other end (called the front of the queue). The BFS algorithm specifies the
following steps.
Step I: Assign the first vertex 𝑣1 and insert this vertex in the queue and initialize T as the tree made up of this one
vertex 𝑣1 .
Step II: Delete v from the front of 𝑄. When 𝑣 is deleted, consider 𝑣𝑘 for each 2 ≤ 𝑘 ≤ 𝑛. If the edge {𝑣, 𝑣𝑘 } ∈ 𝐸 and
𝑣𝑘 has not been visited (considered) previously, attach this edge to T. If we examine all of the vertices
previously visited and obtain no new edge, the tree T (generated to this point) is the desired spanning tree.
Step III: Insert the vertices adjacent to each 𝑣 (from Step II) at the rear of the queue 𝑄, according to the order in
which they are (first) visited. Then return to Step II.
Show that a Hamiltonian path is a spanning tree.
Proof: By definitionn of a Hamiltonian path, we know that a Hamiltonian path in a graph G contains all the vertices of
G. A path is a tree since it doesn’t contain a cycle.
⸫ A Hamiltonian path is a tree contains all the vertices of the given graph G. A Hamiltonian path is a
panning tree.
Weighted Graph: Let G be a graph in which there is a positive number associated with each edge is called a weighted
graph.
Minimal spanning tree: The spanning tree of a weighted graph whose weight is least is called the minimal spanning
tree
Page 106
.
Example:
 *. *
* *. *
(G)
The following are some spanning trees of G
 *. * *. *. *
 *. * * * *
(T1) (T2)
T1 and T2 are spanning trees of G but Since weight of T2 is 13 and it is the minimal spanning tree of G.
Algorithm to find minimal spanning tree:
1. Kruskal’s Algorithm:
Step I: Let G be a connected weighted graph G with n vertices. List edges of G in increasing weights.
Step II: Starting with a smallest weighted edge, proceed sequentially by selecting one edge at a time: no cycle
is formed.
Step III: Stop the process of Step II when ‘n-1 edges are selected as above. These n-1 edges constitute a
minimal spanning tree G.
Page 107
Example:
(G)
Edge: CR. QR. CQ. BP. AB. AP. CP. AC. BQ
Weight: 3. 3. 5. 5. 6. 6. 7. 8. 10
Selection: Yes. Yes No. Yes. Yes. No. Yes. - -
By Kruskal’s Algorithm, the following tree T is the minimal spanning tree of the above graph with weight 24
Page 108
Prims Algorithm to get minimum spanning tree.
Step I: Prepare a nxn table in which weights of all edges are shown. Indicate the wights of non-existing
edges as ∞
Step II: Start from vertex v1and connect it to the nearest neighbor which has a smaller weight in the v1 row
say vk. Now consider edge v1vk and connect this edge to a new vertex which has a minimum value
in the v1 and vk rows. Let this vertex be vm.
Step III: Start from vm and repeat step II. Stop the process when all the n vertices are connected by n-1
Edges.
Page 109

DM

Uploaded by

Copyright:

Available Formats

DM

Uploaded by

Document Information

Copyright

Available Formats

Share this document

Share or Embed Document

Sharing Options

Did you find this document useful?

Is this content inappropriate?

Copyright:

Available Formats

DM

Uploaded by

Copyright:

Available Formats

Units Topics Page

2 Set Theory 34-52

3 Algebraic Structure 53-69

5 Graph Theory 88-109

• Discrete Mathematics is the study of discrete structures which mathematical models

Why it is important for computer science

• ∫50 𝑥 dx=[1/2∗x2]50=52 /2−0=12.5

The true or false of a proposition is called truth value of a proposition

Ex: 1) India capital is new Delhi True

3) 5 is a prime number true

Next consider the following sentences:

4) How beautiful are you?

• A Proposition which cannot be divided further is called an atomic proposition.

• Statements are symbolically represented as A,B,C,..P,Q,R,S… Those are called

Connectivity Symbol Word

Truth table for Negation

• If P and Q are any two propositions then ‘P OR Q’ symbolically written as P V Q .

Truth table for Disjunction

P: I shall go to the game.

Q : I shall watch the game on television.

P V Q: I shall go to the game OR I shall watch the game on television.

IF P and Q are any two propositions then P and Q Symbolically written as P ˄ Q.

Truth table for Conjunction

Q: There are 10 chairs in the room.

P 𝖠 Q: It is raining today AND There are 10 chairs

Conditional (or) Implication (→)

In this conditional statement, P is called the hypothesis or premise or antecedent and Q is

TAUTOLOGY AND CONTRADICTION

Example: The proposition P V ¬P is a tautology.

How to prove given compound proposition is tautology

1)By Constructing truth table

2)By using substitution method

1)Constructing truth table

Show that following function is tautology

P Q R P → Q→R ((P → Q) ˄ (Q→R) P→ R ((P → Q) ˄ (Q→R)) →(P→ R)

• When ever P is false P->Q is true

If P → Q is a conditional statement, then (1).

Q → P is called its converse (2).

¬P → ¬Q is called its inverse

(3). ¬Q → ¬P is called its contrapositive.

• Converse Statement: If it is a holiday, then today is Sunday.

• Inverse Statement: If today is not Sunday, then it is not a holiday.

• Contrapositive Statement- If it is not a holiday, then today is not Sunday.

Converse and inverse are opposite propositions.

Well formed formulas(wff):

Wffs are constructed using the following rules:

1. True and False are wffs.

Note : 1. ⇔ is only symbol, but not connective.

Symbolically written as P⇔ Q or P ≡ Q if P and Q have same truth table.

Example: Prove (P → Q) ⇔ (¬P ∨ Q).

So that (P → Q) ⇔ (¬P ∨ Q).

Identity laws (or)

(a) (i) P ∨ F ⇔ P (ii) P ∨ T ⇔ T

(a) (i) P ∨ ¬P ⇔ T (ii) P ∧ ¬P ⇔ F .

A statement formula A is said to tautologically imply a statement B if and only if A → B is a

Note: ⇒ is not a connective, A ⇒ B is not a statement formula.

A ⇒ B states that A → B is tautology.

Example: Prove that (P → Q) ⇒ (¬Q → ¬P ).

P Q ¬P ¬Q P→Q ¬Q→¬P (P→Q)→(¬Q→¬P)

Hence (P → Q) is Tautological Implications to (¬Q → ¬P ).