0% found this document useful (0 votes)

334 views407 pages

DM Gate Notes

Uploaded by

bishalkumarharijan4

We take content rights seriously. If you suspect this is your content, claim it here.

Available Formats

Download as PDF, TXT or read online on Scribd

0% found this document useful (0 votes)

334 views407 pages

DM Gate Notes

Uploaded by

bishalkumarharijan4

We take content rights seriously. If you suspect this is your content, claim it here.

Available Formats

Download as PDF, TXT or read online on Scribd

You are on page 1/ 407

http://www.knowledgegate.

in/gate
• Discrete mathematics is a core subject of theoretical computer science. It is not
a directly application-oriented subject, but it provides tolls and mathematical
models, which are applied to different areas in computer science.

• GATE (7-9 MARKS)

• Has a good weightage in general all objective and subjective examination.

• Will be asked in Interview for M.Tech, PhD or other government jobs. Not that
important in software industry.

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}

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

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

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

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

• 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
• Set of all-Natural number(N) - A natural number is a number that
occurs commonly and obviously in nature. The set of natural
numbers, can be defined as N = {1,2,3, 4.... ∞}
• Set of all Whole number(W) - A whole number is a science
expanded natural number. Set of natural number and zero

http://www.knowledgegate.in/gate
• Set of all Rational number (Q) - A rational number is any number that can be
expressed as a fraction P/Q of two integers, a numerator P and a non-zero
denominator Q.
• Set of all Irrational number (R-Q or R/Q or P) - An irrational number is a real
number that cannot be expressed as a fraction i.e. as a ratio of integers.
Therefore, irrational numbers, when written as decimal numbers, do not
terminate, nor do they repeat. E.g. root2.

http://www.knowledgegate.in/gate
• Set of all Real number(R) - A real number is a value that represents a
quantity along a continuous line, containing all of the rational
numbers and all of the irrational numbers.

http://www.knowledgegate.in/gate
• Set of all Complex number(C) - A complex number is a number that
can be expressed in the form ‘a + bi’, where ‘a’ and ‘b’ are real
numbers and ‘i’ is the imaginary unit, that satisfies the equation
i2 = −1. In this expression, ‘a’ is the real part and ‘b’ is the imaginary
part of the complex number.

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}

• For e.g. A = {0,2,4,6}, |A| = 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
Set

Empty Non-Empty

Finite Finite Infinite

Countable Countable Countable Uncountable

http://www.knowledgegate.in/gate
• Countable set – A set is said to be countable if there can be a one to
one mapping between the elements of the set and natural numbers.
E.g. Set of stars, N, W, Z, Q.

http://www.knowledgegate.in/gate
• Uncountable set – A set is said to be uncountable if there cannot be a
one to one mapping between the elements of the set and natural
numbers. E.g. Set of real 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 {}.

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.

• 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)

• 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

2) ɸ ⊑ A

3) ɸ ϵ 2A

4) ɸ ⊑ 2A

5) A ϵ 2A

6) A ⊑ 2A

http://www.knowledgegate.in/gate
Q For a set A, the power set of A is denoted by 2A. If A = {5, {6}, {7}},
which of the following options are True.
I) ɸ ∈ 2A II) ɸ ⊑ 2A III) {5, {6}} ∈ 2A IV) {5, {6}} ⊑ 2A

(A) I and III only

(B) II and III only

(C) I, II and III only

(D) I, II and IV only

(b) P(S) ∩P(P(S)) = {φ}

(c) P(S) ∩S = P(S)

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
Q Consider the following statements?
a) Finite union of finite sets(disjoint) is ________(finite/infinite)

b) Finite union of Infinite sets(disjoint) is ________(finite/infinite)

c) Infinite union of finite sets(distinct) is ________(finite/infinite)

d) if after finite number of union result is infinite set, then at least of the input
set(disjoint) is infinite (T / F)

e) if after finite number of union result is infinite set, then all of the input set is
infinite (T / F)

g) Finite intersection of Infinite sets(disjoint) is ________(finite/infinite)

h) If after finite number of intersection result is infinite set, then at least

of the input set(disjoint) is infinite (T / F)

i) If after finite number of intersection result is infinite set, then all of the
input set(disjoint) is infinite (T / F)

(a) At least one of the set Si is a finite set

(b) Not more than one of the set Si can be finite

(c) At least one of the sets Si is an infinite set

(d) Not more than one of the sets Si can be infinite

c) A - (A ⋂ B) = A - B d) A - (A - B) = B

(ii) (A – B) – C = (A - C) – B

(iii) (A - B) – C = A – (B ⋂ C)

(iv) (A ⋂ B) – (B ⋂ C) = {A – (A⋂C)} – (A – B)

a) i & iii b) ii & iv

c) i, ii, iv d) ii & iii

(A) Qc U Rc (B) P U Qc U Rc

II) p∩ (q ∩ r) = (p ∩ q) @ (p @ r)

a) I only b) II only
c) neither I nor II d) both I and II

http://www.knowledgegate.in/gate
Q Let E, F and G be finite sets.
Let X = (E ∩ F) – (F ∩ G) and Y = (E – (E ∩ G)) – (E – F).
Which one of the following is true?
(A) X ⊂ Y (B) X ⊃ Y (C) X = Y (D) X – Y ≠ φ and Y – X ≠ φ

X = {n| 1<=n<=123, n is not divisible by 2,3 or 5}?

a)90

b)33

c)37

d)44

Y=(A−C) −(B−C)

Which one of the following is TRUE?

a) X=Y b) X⊂Y c) Y⊂X d) None of these

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) 175 (B) 20 (C) 25 (D) 35

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

http://www.knowledgegate.in/gate
Q Let A and B be sets and let Ac and Bc denote the complements
of the sets A and B. the set (a – b) ∪ (b - a) ∪ (a ∩ b) is equal to.
(a) A ∪ B (b) Ac ∪ bc (c) A ∩ B (d) Ac ∩ bc

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⋂A

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
• 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. 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}
• For E.g. if A = {a, b}, B = {1, 2, 3}
• A×B = { }

1
a
2
b
3
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| =

• 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 ________

• Smallest possible relation will be _______

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 0 1 1
0 0 1 0 2
0 0 1 1 3
0 1 0 0 4
0 1 0 1 5
0 1 1 0 6
0 1 1 1 7
1 0 0 0 8
1 0 0 1 9
1 0 1 0 10
1 0 1 1 11
1 1 0 0 12
1 1 0 1 13
1 1 1 0 14
1 1 1 1 15

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 0 1 1 {(b, 2)}
0 0 1 0 2 {(b, 1)}
0 0 1 1 3 {(b, 1), (b, 2)}
0 1 0 0 4 {(a, 2)}
0 1 0 1 5 {(a, 2), (b, 2)}
0 1 1 0 6 {(a, 2), (b, 1)}
0 1 1 1 7 {(a, 2), (b, 1), (b, 2)}
1 0 0 0 8 {(a, 1)}
1 0 0 1 9 {(a, 1), (b, 2)}
1 0 1 0 10 {(a, 1), (b, 1)}
1 0 1 1 11 {(a, 1), (b, 1), (b, 2)}
1 1 0 0 12 {(a, 1), (a, 2)}
1 1 0 1 13 {(a, 1), (a, 2), (b, 2)}
1 1 1 0 14 {(a, 1), (a, 2), (b, 1)}
1 1 1 1 15 {(a, 1), (a, 2), (b, 1), (b, 2)}

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

• 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’ = { }

• 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

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)}

2. Largest reflexive relation is ________

3. Total number of reflexive relations will be _________

