http://www.knowledgegate.

in/gate
 Video chapters
• Chapter-1 (Set Theory):
• Chapter-2 (Relations):
• Chapter-3 (POSET & Lattices):
• Chapter-4 (Functions):
• Chapter-5 (Theory of Logics):
• Chapter-6 (Algebraic Structures):
• Chapter-7 (Graphs):
• Chapter-8 (Combinatorics):
http://www.knowledgegate.in/gate
Chapter-1 (Set Theory)

http://www.knowledgegate.in/gate
 What is a SET
• Set are the fundamental discrete structures on which all the discrete structures
are built. Sets are used to group objects together, formally speaking

• “An unordered ,well-defined, collection of distinct objects (Called elements or

members of a set) of same type”. Here the type is defined by the one who is
defining the set. For e.g.

• A = {0,2,4,6, ---}

• B = {1,3,5, ---}

• C= {x| x ∈ Natural number}

http://www.knowledgegate.in/gate
http://www.knowledgegate.in/gate
http://www.knowledgegate.in/gate
• A Set is generally denoted usually by capital letter. The objects of a set
called the elements, or members of the set.
• A set is said to contain its elements.
• Lower case letters are generally used to denote the elements of the
set.

http://www.knowledgegate.in/gate
• x ϵ A, means element x is a member of A

• x ∉ A means x is not a member of A

http://www.knowledgegate.in/gate
• Cardinality of a set — It is the number of elements present in
a Set, denoted like |A|.

• For e.g. A = {0,2,4,6}, |A| = 4

http://www.knowledgegate.in/gate
 Representation of set
• Tabular/Roster representation of set - here a set is defined by
actually listing its members. E.g.

• A = {a, e, i, o, u}

• B = {1, 2, 3, 4}

• C = {---- -4, -2, 0, 2, 4, -----}.

http://www.knowledgegate.in/gate
• Set Builder representations of set- here we specify the property which the
elements of the set must satisfy. E.g.

• A = {x| x is an odd positive number less than 10},

• A = {x | x ϵ English alphabet && x is vowel}

• B = {x | x ϵ N && x <5}

• C = {x | x ϵ Z && x%2 = 0 }

http://www.knowledgegate.in/gate
• Finite set - If there are exactly ‘n’ elements in S where ‘n’ is a
nonnegative integer, we say that S is a finite set.
• i.e. if a set contain specific or finite number of elements is called is
called finite set. For e.g. A = {1,2,3,4}

http://www.knowledgegate.in/gate
• Infinite set – A set contain infinite number of elements is called
infinite set, if the counting of different elements of the set does not
come to an end. For e.g. a set of natural numbers.

http://www.knowledgegate.in/gate
• Null set / empty set - Is the unique set having no elements. its size
or cardinality is zero i.e. |ɸ| = 0. It is denoted by a symbol ɸ or {}. A
set with one element is called singleton set.

http://www.knowledgegate.in/gate
• Universal set – if all the sets under investigation are subsets of a fixed
set, i.e. the set containing all objects under investigation, in Venn
diagram it is represented by a rectangle, and it is denoted by U.

http://www.knowledgegate.in/gate
• Subset of a set – If every element of set A is also an element of set B i.e.
• ∀x(x ∈ A → x ∈ B), then A is called subset of B and is written as A ⊑ B. B is called
the superset of A.
• E.g. A = {1,2,3} B = {1,2,3,4,5}
• Note that to show that A is not a subset of B we need only find one element x ϵ
A with x ∉ B. To show that A ⊑ B, show that if x ϵ A, then x ϵ B.

http://www.knowledgegate.in/gate
• ɸ ⊑ A, Empty Set ɸ is a subset for every set
• A ⊑ U, Every Set is a subset of Universal set U

• A ⊑ A, Every Set is a subset of itself.

http://www.knowledgegate.in/gate
• Proper subset – if A is a subset of B and A ≠ B, then A is said to be a
proper subset of B, i.e. there is at least one element in B which is not
in A. denoted as A ⊂ B.

http://www.knowledgegate.in/gate
• Equality of sets – If two sets A and B have the same element and
therefore every element of A also belong to B and every element of B
also belong to A, then the set A and B are said to be equal and written
as A=B.
• if A ⊑ B and B ⊑ A, then A=B
• ∀x(x ∈ A ↔ x ∈ B)

http://www.knowledgegate.in/gate
• Power set – let A be any set, then the set of all subsets of A is called
power set of A and it is denoted by P(A) or 2A.
• If A= {1,2,3}, then P(A) = {ɸ, {1}, {2}, {3}, {1,2}, {2,3}, {1,3}, {1,2,3}}
• Cardinality of the power set of A is n, |P(A)|= 2n

http://www.knowledgegate.in/gate
 Operation on sets

• Complement of set – Set of all x such that x ∉ A, but x ϵ U.

• Ac = {x | x ∉ A & x ϵ U}

U = {1, 2, 3, 4, 5, 6}

A = {2, 3, 6}

Ac = { }

http://www.knowledgegate.in/gate
• Union of sets – Union of two sets A and B is a set of all those
elements which either belong to A or B or both, it is denoted by A U
B.
• A U B = {x| x ϵ A or x ϵ B}

A = {1, 2, 3, 4}

B = {3, 4, 5, 6}

AUB={ }

|A|+|B|=| A U B | ?

http://www.knowledgegate.in/gate
• Intersection of sets - Intersection of two sets A and B is a set of all
those elements which belong to both A and B, and is denoted by
A ⋂ B.
• A ⋂ B = {x| x ϵ A and x ϵ B}

A = {1, 2, 3, 4}

B = {3, 4, 5, 6}

A⋂B={ }

http://www.knowledgegate.in/gate
• Disjoint sets -- Two sets are said to be disjoint if they do not have a
common element, i.e. no element in A is in B and no element in B is in
A.

• A⋂B=ɸ

http://www.knowledgegate.in/gate
• Set difference – the set difference of two sets A and B, is the set of all
the elements which belongs to A but do not belong to B.
• A – B = {x| x ϵ A and x ∉ B}

A = {1, 2, 3, 4}

B = {3, 4, 5, 6}

A-B={ }

http://www.knowledgegate.in/gate
Symmetric difference – the symmetric difference of two sets A and B is
the set of all the elements that are in A or in B but not in both, denoted
as. A ⨁ B = (A U B) – (A ⋂ B)

A ⨁ B = {x| (x ϵ A and x ∉ B) or (x ϵ B and x ∉ A)}

A ⨁ B = (A – B) U (B – A)

A = {1, 2, 3, 4}

B = {3, 4, 5, 6}

A⨁B={ }
http://www.knowledgegate.in/gate
Idempotent law
• AUA=A
• A⋂A=A

Associative law
• (A U B) U C = A U (B U C)
• (A ⋂ B) ⋂ C= A ⋂ (B ⋂ C)

Commutative law
• AUB=BUA
• A ⋂ B = B ⋂http://www.knowledgegate.in/gate
A
Distributive law
• A U (B ⋂ C) = (A U B) ⋂ (A U C)
• A ⋂ (B U C) = (A ⋂ B) U (A ⋂ C)

De Morgan’s law
• (A U B)C = AC ⋂ BC
• (A ⋂ B)C = AC U BC

Identity law
• AUɸ=A
• A⋂ɸ=ɸ
• AUU=U
• A⋂U=A http://www.knowledgegate.in/gate
Complement law
• A U AC = U
• A ⋂ AC = ɸ
• UC = ɸ
• ɸC = U

Involution law
• ((A)C)C = A

http://www.knowledgegate.in/gate
Chapter-2 (Relations)

http://www.knowledgegate.in/gate
 Cartesian Product
1. Cartesian Product of two sets A and B in the set of all ordered pairs,
whose first member belongs to the first set and second member
belongs to the second set, denoted by A × B.
2. For E.g. if A = {a, b}, B = {1, 2, 3}
3. A×B = { }

a 1
b 2
3
http://www.knowledgegate.in/gate
• It is a kind of maximum relation possible, where every member of the
first set belong to every member of the second set.
• A×B = {(a, b) | a ∈ A and b ∈ B}

http://www.knowledgegate.in/gate
1. In general, commutative law does not hold good A× B != B×A

2. If |A| = m and |B| = n then |A×B| =

http://www.knowledgegate.in/gate
 Relation
• Relation: - Let A and B are sets then every possible subset of ‘A×B’ is called a
relation from A to B.
• If |A| =m and |B| = n then total no of element(pair) will be m*n, every element
will have two choice weather to present or not present in the subset(relation),
therefore the total number of relation possible is ________

http://www.knowledgegate.in/gate
For E.g. if A = {a, b}, B = {1, 2}, A×B = {(a, 1), (a, 2), (b, 1), (b, 2)}
(a , 1) (a , 2) (b , 1) (b , 2)
0 0 0 0
0 0 0 1
0 0 1 0
0 0 1 1
0 1 0 0
0 1 0 1
0 1 1 0
0 1 1 1
1 0 0 0
1 0 0 1
1 0 1 0
1 0 1 1
1 1 0 0
1 1 0 1
1 1 1 0
1 1 http://www.knowledgegate.in/gate
1 1
For E.g. if A = {a, b}, B = {1, 2}
(a , 1) (a , 2) (b , 1) (b , 2)
0 0 0 0 {}
0 0 0 1 {(b, 2)}
0 0 1 0 {(b, 1)}
0 0 1 1 {(b, 1), (b, 2)}
0 1 0 0 {(a, 2)}
0 1 0 1 {(a, 2), (b, 2)}
0 1 1 0 {(a, 2), (b, 1)}
0 1 1 1 {(a, 2), (b, 1), (b, 2)}
1 0 0 0 {(a, 1)}
1 0 0 1 {(a, 1), (b, 2)}
1 0 1 0 {(a, 1), (b, 1)}
1 0 1 1 {(a, 1), (b, 1), (b, 2)}
1 1 0 0 {(a, 1), (a, 2)}
1 1 0 1 {(a, 1), (a, 2), (b, 2)}
1 1 1 0 {(a, 1), (a, 2), (b, 1)}
1 1 http://www.knowledgegate.in/gate
1 1 {(a, 1), (a, 2), (b, 1), (b, 2)}
 Matrix Representation

http://www.knowledgegate.in/gate
• Complement of a relation: - Let R be a relation from A to B,
then the complement of relation will be denoted by R’, RC or R.

• R’ = {(a, b)|(a, b) ϵ A×B, (a, b) ϵ! R}

• R’ = (A×B) – R

http://www.knowledgegate.in/gate
• For E.g. if A×B = {(a, 1), (a, 2), (a, 3), (b, 1), (b, 2), (b, 3)}

• R= {(a, 1), (a, 3), (b, 2)}

• R’ = { }

http://www.knowledgegate.in/gate
R U R’ =

R ⋂ R’ =

http://www.knowledgegate.in/gate
• Inverse of a relation: - Let R be a relation from A to B, then the
inverse of relation will be a relation from B to A, denoted by R-1.

• R-1 = {(b, a) | (a, b) ∈ R}

• A×B = {(a, 1), (a, 2), (a, 3), (b, 1), (b, 2), (b, 3)}

• R = {(a, 1), (a, 3), (b, 2)}

• R-1 = { }

• |R| | R-1 |

http://www.knowledgegate.in/gate
• Diagonal relation: - A relation R on a set A is said to be diagonal
relation if, R is a set of all ordered pair (x, x), for every ∀x ∈ A,
sometimes it is also denoted by ▲A

• R = {(x, x) | ∀ x ∈ A}

1 2 3
1 11
2 22
3 33

http://www.knowledgegate.in/gate
 Types of a Relation

• To further study types of relations, we consider a set A with n

elements, then a cartesian product A×A will have n2 elements(pairs).
Therefore, total number of relation possible is 2n * n

http://www.knowledgegate.in/gate
• Reflexive relation: - A relation R on a set A is said to be reflexive,
• If ∀ x ∈ A
• (x, x) ∈ R

