Discrete Mathematics Set Theory and Algebra Previous Year GATE Questions

Ques 1: State whether the following statements are TRUE or FALSE:

GATE 1987

The union of two equivalence relations is also an equivalence relation.

Solution: Equivalence Relation: Relation is reflexive, symmetric, transitive.

A relation R1 is defined on a set A={a,b,c}.

R1={(a,a),(b,b),(c,c),(a,b),(b,a)} → Equivalence Relation.

A relation R2 is defined on a set A={a,b,c}.

R2={(a,a),(b,b),(c,c),(c,b),(b,c)} → Equivalence Relation.

R = (R1 U R2) = {(a,a),(b,b),(c,c),(a,b),(b,a),(c,b),(b,c)}. → Not an Equivalence Relation.

R is reflexive, symmetric but not transitive. because (a,b) and (b,c) doesn’t imply (a,c).

Ans: FALSE. (The union of two equivalence relations may or may not be an equivalence relation.)

NOTE: You can also take relation defined on different sets and then take union.

The union of two reflexive relations is always reflexive.

The union of two symmetric relations is always symmetric.

This is not true for transitivity that’s why the answer is false. 

Ques 2: How many binary relations are there on a set A with n elements?

GATE 1987


Binary relation on a set A is a subset of (AxA).

Ternary relation on a set A is a subset of (AxAxA).

now AxA will contain n2 terms

So the total no of binary relation on set A

= cardinality of power set of (A⨉A) 

= ∣ p(A⨉A) ∣


Ques 3: How many one-to-one functions are there from a set A with n elements onto itself?

GATE 1987

Solution: There are n! one to one function possible from a set of n elements to itself.

i.e., nPn=n!

Ques 4: The complement(s) of the element ′a′ in the lattice shown in below figure is (are) ____

GATE 1988


lub(a,e)=lub(a,b)=lub(a,c)=lub(a,d)=I (Upper Bound of Lattice)

glb(a,e)=glb(a,b)=glb(a,c)=glb(a,d)=O (Lower Bound of Lattice)

So, {b,c,d,e} all are complements of a.

Ques 5: The transitive closure of the relation {(1,2),(2,3),(3,4),(5,4)}{(1,2),(2,3),(3,4),(5,4)} on the set {1,2,3,4,5}{1,2,3,4,5} is ___________.

GATE 1989

Solution: {(1,2),(2,3),(1,3) ,(3,4),(2,4),(1,4),(5,4)}

Ques 6: Let S be an infinite set and S1…,Sn be sets such that S1∪S2∪⋯∪Sn=S. Then

GATE 1993

(A) at least one of the sets Si is a finite set

(B) not more than one of the sets Si can be finite

(C) at least one of the sets Si is an infinite

(D) not more than one of the sets Si can be infinite

Ans: (C) at least one of the sets Si is an infinite

Ques 7: Let A be a finite set of size n. The number of elements in the power set of A×A is:

GATE 1993

(A) 2^2^n

(B) 2^n^2

(C) 2n

(D) 2^n

Ans: (B)

Solution:Cardinality of A×A=n^2
Cardinality of power  set of A×A=2^n^2

Ques 8: Some group (G,o) is known to be abelian. Then, which one of the following is true for G?

GATE 1994

(A) g=g−1 for every g∈G

(B) g=g2 for every g∈G

(C) (goh)2=g2oh2 for every g,h∈G

(D) G is of finite order

Ans: (C)

Solution: Abelian group is commutative and associative. So,







So, C is correct.  

Ques 9: Let R be a symmetric and transitive relation on a set A. Then

GATE 1995

(A) R is reflexive and hence an equivalence relation

(B)R is reflexive and hence a partial order

(C) R is reflexive and hence not an equivalence relation

(D) None of the above

Ans: (D) None of the above

Solution: A symmetric and Transitive relation need not be reflexive.

Let A={1,2,3} and

relation R={(1,2),(2,1),(1,1),(2,2)}.

R is symmetric and transitive but not reflexive.

Because (3,3) is not there.

Ques 10: The number of elements in the power set P(S) of the set S={{∅},1,{2,3}} is:

GATE 1995

(A) 2

(B) 4

(C) 8

(D) None of the above

Ans: (C) 8

Solution: no of element in power set is 2^(set size)

In {∅,1,{2,3}} there are 3 elements

i.e ∅,1,{2,3}

Note {2,3} is a single element

now power set 2^3=8

Note:  ∅ and {∅} are not same.

first means no element whereas second means one element which is ∅.

error: You can only copy the programs code and output from this website. You are not allowed to copy anything else.