4. If two relations R1 and R2 are reflexive then their union and intersection will also be reflexive
(T / F).

5. Any super set of reflexive relation will also be reflexive(T / F).

6. If a relation is reflexive then its inverse R-1 will also be reflexive (T / F).

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 0 1 1 {(b, b)}
0 0 1 0 2 {(b, a)}
0 0 1 1 3 {(b, a), (b, b)}
0 1 0 0 4 {(a, b)}
0 1 0 1 5 {(a, b), (b, b)}
0 1 1 0 6 {(a, b), (b, a)}
0 1 1 1 7 {(a, b), (b, a), (b, b)}
1 0 0 0 8 {(a, a)}
1 0 0 1 9 {(a, a), (b, b)}
1 0 1 0 10 {(a, a), (b, a)}
1 0 1 1 11 {(a, a), (b, a), (b, b)}
1 1 0 0 12 {(a, a), (a, b)}
1 1 0 1 13 {(a, a), (a, b), (b, b)}
1 1 1 0 14 {(a, a), (a, b), (b, a)}
1 1 1 1 15 {(a, a), (a, b), (b, a), (b, b)}

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 0 1 1
0 0 1 0 2
0 0 1 1 3
0 1 0 0 4
0 1 0 1 5
0 1 1 0 6
0 1 1 1 7
1 0 0 0 8
1 0 0 1 9 {(a, a), (b, b)}
1 0 1 0 10
1 0 1 1 11 {(a, a), (b, a), (b, b)}
1 1 0 0 12
1 1 0 1 13 {(a, a), (a, b), (b, b)}
1 1 1 0 14
1 1 1 1 15 {(a, a), (a, b), (b, a), (b, b)}

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

2. Largest irreflexive relation is _______

3. Total number of irreflexive relation will be ________

4. If two relations R1 and R2 are Irreflexive then their union and intersection will
also be Irreflexive (T / F).

5. If a relation R on a set A is reflexive, then RC is Irreflexive, and vice versa (T / F).

6. Any sub set of irreflexive relation will also be irreflexive(T / F).

7. If a relation is irreflexive then its inverse R-1 will also be irreflexive (T / F).

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 0 1 1 {(b, b)}
0 0 1 0 2 {(b, a)}
0 0 1 1 3 {(b, a), (b, b)}
0 1 0 0 4 {(a, b)}
0 1 0 1 5 {(a, b), (b, b)}
0 1 1 0 6 {(a, b), (b, a)}
0 1 1 1 7 {(a, b), (b, a), (b, b)}
1 0 0 0 8 {(a, a)}
1 0 0 1 9 {(a, a), (b, b)}
1 0 1 0 10 {(a, a), (b, a)}
1 0 1 1 11 {(a, a), (b, a), (b, b)}
1 1 0 0 12 {(a, a), (a, b)}
1 1 0 1 13 {(a, a), (a, b), (b, b)}
1 1 1 0 14 {(a, a), (a, b), (b, a)}
1 1 1 1 15 {(a, a), (a, b), (b, a), (b, b)}

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 0 1 1
0 0 1 0 2 {(b, a)}
0 0 1 1 3
0 1 0 0 4 {(a, b)}
0 1 0 1 5
0 1 1 0 6 {(a, b), (b, a)}
0 1 1 1 7
1 0 0 0 8
1 0 0 1 9
1 0 1 0 10
1 0 1 1 11
1 1 0 0 12
1 1 0 1 13
1 1 1 0 14
1 1 1 1 15

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)}

2. Largest symmetric relation is_______

3. Total number of symmetric relation will be _________

4. If a relation on a set A is symmetric then R __ R-1

5. If two relations R1 and R2 are symmetric then their Union and Intersection will also be
symmetric. (T / F)

6. If a relation is symmetric then its superset and subset will always be symmetric. (T / F)

7. If a relation is symmetric then its complement Rc will always be symmetric. (T / F)

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 0 1 1 {(b, b)}
0 0 1 0 2 {(b, a)}
0 0 1 1 3 {(b, a), (b, b)}
0 1 0 0 4 {(a, b)}
0 1 0 1 5 {(a, b), (b, b)}
0 1 1 0 6 {(a, b), (b, a)}
0 1 1 1 7 {(a, b), (b, a), (b, b)}
1 0 0 0 8 {(a, a)}
1 0 0 1 9 {(a, a), (b, b)}
1 0 1 0 10 {(a, a), (b, a)}
1 0 1 1 11 {(a, a), (b, a), (b, b)}
1 1 0 0 12 {(a, a), (a, b)}
1 1 0 1 13 {(a, a), (a, b), (b, b)}
1 1 1 0 14 {(a, a), (a, b), (b, a)}
1 1 1 1 15 {(a, a), (a, b), (b, a), (b, b)}

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 0 1 1 {(b, b)}
0 0 1 0 2
0 0 1 1 3
0 1 0 0 4
0 1 0 1 5
0 1 1 0 6 {(a, b), (b, a)}
0 1 1 1 7 {(a, b), (b, a), (b, b)}
1 0 0 0 8 {(a, a)}
1 0 0 1 9 {(a, a), (b, b)}
1 0 1 0 10
1 0 1 1 11
1 1 0 0 12
1 1 0 1 13
1 1 1 0 14 {(a, a), (a, b), (b, a)}