1 2 3
1 11
2 22
3 33

http://www.knowledgegate.in/gate
Q consider a set A = {1,2,3}, find which of the following relations are
reflexive and Irreflexive?

Relation Reflexive Irreflexive

1 A×A
2 ɸ
3 {(1,1), (2,2), (3,3)}
4 {(1,2), (2,3), (1,3)}
5 {(1,1), (1,2), (2,1), (2,2)}
6 {(1,1), (2,2), (3,3), (1,3), (2,1)}
7 {(1,3), (2,1), (2,3), (3,2)}
http://www.knowledgegate.in/gate
For E.g. if A = {a, b}, A×A = {(a, a), (a, b), (b, a), (b, b)}
(a , a) (a , b) (b , a) (b , b)
0 0 0 0 {}
0 0 0 1 {(b, b)}
0 0 1 0 {(b, a)}
0 0 1 1 {(b, a), (b, b)}
0 1 0 0 {(a, b)}
0 1 0 1 {(a, b), (b, b)}
0 1 1 0 {(a, b), (b, a)}
0 1 1 1 {(a, b), (b, a), (b, b)}
1 0 0 0 {(a, a)}
1 0 0 1 {(a, a), (b, b)}
1 0 1 0 {(a, a), (b, a)}
1 0 1 1 {(a, a), (b, a), (b, b)}
1 1 0 0 {(a, a), (a, b)}
1 1 0 1 {(a, a), (a, b), (b, b)}
1 1 1 0 {(a, a), (a, b), (b, a)}
1 1 http://www.knowledgegate.in/gate
1 1 {(a, a), (a, b), (b, a), (b, b)}
For E.g. if A = {a, b}, A×A = {(a, a), (a, b), (b, a), (b, b)}
(a , a) (a , b) (b , a) (b , b)
0 0 0 0
0 0 0 1
0 0 1 0
0 0 1 1
0 1 0 0
0 1 0 1
0 1 1 0
0 1 1 1
1 0 0 0
1 0 0 1 {(a, a), (b, b)}
1 0 1 0
1 0 1 1 {(a, a), (b, a), (b, b)}
1 1 0 0
1 1 0 1 {(a, a), (a, b), (b, b)}
1 1 1 0
1 1 http://www.knowledgegate.in/gate
1 1 {(a, a), (a, b), (b, a), (b, b)}
• Irreflexive relation: - A relation R on a set A is said to be
Irreflexive,
1. If ∀ x ∈ A
2. (x, x) ∉ R

http://www.knowledgegate.in/gate
Q consider a set A = {1,2,3}, find which of the following relations are
reflexive and Irreflexive?

Relation Reflexive Irreflexive

1 A×A Y
2 ɸ N
3 {(1,1), (2,2), (3,3)} Y
4 {(1,2), (2,3), (1,3)} N
5 {(1,1), (1,2), (2,1), (2,2)} N
6 {(1,1), (2,2), (3,3), (1,3), (2,1)} Y
7 {(1,3), (2,1), (2,3), (3,2)} N

http://www.knowledgegate.in/gate
For E.g. if A = {a, b}, A×A = {(a, a), (a, b), (b, a), (b, b)}
(a , a) (a , b) (b , a) (b , b)
0 0 0 0 {}
0 0 0 1 {(b, b)}
0 0 1 0 {(b, a)}
0 0 1 1 {(b, a), (b, b)}
0 1 0 0 {(a, b)}
0 1 0 1 {(a, b), (b, b)}
0 1 1 0 {(a, b), (b, a)}
0 1 1 1 {(a, b), (b, a), (b, b)}
1 0 0 0 {(a, a)}
1 0 0 1 {(a, a), (b, b)}
1 0 1 0 {(a, a), (b, a)}
1 0 1 1 {(a, a), (b, a), (b, b)}
1 1 0 0 {(a, a), (a, b)}
1 1 0 1 {(a, a), (a, b), (b, b)}
1 1 1 0 {(a, a), (a, b), (b, a)}
1 1 http://www.knowledgegate.in/gate
1 1 {(a, a), (a, b), (b, a), (b, b)}
For E.g. if A = {a, b}, A×A = {(a, a), (a, b), (b, a), (b, b)}
(a , a) (a , b) (b , a) (b , b)
0 0 0 0 {}
0 0 0 1
0 0 1 0 {(b, a)}
0 0 1 1
0 1 0 0 {(a, b)}
0 1 0 1
0 1 1 0 {(a, b), (b, a)}
0 1 1 1
1 0 0 0
1 0 0 1
1 0 1 0
1 0 1 1
1 1 0 0
1 1 0 1
1 1 1 0
1 1 http://www.knowledgegate.in/gate
1 1
• Symmetric relation: - A relation R on a set A is said to be Symmetric,
If ∀ a, b ∈ A
(a, b) ∈ R
……………………………
then (b, a) ∈ R
……………………………

http://www.knowledgegate.in/gate
Q consider a set A = {1,2,3}, find which of the following relations are
Symmetric, Anti-Symmetric and Asymmetric?

Relation Symmetric Anti-Symmetric Asymmetric

1 A×A
2 ɸ
3 {(1,1), (2,2), (3,3)}
4 {(1,2), (2,3), (1,3)}
5 {(1,1), (1,2), (2,1), (2,2)}
6 {(1,1), (2,2), (3,3), (1,3), (2,1)}
7 {(1,3), (2,1), (2,3), (3,2)}

http://www.knowledgegate.in/gate
For E.g. if A = {a, b}, A×A = {(a, a), (a, b), (b, a), (b, b)}
(a , a) (a , b) (b , a) (b , b)
0 0 0 0 {}
0 0 0 1 {(b, b)}
0 0 1 0 {(b, a)}
0 0 1 1 {(b, a), (b, b)}
0 1 0 0 {(a, b)}
0 1 0 1 {(a, b), (b, b)}
0 1 1 0 {(a, b), (b, a)}
0 1 1 1 {(a, b), (b, a), (b, b)}
1 0 0 0 {(a, a)}
1 0 0 1 {(a, a), (b, b)}
1 0 1 0 {(a, a), (b, a)}
1 0 1 1 {(a, a), (b, a), (b, b)}
1 1 0 0 {(a, a), (a, b)}
1 1 0 1 {(a, a), (a, b), (b, b)}
1 1 1 0 {(a, a), (a, b), (b, a)}
1 1 http://www.knowledgegate.in/gate
1 1 {(a, a), (a, b), (b, a), (b, b)}
For E.g. if A = {a, b}, A×A = {(a, a), (a, b), (b, a), (b, b)}
(a , a) (a , b) (b , a) (b , b)
0 0 0 0 {}
0 0 0 1 {(b, b)}
0 0 1 0
0 0 1 1
0 1 0 0
0 1 0 1
0 1 1 0 {(a, b), (b, a)}
0 1 1 1 {(a, b), (b, a), (b, b)}
1 0 0 0 {(a, a)}
1 0 0 1 {(a, a), (b, b)}
1 0 1 0
1 0 1 1
1 1 0 0
1 1 0 1
1 1 1 0 {(a, a), (a, b), (b, a)}
1 1 http://www.knowledgegate.in/gate
1 1 {(a, a), (a, b), (b, a), (b, b)}
• Anti-Symmetric relation: - A relation R on a set A with cartesian
product A×A is said to be Anti-Symmetric,
If ∀ a, b ∈ A
(a, b) ∈ R
(b, a) ∈ R
……………………………
a=b
……………………………
Conclusion: Symmetry is not allowed but diagonal pairs are allowed

http://www.knowledgegate.in/gate
 Relation Symmetric Anti-Symmetric Asymmetric
1 A×A Y
2 ɸ Y
3 {(1,1), (2,2), (3,3)} Y
4 {(1,2), (2,3), (1,3)} N
5 {(1,1), (1,2), (2,1), (2,2)} Y
6 {(1,1), (2,2), (3,3), (1,3), (2,1)} N
7 {(1,3), (2,1), (2,3), (3,2)} N

http://www.knowledgegate.in/gate
For E.g. if A = {a, b}, A×A = {(a, a), (a, b), (b, a), (b, b)}
(a , a) (a , b) (b , a) (b , b)
0 0 0 0 {}
0 0 0 1 {(b, b)}
0 0 1 0 {(b, a)}
0 0 1 1 {(b, a), (b, b)}
0 1 0 0 {(a, b)}
0 1 0 1 {(a, b), (b, b)}
0 1 1 0 {(a, b), (b, a)}
0 1 1 1 {(a, b), (b, a), (b, b)}
1 0 0 0 {(a, a)}
1 0 0 1 {(a, a), (b, b)}
1 0 1 0 {(a, a), (b, a)}
1 0 1 1 {(a, a), (b, a), (b, b)}
1 1 0 0 {(a, a), (a, b)}
1 1 0 1 {(a, a), (a, b), (b, b)}
1 1 1 0 {(a, a), (a, b), (b, a)}
1 1 http://www.knowledgegate.in/gate
1 1 {(a, a), (a, b), (b, a), (b, b)}
For E.g. if A = {a, b}, A×A = {(a, a), (a, b), (b, a), (b, b)}
(a , a) (a , b) (b , a) (b , b)
0 0 0 0 {}
0 0 0 1 {(b, b)}
0 0 1 0 {(b, a)}
0 0 1 1 {(b, a), (b, b)}
0 1 0 0 {(a, b)}
0 1 0 1 {(a, b), (b, b)}
0 1 1 0
0 1 1 1
1 0 0 0 {(a, a)}
1 0 0 1 {(a, a), (b, b)}
1 0 1 0 {(a, a), (b, a)}
1 0 1 1 {(a, a), (b, a), (b, b)}
1 1 0 0 {(a, a), (a, b)}
1 1 0 1 {(a, a), (a, b), (b, b)}
1 1 1 0
1 1 http://www.knowledgegate.in/gate
1 1
• Asymmetric relation: - A relation R on a set A is said to be Asymmetric,
If ∀ a, b ∈ A
(a, b) ∈ R
……………………………
(b, a) ∉ R
……………………………
Conclusion: Symmetry is not allowed; even diagonal pairs are not allowed

http://www.knowledgegate.in/gate
 Relation Symmetric Anti-Symmetric Asymmetric
1 A×A Y N
2 ɸ Y Y
3 {(1,1), (2,2), (3,3)} Y Y
4 {(1,2), (2,3), (1,3)} N Y
5 {(1,1), (1,2), (2,1), (2,2)} Y N
6 {(1,1), (2,2), (3,3), (1,3), (2,1)} N Y
7 {(1,3), (2,1), (2,3), (3,2)} N N

http://www.knowledgegate.in/gate
For E.g. if A = {a, b}, A×A = {(a, a), (a, b), (b, a), (b, b)}
(a , a) (a , b) (b , a) (b , b)
0 0 0 0 {}
0 0 0 1 {(b, b)}
0 0 1 0 {(b, a)}
0 0 1 1 {(b, a), (b, b)}
0 1 0 0 {(a, b)}
0 1 0 1 {(a, b), (b, b)}
0 1 1 0 {(a, b), (b, a)}
0 1 1 1 {(a, b), (b, a), (b, b)}
1 0 0 0 {(a, a)}
1 0 0 1 {(a, a), (b, b)}
1 0 1 0 {(a, a), (b, a)}
1 0 1 1 {(a, a), (b, a), (b, b)}
1 1 0 0 {(a, a), (a, b)}
1 1 0 1 {(a, a), (a, b), (b, b)}
1 1 1 0 {(a, a), (a, b), (b, a)}
1 1 http://www.knowledgegate.in/gate
1 1 {(a, a), (a, b), (b, a), (b, b)}
For E.g. if A = {a, b}, A×A = {(a, a), (a, b), (b, a), (b, b)}
(a , a) (a , b) (b , a) (b , b)
0 0 0 0 {}
0 0 0 1
0 0 1 0 {(b, a)}
0 0 1 1
0 1 0 0 {(a, b)}
0 1 0 1
0 1 1 0
0 1 1 1
1 0 0 0
1 0 0 1
1 0 1 0
1 0 1 1
1 1 0 0
1 1 0 1
1 1 1 0
1 1 http://www.knowledgegate.in/gate
1 1
• Transitive relation: - A relation R on a set A is said to be Transitive,
If ∀ a, b, c ∈ A
(a, b) ∈ R
(b, c) ∈ R
……………………………
(a, c) ∈ R
……………………………

