Discrete structures Class 1 Notes | EduRev

Class 1 : Discrete structures Class 1 Notes | EduRev

 Page 1


     Discrete Structures 
 
Set1 
 
Q1.  Which of the following refers to Idempotent law? 
 
a) a b = b a 
b) 
a b = b a 
c) 
a ( b c ) = ( a b ) c 
d) a a = a 
 
Q2.  Which of the following distributive laws should hold true for a distributive lattice? 
 
(i) p ( q r ) = ( p q ) ( p r ). 
(ii) p ( q r ) = ( p q ) r. 
(iii) p ( q r ) = ( p q ) ( p r ). 
(iv) p ( q r ) = ( p q ) r 
 
a) (i) and (ii) 
b) (i) and (iii) 
c) (ii) and (iii) 
d) (ii) and (iv) 
 
Q3.  The Dual of any theorem in a lattice is : 
 
a) a law 
b) an order 
c) a theorem 
d) None of these 
 
Q4.  Simplify the Boolean expression : (A + B)'(C + D + E)' + (A + B)' 
 
a) A'B' 
b) C'D'E' 
c) C+D+E 
d) A'B'C'D'E' 
 
 
 
 
Page 2


     Discrete Structures 
 
Set1 
 
Q1.  Which of the following refers to Idempotent law? 
 
a) a b = b a 
b) 
a b = b a 
c) 
a ( b c ) = ( a b ) c 
d) a a = a 
 
Q2.  Which of the following distributive laws should hold true for a distributive lattice? 
 
(i) p ( q r ) = ( p q ) ( p r ). 
(ii) p ( q r ) = ( p q ) r. 
(iii) p ( q r ) = ( p q ) ( p r ). 
(iv) p ( q r ) = ( p q ) r 
 
a) (i) and (ii) 
b) (i) and (iii) 
c) (ii) and (iii) 
d) (ii) and (iv) 
 
Q3.  The Dual of any theorem in a lattice is : 
 
a) a law 
b) an order 
c) a theorem 
d) None of these 
 
Q4.  Simplify the Boolean expression : (A + B)'(C + D + E)' + (A + B)' 
 
a) A'B' 
b) C'D'E' 
c) C+D+E 
d) A'B'C'D'E' 
 
 
 
 
Q5.  Which of the following statement(s) is true regarding ISOMORPHIC BOOLEAN ALGEBRA? 
 
a) Every Boolean sub-algebra of a Boolean algebra B is a Boolean algebra. 
b) Boolean algebra may not be a Boolean sub algebra of B. 
c) Both every Boolean sub-algebra of a Boolean algebra B is a Boolean algebra & Boolean algebra may 
not be a Boolean sub algebra of B. 
d) None of these 
 
Q6.  If a finite lattice L does not contain _____ elements for some positive integer n, then L cannot be a 
Boolean algebra. 
 
a) 2
n
 
b) 2
n + 1
 
c) 2
n
 + 1 
d) 2
n – 1 
 
Q7.  What is the complement of 6 in the lattice D = { 1, 2, 3, 4, 6, 12} ? 
 
a) 2 
b) 4 
c) 12 
d) No complement 
 
Q8.  A lattice L is called ________ if every non empty sub-set of L has a least upper bound and a greatest 
lower bound. 
 
a) Distributive lattice 
b) Complete lattice 
c) Modular lattice 
d) Complemented lattice 
 
 
 
 
 
 
 
 
 
 
 
 
 
Page 3


     Discrete Structures 
 
Set1 
 
Q1.  Which of the following refers to Idempotent law? 
 
a) a b = b a 
b) 
a b = b a 
c) 
a ( b c ) = ( a b ) c 
d) a a = a 
 
Q2.  Which of the following distributive laws should hold true for a distributive lattice? 
 
(i) p ( q r ) = ( p q ) ( p r ). 
(ii) p ( q r ) = ( p q ) r. 
(iii) p ( q r ) = ( p q ) ( p r ). 
(iv) p ( q r ) = ( p q ) r 
 