http://www.knowledgegate.in/gate
1 1 1 1 15 {(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

2. Largest Anti-symmetric relation will contain ________elements

3. Total number of Anti-symmetric relation will be _________

4. A relation R on a set A is Anti-Symmetric if (R ⋂ R-1) ⊑ ▲A (T / F)

5. Sub set of a Anti-Symmetric will also be (T / F)

6. Super set of a Anti-Symmetric will also be (T / F)

7. If two relations R1 and R2 are Anti-symmetric then their _________need not to be Anti-
symmetric but _________ will also be Anti-symmetric.

8. If a relation is Anti-symmetric then its complement Rc will always be Anti-symmetric. (T / F)

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 0 1 1 {(b, b)}
0 0 1 0 2 {(b, a)}
0 0 1 1 3 {(b, a), (b, b)}
0 1 0 0 4 {(a, b)}
0 1 0 1 5 {(a, b), (b, b)}
0 1 1 0 6 {(a, b), (b, a)}
0 1 1 1 7 {(a, b), (b, a), (b, b)}
1 0 0 0 8 {(a, a)}
1 0 0 1 9 {(a, a), (b, b)}
1 0 1 0 10 {(a, a), (b, a)}
1 0 1 1 11 {(a, a), (b, a), (b, b)}
1 1 0 0 12 {(a, a), (a, b)}
1 1 0 1 13 {(a, a), (a, b), (b, b)}
1 1 1 0 14 {(a, a), (a, b), (b, a)}
1 1 1 1 15 {(a, a), (a, b), (b, a), (b, b)}

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 0 1 1 {(b, b)}
0 0 1 0 2 {(b, a)}
0 0 1 1 3 {(b, a), (b, b)}
0 1 0 0 4 {(a, b)}
0 1 0 1 5 {(a, b), (b, b)}
0 1 1 0 6
0 1 1 1 7
1 0 0 0 8 {(a, a)}
1 0 0 1 9 {(a, a), (b, b)}
1 0 1 0 10 {(a, a), (b, a)}
1 0 1 1 11 {(a, a), (b, a), (b, b)}
1 1 0 0 12 {(a, a), (a, b)}
1 1 0 1 13 {(a, a), (a, b), (b, b)}
1 1 1 0 14
1 1 1 1 15

http://www.knowledgegate.in/gate
Q Consider a set A = {a, b, c} and R1, R2, R3 and R4 are relations on A which of the
following is not true?
Symmetric Anti-Symmetric True
1 R1 = {(a, a), (c, c)} Y Y
2 R2 = {(a, b), (b, a), (a, c)} N N
3 R3 = {(a, b), (b, c), (a, c)} N Y
4 R4 = {(a, b), (b, a), (c, c)} Y N

http://www.knowledgegate.in/gate
Q Consider the binary relation R = {(x, y), (x, z), (z, x), (z, y)} on the set {x,
y, z}. Which one of the following is TRUE?
(A) R is symmetric but NOT antisymmetric

(B) R is NOT symmetric but antisymmetric

(C) R is both symmetric and antisymmetric

(D) R is neither symmetric nor antisymmetric

http://www.knowledgegate.in/gate
• 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

2. Largest Asymmetric relation will contain _________elements

3. Total number of Asymmetric relation will be ________

4. Every asymmetric relation is also anti-symmetric (T / F)

5. Sub set of a Asymmetric will also be Asymmetric (T / F)

6. Super set of a Asymmetric will also be Asymmetric(T / F)

7. If two relations R1 and R2 are Asymmetric then their Union will also be Asymmetric(T / F).

8. If two relations R1 and R2 are Asymmetric then their Intersection will also be Asymmetric(T /
F).

http://www.knowledgegate.in/gate
9. If a relation is Asymmetric then its complement Rc will always be Asymmetric. (T / F)
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 0 1 1 {(b, b)}
0 0 1 0 2 {(b, a)}
0 0 1 1 3 {(b, a), (b, b)}
0 1 0 0 4 {(a, b)}
0 1 0 1 5 {(a, b), (b, b)}
0 1 1 0 6 {(a, b), (b, a)}
0 1 1 1 7 {(a, b), (b, a), (b, b)}
1 0 0 0 8 {(a, a)}
1 0 0 1 9 {(a, a), (b, b)}
1 0 1 0 10 {(a, a), (b, a)}
1 0 1 1 11 {(a, a), (b, a), (b, b)}
1 1 0 0 12 {(a, a), (a, b)}
1 1 0 1 13 {(a, a), (a, b), (b, b)}
1 1 1 0 14 {(a, a), (a, b), (b, a)}
1 1 1 1 15 {(a, a), (a, b), (b, a), (b, b)}

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 0 1 1
0 0 1 0 2 {(b, a)}
0 0 1 1 3
0 1 0 0 4 {(a, b)}
0 1 0 1 5
0 1 1 0 6
0 1 1 1 7
1 0 0 0 8
1 0 0 1 9
1 0 1 0 10
1 0 1 1 11
1 1 0 0 12
1 1 0 1 13
1 1 1 0 14
1 1 1 1 15

http://www.knowledgegate.in/gate
• 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 {(2,3), (1,2)}
http://www.knowledgegate.in/gate
1. Smallest Transitive relation is ______

2. Largest Transitive relation will contain __________ elements

3. If two relations R1 and R2 are Transitive then their _______ need not
to be transitive but ___________ will also be transitive.

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 0 1 1 {(b, b)}
0 0 1 0 2 {(b, a)}
0 0 1 1 3 {(b, a), (b, b)}
0 1 0 0 4 {(a, b)}
0 1 0 1 5 {(a, b), (b, b)}
0 1 1 0 6 {(a, b), (b, a)}
0 1 1 1 7 {(a, b), (b, a), (b, b)}
1 0 0 0 8 {(a, a)}
1 0 0 1 9 {(a, a), (b, b)}
1 0 1 0 10 {(a, a), (b, a)}
1 0 1 1 11 {(a, a), (b, a), (b, b)}
1 1 0 0 12 {(a, a), (a, b)}
1 1 0 1 13 {(a, a), (a, b), (b, b)}
1 1 1 0 14 {(a, a), (a, b), (b, a)}
1 1 1 1 15 {(a, a), (a, b), (b, a), (b, b)}

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 0 1 1 {(b, b)}
0 0 1 0 2 {(b, a)}
0 0 1 1 3 {(b, a), (b, b)}
0 1 0 0 4 {(a, b)}
0 1 0 1 5 {(a, b), (b, b)}
0 1 1 0 6
0 1 1 1 7
1 0 0 0 8 {(a, a)}
1 0 0 1 9 {(a, a), (b, b)}
1 0 1 0 10 {(a, a), (b, a)}
1 0 1 1 11 {(a, a), (b, a), (b, b)}
1 1 0 0 12 {(a, a), (a, b)}
1 1 0 1 13 {(a, a), (a, b), (b, b)}
1 1 1 0 14
1 1 1 1 15 {(a, a), (a, b), (b, a), (b, b)}

1
Column
2

Row 3

1
Column
2

Row 3

http://www.knowledgegate.in/gate
Q The binary relation R= {(1,1), (2,1), (2,2), (2,3), (2,4), (3,1), (3,2), (3,3),
(3,4)} on the set A = {1,2,3,4} is
(a) reflexive, symmetric and transitive

(b) neither reflexive, nor irreflexive but transitive

(c) irreflexive, symmetric and transitive

(d) irreflexive and antisymmetric

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
Q Let S be a set of n elements. The number of ordered pairs in
the largest and the smallest equivalence relations on S are
(A) n and n (B) n2 and n
(C) n2 and 0 (D) n and 1

• We can have [x] = [y], even if x != y

http://www.knowledgegate.in/gate
Q Consider A = {1, 2, 3, 4, 5} an equivalence relation R on A, R =
{(1,1),(2,2),(3,3),(4,4),(5,5),(1,4),(4,1),(2,5),(5,2)} find the partition of a
set A, defined by R.
[1] =
[2] =
[3] =
[4] =
[5] =

http://www.knowledgegate.in/gate
Partitions of a Set: - let A be a set, with n elements. Based on our
understanding of equivalent classes, a subdivision of A into non-empty
and non-overlapping subset is called a partition of A.

A1 U A2 U A3 U ………….. U An = A

A1 ⋂ A2 ⋂ A3 ⋂ ………….. ⋂ An = ɸ

http://www.knowledgegate.in/gate
Q Consider A = {1, 2, 3, 4, 5} an equivalence relation R on A, R =
{(1,1),(2,2),(3,3),(4,4),(5,5),(1,4),(4,1),(2,5),(5,2)} find the partition of a
set A, defined by R.
[1] = {1, 4}
[2] = {2, 5}
[3] = {3}
[4] = {1,4}
[5] = {2, 5}

so we have partitions =

http://www.knowledgegate.in/gate
Q Let A = {1,2,3,4,5} is a set having partitions as {1, 4}, {2, 3, 5} , find the
equivalence relation from which these partitions are created?

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

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

http://www.knowledgegate.in/gate
• Total order relation: - A Poset [A, R] is called a total order set, if
every pair of elements are comparable i.e. either (a, b) or (b, a) ∈ R,
for ∀ a, b ∈ A

• For e.g. A = {1, 2, 3, 6}, then Poset [A,/] is not a total order relation
but A = {1,2,4,8} will be

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.
• 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)}

(1) (2)

http://www.knowledgegate.in/gate
(3) (4) (5)

http://www.knowledgegate.in/gate
(5) (6) (7)

http://www.knowledgegate.in/gate
(8) (9) (10)
Conclusion
• We can not have a horizontal edge in a hasse diagram
• We can not have a reflexive and transitive edge in Hasse Diagram