http://www.knowledgegate.in/gate
 Relation Transitive
1 A×A
2 ɸ
3 {(1,1), (2,2), (3,3)}
4 {(1,2), (2,3), (1,3)}
5 {(1,1), (1,2), (2,1), (2,2)}
6 {(1,1), (2,2), (3,3), (1,3), (2,1)}
7 {(1,3), (2,1), (2,3), (3,2)}
8 {(1,2)}
9 {(1,3), (2,3)}
10 {(1,2), (1,3)}
11 http://www.knowledgegate.in/gate
{(2,3), (1,2)}
For E.g. if A = {a, b}, A×A = {(a, a), (a, b), (b, a), (b, b)}
(a , a) (a , b) (b , a) (b , b)
0 0 0 0 {}
0 0 0 1 {(b, b)}
0 0 1 0 {(b, a)}
0 0 1 1 {(b, a), (b, b)}
0 1 0 0 {(a, b)}
0 1 0 1 {(a, b), (b, b)}
0 1 1 0 {(a, b), (b, a)}
0 1 1 1 {(a, b), (b, a), (b, b)}
1 0 0 0 {(a, a)}
1 0 0 1 {(a, a), (b, b)}
1 0 1 0 {(a, a), (b, a)}
1 0 1 1 {(a, a), (b, a), (b, b)}
1 1 0 0 {(a, a), (a, b)}
1 1 0 1 {(a, a), (a, b), (b, b)}
1 1 1 0 {(a, a), (a, b), (b, a)}
1 1 http://www.knowledgegate.in/gate
1 1 {(a, a), (a, b), (b, a), (b, b)}
For E.g. if A = {a, b}, A×A = {(a, a), (a, b), (b, a), (b, b)}
(a , a) (a , b) (b , a) (b , b)
0 0 0 0 {}
0 0 0 1 {(b, b)}
0 0 1 0 {(b, a)}
0 0 1 1 {(b, a), (b, b)}
0 1 0 0 {(a, b)}
0 1 0 1 {(a, b), (b, b)}
0 1 1 0
0 1 1 1
1 0 0 0 {(a, a)}
1 0 0 1 {(a, a), (b, b)}
1 0 1 0 {(a, a), (b, a)}
1 0 1 1 {(a, a), (b, a), (b, b)}
1 1 0 0 {(a, a), (a, b)}
1 1 0 1 {(a, a), (a, b), (b, b)}
1 1 1 0
1 1 http://www.knowledgegate.in/gate
1 1 {(a, a), (a, b), (b, a), (b, b)}
• Equivalence Relation: - A relation R on a set A with cartesian product
A×A is said to be Equivalence, if it is

1. Reflexive
2. Symmetric
3. Transitive

http://www.knowledgegate.in/gate
• If two relations R1 and R2 are Equivalence then their union
need not to be equivalence but intersection will also be
Equivalence.

http://www.knowledgegate.in/gate
R1 : (a, b) iff (a + b) is even over the set of integers

http://www.knowledgegate.in/gate
R2 : (a, b) iff (a + b) is odd over the set of integers

http://www.knowledgegate.in/gate
R3 : (a, b) iff a x b > 0 over the set of non-zero rational numbers

http://www.knowledgegate.in/gate
R4 : (a, b) iff |a – b| ≤ 2 over the set of natural numbers

http://www.knowledgegate.in/gate
• Partial Order Relation: - A relation R on a set A with cartesian product
A×A is said to be partial order, if it is
1. Reflexive
2. Anti - Symmetric
3. Transitive

http://www.knowledgegate.in/gate
• Partial ordering set (Poset): - a set A with partial ordering relation R defined on
A is called a POSET and is denoted by [A, R]

• For e.g. [A, /], [A, <=], [P(S), ⊑]

http://www.knowledgegate.in/gate
Q let R1 be a relation from A = {1,3,5,7} to B = {2,4,6,8} and R2 be another relation
from B to C = {1,2,3,4} as defined below
(i) an element x in A is related to an element y in B if x + y is divisible by 3
(ii) an element x in B is related to an element y in C if x + y is even but not divisible
by 3. Which is the composite relation R1R2 from A to C?
a) {(1,2), (1,4), (3,3), (5,4), (7,3)} b) {(1,2), (1,3), (3,2), (5,2), (7,3)}
c) {(1,2), (3,2), (3,4), (5,4), (7,2)} d) {(3,2), (3,4), (5,1), (5,3), (7,1)}

http://www.knowledgegate.in/gate
Chapter-3 (POSET & Lattices)

http://www.knowledgegate.in/gate
 Conversion of POSET into a Hasse Diagram

• If we want to study Partial order relation further then it will be better

to convert it into more convenient notation so that it can be studied
easily.
• This graphical representation is called Hasse Diagram

http://www.knowledgegate.in/gate
• In order theory, a Hasse diagram is a type of mathematical diagram used to
represent a finite partially ordered set, in the form of a drawing of its transitive
reduction. The diagrams are named after Helmut Hasse (1898–1979)

http://www.knowledgegate.in/gate
Steps to convert partial Q Consider a Partial order relation and
order relation into hasse
diagram convert it into hasse diagram?
1- Draw a vertex for each R = {(1,1), (1,2), (1,4), (1,8), (2,2), (2,4), (2,8),
element in the Set
(4,4), (4,8), (8,8)}
2- If (a, b) ϵ R then draw an
edge from a to b

3- Remove all Reflexive and

Transitive edges

4- Remove the direction of

edges and arrange them in
the increasing order of
heights.
http://www.knowledgegate.in/gate
Q Consider a Partial order relation and convert it into hasse diagram?
R = {(1,1), (1,2), (1,3), (1,6), (2,2), (2,6), (3,3), (3,6), (6,6)}

http://www.knowledgegate.in/gate
Q Let A = (1, 2, 3, 4, 6, 8, 9, 12, 18, 24) be ordered set with
relation "x divides y". Draw its Hasse diagram?

http://www.knowledgegate.in/gate
Q Draw the Hasse diagram of (A, ≤), where A = (3, 4, 12, 24, 48, 72)
and relation ≤ be such that a ≤ b if a divides b.

http://www.knowledgegate.in/gate
Q Let A = (2, 3, 6, 12, 24, 36) and relation '≤' be such that x≤y if x
divides y. Draw the Hasse diagram of (A, ≤)?

http://www.knowledgegate.in/gate
Lattice :- A hasse diagram/Partial order relation is called Lattice if their
exist a Join and Meet for every pair of element. Or A hasse
diagram/Partial order relation is called Lattice if it is both Join Semi
Lattice and Meet Semi Lattice.

http://www.knowledgegate.in/gate
http://www.knowledgegate.in/gate
http://www.knowledgegate.in/gate
http://www.knowledgegate.in/gate
http://www.knowledgegate.in/gate
http://www.knowledgegate.in/gate
http://www.knowledgegate.in/gate
http://www.knowledgegate.in/gate
http://www.knowledgegate.in/gate
http://www.knowledgegate.in/gate
http://www.knowledgegate.in/gate
http://www.knowledgegate.in/gate
http://www.knowledgegate.in/gate
http://www.knowledgegate.in/gate
Idempotent law
• A∨A=A
• A∧A=A

Associative law
• (A ∨ B) ∨ C = A ∨ (B ∨ C)
• (A ∧ B) ∧ C= A ∧ (B ∧ C)

Commutative law
• A∨B=B∨A
• A ∧ B = B ∧http://www.knowledgegate.in/gate
A
Distributive law
• A ∨ (B ∧ C) = (A ∨ B) ∧ (A ∨ C)
• A ∧ (B ∨ C) = (A ∧ B) ∨ (A ∧ C)

De Morgan’s law
• (A ∨ B)C = AC ∧ BC
• (A ∧ B)C = AC ∨ BC
Identity law
• A∨ɸ=A
• A∧ɸ=ɸ
• A∨U=U
• A∧U=A http://www.knowledgegate.in/gate
Complement law
• A ∨ AC = U
• A ∧ AC = ɸ
• UC = ɸ
• ɸC = U

Involution law
• ((A)C)C = A

http://www.knowledgegate.in/gate
 Boolean algebra
• Unbounded Lattice :- If a lattice has
infinite of elements then it is called
Unbounded Lattice.

http://www.knowledgegate.in/gate
• Bounded Lattice :- If a lattice has finite number of elements
then it is called Bounded lattice, there will be upper and lower
bound in lattice.

http://www.knowledgegate.in/gate
• Complement of an element in a Lattice :- If two elements a
and ac, are complement of each other, then the following
equations must always holds good.
a ∨ ac = Upper bound of lattice
a ∧ ac = Lower bound of lattice

http://www.knowledgegate.in/gate
• Distributive Lattice :- A lattice is said to be distributed lattice. if for
every element their exist at most one completemt(zero or one).

http://www.knowledgegate.in/gate
• Complement Lattice :- A Lattice is said to be Complement lattice. if
for every element their exist at least one complement(one or more).

http://www.knowledgegate.in/gate
• Boolean Algebra :- A Lattice is said to be Boolean Algebra, if for every
element their exist exactly one complement. Or if a lattice is both
complemented and distributed then it is called Boolean Algebra.

http://www.knowledgegate.in/gate
http://www.knowledgegate.in/gate
http://www.knowledgegate.in/gate
http://www.knowledgegate.in/gate
http://www.knowledgegate.in/gate
http://www.knowledgegate.in/gate
http://www.knowledgegate.in/gate
Q Find which of the following is a lattice and Boolean Algebra?
(1)[D10, /] (2) [D12, /]

(3) [D30, /] (4) [D45, /]

(5) [D64, /] (6) [D81, /]

(7) [D91, /] (8) [D110, /]

http://www.knowledgegate.in/gate
Chapter-4 (Functions)

http://www.knowledgegate.in/gate
 Function
• Functions are widely used in science, and in most fields of mathematics. It has been said that
functions are "the central objects of investigation" in most fields of mathematics.

• Let X = {1, 2, 3, 4, 5} and Y = {2, 3, 4, 5, 6, 7} and R ⊑ X * Y. Now this is a valid relation but not a
function, because there is a element which is not participating in the relationship secondly 5 is
relating with more than one element.

http://www.knowledgegate.in/gate
 Function
• In mathematics, a function is a relation between sets that associates to every
element of a first set exactly one element of the second set.
• A relation ‘f’ from a set ‘A’ to a Set ‘B’ is called a function, if each element of A is
mapped with a unique element on B.
• f: AàB

• Range of fun ⊑ B
• Range of f = { y | y ϵ B and (x, y) ϵ f}

http://www.knowledgegate.in/gate
• If |A| = m and |B|= n, then number of functions
possible from A to B = nm

http://www.knowledgegate.in/gate
 Function composition
• In mathematics, function composition is an operation that takes two functions f and g and
produces a function h such that h(x) = g(f(x)).

• In this operation, the function g is applied to the result of applying the function f to x. That is,
the functions f: X → Y and g: Y → Z are composed to yield a function that
maps x in X to g(f(x)) in Z.

http://www.knowledgegate.in/gate
• fog(x) = f(g(x))
• gof(x) = g(f(x))