a) (i) and (ii) 
b) (i) and (iii) 
c) (ii) and (iii) 
d) (ii) and (iv) 
 
Q3.  The Dual of any theorem in a lattice is : 
 
a) a law 
b) an order 
c) a theorem 
d) None of these 
 
Q4.  Simplify the Boolean expression : (A + B)'(C + D + E)' + (A + B)' 
 
a) A'B' 
b) C'D'E' 
c) C+D+E 
d) A'B'C'D'E' 
 
 
 
 
Q5.  Which of the following statement(s) is true regarding ISOMORPHIC BOOLEAN ALGEBRA? 
 
a) Every Boolean sub-algebra of a Boolean algebra B is a Boolean algebra. 
b) Boolean algebra may not be a Boolean sub algebra of B. 
c) Both every Boolean sub-algebra of a Boolean algebra B is a Boolean algebra & Boolean algebra may 
not be a Boolean sub algebra of B. 
d) None of these 
 
Q6.  If a finite lattice L does not contain _____ elements for some positive integer n, then L cannot be a 
Boolean algebra. 
 
a) 2
n
 
b) 2
n + 1
 
c) 2
n
 + 1 
d) 2
n – 1 
 
Q7.  What is the complement of 6 in the lattice D = { 1, 2, 3, 4, 6, 12} ? 
 
a) 2 
b) 4 
c) 12 
d) No complement 
 
Q8.  A lattice L is called ________ if every non empty sub-set of L has a least upper bound and a greatest 
lower bound. 
 
a) Distributive lattice 
b) Complete lattice 
c) Modular lattice 
d) Complemented lattice 
 
 
 
 
 
 
 
 
 
 
 
 
 
Q9.  Convert the below logical circuit into Boolean expression : 
 
 
 
a) ( A + B )'BC' 
b) ( A + B' )BC' 
c) ( A'B' )BC' 
d) ( AB)'BC' 
 
Q10.  A lattice L is said to be complemented if every element of L has at least __________ 
complement(s). 
 
a) 4 
b) 3 
c) 2 
d) 1 
 
Q11.  Find the in-degrees and out-degrees of vertices a, b, c and d in the same order for the following 
graph? 
 
 
 
a) 2 & 4, 2 & 1, 2 & 2 and 3 & 2 respectively 
b) 2 & 1, 3 & 2, 2 & 4 and 2 & 2 respectively 
c) 2 & 4, 2 & 1, 3 & 2, 2 & 2 respectively 
d) 2 & 1, 3 & 2, 2 & 2 and 2 & 4 respectively 
 
 
Page 4


     Discrete Structures 
 
Set1 
 
Q1.  Which of the following refers to Idempotent law? 
 
a) a b = b a 
b) 
a b = b a 
c) 
a ( b c ) = ( a b ) c 
d) a a = a 
 
Q2.  Which of the following distributive laws should hold true for a distributive lattice? 
 
(i) p ( q r ) = ( p q ) ( p r ). 
(ii) p ( q r ) = ( p q ) r. 
(iii) p ( q r ) = ( p q ) ( p r ). 
(iv) p ( q r ) = ( p q ) r 
 
a) (i) and (ii) 
b) (i) and (iii) 
c) (ii) and (iii) 
d) (ii) and (iv) 
 
Q3.  The Dual of any theorem in a lattice is : 
 
a) a law 
b) an order 
c) a theorem 
d) None of these 
 
Q4.  Simplify the Boolean expression : (A + B)'(C + D + E)' + (A + B)' 
 
a) A'B' 
b) C'D'E' 
c) C+D+E 
d) A'B'C'D'E' 
 
 
 
 
Q5.  Which of the following statement(s) is true regarding ISOMORPHIC BOOLEAN ALGEBRA? 
 
a) Every Boolean sub-algebra of a Boolean algebra B is a Boolean algebra. 
b) Boolean algebra may not be a Boolean sub algebra of B. 
c) Both every Boolean sub-algebra of a Boolean algebra B is a Boolean algebra & Boolean algebra may 
not be a Boolean sub algebra of B. 
d) None of these 
 