http://www.knowledgegate.in/gate
Q Let X = {2,3,6,12,24}, Let ≤ be the partial order defined by X ≤ Y if x
divides y. Number of edges as in the Hasse diagram of (X, ≤) is.
(a) 3 (b) 4 (c) 9 (d) None of the above

Greatest Lower Bound / GLB / Meet / Infimum / ∧

Greatest value in the lower bound

http://www.knowledgegate.in/gate
Join Semi Lattice :- A hasse diagram/Partial order relation is called Join Semi
Lattice if for every elements their exists a Join.

Meet Semi Lattice :- A hasse diagram/Partial order relation is called Meet Semi
Lattice if for every elements their exists a Meet.

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
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 complement(zero or one).
• Complement Lattice :- A Lattice is said to be Complement lattice. if for every
element their exist at least one complement(one or more).
• 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.

(2) [{2,3,4,6,12}, /]

(3) [{1,2,3,5,30}, /]

(4) [{1,2,3,6,9,18}, /]

(5) [{2,3,4,9,12,18}, /]

(6) [R, <=]

(7) [P(A), ⊑], A = {1,2,3}

b) subset {a, b, f, g} is a lattice

c) subset {a, d, e, g} is a lattice

d) subset {a, c, e, g} is a lattice

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
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 = ?

http://www.knowledgegate.in/gate
Q Let X and Y denote the sets containing 2 and 20 distinct objects respectively and
F denote the set of all possible functions defined from X and Y. Let f be randomly
chosen from F. The probability of f being one-to-one is _________

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
Q How many onto (or surjective) functions are there from an n-element
(n >= 2) set to a 2-element set?
(A) 2n (B) 2n – 1 (C) 2n – 2 (D) 2(2n – 2)

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 = 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
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
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.

• 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
•Chapter-5 (Graph Theory)

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.

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.

2. For simple graph we can say if the number of vertices are finite then number of
edges will also be finite.

1. Trivial Graph: A graph with only one vertex without an edge is called trivial
graph. It is the smallest possible.

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.

2. Number of edges in a simple 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).

• Pendant vertex: A vertex with degree one is called pendant vertex.

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
Q A simple graph G contains 21 edges, 3 vertices of degree 4 and all the
remaining vertices are of degree 2. Then number of vertices |v| is?

http://www.knowledgegate.in/gate
Q Consider a simple graph with 35 edges such that 4 vertex of
degree 5, 5 vertex of degree 4, 4 vertex of degree 3, find the
number of vertex with degree 2?

http://www.knowledgegate.in/gate
Q Simple non-directed graph G has 24 edges and degree of each
vertex is K, the which of the following is possible no of vertices?
a) 20 b) 15 c) 10 d) 8

• Δ(G) is the maximum possible degree of any vertex in a graph.

http://www.knowledgegate.in/gate
Q G is undirected graph with n vertices and 25 edges such that each
vertex has degree at least 3. Then the maximum possible value of n is
________

http://www.knowledgegate.in/gate
1. The Havel–Hakimi algorithm is an algorithm in graph theory solving the graph realization
problem. That is, it answers the following question: Given a finite list of nonnegative integers,
is there a simple graph such that its degree sequence is exactly this list.

2. Here, the "degree sequence" is a list of numbers that for each vertex of the graph states how
many neighbors it has. For a positive answer the list of integers is called graphic.

3. The algorithm constructs a special solution if one exists or proves that one cannot find a
positive answer. This construction is based on a recursive algorithm. The algorithm was
published by Havel (1955), and later by Hakimi (1962).

2) {2, 3, 4, 4, 5}

3) {3, 3, 3, 1}

http://www.knowledgegate.in/gate
4) {1, 3, 3, 4, 5, 6, 6}

5) {2, 3, 3, 3, 3}

6) {6, 6, 6, 6, 4, 3, 3, 0}

7) {6, 5, 5, 4, 3, 3, 2, 2, 2}

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
• 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)

2. G ⋂ Gc = null graph

3. |E(G)| + |E(Gc)| = E(Kn) = n(n-1)/2

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, such that each edge is incident with the vertices
preceding and following it. Both vertex and edges may appear more than once.
• An open walk in graph theory is a walk that starts and ends
at different vertices, whereas a closed walk starts and ends
at the same vertex.
• An open walk becomes a path when it does not revisit any
vertices Number of edges in a path is called length of a
path.

Traversal Walk Open Walk Closed Walk Path

V1 g V3 b V2 e V4 d V3 b V2
V1 a V2 e V4 d V3 b V2 f V5
V1 g V3 c V3 b V2 a V1
V1 a V2 b V3 d V4 h V5

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.
• if a graph (connected or disconnected) has exactly two vertices of odd degree,
there must be a path joining these two vertices

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
• 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.
• 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
Euler
Graph
Hamiltonian
Graph

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
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
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
• Euler's formula can be proved by mathematical induction

(a) 10

(b) 11

(d) 6

http://www.knowledgegate.in/gate
Q Let G be a simple connected planar graph with 13 vertices and 19 edges.
Then, the number of faces in the planar embedding of the graph is
(A) 6 (B) 8 (C) 9 (D) 13

http://www.knowledgegate.in/gate
Other formula derived from Euler’s formula
• Connected planar graphs with more than one edge obey the inequality 2e>=3r,
because each face has at least three face-edge incidences and each edge
contribute exactly two incidences.

• Degree of the region is number of edges covering the region. Sum of degree of
regions = 2|E|

• 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.

http://www.knowledgegate.in/gate
• 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
• Cost of finding chromatic number is an NPC problem and there exists no
polynomial algorithm to do that. There exists some greedy approach which try
to solve it in P time, but they do not guarantee optimal solution.

http://www.knowledgegate.in/gate
• 5-color theorem-any planer graph is at most 5-chromatic
• 4-colour theorem/hypothesis- any planer graph is 4-chromatic
• If Δ(G) is the maximum degree of any vertex in a graph then, χ(G) <= 1 + Δ(G)

http://www.knowledgegate.in/gate
Eccentricity: - Eccentricity of a vertex is denoted by E(v) of a
vertex v in a graph G, it is the distance from V to the vertex
farthest from V in G. E(v) = max d(v, vi) vi ϵ G

http://www.knowledgegate.in/gate
• A vertex with minimum eccentricity in a tree T is called center of T.
• Minimum eccentricity of any vertex in a tree T is called radius of tree.
(eccentricity of center)
• Maximum eccentricity of any vertex in a tree T is called diameter of tree. (length
of the longest path)

http://www.knowledgegate.in/gate
• An edge in a spanning tree T is called a branch of T
• An edge that is not in the given spanning tree T is called a chord.
• Branch and Chord are defined with respect to a given spanning tree.

http://www.knowledgegate.in/gate
1. With respect to any of its spanning tree, a connected graph of n vertices and e edges has n-1
branches and e-n+1 chord
2. A connected graph G is a tree if and only if adding an edge between any two vertices in g
creates exactly one cycle.
3. Rank(r) = n-1
4. Nullity(µ) = e – n + 1
5. Rank + nullity = number of edges in G

http://www.knowledgegate.in/gate
Spanning Forest: - if a graph is not connected, then there is no possibility of finding a spanning
tree, but we can find a spanning forest. If a graph is not connected then we can find connected
components, finding a spanning tree in each component we can find spanning forest.
A disconnected graph with K components has a spanning forest consisting of K spanning tree.

http://www.knowledgegate.in/gate
Fundamental circuit: - With respect to a spanning tree T in a connected graph G,
adding any one chord to T will create exactly one circuit such a circuit formed by
adding a chord to a spanning tree is called fundamental circuit.