• Composition of functions on a finite set: If f = {(1, 3), (2, 1), (3, 4), (4, 6)}, and g = {(1, 5), (2, 3),
(3, 4), (4, 1), (5, 3), (6, 2)}, then g ∘ f = {(1, 4), (2, 5), (3, 1), (4, 2)}.
• The composition of functions is always associative—a property inherited from the
composition of relations. That is, if f, g, and h are three functions with suitably chosen
domains and codomains, then f ∘ (g ∘ h) = (f ∘ g) ∘ h

http://www.knowledgegate.in/gate
 One-to-One (Injective Function)

• An injective function (also known as injection, or one-to-one function) is

a function that maps distinct elements of its domain to distinct elements of
its codomain. In other words, every element of the function's codomain is
the image of at most one element of its domain.

http://www.knowledgegate.in/gate
 One-to-One (Injective Function)
• A function F: AàB is said to be one-to-one function if every element of A has
distinct image in B
• If A and B are finite set, then one-to-one from AàB is possible
• if |A| <= |B|

http://www.knowledgegate.in/gate
• No of function possible = npm = P (n, m)
• If |A| = |B| = n, then no of functions possible is n!

http://www.knowledgegate.in/gate
 Onto (Surjective Function)
• A function f from a set X to a set Y is surjective (also known as onto, or
a surjection), if for every element y in the co-domain Y of f, there is at least one
element x in the domain X of f such that f(x) = y. It is not required
that x be unique; the function f may map one or more elements of X to the same
element of Y.

http://www.knowledgegate.in/gate
 Onto (Surjective Function)
• A function f: A à B is said to be onto if and only if every element of B is mapped
by at least one element of A.
• Range of f = B

• If A and B are finite sets, then onto function from AàB is possible, |B|<=|A|
• If |A| = |B|, then every onto function from A to B is also one-to-one function.

http://www.knowledgegate.in/gate
No of onto function possible from A to B
= nm – nc1(n-1)m + nc2(n-2)m - nc3(n-3)m +---------+ (-1)n nc n-1 1m

http://www.knowledgegate.in/gate
 Bijective Function
• In mathematics, a bijection, bijective function, one-to-one correspondence,
or invertible function, is a function between the elements of two sets, where
each element of one set is paired with exactly one element of the other set, and
each element of the other set is paired with exactly one element of the first set.
There are no unpaired elements.

http://www.knowledgegate.in/gate
• A function f: AàB is said to be bijection if f is one-to-one and onto.
• Bijection from A and B is possible, if |A| |B|
• No of Bijection from A to B = ?

http://www.knowledgegate.in/gate
• A function f: AàB is said to be bijection if f is one-to-one and onto.
• Bijection from A and B is possible, if |A| = |B|
• No of Bijection from A to B = n!

http://www.knowledgegate.in/gate
 Inverse of a function
• In mathematics, an inverse function (or anti-function) is a function that "reverses" another
function
• If the function f applied to an input x gives a result of y, then applying its inverse function f-1
to y gives the result x, and vice versa.
• f(x) = y then f-1 (y) = x.

http://www.knowledgegate.in/gate
• Inverse of a function f: AàB exists, iff f: AàB is a bijection.
http://www.knowledgegate.in/gate
• f(x) = 5x – 7
• f-1(y) = (y + 7)/5

http://www.knowledgegate.in/gate
Q Let R denote the set of real numbers. Let f: R×R→R×R be a bijective function
defined by f (x, y) = (x + y, x− y). The inverse function of f is given by
a) f−1(x, y)=(1 / (x + y), 1 / (x − y))

b) f−1(x, y)=(x − y, x + y)

c) f−1(x, y)=( (x + y) / 2, (x – y) / 2)

d) f−1(x, y)=[2(x − y),2(x + y)]

http://www.knowledgegate.in/gate
Chapter-5 (Theory of Logics)

http://www.knowledgegate.in/gate
• A proposition is a declarative sentence (that is, a sentence that declares a fact) that is either
true or false, but not both.
1. Delhi is the capital of USA

2. How are you doing

3. 5<= 11

4. Temperature is less than 10 C

5. It is cold today

6. Read this carefully

7. X + y = z

http://www.knowledgegate.in/gate
• Premises(proposition) is always considered to be true. Premises is a statement that provides
reason or support for the conclusion(proposition).
• If a set of Premises(P) yield another proposition Q(Conclusion), then it is called an Argument.
• An argument is said to be valid if the conclusion Q can be derived from the premises by
applying the rules of inference.

{P1, P2, P3..., PN} |- Q P1 {P1 ∧ P2 ∧ P3 ∧.... ∧ PN} |- Q

P2
P3
.
.
.
PN
……
Q
…….

http://www.knowledgegate.in/gate
 Types of proposition
1. We use letters to denote propositional variables (or statement variables), that is, variables
that represent propositions, just as letters are used to denote numerical variables.
2. The conventional letters used for propositional variables are p, q, r, s. The truth value of a
proposition is true, denoted by T, if it is a true proposition, and the truth value of a
proposition is false, denoted by F, if it is a false proposition.
3. Many mathematical statements are constructed by combining one or more propositions.
New propositions, called compound propositions, are formed from existing propositions
using logical operators.

http://www.knowledgegate.in/gate
 Operators / Connectives
1. Negation: - let p be a proposition, then negation of p new proposition, denoted
by ¬p, is the statement “it is not the case that p”.

2. The truth value of the negation of p, ¬p, is the opposite of the truth value of p.
e.g. ¬“Michael’s PC runs Linux” = “It is not the case that Michael’s PC runs
Linux.” = “Michael’s PC does not run Linux.”

Negation
P ¬P
F
T
http://www.knowledgegate.in/gate
 Conjunction
• Let p and q be propositions. The conjunction of p and q, denoted by p
∧ q, is the proposition “p and q.”

• The conjunction p ∧ q is true when both p and q are true and is false
otherwise.
Conjunction
p q p∧q
F F
F T
T F
T T
http://www.knowledgegate.in/gate
Q consider the following arguments and find which of them are valid?
1 2 3 4
P1 (p ∧ q) P1 P P1 ¬(p ∧ q) P1 ¬ (p ∧ q)
Q p Q p∧q P2 P P2 q
Q ¬q Q ¬p

http://www.knowledgegate.in/gate
 Disjunction
• Let p and q be propositions. The disjunction of p and q, denoted by p ∨ q, is the
proposition. “p or q.” The disjunction p ∨ q is false when both p and q are false
and is true otherwise.

Disjunction
p q p∨q
F F
F T
T F
T T
http://www.knowledgegate.in/gate
Q consider the following arguments and find which of them are valid?
1 2 5 6
P1 (p ∧ q) P1 p∨q P1 (p ∨ q) P1 (p ∨ q)
Q p∨q Q (p ∧ q) P2 ¬p P2 ¬q
Q q Q p

http://www.knowledgegate.in/gate
 Implication
1. Let p and q be propositions. The conditional statement p → q is the proposition “if p, then q”.
The conditional statement p → q is false when p is true and q is false, and true otherwise.
2. In conditional statement p → q, p is called the hypothesis (or antecedent or premise) and q is
called the conclusion.
3. The statement p → q is called a conditional statement because p → q asserts that q is true on
the condition that p holds.

Implication
p q p→q
F F
F T
T F
T T
http://www.knowledgegate.in/gate
p q P→q ¬p ¬q ¬P → ¬q q→p ¬q → ¬p ¬p ∨ q
F F
F T
T F
T T

http://www.knowledgegate.in/gate
1. p → q implication

2. q → p converse

3. ¬p → ¬q inverse

4. ¬q → ¬p contra positive

http://www.knowledgegate.in/gate
1. p → q = ¬q → ¬p

2. p → q will be true if either p is false or q is true, p → q = ¬p ∨ q

http://www.knowledgegate.in/gate
Q Express Converse, Inverse and Contrapositive of the following
Statement "If x + 5 = 8 then x = 3"

http://www.knowledgegate.in/gate
Q consider the following arguments and find which of them are valid?
Modus Ponens Modus Tollens 1 2
P1 p→q P1 p→q P1 ¬p P1 q
P2 P P2 ¬Q Q p→q Q p→q
Q Q Q ¬p

http://www.knowledgegate.in/gate
 Bi-conditional
• Let p and q be propositions. The biconditional statement p ↔ q is the proposition.
• “ p if and only q”.
• The biconditional statement p ↔ q is true when p and q have the same values, and false
otherwise. Biconditional statements are also called bi-implications.
• “p is necessary and sufficient for q”
• “if p then q, and conversely”
• “p iff q.”
• p←→ q = (p → q ) ∧ ( q → p)
Bi-conditional
p q P↔q
F F
F T
T F
T T
http://www.knowledgegate.in/gate
Q Construct the truth table for the following statement ?
(P à¬Q) à ¬P

http://www.knowledgegate.in/gate
Q The statement (¬p) ⟹ (¬q) is logically equivalent to which of the
statement below?
1) p ⟹ q 2) q ⟹ p 3) (¬q) ∨ (p) 4) (¬p) ∨ q

http://www.knowledgegate.in/gate
 Type of cases
• Tautology/valid: - A propositional function which is always having
truth in the last column, is called tautology. E.g. p ∨ ¬ p

p ¬p p∨¬p
F T
T F

http://www.knowledgegate.in/gate
• Contradiction/ Unsatisfiable: - A propositional function which is always
having false in the last column, is called Contradiction. E.g. p ∧ ¬ p

p ¬p p∧¬p
F T
T F

http://www.knowledgegate.in/gate
• Contingency: - A propositional function which is neither a tautology
nor a contradiction, is called Contingency. E.g. p ∨ q

p q p∨q
F F
F T
T F
T T

http://www.knowledgegate.in/gate
• Satisfiable: - A propositional function which is not contradiction is
satisfiable. i.e. it must have at least one truth value in the final
column e.g. p ∨ q

http://www.knowledgegate.in/gate
• Functionality Complete Set: - A set of connectives is said to be
functionally complete if it is able to write any propositional function.
• {∧, ¬}
• {∨, ¬}

http://www.knowledgegate.in/gate
Q consider the following argument
I1: if today is Gandhi ji’s birthday, then today is oct 2nd

I2: today is oct 2nd

C: today is Gandhi ji’s birthday

http://www.knowledgegate.in/gate
Q consider the following argument
I1: if Canada is a country, then London is a city

I2: London is not a city

C: Canada is not a country

http://www.knowledgegate.in/gate
Q Consider the following logical inferences.
I1: If it rains then the cricket match will not be played.
The cricket match was played.
Inference: There was no rain.

I2: If it rains then the cricket match will not be played.

It did not rain.
Inference: The cricket match was played.

http://www.knowledgegate.in/gate
Q Consider the following propositional statements:
P1 : ((A ∧ B) → C)) ≡ ((A → C) ∧ (B → C))

http://www.knowledgegate.in/gate
Q Consider the following propositional statements:
P2 : ((A ∨ B) → C)) ≡ ((A → C) ¬ (B → C))

http://www.knowledgegate.in/gate
Q Use rules of inference to justify that the three hypotheses
i. "If it does not rain or if it is not foggy, then the sailing race will be held and
the lifesaving demonstration will go on."
ii. "If the sailing race is held, then the trophy will be awarded."
iii. "The trophy was not awarded." imply the conclusion
iv. "It rained."

http://www.knowledgegate.in/gate
Show that ((p ∨ q) ∧ ¬(¬p ∧ (¬q ∨ ¬r))) ∨ (¬p ∧ ¬q) ∨ (¬p ∨ r)
is tautology without using truth table.

http://www.knowledgegate.in/gate
Q "If the labour market is perfect then the wages of all
persons in a particular employment will be equal. But it is always the case
that wages for such persons are not equal therefore the labour market is not
perfect". Test the validity of this argument using truth table.

http://www.knowledgegate.in/gate
Q Prove the validity of the following argument.
If Mary runs for office, she will be elected. If Mary attends the meeting, she will run for
office. Either Mary will attend the meeting or she will go to India. But Mary cannot go to
India."Thus Mary will be elected".

