Courses

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

```
Offer running on EduRev: Apply code STAYHOME200 to get INR 200 off on our premium plan EduRev Infinity!

,

,

,

,

,

,

,

,

,

,

,

,

,

,

,

,

,

,

,

,

,

;