http://www.knowledgegate.in/gate
Cut-Set (edge and vertex connectivity)
Cut-Set (Edges)
Cut Set: - In a connected graph G, a cut set is a set of edges whose removal from g
leaves G disconnected, provided removal of no proper subset of these edges
disconnects G.

Cut Set Validity

{a, f, g}
{a, e, h, c}
{a, i}
{e, h, f, g}
{d, h, c, g}
{d, e, f}
http://www.knowledgegate.in/gate
Connectivity: - each cut-set of a connected graph G consist of a certain
number of edges. The number of edges in the smallest cut-set is defined
as the edges connectivity of G. It is denoted by λ(G).
• if the edge connectivity from a graph is one, then that edge how’s
removal disconnect the graph is called a bridge.

http://www.knowledgegate.in/gate
k(G)
λ(G)
δ(G)

http://www.knowledgegate.in/gate
• Every Cut Set in a connected graph G must contain at least
one branch of every spanning tree of G.
• Every circuit has an even number of edges in common with
any Cut-Set.

http://www.knowledgegate.in/gate
k(G)
λ(G)
δ(G)

http://www.knowledgegate.in/gate
Cut-Set (Vertex)
Cut Set: - In a connected graph G, a cut set is a set of vertices whose removal from
g leaves G disconnected, provided removal of no proper subset of these vertices
disconnects G.
Cut Set Validity
{5, 3}
{6}
{5, 2}
{2}
{1, 5, 3}

http://www.knowledgegate.in/gate
Vertex Connectivity: - Each cut-set of a connected graph G consist of a certain
number of vertices. The number of vertices in the smallest cut-set is defined as the
vertex connectivity of G. It is denoted by k(G).
• A connected graph is said to be separable of its vertex connectivity is one.
• If the vertex connectivity of a graph is one, then that vertex how removal
disconnects a graph is called articulation point.

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.
2. Formally speaking: - Two graphs G and G’ are said to be isomorphic, if there is a one to one
correspondence between their vertices and between their edges such that the incidence
relationship is preserved.

http://www.knowledgegate.in/gate
1. Determining if two graphs are isomorphic is thought to be neither an NP-
complete problem nor a P-problem, although this has not been proved.

2. In fact, there is a famous complexity class called graph isomorphism

complete which is thought to be entirely disjoint from both NP-complete and
from P.

http://www.knowledgegate.in/gate
How to check weather two graphs are isomorphic or not
1. Number of vertices
2. Number of edges
3. Number of vertices with a given degree
4. Check degree property of vertices with their neighbor
5. Check minimum cycle length, maximum cycle length, or
number of cycle with a specific length
6. Can check isomorphism for complement of the graph
7. Planer, non-planer
8. Connected disconnected
9. Chromatic number
10. Matching number, covering number
11. Edge connectivity, vertex connectivity
12. If it seems that graphs are isomorphic to each other then
identify the similar vertex and delete both, and keep
repeating the process until we are sure..

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
Matching: - Let G be a graph, a subgraph M of G is called a matching of G, if every vertex of G is
incident with at most one edge in M.
deg(v) <= 1, ∀v VϵV(G)

M1 M2 M3 M4

• In matching no two edges are adjacent

http://www.knowledgegate.in/gate
Maximal Matching: - A matching M of a graph G is said to be maximal, if no other edges of G can be added to M,
without violating the deg condition.

Maximum Matching: - A matching of a graph with maximum no of edges is called a maximum matching of G.
• Number of edges in a maximum matching of G is called matching number.

M1 M2 M3 M4

http://www.knowledgegate.in/gate
Perfect Matching: - A matching of a graph in which every vertex is matched is called perfect
matching.
1. If a graph G has a perfect match then no of vertices in G is even.
2. If no of vertexes is even, it is not necessary to have a perfect match.
3. No of perfect matchings are there in a complete graph Kn is [(2n)!]/n!2n

M1 M2 M3 M4

http://www.knowledgegate.in/gate
Covering
Line Covering: - Let G (V, E) be a graph, a subset C of E is called a line covering of G, if every
vertex of G is incident with at least one edge in C. (deg at least one)
deg(v) >= 1

C1 C2 C3 C4

• Line covering of a graph G does not exist if G has an isolated vertex

http://www.knowledgegate.in/gate
• Minimal Line covering: - A line covering is said to be minimal if no edge can be
deleted from the line covering, without destroying its ability to cover the graph.
• Minimum line covering: - A line covering with minimum no of edges is called a
minimum line covering.

C1 C2 C3 C4

http://www.knowledgegate.in/gate
• No of edges in minimum line covering is called line covering number of a graph
G, denoted by α1
• line covering of a graph with n vertices contain at least upper bound(n/2) edges.
• no minimal line covering can contain a cycle.

http://www.knowledgegate.in/gate
Independent Line set: - Let G (V, E) be a graph, a subset L of E is called
independent line set of G, if no two edges are adjacent.
L1 = {(b, d)}
L2 = {(b, d), (e, f)}
L3 = {(a, d), (b, c), (e, f)}
L4 = {(a, b), (e, f)}
L5 = {(a, b), (d, c), (e, f)}

http://www.knowledgegate.in/gate
• Maximal independent Line set: - An independent line set L of a graph G is said to be maximal if no
other edges of G can be added to L.
• Maximum independent line set: - An independent line set L of a graph G, with maximum no of edges is
called maximum independent line set.
• No of edges in maximum independent line set is called Line independent number of G denoted by β1.
• line independent no = matching no of G

α1 + β1 = |v|
L1 = {(b, d)}
L2 = {(b, d), (e, f)}
L3 = {(a, d), (b, c), (e, f)}
L4 = {(a, b), (e, f)}
L5 = {(a, b), (d, c), (e, f)}

http://www.knowledgegate.in/gate
Vertex Covering: - Let G (V, E) be graph, a subset K of V is called a vertex coving of
G. if every edge of G is incident with a vertex in K.

K1 = {b, d}
K2 = {a, b, c}
K3 = {b, c, d}
K4 = {a, b, c, d}

http://www.knowledgegate.in/gate
Minimal vertex cover: - Vertex covering K of a graph G is said to be minimal if no vertex can be deleted
from K, without violating the condition.
Minimum vertex covering: - A vertex covering of a graph G with minimum number of vertices is called as
minimum vertex covering.
• No of vertices in a minimum vertex covering is called vertex Covering no of graph G denoted by α2

K1 = {b, d}
K2 = {a, b, c}
K3 = {b, c, d}
K4 = {a, b, c, d}

http://www.knowledgegate.in/gate
Independent vertex set: - let G (V, E) be a graph, a subset S of V is called an
independent vertex set if no two vertices in S are adjacent.

S1 = {b}
S2 = {d, e}
S3 = {a, c}
S4 = {a, b, c}
S5 = {a, c, e}

http://www.knowledgegate.in/gate
Maximum independent Vertex Set: - An independent vertex set is said to be maximal, if no other vertex
of G can be added to the set.
Maximum independent vertex set: - An independent vertex set of graph G with maximum no of vertices
is called maximum independent vertex set.
The number of vertices in maximum independent vertex set is called as vertex independent number of G
donated by β2
α2 + β2 = |V|

S1 = {b}
S2 = {d, e}
S3 = {a, c, e}

http://www.knowledgegate.in/gate
•Chapter-6 (Group Theory):

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. 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
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
2
(N, +)
(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, -)
7 (Z, /)
an algebraic structure with respect to a binary 8 (Z, x)
9 (R, +)
operation *, if A satisfy closure property with respect 10 (R, -)
to *. 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
4 (N, x) Y
(a*b) *c = a*(b*c) 5 (Z, +) Y
6 (Z, -) Y
7 (Z, /) N
2. Semi-Group: - A non-empty set A is said to be a Semi- 8 (Z, x) Y
group with respect to a binary operation *, if A satisfy 9
10
(R, +)
(R, -)
Y
Y
closure, Associative property with respect to *. 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
21 (Non-Singular Y
Matrix, x)