http://www.knowledgegate.in/gate
Q Prove the validity of the following argument.
If Mary runs for office, she will be elected. If Mary attends the meeting, she will run for
office. Either Mary will attend the meeting or she will go to India. But Mary cannot go to
India."Thus Mary will be elected".

http://www.knowledgegate.in/gate
Q Prove the validity of the following argument "if the races are fixed so the casinos are
cooked, then the tourist trade will decline. If the tourist trade decreases, then the police
will be happy. The police force is never happy. Therefore, the races are not fixed."

http://www.knowledgegate.in/gate
Q Prove the validity of the following argument "If I get the job and work hard, then I will
get promoted. If I get promoted, then I will be happy. I will not be happy. Therefore, either
I will not get the job, or I will not work hard."

http://www.knowledgegate.in/gate
• Canonical SOP form: - In a sum of product form expression, if each AND term (product term)
consists all the literals(variables) appearing either in complements or uncomplemented form.
E.g. a’bc + ab’c’ + abc. Then the form is said to be canonical SOP. Here we have Principle
Disjunction Normal Form

• Canonical POS form: - In a product of sum form expression, if each OR term (sum term)
consists all the literals(variables) appearing either in complements or uncomplemented form.
E.g. (a’ + b + c). (a + b’ + c’). (a + b + c). Then the form is said to be Canonical POS form. Here
we have Principle Conjunctive Normal Form.

http://www.knowledgegate.in/gate
 First order Predicate Logic
• Sometime propositional logic cannot derive any meaningful information even though, we as
human can understand that argument is meaningful or not.

• P1: Every Indian like cricket

• P2: Sunny is an Indian
• Q: Sunny Likes cricket

• The reason propositional logic fails here because using only inference system we can not
conclude Q from P1 and P2.

http://www.knowledgegate.in/gate
• In first order logic we understand, a new approach of subject and predicate to extract more
information from a statement
• 1 is a natural number (1 is subject, natural number is predicate)

• we can write FOPL (short hand notation) for this as NatNo(1) = 1 is natural number

• Similarly, we can understand the meaning of NatNo(2) as 2 is a natural number

• NatNo(x): x is a natural number

http://www.knowledgegate.in/gate
• Sometime subject is not a single element but representing the entire group.

• Every Indian like Cricket.

• We can have a propositional function Cricket(x): x likes Cricket.

• We can fix domain of discussion or universe of discourse as, x is an Indian.

http://www.knowledgegate.in/gate
• If i say four Indian are there I1, I2, I3, I4
• I1 likes cricket ∧ I2 likes cricket ∧ I3 likes cricket ∧ I4 likes cricket

• Cricket(I1) ∧ Cricket(I2) ∧ Cricket(I3) ∧ Cricket(I4)

• But problem with this notation is as there is 130+ corers Indian this formula will become very
long and in some case we actually do not know how many subjects are there in the universe
of discourse. so, we again need a short hand formula.

• ∀x Cricket(x), if we confine x to be Indian then it means every x like cricket.

http://www.knowledgegate.in/gate
• Universal quantifiers: - The universal quantification of a propositional function is the
proposition that asserts

• P(x) is true for all values of x in the universe of discourse.

• The universe of discourse specifies the possible value of x.

• ∀x P(x), i.e. for all value of a P(x) is true

http://www.knowledgegate.in/gate
• Let try some other statement ‘Some Indian like samosa’

• if i say four Indian are there I1, I2, I3, I4

• I1 like samosa ∨ I2 like samosa ∨ I3 like samosa ∨ I4 like samosa

• Samosa(I1) ∨ Samosa(I2) ∨ Samosa(I3) ∨ Samosa(I4)

• ∃x Samosa(x), if we confine x to be Indian then it means some x likes samosa.

http://www.knowledgegate.in/gate
• Existential quantifiers: - with existential quantifier of a propositional that is true if and only if
P(x) is true for at least one value of x in the universe of discourse.

• There exists an element x is the universe of discourse such that P(x) is true.

• ∃x P(x), i.e. for at least one value of a P(x) is true

http://www.knowledgegate.in/gate
• let’s change the universe of discourse from Indian to human
• if human is Indian then it likes cricket
• Indian(x): x is an Indian
• Cricket(x): x likes Cricket

• if I1 is Indian then likes cricket ∧ if I2 is Indian then likes cricket ∧ if I3 is Indian then likes
cricket ∧ if I4 is Indian then likes cricket

• [Indian(I1) à cricket(I1)] ∧ [Indian(I2) à cricket(I2)] ∧ [Indian(I3) à cricket(I3)] ∧

[Indian(I4) à cricket(I4)]

• ∀x [Indian(x) à cricket(x)]

http://www.knowledgegate.in/gate
• let’s change the universe of discourse from Indian to human
• if human is Indian then it likes samosa
• Indian(x): x is an Indian
• Samosa(x): x likes Samosa

• if I1 is Indian then likes samosa ∨ if I2 is Indian then likes samosa ∨ if I3 is Indian then
likes samosa ∨ if I4 is Indian then likes samosa

• [Indian(I1) ∧ samosa(I1)] ∨ [Indian(I2) ∧ samosa(I2)] ∨ [Indian(I3) ∧ samosa(I3)] ∨

[Indian(I4) ∧ samosa(I4)]

• ∃x [Indian(x) ∧ samosa(x)]

http://www.knowledgegate.in/gate
• let check validity of a statement “Some Indians like samosa” = ∃x [Indian(x) àsamosa(x)], x is
human
• let human contains four elements I1, I2, I3, I4 out of which I1, I2 are Indian while I3, I4 are not
Indian
• Suppose I1, I2, I3 do not likes samosa

• [Indian(I1) à samosa(I1)] ∨ [Indian(I2) à samosa(I2)] ∨ [Indian(I3) à samosa(I3)]

• [T à F] ∨ [T à F] ∨ [F à F]

• [F] ∨ [F] ∨ [T]

• T

• conclusion ∃x is not used with à

http://www.knowledgegate.in/gate
 Negation

• ¬ [∀x P(x)] = ∃x ¬P(x)

• ¬ [∃x P(x)] = ∀x ¬P(x)

http://www.knowledgegate.in/gate
Universal specification: By this rule if the premise ∀xP(x) is true
then P(c) is true where c is particular member of Universe of
Discourse.
∀xP(x)

P(c)

http://www.knowledgegate.in/gate
Universal generalization: By this rule if P(c) is true for all c in
Universe of Discourse then ∀xP(x) is true.

P(c)

∀xP(x)

http://www.knowledgegate.in/gate
Existential specification: By this rule if ∃xP(x) is true then P(x) is
true for some particular member of Universe of Discourse.

∃xP(x)

P(c)

http://www.knowledgegate.in/gate
Existential generalization: By this rule if P(c) is true for some
particular member c in Universe of Discourse, then ∃xP(x) is true

P(c)

∃xP(x)

http://www.knowledgegate.in/gate
Universal modus ponens: By this rule if P(x) → Q(c) is true for
every x and P(c) is true for some particular member c in Universe
of Discourse then Q(c) is true.

∀xP(x) → Q(x)
P(c)

Q(c)

http://www.knowledgegate.in/gate
Universal modus tollens: By this rule if P(x) → Q(x) is true for
every x and ~Q(c) is true for some particular c in Universe of
Discourse then ~Q(c) is true.

∀x P(x) → Q(x)
~ Q(c)

~ P(c)

http://www.knowledgegate.in/gate
Q The CORRECT formula for the sentence is
“not all rainy days are cold”

∃d (Rainy(d) ∧ ~Cold(d))

http://www.knowledgegate.in/gate
Q Consider the statement

"Not all that glitters is gold”

∃x: glitters(x) ∧ ¬gold(x)

http://www.knowledgegate.in/gate
Q Consider the statement

"None of my friends are perfect."

¬∃x(F(x) ∧ P(x))

http://www.knowledgegate.in/gate
Q Consider the statement

“Some real numbers are rational”

∃x (real(x) ∧ rational(x))

http://www.knowledgegate.in/gate
Q Consider the statement

“Gold and silver ornaments are precious”.

∀x ((G(x) ∨ S(x)) → P(x))

http://www.knowledgegate.in/gate
Q Consider the statement

“Not every graph is connected” ?

¬∀x (Graph(x) → Connected(x))

∃x (Graph(x) ∧ ¬Connected(x))

¬∀x (¬Graph(x) ∨ Connected(x))

http://www.knowledgegate.in/gate
Q Consider the statement

“Tigers and lions attack if they are hungry or threatened”

∀x[(tiger(x) ∨ lion(x)) → (hungry(x) ∨ threatened(x)) → attacks(x)]

http://www.knowledgegate.in/gate
Q Consider the statement

Every teacher is liked by some student

∀(x) [teacher (x) → ∃(y)[student (y) ^ likes (y, x)]]

http://www.knowledgegate.in/gate
Q Consider the statement

Some boys in the class are taller than all the girls

(∃x) (boy(x) ^ (∀y) (girl(y) → taller (x, y)))

http://www.knowledgegate.in/gate
Q Convert the following two statements in quantified expressions of
predicate logic

• For every number there is a number greater than that number.

P(x) : x is a number
Q(y) : y is a number greater than x
∀x(P(x) → Q(y))

• Sum of every two integer is an integer.

P(x) : x is a integer
S(x) : x is sum of integer
∀x(S(x) → P(x))

http://www.knowledgegate.in/gate
• Not Every man is perfect.
P(x) : x is perfect man
~ ∀x(P(x))

• There is no student in the class who knows Spanish and German.

P(x) : x is a student
L(x) : x knows Spanish and German
∃x(P(x) v L(x))

http://www.knowledgegate.in/gate
Chapter-6 (Algebraic Structures)

http://www.knowledgegate.in/gate
 Group Theory
• Group theory is very important mathematical tool which is used in a number of
areas in research and application. Using group theory, we can estimate the
strength of a set with respect to an operator.

http://www.knowledgegate.in/gate
• This idea will further help us in research field to identify the correct
mathematical system to work in a particular research area. E.g. can we use
natural numbers in complex problem area like soft computing or studying black
holes.

http://www.knowledgegate.in/gate
• Now we will directly study some of the basic set related properties and will
define some structure of set and operator based on the properties and will check
those properties on basics number systems like natural numbers, integers, real
numbers etc.

http://www.knowledgegate.in/gate
 Algebraic
1. Closure property: - Consider a non-empty set A and a Structure
binary operation * on A. A is said to be closed with 1 (N, +)
2 (N, -)
respect to *, if ∀ a, b ∈ A, then a*b ∈ A. 3 (N, /)
4 (N, x)
5 (Z, +)
2. Algebraic Structure: - A non-empty set A is said to be 6 (Z, -)
an algebraic structure with respect to a binary 7 (Z, /)
8 (Z, x)
operation *, if A satisfy closure property with respect 9 (R, +)
to *. 10 (R, -)
11 (R, /)
12 (R, x)
13 (M, +)
14 (M, x)
15 (E, +)
16 (E, x)
17 (O, +)
18 (O, x)
19 (R-0, x)
20 (R-0, /)
21 (Non-Singular Matrix, x)
http://www.knowledgegate.in/gate
 Algebraic Semi
1. Associative property: - Consider a non-empty set A Structure Group
and a binary operation * on A. A is said to be 1 (N, +) Y
2 (N, -) N
associative with respect to *, if ∀ a, b, c ∈ A, then 3 (N, /) N
(a*b) *c = a*(b*c) 4 (N, x) Y
5 (Z, +) Y
6 (Z, -) Y
2. Semi-Group: - A non-empty set A is said to be a Semi- 7 (Z, /) N
8 (Z, x) Y
group with respect to a binary operation *, if A satisfy 9 (R, +) Y
closure, Associative property with respect to *. 10 (R, -) Y
11 (R, /) N
12 (R, x) Y
13 (M, +) Y
14 (M, x) Y
15 (E, +) Y
16 (E, x) Y
17 (O, +) N
18 (O, x) Y
19 (R-0, x) Y
20 (R-0, /) Y

