Category: Discrete Mathematics Objective Questions

Discrete Mathematics Multiple Choice Questions on “Graphs – Hasse Diagrams”.

1. Hasse diagrams are first made by ______
a) A.R. Hasse
b) Helmut Hasse
c) Dennis Hasse
d) T.P. Hasse

Answer: b
Clarification: Hasse diagrams can be described as the transitive reduction as an abstract directed acyclic graph. This graph drawing techniques are constructed by Helmut Hasse(1948).

2. If a partial order is drawn as a Hasse diagram in which no two edges cross, its covering graph is called ______
a) upward planar
b) downward planar
c) lattice
d) biconnected components

Answer: a
Clarification: In a Hasse diagram if no two edges cross each other in the drawing of partial order Hasse diagram, then its covering graph called the upward planar.

3. If the partial order of a set has at most one minimal element, then to test whether it has a non-crossing Hasse diagram its time complexity __________
a) NP-complete
b) O(n²)
c) O(n+2)
d) O(n³)

Answer: a
Clarification: If the partial order has at most one minimal element, or it has at most one maximal element, then to test whether a partial order with multiple sources and sinks can be drawn as a crossing-free Hasse diagram or not it’s time complexity is NP-complete.

4. Which of the following relation is a partial order as well as an equivalence relation?
a) equal to(=)
b) less than(<)
c) greater than(>)
d) not equal to(!=)

Answer: a
Clarification: The identity relation = on any set is a partial order in which every two distinct elements are incomparable and that depicts the relation of both a partial order and an equivalence relation. For non-linear orders, there are many advanced properties of posets.

5. The relation ≤ is a partial order if it is ___________
a) reflexive, antisymmetric and transitive
b) reflexive, symmetric
c) asymmetric, transitive
d) irreflexive and transitive

Answer: a
Clarification: Let A is a set and ≤ is a relation on A, then ≤ is a partial order if it satisfies reflexive, antisymmetric, and transitive, i.e., for all x, y and z in P. That means, x ≤ x (reflexivity);
if x ≤ y and y ≤ x then x = y (antisymmetry) and if x ≤ y and y ≤ z then x ≤ z (transitivity).

6. In which of the following relations every pair of elements is comparable?
a) ≤
b) !=
c) >=
d) ==

Answer: a
Clarification: In the ≤(or less than and equal to) relation, every pair of elements is comparable.

7. In a poset (S, ⪯), if there is no element n∈S with m<n, then which of the following is true?
a) an element n exists for which m=n
b) An element m is maximal in the poset
c) A set with the same subset of the poset
d) An element m is minimal in the poset

Answer: b
Clarification: By the definition, an element m exists in a poset (S, ⪯) is maximal if and only if there is no n∈S with m≺n.

8. In a poset P({v, x, y, z}, ⊆) which of the following is the greatest element?
a) {v, x, y, z}
b) 1
c) ∅
d) {vx, xy, yz}

Answer: a
Clarification: We know that, in a Hasse diagram, the maximal element(s) are the top and the minimal elements are at the bottom of the diagram. In the given poset, {v, x, y, z} is the maximal or greatest element and ∅ is the minimal or least element.

9. Suppose P₁ is a partially ordered class and a cut of P₁ is pair (D, T) of nonempty subclasses of P₁ satisfies which of the following properties?
a) D∩T=Ø
b) D∪T=P₁
c) xyz∈T
d) z∈T and zx∈D

Answer: a
Clarification: Suppose P₁ is a partially ordered class and a cut of P₁ is pair (D, T) of nonempty subclasses of P₁ satisfies the following properties: i) D∩T=Ø and D∪T=P₁ ii) If z∈D and y≤z, then y∈D and iii) If z∈T and y≥z, then y∈T.

10. Let G be the graph defined as the Hasse diagram for the ⊆ relation on the set S{1, 2,…, 18}. How many edges are there in G?
a) 43722
b) 2359296
c) 6487535
d) 131963

Answer: b
Clarification: Here the total number of elements in S is 18 and so number of vertices in Hasse diagram are 2¹⁸. Hence, the number of edges in Hasse diagram are 18 * 2^18-1=2359296.

Discrete Mathematics Multiple Choice Questions on “Minimization of Boolean Functions”.