http://www.knowledgegate.in/gate
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

http://www.knowledgegate.in/gate 21 (Non-Singular
Matrix, x)
Y Y Y
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 Consider a set of natural numbers N, with respect to *, such that
a * b = ab which of the following is true?
a) semi group but not monoid b) A monoid but not a group

c) A group d) not a semi group

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

b) semi-group

c) Monoid

d) group

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

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

d) set of complex number, X

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 = (aXb)/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

• 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.

+ 0 * 1
0 1

3- {0,1}, + 4- {0,1}, X 5- {-1, 0, 1}, + 6- {-1, 0, 1}, X

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

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

* -2 -1 0 1 2 * 1 ω ω2 * -1 1 i -i
-2
1 -1
-1
ω 1
0
1 ω2 i
2 -i

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.

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

• a +m b = a + b - m if (a + b >= m)

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

• a Xm b = a X b if (a X b < m)

• a Xm b = (a X b) % m if (a X b >= m)
X5 1 2 3 4
1
{1,2,3,4}, X5
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}, X4
+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}, X4
+4 1 2 3 *4 1 2 3
1 1
2 2
3 http://www.knowledgegate.in/gate
3
5- {0,1,2,3,4,5,6}, +7 6- {0,1,2,3,4,5,6}, X7
+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
7- {1,2,3,4,5,6}, +7 8- {1,2,3,4,5,6}, X7
+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}, X8 14- {1,2,4,7,8,11,13,14}, X15

*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

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

a) it is closed

b) it does not form a group

c) it forms a group but not an abelian group

d) it is an abelian 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}, X8 which of the following sub set of this set does not form is sub
group?
a) {1,3} b) {1,5} c) {1,7} d) {1,3,7}
*8 1 3 *8 1 5 *8 1 7 *8 1 3 7

1 1 1 1

3 5 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

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.

5. Order of a group is always divisible by order of every element of the group.

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….}

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.
3. Cyclic group is always alelian group.
4. Every group of order prime no is always always cyclic group where every
number expect identity is generator.

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)

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 and S3

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

http://www.knowledgegate.in/gate
Proposition
• First we must look at the difference between Scientist and Philosopher. Philosopher give an
idea or theory which may have different interpretation from person to person. It depends on
the wisdom of a person.

Confucius Laozi
http://www.knowledgegate.in/gate
• Logic in Reasoning: Developed by Aristotle, it's a precise method for
reasoning.
• Beyond Propositions: Other reasoning methods exist for problem-solving.
• Role of Logic: Central to mathematical statements, automated reasoning,
and computer science.
• Proofs and Theorems: Correct arguments in math called proofs; proven
statements are theorems.
• Propositional Calculus: A section of logic, also known as propositional or
predicate logic, formalized by Aristotle.
• Generating Propositions: George Boole discussed methods in "The Laws of
Thought" (1854).

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 is a statement that provides reason or support for the
conclusion(proposition). Premises(proposition) is always considered to be true.
• 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
• Law of contradiction - the law of non-contradiction (LNC) (also known as the law
of contradiction, principle of non-contradiction (PNC), or the principle of
contradiction) states that, ”Contradictory propositions cannot both be true in
the same sense at the same time”.
• e.g. the two propositions "A is B" and "A is not B" are mutually exclusive.

• Law of excluded middle - The law of excluded middle (or the principle of
excluded middle) states that for any proposition, either that proposition
is true or its negation is true.

http://www.knowledgegate.in/gate
Types of proposition
• We use letters to denote propositional variables to represent propositions, just as letters are
used to denote numerical variables. The conventional letters used for propositional variables
are p, q, r, s.

• 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”.

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 P1 ¬(p ∧ q)
Q p Q p∧q P2 q P2 P
Q p∧q Q ¬q

5 6 7
P1 ¬ (p ∧ q) P1 ¬ (p ∧ q) P1 ¬ (p ∧ q)
P2 q P2 ¬p P2 ¬p
Q ¬p Q q Q ¬q

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 3 4
P1 (p ∧ q) P1 p∨q P1 ¬(p ∨ q) P1 (p ∨ q)
Q p∨q Q (p ∧ q) Q ¬p Q ¬p

5 6 7 8
P1 (p ∨ q) P1 (p ∨ q) P1 (p ∨ q) P1 (p ∨ q)
P2 ¬p P2 ¬q P2 p P2 p
Q q Q p Q ¬q Q q

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.

Implication
p q p→q
F F
F T
T F
T T
http://www.knowledgegate.in/gate
• Let p be the statement “Tori learns discrete mathematics” and q the statement “Tori will find
a good job.” Express the statement p → q as a statement in English.

1. “If Tori learns discrete mathematics, then she will find a good job.”

2. “Tori will find a good job when she learns discrete mathematics.”

3. “For Tori to get a good job, it is sufficient for her to learn discrete mathematics.”

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

• q → p converse

• ¬p → ¬q inverse

• ¬q → ¬p contra positive

• p → q = ¬q → ¬p

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

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

3 4
P1 ¬(p→q) P1 ¬(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”.
• “p is necessary and sufficient for q” Bi-conditional
• “if p then q, and conversely”
• “p iff q.” p q P↔q
• p←→ q = (p → q ) ∧ ( q → p) F F
• The biconditional statement p ↔ q is true when
p and q have the same values, and false otherwise. 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∨q P1 p∨q P1 p→r
P2 q→r P2 p→r P2 p→r P2 q→s
Q p→r P3 q→r P3 q→s P3 ¬r∨¬s
Q r Q r∨s Q ¬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 two well-formed formulas in propositional logic
F1:P⇒¬P F2:(P⇒¬P) ∨ (¬P⇒P)
Which one of the following statements is correct?

A) F1 is satisfiable, F2 is valid

B) F1 unsatisfiable, F2 is satisfiable

C) F1 is unsatisfiable, F2 is valid

http://www.knowledgegate.in/gate
D) F1 and F2 are both satisfiable
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

a) 1 only b) 1 and 4 only c) 2 only d) 2 and 3 only

S2: If a candidate is kind, he will be elected.

Which one of the following statements follows from S1 and S2 as per sound
inference rules of logic?

(A) If a person is known to be corrupt, he is kind

(B) If a person is not known to be corrupt, he is not kind

(C) If a person is kind, he is not known to be corrupt

(D) If a person is not kind, he is not known to be corrupt

c) (¬p ∧ q) ∨ (p ∧ ¬q) d) (¬p ∧ ¬q) ∨ (p ∧ q)

L: P implies Q
M: Q implies P
N: P is equivalent to Q

Which one of the following about L, M, and N is CORRECT?

(A) Only L is TRUE.
(B) Only M is TRUE.
(C) Only N is TRUE.
http://www.knowledgegate.in/gate
(D) L, M and N are TRUE
Q Which one of the following Boolean expressions is NOT a tautology?
A) ((a → b) ∧ (b → c)) → (a → c) B) (a → c) → (∼b → (a ∧ c))

C) (a ∧ b ∧ c) → (c ∨ a) D) a → (b → a)

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.

Which of the following is TRUE?