http://www.knowledgegate.in/gate 21 (Non-Singular
Matrix, x)
Y
 Algebraic Semi Monoid
1. Identity property: - Consider a non- Structure Group
empty set A and a binary operation * on 1 (N, +) Y Y
A. A is said to satisfy identity property 2 (N, -) N N
3 (N, /) N N
with respect to *, if ∀ a ∈ A, there must 4 (N, x) Y Y
be unique e ∈ A, such that 5 (Z, +) Y Y
6 (Z, -) Y N
a*e = e*a = a 7 (Z, /) N N
8 (Z, x) Y Y
9 (R, +) Y Y
2. There is exactly one Identity element in 10 (R, -) Y N
the set and will be same for all element in 11 (R, /) N N
12 (R, x) Y Y
the set. 13 (M, +) Y Y
14 (M, x) Y Y
3. Monoid: - A non-empty set A is said to be 15 (E, +) Y Y
16 (E, x) Y Y
a Monoid with respect to a binary 17 (O, +) N N
operation *, if A satisfy closure, 18 (O, x) Y Y
19 (R-0, x) Y Y
Associative, identity property with 20 (R-0, /) Y N
respect to *. 21 (Non-Singular Y Y
Matrix, x)

http://www.knowledgegate.in/gate
1. Inverse property: - Consider a non-empty set A and a binary AS Semi Monoid Group
operation * on A. A is said to satisfy inverse property with respect to Group
*, if ∀ a ∈ A, there must be unique element a-1 ∈ A, such that 1 (N, +) Y Y N
a* a-1 = a-1*a = e 2 (N, -) N N N
3 (N, /) N N N
2. Every element has a exactly one unique inverse which is also present 4 (N, x) Y Y Y
in the same set. 5 (Z, +) Y Y Y
6 (Z, -) Y N N
3. If a is the inverse of b, then b will be invers one a. 7 (Z, /) N N N
8 (Z, x) Y Y Y
4. No two elements can have the same inverse 9 (R, +) Y Y Y
10 (R, -) Y N N
5. Identity element is its own inverse. 11 (R, /) N N N
12 (R, x) Y Y Y
6. Group: - A non-empty set A is said to be a group with respect to a 13 (M, +) Y Y Y
binary operation *, if A satisfy closure, Associative, identity, inverse 14 (M, x) Y Y Y
property with respect to *. 15 (E, +) Y Y Y
16 (E, x) Y Y N
17 (O, +) N N N
18 (O, x) Y Y Y
19 (R-0, x) Y Y Y
20 (R-0, /) Y N N
21 (Non-Singular Y Y Y
http://www.knowledgegate.in/gate Matrix, x)
1. If the total number of elements in a group is even then there exists at least one
element in the group who is the inverse of itself.

2. Some time it is also possible that every element is inverse of itself in a group.

3. In a group (a * b)-1 = b-1 * a-1 for ∀ a, b ∈ A

4. Cancelation law holds good

1. a * b = a * c à b = c

2. a * c = b * c à a = b

http://www.knowledgegate.in/gate
 AS SG Monoid Group Abelian
1. Commutative property: - Consider a non- Group
empty set A and a binary operation * on A. 1 (N, +) Y Y N N
A is said to satisfy commutative property 2 (N, -) N N N N
3 (N, /) N N N N
with respect to *, if ∀ a, b ∈ A, such that 4 (N, x) Y Y Y N
a* b = b*a 5 (Z, +) Y Y Y Y
6 (Z, -) Y N N N
7 (Z, /) N N N N
2. Abelian Group: - A non-empty set A is said 8 (Z, x) Y Y Y N
9 (R, +) Y Y Y Y
to be a group with respect to a binary 10 (R, -) Y N N N
operation *, if A satisfy closure, 11 (R, /) N N N N
Associative, identity, inverse, commutative 12 (R, x) Y Y Y N
13 (M, +) Y Y Y Y
property with respect to *. 14 (M, x) Y Y Y N
15 (E, +) Y Y Y Y
16 (E, x) Y Y N N
17 (O, +) N N N N
18 (O, x) Y Y Y N
19 (R-0, x) Y Y Y Y
20 (R-0, /) Y N N N
21 (Non-Singular Y Y Y Y
Matrix, x)

http://www.knowledgegate.in/gate
Q let A = {1, 3, 5, ……., ∞} and B = {2, 4, 6, ……., ∞}, what is the
highest structure achieved by anyone of them?
1) (A,+) 2) (A,*) 3) (B,+) 4) (B,*)

http://www.knowledgegate.in/gate
Q Consider a set of natural numbers N, with respect to *, such
that a * b = ab which structure it will satisfy?

http://www.knowledgegate.in/gate
Q let {p, q, r, s} be the set. A binary operation * is defined on the set and
is given by the following table: Which of the following is true about the
binary operation? * p q r s
a) it is commutative but not associative
b) it is associative but not commutative P p r s p
c) it is both associative and commutative q p q r s
d) it is neither associative nor commutative r p q p r
S p q q q

http://www.knowledgegate.in/gate
Q which of the following is not a group?
a) {……. -6, -4, -2, 0, 2, 4, 6, ……}, +

b) {…. -3k, -2k, -k, 0, k, 2k, 3k, ….}, + [k ∈ Z]

c) {2n, n ∈ Z}, *

d) set of complex number, *

http://www.knowledgegate.in/gate
Q Consider the set of all integers(Z) with the operation defined
as m * n = m + n + 2, m, n ∈ Z
if (z, *) forms a group, then determine the identity element
a) 0 b) -1 c) -2 d) 2

http://www.knowledgegate.in/gate
Q Consider a set of positive rational number with respect to an
operation *, such that a*b = (a.b)/3, it is known that the it is an abelian
group, which of the following is not true?
a) identity element e = 3 b) inverse of a = 9/a

c) inverse of 2/3 = 6 d) inverse of 3 = 3

http://www.knowledgegate.in/gate
Q A binary operation α on a set of integers is defined as x * y = x2 + y2.
Which one of the following statements is TRUE about *?
(A) Commutative but not associative

(B) Both commutative and associative

(C) Associative but not commutative

(D) Neither commutative nor associative

http://www.knowledgegate.in/gate
Q Which one of the following in NOT necessarily a property of a Group?

(A) Commutativity

(B) Associativity

(C) Existence of inverse for every element

(D) Existence of identity

http://www.knowledgegate.in/gate
• Finite Group: - A group with finite number of elements is called a
finite group.

• Order of group: - Order of a group is denoted by O(G) = no of

elements in G
• If there is only one element in the Group, it must be an identity
element.

http://www.knowledgegate.in/gate
Q Check out which of the following is a finite group?
1- {0}, + 2- {0}, * 3- {1}, + 4- {1}, *

+ 0 * 0 + 1 * 1
0 0 1 1

5- {0,1}, + 6- {0,1}, * 7- {-1, 0, 1}, + 8- {-1, 0, 1}, *

+ 0 1 * 0 1 + -1 0 1 * -1 0 1
-1 -1
0 0
0 0
1 1
+1
http://www.knowledgegate.in/gate 1
Q Check out which of the following is a finite group?
9- {-1, 1}, + 10- {-1, 1}, * 11- {-2, -1, 0, 1, 2}, +

+ -1 1 * -1 1 + -2 -1 0 1 2
-1 -1 -2
-1
1 1
0
1
2

http://www.knowledgegate.in/gate
Q Check out which of the following is a finite group?
12- {-2, -1, 0, 1, 2}, * 13- {1, ω, ω2}, * 14- {-1, 1, i, -i}, *
* -2 -1 0 1 2 * 1 ω ω2 * -1 1 i -i
-2 1 -1
-1 1
ω
0 i
1 ω2
-i
2

http://www.knowledgegate.in/gate
1. Conclusion: - it is very difficult to design finite group as with
number greater than 2 closure property fails with simple addition
and multiplication operation.

2. So we will try to develop new modified addition and multiplication

operators with which closure and other properties can be satisfied.

http://www.knowledgegate.in/gate
• Addition modulo: - addition modulo is a binary operator
denoted by +m such that

• a +m b = a + b if (a + b < m)

• a +m b = a + b - m if (a + b >= m)
+4 0 1 2 3
0
{0,1,2,3}, +4 1
2
3
http://www.knowledgegate.in/gate
• Multiplication modulo: - Multiplication modulo is a binary
operator denoted by *m such that

• a *m b = a * b if (a * b < m)

• a *m b = (a * b) % m if (a * b >= m)
*5 1 2 3 4
1
{1,2,3,4}, * 5 2
3
4
http://www.knowledgegate.in/gate
Q Check out which of the following is a group?
1- {0,1,2,3}, +4 2- {0,1,2,3}, *4
+4 0 1 2 3 *4 0 1 2 3
0 0
1 1
2 2
3 3
3- {1,2,3}, +4 4- {1,2,3}, *4
+4 1 2 3 *4 1 2 3
1 1
2 2
3 3
http://www.knowledgegate.in/gate
5- {0,1,2,3,4}, +5 6- {0,1,2,3,4}, *5
+5 0 1 2 3 4 *5 0 1 2 3 4
0 0
1 1
2 2
3 3
4 4

7- {1,2,3,4}, +5 8- {1,2,3,4}, *5
+5 1 2 3 4 *5 1 2 3 4
1 1
2 2
3 3
4 4
http://www.knowledgegate.in/gate
9- {0,1,2,3,4,5,6}, +7 10- {0,1,2,3,4,5,6}, *7
+7 0 1 2 3 4 5 6 *7 0 1 2 3 4 5 6
0 0
1 1
2 2
3 3
4 4
5 5
6 6
11- {1,2,3,4,5,6}, +7 12- {1,2,3,4,5,6}, *7
+7 1 2 3 4 5 6 *7 1 2 3 4 5 6
1 1
2 2
3 3
4 4
5 5
6 http://www.knowledgegate.in/gate
6
13- {1,3,5,7}, *8 14- {1,2,4,7,8,11,13,14}, *15
*8 1 3 5 7 *15 1 2 4 7 8 11 13 14
1 1
2
3
4
5
7
7 8
11
13
14

http://www.knowledgegate.in/gate
15- {1,2,3, 4……., p-1}, *p 16- {0,1,2,3, 4……., p-1}, *p

17- {1,2,3, 4……., p-1}, +p 18- {0,1,2,3, 4……., p-1}, +p

http://www.knowledgegate.in/gate
Q Let s = set of all integers. A binary operation * is defined by
a*b=a+b+3
consider the following statements
S1: (S,*) is a group

S2: -3 is identity element of (S, *)

S3: the inverse of -6 is 0

which of the following are true

a) Only S1 and S2
b) Only S2 and S3
c) Only S1 and S3
d) Only S1 ,S2 andhttp://www.knowledgegate.in/gate
S3
Q {0,1,2,3,4,5}, +6 is a group which of the following is not true?
a) 1-1 = 5 b) 2-1 = 4 c) 3-1 = 6 d) 0-1 = 0

+6 0 1 2 3 4 5
0
1
2
3
4
5
http://www.knowledgegate.in/gate
Q {1,2,3,4,5,6}, *7 is a group which of the following is not true?
a) 1-1 = 1 b) 2-1 = 4 c) 3-1 = 5 d) 6-1 = 6

*7 1 2 3 4 5 6
1
2
3
4
5
6
http://www.knowledgegate.in/gate
Q {1,3,5,7}, *8 is a group which of the following is not true?
a) 1-1 = 1 b) 3-1 = 3 c) 5-1 = 5 d) 7-1 = 7

*8 1 3 5 7
1
3
5
7
http://www.knowledgegate.in/gate
Q {1,2,4,7,8,11,13,14}, *15 is a group which of the following is not true?
a) 2-1 = 8 b) 4-1 = 4 c) 7-1 = 13 d) 11-1 = 14