1. Find the simplified expression A’BC’+AC’.
a) B
b) A+C
c) (A+B)C’
d) B’C

Answer: c
Clarification: Given: A’BC’ + AC’
= C’(A’B + A)
= C’(A + B).

2. Evaluate the expression: (X + Z)(X + XZ’) + XY + Y.
a) XY+Z’
b) Y+XZ’+Y’Z
c) X’Z+Y
d) X+Y

Answer: d
Clarification: (X + Z)(X + XZ’) + XY + Y [Original Expression]
= (x + z)X(1 + Z’) + XY + Y [Distributive]
= (X + Z)X + XY + Y [Complement, Identity]
= (X+Z)X + Y(X+1) [ Distributive]
= (X+Z)X + Y [Idempotent]
= XX + XZ + Y [Distributive]
= X + XZ + Y [Identity]
= X(1+Z) + Y
= X + Y [Idempotent].

3. Simplify the expression: A’(A + BC) + (AC + B’C).
a) (AB’C+BC’)
b) (A’B+C’)
c) (A+ BC)
d) AC

Answer: b
Clarification: Given: A’(A + BC) + (AC + B’C)
= A’A + A’BC + AC + B’C
= A’BC + C(A + B’)
= C(A’B + A + B’)
= C(A + B + B’)
= C(A + 1)
= AC.

4. What is the simplification value of MN(M + N’) + M(N + N’)?
a) M
b) MN+M’N’
c) (1+M)
d) M+N’

Answer: b
Clarification: Given: MN(M + N’) + M(N + N’)
= MN(M+N’) + M.1
= MNM + MNN’ + M
= MN + 0 +M
= M(N + 1)
= M.

5. Simplify the expression XZ’ + (Y + Y’Z) + XY.
a) (1+XY’)
b) YZ + XY’ + Z’
c) (X + Y +Z)
d) XY’+ Z’

Answer: c
Clarification: Given: X Z’ + (Y + Y’Z) + XY
= XZ’ + (Y + Z) + XY
= XZ’ + Y + Z + XY
= (XZ’ + Z) + (Y + XY)
= (X + Z) + Y (1 + X)
= X + Y + Z.

6. Find the simplified term Y’ (X’ + Y’) (X + X’Y)?
a) XY’
b) X’Y
c) X + Y
d) X’Y’

Answer: a
Clarification: Given: Y’ (X’ + Y’) (X + X’Y)
= Y’(X’ + Y’)(X + Y)
= (X’Y’ + Y’)(X + Y)
= (XX’Y’ + X’Y’Y + XY’ + YY’)
= XY’.

7. If an expression is given that x+x’y’z=x+y’z, find the minimal expression of the function F(x,y,z) = x+x’y’z+yz?
a) y’ + z
b) xz + y’
c) x + z
d) x’ + y

Answer: c
Clarification: We have, x+x’y’z+yz
= x+y’z+yz [since, x+x’y’z=x+y’z]
= x+z(y’+y)
= x + z.

8. Simplify the expression: XY’ + X’ + Y’X’.
a) X’ + Y
b) XY’
c) (XY)’
d) Y’ + X

Answer: c
Clarification: Given XY’+X’+Y’X’ = Y’(X+X’) + X’ = Y’.1 + X’ = X’ + Y’ = (XY)’ [De Morgan’s law].

9. Minimize the Boolean expression using Boolean identities: A′B+ABC′+BC’+AB′C′.
a) B(AC)’ + AC’
b) AC’ + B’
c) ABC + B’ + C
d) BC’ + A’B

Answer: a
Clarification: Given: A′B+ABC′+BC’+AB′C′
= A’B + BC’ (1 + A) + AB’C”
= A’B + BC’ + AB’C’
= A’B + BC’ + BC’ + AB’C’
= B(A’ + C’) + C’(A + AB’)
= B(AC)’ + C’ A(1 + B’)
= B(AC)’ + AC’.

10. Minimize the following Boolean expression using Boolean identities.
F(A,B,C) = (A+BC’)(AB’+C)
a) A + B + C’
b) AC’ + B
c) B + AC
d) A(B’ + C)

Answer: d
Clarification: Given, F(A,B,C) = (A+BC’)(AB’+C)
= (AAB’ + BC’AB’ + AC + BC’C)
= (AB’ + 0 + AC + 0)
= A(B’ + C).