(A) Both I1 and I2 are correct inferences
(B) I1 is correct but I2 is not a correct inference
(C) I1 is not correct but I2 is a correct inference
(D) Both I1 and I2 are not correct inferences
http://www.knowledgegate.in/gate
Q Consider the following propositional statements:
P1 : ((A ∧ B) → C)) ≡ ((A → C) ∧ (B → C))

P2 : ((A ∨ B) → C)) ≡ ((A → C) ∨ (B → C))

Which one of the following is true?

(A) P1 is a tautology, but not P2
(B) P2 is a tautology, but not P1
(C) P1 and P2 are both tautologies
http://www.knowledgegate.in/gate
(D) Both P1 and P2 are not tautologies
Q Which of the following is/are a tautology?
a) a ∨ b → b ∧ c b) a ∧ b → b ∨ c

c) a ∨ b → (b → c) d) a → b → (b → c)

I2: today is oct 2nd

C: today is Gandhi ji’s birthday

I2: London is not a city

C: Canada is not a country

2) ¬ (p ∨ q) ∨ (¬p ∧ q) ∨ p = T

3) ((p → q) ←→ (¬q → ¬p)) ∧ r = r

5) (p ∨ ¬ (p ∧ q)) = T

6) (p ∧ q) ∧ (¬p ∨ ¬q) = F

7) (¬p ∧ (¬q ∧ r)) ∨ (q ∧ r) ∨ (p ∧ r) = r

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.

• 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.

• 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.

• 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

• 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
Negation

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

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

1- ∀x∀y L(x, y) 5- ∀x ∃y L(x, y)

2- ∀y∀x L(x, y) 6- ∃y ∀x L(x, y)

3- ∃x ∃y L(x, y) 7- ∀y ∃x L(x, y)

4- ∃y ∃x L(x, y) 8- ∃x ∀y L(x, y)

3 4
P1 ∃x P(x) ∧ ∃x Q(x) P1 ∃x (P(x) ∧ Q(x))
Q ∃x (P(x) ∧ Q(x)) Q ∃x P(x) ∧ ∃x Q(x)

3 4
P1 ∀x P(x) ∧ ∀x Q(x) P1 ∀x (P(x) ∧ Q(x))
Q ∀x (P(x) ∧ Q(x)) Q ∀x P(x) ∧ ∀x Q(x)

b) ∀x [¬P(x) → Q(x)]

c) ¬ {∀x [P(x) → Q(x)]}

d) ¬ {∀x [¬P(x) → Q(x)]}

http://www.knowledgegate.in/gate
Q let in a set of all integers
G (x, y): x is greater than y
“for any given positive integer, there is a greater positive integer”
a) ∀x ∃y G (x, y)

b) ∃y ∀x G (x, y)

c) ∀y ∃x G (x, y)

d) ∃x ∀y G (x, y)
http://www.knowledgegate.in/gate
Q let in a set of all humans
L (x, y): x likes y
“there is someone, whom no one like”
a) ∀x ∃y {¬L (x, y)}

b) {¬ ∀x ∃y L (x, y)}

c) ¬ {∀y ∃x L (x, y)}

d) ¬ {∃Y ∀X L (x, y)}

http://www.knowledgegate.in/gate
Q The CORRECT formula for the sentence, “not all rainy days are cold”
is (GATE-2014) (2 Marks)
a) ∀d (Rainy(d) ∧ ~Cold(d)) b) ∀d (~Rainy(d) → Cold(d))

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

http://www.knowledgegate.in/gate
Q What is the logical translation of the following
lowing statement? (GATE-2013) (2 Marks)
"None of my friends are perfect."
A) ∃x(F(x) ∧ ¬P(x)) B) ∃x(¬F(x) ∧ P(x))

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

http://www.knowledgegate.in/gate
Q Which one of the following options is CORRECT given three positive integers x, y and z, and a
predicate? (GATE-2011) (2 Marks)
P(x) = ¬(x=1) ∧∀y(∃z(x=y*z) ⇒(y=x) ∨(y=1))
(A) P(x) being true means that x is a prime number

(B) P(x) being true means that x is a number other than 1

(C) P(x) is always true irrespective of the value of x

(D) P(x) being true means that x has exactly two factors other than 1 and x

Which of the above are equivalent? (GATE-2009) (2 Marks)

a) I and III
b) I and IV
c) II and III
d) II and IV

http://www.knowledgegate.in/gate
Q Which one of the following is the most appropriate logical formula to represent
the statement? “Gold and silver ornaments are precious”. The following notations
are used:
G(x): x is a gold ornament
S(x): x is a silver ornament
P(x): x is precious (GATE-2009) (2 Marks)
(A) ∀x (P(x) → (G(x) ∧ S(x)))

(B) ∀x ((G(x) ∧ S(x)) → P(x))