*15 1 2 4 7 8 11 13 14
1
2
4
7
8
11
13
14
http://www.knowledgegate.in/gate
 Sub Group
1. The subset of a group may or may not be a group.

2. When the subset of a group is also a group then it is called sub group.

3. The identity element of a group and its sub group is always same.

4. Union of two subgroup may or may not be a subgroup.

5. Intersection of two subgroup is always a subgroup.

6. Lagrange’s theorem: - the order of a group is always exactly divisible by the

order of a sub group.

http://www.knowledgegate.in/gate
Q Consider a group G = {1,3,5,7}, *8 which of the following sub set of this set does not form is
sub group?
a) {0,1} b) {1,3} c) {1,5} d) {1,7} e) {1,3,7}

*8 0 1 *8 1 3 *8 1 5 *8 1 7 *8 1 3 7
0 1 1
1 1
1
5 3
3 7
7

http://www.knowledgegate.in/gate
Q Let G be a group with 15 elements. Let L be a subgroup of G. It is
known that L != G and that the size of L is at least 4. The size of L is
__________.
(A) 3 (B) 5 (C) 7 (D) 9

http://www.knowledgegate.in/gate
Q Let G be a finite group on 84 elements. The size of a largest
possible proper subgroup of G is _______ .

http://www.knowledgegate.in/gate
Order of an element: - (A, *) be a group, then ∀ a ∈ A, order of a is denoted by O(a).

1. O(a) =n (smallest positive integer), such that an = e

2. Order of identity element is always one.

3. Order of an element and its inverse is always same.

4. Order of an element in an infinite group does not exist or infinite expect identity.

http://www.knowledgegate.in/gate
Q consider a group {0,1,2,3}, +4 and find the order of each element?

+4 0 1 2 3
0
1
2
3

http://www.knowledgegate.in/gate
Q consider a set on cube root of unity {1, ω, ω2}, * and find the
order of each element?

* 1 ω ω 2

1
ω
ω 2

http://www.knowledgegate.in/gate
Q consider a set on forth root of unity {-1, 1, I, -i}, * and find the order of
each element?

* -1 1 i -i
-1
1
i
-i
http://www.knowledgegate.in/gate
Generating element or Generator: - A element ‘a’ is said to be a
generating element, if every element of A is an integral power of a, i.e.
every element of A can be represented using power of a.

A = {a1, a2, a3, a4, a5….}

http://www.knowledgegate.in/gate
Cyclic group: - A group (A, *) is said to be a cyclic group if it contains at least one
generator.

1. In a cyclic group if an element is a generator than its inverse will also be a

generator.

2. The order of a cyclic group is always the order of the generating element of G.

http://www.knowledgegate.in/gate
Q Show that G = {1,2,4,5,7,8}, +15 is a cyclic group. How many generators
are there?

*15 1 2 4 5 7 8
1
2
4
5
7
8

http://www.knowledgegate.in/gate
Q consider a group {1,2,4,7,8,11,13,14}, *15 and find the order of
each element?
*15 1 2 4 7 8 11 13 14
1
2
4
7
8
11
13
14
http://www.knowledgegate.in/gate
Q For the composition table of a cyclic group shown below
* a b c d
a a b c d
b b a d c
c c d b a
d d c a b
Which one of the following choices is correct?
(A) a, b are generators
(B) b, c are generators
(C) c, d are generators
(D) d, a are generators
http://www.knowledgegate.in/gate
 Number of generators

Lagrange’s theorem: - let A be a cyclic group of order n, number of

Generator in A is denoted by ɸ(n) = {n(p1-1) (p2-1) (p3-1) ………. (pk-1)} /
(p1p2p3………pk)

http://www.knowledgegate.in/gate
Q let G be a cyclic group, O(G) = 8, number of generators in G =?

http://www.knowledgegate.in/gate
Q let G be a cyclic group, O(G) = 12, number of generators in G =?

http://www.knowledgegate.in/gate
Q let G be a cyclic group, O(G) = 70, number of generators in G =?

http://www.knowledgegate.in/gate
Q let G be a cyclic group, O(G) = 23100, number of generators in G =?

http://www.knowledgegate.in/gate
 Coset
Let H be a subgroup of a group G and a ϵ G, then the set
aH = {ah | h ϵ H} is called a left coset of H in G
and Ha = {ha |h ϵ H} is called a right coset of H in G.

By this definition, it is clear that corresponding to every element of G,

we have a left coset and right coset of H in G. It is obvious that
aH ⊂ G, Ha ⊂ G, ∀ a ϵ G
Further we may note that
eH = Н = Не
i.e., the left and the right cosets of H corresponding to the identity e
coincide with H. Hence H itself is a left as well as a right coset of H in G.
http://www.knowledgegate.in/gate
Let G= (Z, +) and H = 2Z = {0, ± 2, ± 4,....}
then the right cosets of H in G are :
H+ 0={0, ±2, ±4, ......} = H
H + 1={0 + 1, ± 2+1, ± 4+1, ....}
H + 2={0 + 2, ± 2+2, ± 4+2, ....} etc.
It can be easily observed that any right coset and its corresponding left coset are
equal i.e.,
H+ 1=1 + H, H + 2=2 + H etc.
Again
H + 3 ={.., - 6, -3, 0, 3, 6, 9, 12,....} = Н
H + 4 = {..., - 5, - 2, 1, 4, 7, 10, 13,..} = H + 1 etc.
Similarly H + 5 = H + 2, H + 6 = H
Thus H has only two distinct cosets H, H + 1 in Z.

http://www.knowledgegate.in/gate
Find all the cosets of 3Z in the group (Z, +).
H = 3Z = {.....6, -3, 0, 3, 6, ....}
The following distinct cosets of H in G are obtained :
0 + H = H + 0 = {..., -6, -3, 0, 3, 6, .....} = H
1 + H = H + 1 = {.., - 5, -2, 1, 4, 7, .....}
2 + H = H + 2 = {…..-4, - 1, 2, 5, 8,..}
3+H=H+3=0+H=H+0
4+H=H+4=1+H=H+1
5+H=H+5=2+H=H+2
6+H=H+6=0+H=H+0

http://www.knowledgegate.in/gate
Find all the cosets of H = {0, 3} in the group (Z6, +6).
G = { 0, 1, 2, 3, 4, 5} H = {0, 3}, G
The following distinct cosets of H in G are obtained :
0 + H = H + 0 = {0, 3} = H
1 + H = H + 1 = {0 +6 1, 3 +6 1} = {1, 4} = H + 1
2 + H = H + 2 = {0 +6 2, 3 +6 2} = {2, 5} = H + 2
3 + H = H + 3 = {0 +6 3, 3 +6 3} = {3, 0} = H
4 + H = H + 4 = {0 +6 4, 3 +6 4} = {4, 1} = H + 1
5 + H = H + 5 = {0 +6 5, 3 +6 5} = {5, 2} = H + 2
6 + H = H + 6 = {0 +6 6, 3 +6 6} = {0, 3} = H

If we take union of all distinct cosets of G, we will get back G

http://www.knowledgegate.in/gate
 Ring
• A ring is an algebraic system (R, +, •) where R is a non-empty set and + and • are
two binary operations (which can be different from addition and multiplication)
and if the following conditions are satisfied :
• (R, +) is an abelian group.
• (R, •) is semigroup
• The operation • is distributive over +.
• a • (b + c) = (a • b) + (a • c)
• (a + b) • c = (a • c) + (b • c)

• E.g. (Z, +, X) is a ring

http://www.knowledgegate.in/gate
 Integral Domain
• A ring becomes integral domain, if it is a commutative ring with unity and
without zero divisor
• (D, +) is an abelian group.
• (D, •) is semigroup with Commutative and With unity, Without zero divisor if
a.b=0 then a=0 or b=0

• E.g. (Z, +, X) is a integral domain, (Q, +, X) is a integral domain, (R, +, X) is a

integral domain, (C, +, X) is a integral domain, (Z, +3, X3) is a integral domain

http://www.knowledgegate.in/gate
 Field
• A field is an algebraic system (R, +, •) where R is a non-empty set and + and • are
two binary operations (which can be different from addition and multiplication)
and if the following conditions are satisfied :
• (R, +) is an abelian group
• (R, •) is an abelian group(inverse should exist for every non-zero element)
• The operation • is distributive over +.
• a • (b + c) = (a • b) + (a • c)
• (a + b) • c = (a • c) + (b • c)

• E.g. (R, +, X) is a field, (Q, +, X) is a field, (Z, +3, X3) is a field

http://www.knowledgegate.in/gate
 {0,1,2,3,4}, +5 {0,1,2,3,4}, *5
+5 0 1 2 3 4 *5 0 1 2 3 4
0 0
1 1
2 2
3 3
4 4

This is ring, integral domain and field

http://www.knowledgegate.in/gate
Chapter-7 (Graphs)

http://www.knowledgegate.in/gate
 Graph Theory
1. A graph G (V, E) consist of a set off objects V = {V1, V2, V3….,VN} called vertices
and another set E = {E1, E2, E3,….,En} whose elements are called edges.
2. Each edge ek is identified with an unordered pair (vi, vj) of vertices.

3. The vertices vi, vj associated with edge ek are called the end vertices of ek.

http://www.knowledgegate.in/gate
1. Self-Loop: Edge having the same vertex (vi, vi) as both its end vertices is called self-
loop.
2. Parallel Edge: When more than one edge associated with a given pair of vertices such
edges are referred as parallel edges.
3. Adjacent Vertices: If two vertices are joined by the same edges, they are called
adjacent vertices.
4. Adjacent Edges: If two edges are incident on some vertex, they are called adjacent
edges.

http://www.knowledgegate.in/gate
• Complete or Full Graph: In a simple graph there exist an edge between each
and every pair of vertices i.e. every vertex are adjacent to each other, then the
graph is said to be a complete graph, denoted by Kn. Number of edges in a
Complete graph is n(n-1)/2

http://www.knowledgegate.in/gate
 Degree
• Degree of a Vertex: The degree of a vertex in an undirected graph is
the number of edges associated with it, denoted by deg(vi).

http://www.knowledgegate.in/gate
• Hand-shaking theorem: - Since each edge contribute two degree in the
graph, the sum of the degree of all vertices in G is twice the number of
edges in g.
&
• ∑#$% 𝑑(𝑣𝑖) = 2|E|

http://www.knowledgegate.in/gate
• The number of vertices of odd degree in a graph is always even.
$
• !"# 𝑑(𝑣𝑖) = ∑%&%$ 𝑑(𝑣𝑖) + ∑'(( 𝑑(𝑣𝑖)
∑

http://www.knowledgegate.in/gate
 Representation of Graph in Memory
• Following two are the most commonly used representations of a graph.
• Adjacency Matrix
• Adjacency List
• There are other representations also like, Incidence Matrix and Incidence List.
The choice of the graph representation is situation specific. It totally depends on
the type of operations to be performed and ease of use.

http://www.knowledgegate.in/gate
• Adjacency Matrix: Adjacency Matrix is a 2D array of size V x V where V is the number of
vertices in a graph. Let the 2D array be adj[][], a slot adj[i][j] = 1 indicates that there is an edge
from vertex i to vertex j.
• Adjacency matrix for undirected graph is always symmetric.
• Adjacency Matrix is also used to represent weighted graphs. If adj[i][j] = w, then there is an
edge from vertex i to vertex j with weight w.

http://www.knowledgegate.in/gate
 Incidence Matrix
• Representation of undirected graph : Consider a undirected graph G = (V, E) which has n
vertices and m edges all labelled. The incidence matrix I(G) = [bij], is then n x m matrix,
• where bi,j=1 when edge ej is incident with vi
• = 0 otherwise
• Representation of directed graph : The incidence matrix I(D) = [bij] of digraph D with n
vertices and m edges is the n x m matrix in which.
• Bi,j = 1 if arc j is directed away from vertex vi
• =－1 if arc j is directed towards vertex vi
• =0 otherwise.