Q6.  If a finite lattice L does not contain _____ elements for some positive integer n, then L cannot be a 
Boolean algebra. 
 
a) 2
n
 
b) 2
n + 1
 
c) 2
n
 + 1 
d) 2
n – 1 
 
Q7.  What is the complement of 6 in the lattice D = { 1, 2, 3, 4, 6, 12} ? 
 
a) 2 
b) 4 
c) 12 
d) No complement 
 
Q8.  A lattice L is called ________ if every non empty sub-set of L has a least upper bound and a greatest 
lower bound. 
 
a) Distributive lattice 
b) Complete lattice 
c) Modular lattice 
d) Complemented lattice 
 
 
 
 
 
 
 
 
 
 
 
 
 
Q9.  Convert the below logical circuit into Boolean expression : 
 
 
 
a) ( A + B )'BC' 
b) ( A + B' )BC' 
c) ( A'B' )BC' 
d) ( AB)'BC' 
 
Q10.  A lattice L is said to be complemented if every element of L has at least __________ 
complement(s). 
 
a) 4 
b) 3 
c) 2 
d) 1 
 
Q11.  Find the in-degrees and out-degrees of vertices a, b, c and d in the same order for the following 
graph? 
 
 
 
a) 2 & 4, 2 & 1, 2 & 2 and 3 & 2 respectively 
b) 2 & 1, 3 & 2, 2 & 4 and 2 & 2 respectively 
c) 2 & 4, 2 & 1, 3 & 2, 2 & 2 respectively 
d) 2 & 1, 3 & 2, 2 & 2 and 2 & 4 respectively 
 
 
 
Q12
.  
Which of the following graphs are connected? 
 
 
 
a) Only 1 
b) 1 and 3 
c) 1,3 and 4 
d) 1, 2 and 3 
 
Q13.  Which of the following is a POS form for E = ( P + Q + R ) ( P + Q + R' ) ( P' + Q + R) ? 
 
a) PQR + PQR' + P'QR + PQ'R + PQ'R' 
b) PQ'R +PQR + PQR' + P'QR + P'Q'R 
c) PQR + PQR' + P'QR + PQ'R + P'QR' 
d) PQ'R +PQR + PQR' + P'QR + P'Q'R' 
 
Q14.  Determine the number of edges in a graph with 7 nodes, 1 of degree 0, 1 of degree 1, 1 of degree 
2, 1 of degree 3 and 3 of degree 4. 
 
a) 9 
b) 10 
c) 12 
d) 18 
 
Q15.  The space required for an adjacency matrix is : 
 
a) O(V + E) 
b) O(V
2
) 
c) O(E + E) 
d) O(E
2
) 
 
 
 
 
 
Page 5


     Discrete Structures 
 
Set1 
 
Q1.  Which of the following refers to Idempotent law? 
 
a) a b = b a 
b) 
a b = b a 
c) 
a ( b c ) = ( a b ) c 
d) a a = a 
 
Q2.  Which of the following distributive laws should hold true for a distributive lattice? 
 
(i) p ( q r ) = ( p q ) ( p r ). 
(ii) p ( q r ) = ( p q ) r. 
(iii) p ( q r ) = ( p q ) ( p r ). 
(iv) p ( q r ) = ( p q ) r 
 
a) (i) and (ii) 
b) (i) and (iii) 
c) (ii) and (iii) 
d) (ii) and (iv) 
 
Q3.  The Dual of any theorem in a lattice is : 
 
a) a law 
b) an order 
c) a theorem 
d) None of these 
 
Q4.  Simplify the Boolean expression : (A + B)'(C + D + E)' + (A + B)' 
 
a) A'B' 
b) C'D'E' 
c) C+D+E 
d) A'B'C'D'E' 
 
 
 
 
Q5.  Which of the following statement(s) is true regarding ISOMORPHIC BOOLEAN ALGEBRA? 
 
a) Every Boolean sub-algebra of a Boolean algebra B is a Boolean algebra. 
b) Boolean algebra may not be a Boolean sub algebra of B. 
c) Both every Boolean sub-algebra of a Boolean algebra B is a Boolean algebra & Boolean algebra may 
not be a Boolean sub algebra of B. 
d) None of these 
 
