Boolean Algebra

\(X\) is the majority function. Two quick rules: \(X(p, p, r) = p\), and if two arguments differ, \(X\) equals the remaining one.

• (A) False: with \(a = b = 1\), \(c = d = e = 0\), the left side is \(X(1, 1, 0) = 1\) but the right side is \(X(1, 0, 0) = 0\).
• (B) True: if \(a = b\), both sides equal \(a\); if \(a \ne b\), the left side equals its third argument, \(X(a, b, c)\).
• (C) False: the right side is \(a \cdot c\); with \(a = b = 1\), \(c = d = 0\), the left side is \(X(1, 1, 0) = 1\) but the right side is 0.
• (D) True: \(X(a, c, c) = c\), so the right side is \(X(a, X(a, b, c), c)\); if \(a = c\) it equals \(a = X(a, b, c)\), and if \(a \ne c\) it equals the middle argument \(X(a, b, c)\).

Answer: B, D

Write the minterms as \(b_3 b_2 b_1 b_0\): 0 = 0000, 2 = 0010, 4 = 0100, 8 = 1000, 10 = 1010, 11 = 1011, 12 = 1100. Group them on a K-map:

• \(\{0, 4, 8, 12\}\) all have \(b_1 = b_0 = 0\), giving \(\bar{b}_1 \bar{b}_0\).
• \(\{0, 2, 8, 10\}\) all have \(b_2 = b_0 = 0\), giving \(\bar{b}_2 \bar{b}_0\).
• 11 (1011) has only one neighbouring 1, namely 10 (1010), so it needs the pair \(\{10, 11\}\), giving \(b_3 \bar{b}_2 b_1\).

All three groups are essential and together cover exactly the seven minterms, so \(F = \bar{b}_1 \bar{b}_0 + \bar{b}_2 \bar{b}_0 + b_1 \bar{b}_2 b_3\). Option B misses minterm 11, C covers 14 and 15 (not in \(F\)), and D covers 1, 3, 5, 6 and 7.

Answer: A

Reading the three gates that feed the OR gate:

• the NAND gate gives \(\overline{XY}\);
• the NOT gate on \(X\) gives \(\overline{X}\);
• the AND gate gives \(X\overline{Y}\).

So \(F = \overline{XY} + \overline{X} + X\overline{Y}\), which is option C as written. By De Morgan's law \(\overline{XY} = \overline{X} + \overline{Y}\); the term \(\overline{X}\) repeats part of this and \(X\overline{Y}\) is absorbed by \(\overline{Y}\), so \(F = \overline{X} + \overline{Y} = \overline{XY}\). That is option A, and option B reduces to it the same way.

D is wrong: at \(X = Y = 1\), \(F = 0\) but \(X + \overline{Y} = 1\).

Answer: A, B, C

Read the map with the usual Gray-code order (00, 01, 11, 10) for \(wx\) and \(yz\). The four corner 1s are the cells with \(x = 0, z = 0\), and the central block of four 1s has \(x = 1, z = 1\). So \(F = \overline{x}\,\overline{z} + xz\), which is option D.

• A: its four 4-literal terms are exactly the four corner cells, and \(\overline{x}\,\overline{z}(\overline{w}\,\overline{y} + w\overline{y} + \overline{w}y + wy) = \overline{x}\,\overline{z}\), so A equals D.
• B: \(w\overline{x}yz\) has \(x = 0, z = 1\), a 0 cell, and two corner cells are missing.
• C: \(w\overline{x}\,\overline{y}z\) is also a 0 cell, and two corner cells are missing.

Answer: A, D

• (A) is wrong. The left side is \(\sum m(0, 3, 4, 5, 7)\) over \(ABC\). On the right, \(B\,C\) gives \(m_3, m_7\), \(\overline{B}\,\overline{C}\) gives \(m_0, m_4\) and \(\overline{A}\,\overline{B}\) gives \(m_0, m_1\): it contains 001 and misses 101. With \(A\,\overline{B}\) as the last term it would hold.
• (B) is the consensus theorem: \(BC = ABC + \overline{A}BC\), and these two terms are absorbed by \(AB\) and \(\overline{A}C\).
• (C) Expanding gives \(A\overline{A} + AB + \overline{A}C + BC = AB + \overline{A}C + BC\), which reduces to \(AB + \overline{A}C\) by (B).
• (D) By De Morgan, the complement of the product is the sum of the complemented factors: \(\overline{A}BD + \overline{C}\,\overline{D} + A\overline{C}\,\overline{D} + \overline{A}\,\overline{B}D\). The first and last terms combine to \(\overline{A}D\), and \(A\overline{C}\,\overline{D}\) is absorbed by \(\overline{C}\,\overline{D}\).

Answer: B, C, D

• A is true. The maxterms of a function are exactly the minterms it does not contain; out of 0 to 7 these are 0, 1, 2 and 4.
• B is true. \(XY + YZ + XZ\) is 1 exactly when at least two inputs are 1, that is for \(XYZ\) = 011, 101, 110 and 111, which are minterms 3, 5, 6 and 7. \(F\) is the 3-input majority function.
• C and D are false. \(F(X, 0, Z) = XZ\) while \(F(X, 1, Z) = X + Z\), so \(F\) depends on \(Y\). Likewise \(F(0, Y, Z) = YZ\) and \(F(1, Y, Z) = Y + Z\) differ, so \(F\) depends on \(X\).

Answer: A, B

Check each statement for \(x = 0\) and \(x = 1\):

• A: \(x.1 = x\) is the identity law for AND, so it is true.
• B: \(x + 1 = 1\) for every \(x\), so \(x + 1 = x\) fails when \(x = 0\). False.
• C: \(x.x = x\) (idempotent law), so \(x.x = 0\) fails when \(x = 1\). False.
• D: \(x + \overline{x} = 1\) is the complement law, so it is true.

The false statements are B and C.

Answer: B, C

Work with minterm sets: AND keeps the minterms common to both inputs, OR takes their union, and XOR keeps the minterms that appear in exactly one input.

• \(f1 \cdot f2\): common minterms \(\{3, 5, 7, 11, 13\}\).
• \(f3 + f4\): \(\{0, 1, 2, 4, 6, 11, 13\}\).
• XOR: 11 and 13 are in both sets and cancel, leaving \(\{0, 1, 2, 3, 4, 5, 6, 7\}\).

So \(Y = \sum(0,1,2,3,4,5,6,7)\), which is (C). Its maxterms are the remaining minterms 8 to 15, so (D) is the same function. Options (A) and (B) both describe \(\sum(0,1,2,11,13)\), which is not \(Y\).

Answer: C, D