http://www.knowledgegate.in/gate
• Adjacency List: An array of lists is used. Size of the array is equal to the number of vertices.
Let the array be array[]. An entry array[i] represents the list of vertices adjacent to the ith
vertex. This representation can also be used to represent a weighted graph. The weights of
edges can be represented as lists of pairs.

http://www.knowledgegate.in/gate
 Some Popular Graph
1. Bi-partite graph: - A graph G(V, E) is called bi-partite graph if it’s vertex set V(G) can be
partitioned into two non-empty disjoint subset V1(G) and V2(G) in such a way that each edge
e ϵ E(G) has it’s one end point in V1(g) and other end point in V2(g). The partition V = V1 U V2
is called bipartition of G.
2. Complete Bi-partite graph: - A Bi-partite graph G(V, E) is called Complete bi-partite graph if
every vertex in the first partition is connected to every vertex in the second partition,
denoted by Km,n.

http://www.knowledgegate.in/gate
1. Cycle Graph: - A cycle graph or circular graph is a graph that consists of a single cycle, or in other words, some
number of vertices (at least 3) connected in a closed chain. The cycle graph with n vertices is called Cn. The
number of vertices in Cn equals the number of edges, and every vertex has degree 2; that is, every vertex has
exactly two edges incident with it.
2. Wheel graph: - A wheel graph is a graph formed by connecting a single universal vertex to all vertices of
a cycle. Some authors write Wn to denote a wheel graph with n vertices (n ≥ 4); other authors instead use Wn to
denote a wheel graph with n+1 vertices (n ≥ 3), which is formed by connecting a single vertex to all vertices of a
cycle of length n.

http://www.knowledgegate.in/gate
• Regular graph: - A graph in which all the vertices are of equal degree is
called a regular graph. E.g. 2-regular graph, 3-regular graph.

http://www.knowledgegate.in/gate
 Complement of a Graph
1. The complement of a simple graph G (V, E) is a graph Gc (V, Ec) on the same vertices set as of
G, such that there will be an edge between two vertices u, v in Gc if ang only if there is no
edge between u, v in G. i.e. two vertices of Gc are adjacent iff they are not adjacent in G.
2. V(G) = V(Gc)
3. E(Gc) = {(u, v) | (u, v) ∉ E(G)}
4. E(Gc) = E(Kn) - E(G)

http://www.knowledgegate.in/gate
 Properties
1. G U Gc = Kn
2. G ⋂ Gc = null graph
3. |E(G)| + |E(Gc)| = E(Kn) = n(n-1)/2

http://www.knowledgegate.in/gate
 Planer Graph
Planer Graph: - A graph is called a planer graph if it can be drawn on a plan in such
a way that no edges cross each other, otherwise it is called non-planer. Application:
civil engineering, circuit designing

http://www.knowledgegate.in/gate
http://www.knowledgegate.in/gate
 Simplest Non-Planer Graphs

1. Kuratowski’s case I: - K5
2. Kuratowski’s case II: - K3,3
3. Both are simplest non-planer graph
4. Both are regular graph
5. If we delete either an edge or a vertex from any of the graph, they
will become planer

http://www.knowledgegate.in/gate
• Kazimierz Kuratowski ( 2 February 1896 – 18 June 1980)
was a Polish mathematician and logician.

http://www.knowledgegate.in/gate
http://www.knowledgegate.in/gate
http://www.knowledgegate.in/gate
http://www.knowledgegate.in/gate
 Euler's formula
• A planer graph divides the plane into number or regions (faces, planer embedding), which are
further divided into bounded(internal) and unbounded region(external). Euler's formula
states that if a finite, connected, planar graph with v is the number of vertices, e is the
number of edges and r is the number of faces (regions bounded by edges, including the outer,
infinitely large region), then r = e – v + 2

http://www.knowledgegate.in/gate
• Euler's formula (Disconnected graph): V – e + r – k = 1

http://www.knowledgegate.in/gate
 Graph Coloring
• Graph coloring can be of two types vertex coloring and region coloring.

http://www.knowledgegate.in/gate
• Associating a color with each vertex of the graph is called vertex coloring.
• Proper Vertex coloring: - Associating all the vertex of a graph with colors such
that no two adjacent vertices have the same color is called proper vertex
coloring.
• Chromatic number of the graph: - Minimum number of colors required to do a
proper vertex coloring is called the chromatic number of the graph, denoted by
χ(G). the graph is called K-chromatic or K-colorable.

http://www.knowledgegate.in/gate
http://www.knowledgegate.in/gate
http://www.knowledgegate.in/gate
 Traversal
• Walk / Edge Train / Chain: -A Walk is defined as a finite alternating sequence of vertices and
edges, beginning and ending with vertices. Vertex and edge, may appear more than once in a
walk.
• It is possible for a walk to begin and end at the same vertex.
Such a walk is called a closed walk. A walk that is not closed is
called an open walk.
• An open walk in which no vertex appears more than once is
called a path (a path does not interact itself). Number of edges
in a path is called length of a path.

Open Walk
Closed Walk
Path
http://www.knowledgegate.in/gate
• Connected Graph: A graph is said to be connected if there is at least one path
between every pair of vertices in G.
• A graph with n vertices can be connected with minimum n -1 edges.
• A graph with n vertices will necessary be connected if it has more than (n - 1) (n
- 2)/2 edges.

http://www.knowledgegate.in/gate
Q Which condition is necessarily for a graph to be connected?
a) A graph with 6 vertices and 10 edges
b) A graph with 7 vertices and 14 edges
c) A graph with 8 vertices and 22 edges
d) A graph with 9 vertices and 28 edges

http://www.knowledgegate.in/gate
 Euler Graph
1. Euler Graph: - If some closed walk in a graph contains all the edges of the graph(connected),
then the walk is called a Euler line and the graph a Euler Graph.
2. A given connected graph G is a Euler graph if and only if all vertices of G are of even degree.

http://www.knowledgegate.in/gate
 Hamiltonian
1. Hamiltonian Graph: - A Hamiltonian circuit in a connected graph is defined as a
closed walk that traverses every vertex of G exactly once, except of course the
starting vertex, at which the walk also terminates. A graph containing
Hamiltonian circuit is called Hamiltonian graph.
2. Finding weather a graph is Hamiltonian or not is a NPC problem.

http://www.knowledgegate.in/gate
http://www.knowledgegate.in/gate
 Isomorphism
1. In general, two graphs are said to be isomorphic if they are perhaps the same graphs, but just
drawn differently with different names. i.e. two graphs are thought of as isomorphic if they
have identical behavior in terms of graph-theoretic properties.

http://www.knowledgegate.in/gate
Q How many simple non isomorphic graphs are possible with 3 vertices ?

http://www.knowledgegate.in/gate
http://www.knowledgegate.in/gate
http://www.knowledgegate.in/gate
http://www.knowledgegate.in/gate
Chapter-8 (Combinatorics)

http://www.knowledgegate.in/gate
 Permutation
• Permutation refers to the arrangement of a set of items or elements in a
specific order. The key points about permutation are:
• Order Matters: The arrangement is considered different if the order of items
is different.
• Counting Permutations: To find the number of permutations of 'n' items
taken 'r' at a time, we use the formula npm = P (n, m).

http://www.knowledgegate.in/gate
Examples:
• Simple Example:
• Items: A, B
• Permutations: AB, BA
• Total: 2 permutations

• Numerical Example:
• Items: 1, 2, 3
• Permutations: 123, 132, 213, 231, 312, 321
• Total: 6 permutations (3! = 3 × 2 × 1 = 6)

• Real-world Example:
• Scenario: Arranging books on a shelf.
• Books: Physics (P), Chemistry (C), Mathematics (M)
• Permutations: PCM, PMC, CMP, CPM, MPC, MCP
• Total: 6 arrangements

http://www.knowledgegate.in/gate
 Combination
• Combination refers to the selection of items from a larger set where the order
of selection does not matter. The key points about combination are:
• Order Doesn't Matter: Unlike permutations, the arrangement or order of
the selected items is irrelevant in combinations.
• Counting Combinations: To find the number of combinations of 'n' items
taken 'r' at a time, we use the formula nCr = (n!) / ((n−r)!n!).

http://www.knowledgegate.in/gate
• Simple Example:
• Items: A, B, C
• Selecting 2 items at a time.
• Combinations: AB, AC, BC
• Total: 3 combinations

• Numerical Example:
• Items: 1, 2, 3, 4
• Selecting 2 items at a time.
• Combinations: 12, 13, 14, 23, 24, 34
• Total: 6 combinations (4 2=4!2!(4−2)!=64C2=2!(4−2)!4!=6)

• Real-world Example:
• Scenario: Choosing 2 fruits from a basket containing an Apple (A), Banana (B), and Cherry
(C).
• Combinations: AB, AC, BC
• Total: 3 ways to choose 2 fruits out of 3.
http://www.knowledgegate.in/gate
Q A collection of 10 electric bulbs contain 3 defective ones?
• In how many ways can a sample of four bulbs be selected?

• In how many ways can a sample of 4 bulbs be selected which Contain 2 good bulbs and 2
defective ones ?

• In how many ways can a sample of 4 bullbs be selected so that either the sample contain 3
good ones and 1 defectives ones or 1 good and 3 defectives ones ?

http://www.knowledgegate.in/gate
 Pigeonhole Principle
• It states that if more items (pigeons) are put into fewer containers (pigeonholes) than
there are items, then at least one container must contain more than one item. Key
points include:
• Basic Idea: If 'n' items are distributed among 'm' containers, and if n>m, then at
least one container has more than one item.

http://www.knowledgegate.in/gate
• Simple Example:
• Socks: 10 pairs of socks (20 individual socks) and 19 drawers.
• According to the Pigeonhole Principle, since there are more socks than
drawers, at least one drawer must contain more than one sock.

• Real-world Example:
• Scenario: A classroom with 30 students.
• If you want to prove that at least two students have their birthdays in the
same month, you consider the months (12 pigeonholes) and the students (30
pigeons).
• According to the Pigeonhole Principle, at least one month (pigeonhole) will
have more than ⌈30/12⌉ = 3 students (pigeons) sharing their birthdays.

http://www.knowledgegate.in/gate
No of onto function possible from A to B
= nm – nc1(n-1)m + nc2(n-2)m - nc3(n-3)m +---------+ (-1)n nc n-1 1m

http://www.knowledgegate.in/gate
Q In a class of 200 students, 125 students have taken Programming Language course, 85 students
have taken Data Structures course, 65 students have taken Computer Organization course; 50
students have taken both Programming Language and Data Structures, 35 students have taken
both Data Structures and Computer Organization; 30 students have taken both Programming
Language and Computer Organization, 15 students have taken all the three courses. How many
students have not taken any of the three courses?

|A U B U C| = |A| + |B| + |C| - |A ∩ B| - |B ∩ C| - |A ∩ C| + |A ∩ B ∩ C|

125+85+65-50−35−30+15
http://www.knowledgegate.in/gate
Q The number of integers between 1 and 500 (both inclusive) that are
divisible by 3 or 5 or 7 is ______.
A U B U C| = |A| + |B| + |C| - |A ∩ B| - |B ∩ C| - |A ∩ C| + |A ∩ B ∩ C|

166 + 100 + 71 -33-14-23+4

http://www.knowledgegate.in/gate
Q In a college, there are three student clubs, Sixty students are only in the Drama club, 80
students are only in the Dance club, 30 students are only in Maths club, 40 students are in both
Drama and Dance clubs, 12 students are in both Dance and Maths clubs, 7 students are in both
Drama and Maths clubs, and 2 students are in all clubs. If 75% of the students in the college are
not in any of these clubs, then the total number of students in the college is _____________.
A U B U C| = |A| + |B| + |C| - |A ∩ B| - |B ∩ C| - |A ∩ C| + |A ∩ B ∩ C|

http://www.knowledgegate.in/gate