Q6.  If a finite lattice L does not contain _____ elements for some positive integer n, then L cannot be a 
Boolean algebra. 
 
a) 2
n
 
b) 2
n + 1
 
c) 2
n
 + 1 
d) 2
n – 1 
 
Q7.  What is the complement of 6 in the lattice D = { 1, 2, 3, 4, 6, 12} ? 
 
a) 2 
b) 4 
c) 12 
d) No complement 
 
Q8.  A lattice L is called ________ if every non empty sub-set of L has a least upper bound and a greatest 
lower bound. 
 
a) Distributive lattice 
b) Complete lattice 
c) Modular lattice 
d) Complemented lattice 
 
 
 
 
 
 
 
 
 
 
 
 
 
Q9.  Convert the below logical circuit into Boolean expression : 
 
 
 
a) ( A + B )'BC' 
b) ( A + B' )BC' 
c) ( A'B' )BC' 
d) ( AB)'BC' 
 
Q10.  A lattice L is said to be complemented if every element of L has at least __________ 
complement(s). 
 
a) 4 
b) 3 
c) 2 
d) 1 
 
Q11.  Find the in-degrees and out-degrees of vertices a, b, c and d in the same order for the following 
graph? 
 
 
 
a) 2 & 4, 2 & 1, 2 & 2 and 3 & 2 respectively 
b) 2 & 1, 3 & 2, 2 & 4 and 2 & 2 respectively 
c) 2 & 4, 2 & 1, 3 & 2, 2 & 2 respectively 
d) 2 & 1, 3 & 2, 2 & 2 and 2 & 4 respectively 
 
 
 
Q12
.  
Which of the following graphs are connected? 
 
 
 
a) Only 1 
b) 1 and 3 
c) 1,3 and 4 
d) 1, 2 and 3 
 
Q13.  Which of the following is a POS form for E = ( P + Q + R ) ( P + Q + R' ) ( P' + Q + R) ? 
 
a) PQR + PQR' + P'QR + PQ'R + PQ'R' 
b) PQ'R +PQR + PQR' + P'QR + P'Q'R 
c) PQR + PQR' + P'QR + PQ'R + P'QR' 
d) PQ'R +PQR + PQR' + P'QR + P'Q'R' 
 
Q14.  Determine the number of edges in a graph with 7 nodes, 1 of degree 0, 1 of degree 1, 1 of degree 
2, 1 of degree 3 and 3 of degree 4. 
 
a) 9 
b) 10 
c) 12 
d) 18 
 
Q15.  The space required for an adjacency matrix is : 
 
a) O(V + E) 
b) O(V
2
) 
c) O(E + E) 
d) O(E
2
) 
 
 
 
 
 
 
Q16.  Find the path weight using nearest neighbor algorithm for the below graph starting from vertex A? 
 
 
 
a) 20 or 21 
b) 21 or 22 
c) 20 or 22 
d) 21 or 19 
 
Q17.  Every regular graph with n vertices and degree r has ____________ edges. 
 
a) r/2 
b) r n/2 
c) r + n 
d) (r + n)/2 
 
Q18.  Which of the following is an adjacency matrix for the below given graph? 
 
 
 
a) 
 
b) 
 
Read More
Offer running on EduRev: Apply code STAYHOME200 to get INR 200 off on our premium plan EduRev Infinity!

Related Searches

past year papers

,

Discrete structures Class 1 Notes | EduRev

,

study material

,

ppt

,

Discrete structures Class 1 Notes | EduRev

,

Previous Year Questions with Solutions

,

Free

,

Discrete structures Class 1 Notes | EduRev

,

Objective type Questions

,

video lectures

,

Exam

,

Viva Questions

,

Sample Paper

,

shortcuts and tricks

,

practice quizzes

,

pdf

,

Extra Questions

,

mock tests for examination

,

MCQs

,

Important questions

,

Semester Notes

,

Summary

;