(C) ∃x ((G(x) ∧ S(x)) → P(x)

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

http://www.knowledgegate.in/gate

DBMS UNIT 2 Btech 2-2 Jntuh
No ratings yet
DBMS UNIT 2 Btech 2-2 Jntuh
21 pages
WFF and Properties
No ratings yet
WFF and Properties
10 pages
978 93 56819 89 4 GATE 2025 Computer Science Toic Wise
No ratings yet
978 93 56819 89 4 GATE 2025 Computer Science Toic Wise
45 pages
RGPV Syllabus Cs112 Fundamentals of Computer Science and Engineering
No ratings yet
RGPV Syllabus Cs112 Fundamentals of Computer Science and Engineering
2 pages
Database Management System Kcs 501 1
No ratings yet
Database Management System Kcs 501 1
2 pages
DWDM (BCS058) 2nd UNIT NOTES
No ratings yet
DWDM (BCS058) 2nd UNIT NOTES
39 pages
Cyber Previous Paper
50% (2)
Cyber Previous Paper
2 pages
Unit-1, BCS603, Computer Network
No ratings yet
Unit-1, BCS603, Computer Network
36 pages
Unit II 2
No ratings yet
Unit II 2
20 pages
LR (0) Parser
No ratings yet
LR (0) Parser
8 pages
Library Management System Test Plan
No ratings yet
Library Management System Test Plan
12 pages
Fdsa Unit 5
No ratings yet
Fdsa Unit 5
48 pages
Image Enhancement Techniques Overview
No ratings yet
Image Enhancement Techniques Overview
210 pages
Cyber Security Unit-3
No ratings yet
Cyber Security Unit-3
22 pages
2marks For Pondicherry University
No ratings yet
2marks For Pondicherry University
45 pages
Python Notes 3rd Mca
No ratings yet
Python Notes 3rd Mca
99 pages
Automata (Unit - 2)
No ratings yet
Automata (Unit - 2)
8 pages
DBMS Practical Exercises and Queries
100% (1)
DBMS Practical Exercises and Queries
19 pages
Compiler Design
No ratings yet
Compiler Design
7 pages
python-notes-BCC-302 (Unit - 05)
No ratings yet
python-notes-BCC-302 (Unit - 05)
25 pages
UNIT - 5 3D Object Representation
No ratings yet
UNIT - 5 3D Object Representation
59 pages
OS in 6 Hours
No ratings yet
OS in 6 Hours
73 pages
Digital Image Processing Lecture Notes: M.Sc. Cs - (Iv Sem) (2020-2021)
No ratings yet
Digital Image Processing Lecture Notes: M.Sc. Cs - (Iv Sem) (2020-2021)
28 pages
Business Intelligence and Analytic Kds051
No ratings yet
Business Intelligence and Analytic Kds051
2 pages
BARC 2025 Computer Science Model Paper
No ratings yet
BARC 2025 Computer Science Model Paper
19 pages
DBMS Unit 4: Transaction Management Notes
No ratings yet
DBMS Unit 4: Transaction Management Notes
29 pages
TOC Solutions Adi
No ratings yet
TOC Solutions Adi
58 pages
Best Books For UGC NET CS
No ratings yet
Best Books For UGC NET CS
38 pages
Database Transaction Concepts
No ratings yet
Database Transaction Concepts
60 pages
Mca Ai
No ratings yet
Mca Ai
228 pages
Noc20 Cs81 Assignment 01 Week 06
No ratings yet
Noc20 Cs81 Assignment 01 Week 06
5 pages
Object Modeling: Associations and Aggregation
80% (5)
Object Modeling: Associations and Aggregation
14 pages
Data & Info Security Q&A Guide
No ratings yet
Data & Info Security Q&A Guide
5 pages
ML Unit-4
No ratings yet
ML Unit-4
40 pages
Assignment #2 AI
No ratings yet
Assignment #2 AI
5 pages
Enhancing Linear Regression Models
No ratings yet
Enhancing Linear Regression Models
18 pages
CB3491 - CCS Syllabus
No ratings yet
CB3491 - CCS Syllabus
2 pages
Previous University Question Paper
No ratings yet
Previous University Question Paper
3 pages
Artificial Intelligence PPT-7 - Inference in FOL
No ratings yet
Artificial Intelligence PPT-7 - Inference in FOL
46 pages
CD LAB Manual R-22
No ratings yet
CD LAB Manual R-22
73 pages
Unit 2
No ratings yet
Unit 2
11 pages
TCS Codevita Season 13
No ratings yet
TCS Codevita Season 13
28 pages
DSM Module 1
No ratings yet
DSM Module 1
60 pages
Lab Manual-Artificial
No ratings yet
Lab Manual-Artificial
26 pages
Expert System Practical File (1-6)
No ratings yet
Expert System Practical File (1-6)
16 pages
HMAC and CMAC: Cryptographic Overview
No ratings yet
HMAC and CMAC: Cryptographic Overview
14 pages
Cns Unit2
No ratings yet
Cns Unit2
147 pages
Data Warehousing & Mining Overview
75% (4)
Data Warehousing & Mining Overview
14 pages
Introduction to IT Systems Q&A Guide
No ratings yet
Introduction to IT Systems Q&A Guide
9 pages
Python Notes (KNC-402)
No ratings yet
Python Notes (KNC-402)
136 pages
Predicate Calculus
No ratings yet
Predicate Calculus
9 pages
Python Programming Essentials
No ratings yet
Python Programming Essentials
9 pages
Se Lab Manual
No ratings yet
Se Lab Manual
69 pages
Discrete Mathematics Revision Notes JNTUH R22
No ratings yet
Discrete Mathematics Revision Notes JNTUH R22
3 pages
UNIT - II Part 1 LC& LP
No ratings yet
UNIT - II Part 1 LC& LP
39 pages
DBMS Previous Year Question Paper
No ratings yet
DBMS Previous Year Question Paper
3 pages
DM in 5 Hours
No ratings yet
DM in 5 Hours
310 pages
Fundamentals and Types of Relation Part I With Anno
No ratings yet
Fundamentals and Types of Relation Part I With Anno
180 pages
DM Notes Lyst1720677128318
No ratings yet
DM Notes Lyst1720677128318
569 pages
1 SetTheorynoteswithoutkey
No ratings yet
1 SetTheorynoteswithoutkey
13 pages
Mec Ca3 Question PDF
No ratings yet
Mec Ca3 Question PDF
2 pages
The Product Keys For Autodesk 2018 Products Are As Follows
No ratings yet
The Product Keys For Autodesk 2018 Products Are As Follows
4 pages
Design Custom Space Hulk Missions
No ratings yet
Design Custom Space Hulk Missions
5 pages
DIN GS-C25 Material Equivalents Guide
100% (1)
DIN GS-C25 Material Equivalents Guide
2 pages
Capstone Sample Project Report
No ratings yet
Capstone Sample Project Report
6 pages
Lexmark FW5.3 Release Notes Update
No ratings yet
Lexmark FW5.3 Release Notes Update
5 pages
Beam Design Principles and Analysis
No ratings yet
Beam Design Principles and Analysis
49 pages
How To Collect Dset Logs in Linux
No ratings yet
How To Collect Dset Logs in Linux
3 pages
Sakai SV521 - Spec 2019
No ratings yet
Sakai SV521 - Spec 2019
4 pages
Third Culture Kids (Pollock David C, Van Reken Ruth E) (Z-Library)
No ratings yet
Third Culture Kids (Pollock David C, Van Reken Ruth E) (Z-Library)
370 pages
ECG Monitoring System Using Arduino and
No ratings yet
ECG Monitoring System Using Arduino and
4 pages
期末專題1
No ratings yet
期末專題1
14 pages
Egg Grading Manual PDF
100% (1)
Egg Grading Manual PDF
64 pages
Clinical Skills and Simulation Programme Aug2013 July2014 Updated
No ratings yet
Clinical Skills and Simulation Programme Aug2013 July2014 Updated
9 pages
NVS Recruitment 2019: Principal & Teachers
No ratings yet
NVS Recruitment 2019: Principal & Teachers
14 pages
PDF P Classtruncatedtext Module Lineclamped 85ulhh Style Max Lines5lkpd Puzzle Emosi P - Compress
No ratings yet
PDF P Classtruncatedtext Module Lineclamped 85ulhh Style Max Lines5lkpd Puzzle Emosi P - Compress
8 pages
Plaidoirie en Francais-1.Fr - en
No ratings yet
Plaidoirie en Francais-1.Fr - en
67 pages
Season-Wise Area, Production and Yield of Sunflower in India (1950-1951 and 1970-1971 To 2023-2024-3rd Advance Estimates)
No ratings yet
Season-Wise Area, Production and Yield of Sunflower in India (1950-1951 and 1970-1971 To 2023-2024-3rd Advance Estimates)
2 pages
The Unofficial LEGO Technic Builder S Guide 1st Edition Pawel "Sariel" Kmiec Available Full Chapters
No ratings yet
The Unofficial LEGO Technic Builder S Guide 1st Edition Pawel "Sariel" Kmiec Available Full Chapters
79 pages
Beyond The Syllabus
No ratings yet
Beyond The Syllabus
16 pages
R-1234ze Refrigerant Technical Data Sheet
No ratings yet
R-1234ze Refrigerant Technical Data Sheet
3 pages
Shulmans Model of Pedogogical Content Knowledge
No ratings yet
Shulmans Model of Pedogogical Content Knowledge
8 pages
Math Gr. 6 - Q1 PROJECT 2022
No ratings yet
Math Gr. 6 - Q1 PROJECT 2022
3 pages
Fluke 92B 96B 99B 105B Service Manual
No ratings yet
Fluke 92B 96B 99B 105B Service Manual
322 pages
Multiple-Choice Questions On Pressure in Fluids
100% (4)
Multiple-Choice Questions On Pressure in Fluids
3 pages
Sample Size Determination
No ratings yet
Sample Size Determination
4 pages
Proposed VCCT Wind Turbine Foundation Bill of Quantities
No ratings yet
Proposed VCCT Wind Turbine Foundation Bill of Quantities
2 pages
Anxiety Levels of Bse Science Students in Pangasinan - State University During The Covid 19 Pandemic
No ratings yet
Anxiety Levels of Bse Science Students in Pangasinan - State University During The Covid 19 Pandemic
91 pages
2808-Article Text-11401-1-10-20240713
No ratings yet
2808-Article Text-11401-1-10-20240713
9 pages
Borides
No ratings yet
Borides
4 pages