Module 4: Lattice and Boolean Algebra
1. What is meant by a Hasse diagram? Draw the Hasse diagram of the relation R on A where
A = {1, 2, 3, 4} and R = {(1, 1), (1, 2), (2, 2), (2, 4), (1, 3), (3, 3), (3, 4), (1, 4), (4, 4)}.
2. Let n be a positive integer and Sn be the set of all divisors of n. Let D denote the relation of
”division” in Sn such that aDb iff a divides b. Draw the Hasse diagram for (S6 , D).
3. Let A = {1, 2, 3, 4, 6, 8, 9, 12, 24} be ordered by divisibility.
4. Determine the greatest and least elements, if they exist of the poset A = {2, 4, 6, 8, 12, 18, 24, 36, 72}
with the partial order of divisibility.
5. Which of the Hasse diagram in the figure given below represents lattices:
f g e
d
b c b c d
b c
a (i) a (iii)
a (ii)
6. Which of the partially ordered sets shown in the figure below are lattices.
5 6
6
4 5
4 5
2 3 3 4
2 3
1 (a)
1 (b) 1 2 (c)
7. Write the dual of each statement:
(a) (x + y)(x + 1) = x + x · y
(b) (x + y) = x · y
(c) x · y = 0 if and only if x ≤ y
8. Prove the following Boolean identities:
(i) a + (a · b) = a + b
(ii) a · (a + b) = a · b
(iii) (a · b · c) + (a · b) = a · b
9. Simplify the following Boolean expressions:
(a) (a · b)′ + (a · b)′
(b) (a′ · b′ · c) + (a · b′ · c) + (a · b′ · c′ )
10. Write the following Boolean expressions in equivalent sum-of-products form in three variables:
(a) x1 x2
(b) x1 + x2
(c) (x1 · x2 )′ · x3
(d) x1 + (x2 · x′3 )
(e) (x1 + x2 ) + (x′1 · x3 )
11. Obtain the sum-of-products and product-of-sums of canonical forms of the following expressions:
(a) 11.12
(b) x1 x′2 + x3
12. Obtain simplified Boolean expressions which are equivalent to these expressions:
(i) m0 + m1 + m2 + m3
(ii) m0 + m1 + m2 + m5 + m6 + m7
(iii) m2 + m3 + m5 + m6
13. Express F = x(y ′ z)′ in complete sum-of-products form.
14. Write each of the following Boolean expressions in complete sum-of-products form:
(i) E = x(xy ′ + xy ′ + y2′ )
(ii) E = (x + y)′ (xy ′ )′
(iii) E = x3 (x′1 + x2 ) + x′2
15. Simplify:
(i) X = AB + AB
(ii) X = ABC + ABC
(iii) X = ABC + ABC + ABC + ABC
(iv) X = ABCD + ABCD + ABCD + ABCD
(v) X = ABCD + ABCD + ABCD + ABCD
(vi) X = ABCD + ABCD + ABCD + ABCD
P
16. Simplify the following Boolean function in product of sums form: F (A, B, C, D) = (0, 1, 2, 5, 8, 9, 10)
17. What are logic gates? Name three basic logic gates.
18. What is an OR-gate? Explain in brief the function of an OR-gate.
19. What is an AND-gate.
20. What is an exclusive OR-gate? How does it differ from an OR-gate?
21. What is a NOT-gate? Explain its operations and draw its truth table.
22. Draw the circuit symbol of a NAND-gate.
23. Simplify: P ′ Q + P ′ QR′ S ′ + P QRS ′
24. Simplify: (P ′ + Q′ + R′ )(P ′ + Q′ + R)(Q′ + R)(P + R)(R + Q + R)(P ′ + Q)
25. Simplify: P QRS + P ′ RS + P QS + P QRS ′ + QR′ S
26. Simplify the following expressions:
(a) Z = (A · B + B · C)(B · C + C · D)(C · D + A · B)
(b) Z = (A + B) · (A + B) · (A + B)
27. What is the significant of Principle of duality. Write the duals of:
(a) (X + Y ) · (Y + Z) · (Z + X)
(b) A + (B + E) + B · (C + A) + C · (A + B)
28. D70 = {1, 2, 5, 7, 10, 14, 35, 70} (the divisors of 70). We define a + b = lcm(a, b), a · b = gcd(a, b),
a′ = 70/a. Show that D70 is a Boolean algebra with 1 as the zero element and 70 as the unit
element.
29. Find the sum of products form (disjunctive normal form) of the Boolean expression E = ((xy)′ z)((x′ +
z)(y ′ + z ′ )).
30. A logic circuit L has n = 4 inputs A, B, C, D. Write the 16 bit special sequence for A, B, C, D.
31. Given five inputs A, B, C, D and E, find the special sequences which give all the different possible
combinations of input bits.
