Consider the following expressions : (a) Y = f(A, B, C, D) = Σ (1, 2, 4, 7, 8, 11, 13, 14) Which of the above expressions are equivalent to the expression Y = A⊕B⊕C⊕D ?
(b) Y = f(A, B, C, D) = Σ (3, 5, 7, 10, 11, 12, 13, 14)
(c) Y = f(A, B, C, D) = Π (0, 3, 5, 6, 9, 10, 12, 15)
(d) Y = f(A, B, C, D) = Π (0, 1, 2, 4, 5, 8, 9, 15)
(a) and (c)
A multi-input XOR is an odd-parity detector: its output is 1 exactly when the number of input 1s is odd. That single fact generates the whole answer without any algebra.
Step 1 — list the minterms with an odd count of 1s.
| Minterm | ABCD | Number of 1s |
|---|---|---|
| 1 | 0001 | 1 — odd ✓ |
| 2 | 0010 | 1 ✓ |
| 4 | 0100 | 1 ✓ |
| 7 | 0111 | 3 ✓ |
| 8 | 1000 | 1 ✓ |
| 11 | 1011 | 3 ✓ |
| 13 | 1101 | 3 ✓ |
| 14 | 1110 | 3 ✓ |
So \(Y=\Sigma(1,2,4,7,8,11,13,14)\) — exactly statement (a).
Step 2 — convert to the maxterm form. For an n-variable function the minterm and maxterm lists are complementary: whatever is not in the Σ list must appear in the Π list. The remaining eight numbers are
0, 3, 5, 6, 9, 10, 12, 15
and these are precisely the even-parity combinations. So \(Y=\Pi(0,3,5,6,9,10,12,15)\) — exactly statement (c).
Hence (a) and (c) both describe the same function, giving option 4. Statement (b) is neither list, and statement (d) omits several even-parity terms while including odd ones, so both fail.
The check that takes five seconds : a 4-variable XOR must be 1 for exactly half of the sixteen combinations, so both lists must contain eight entries and together must account for all sixteen numbers 0 to 15 with none repeated. (a) and (c) satisfy this perfectly.
Two properties worth carrying away. First, an XOR chain can be built in any order or as a tree, since the operation is associative and commutative. Second, the complement \(\overline{A\oplus B\oplus C\oplus D}\) is the XNOR, the even-parity detector — and the pair is the basis of parity generation and checking, where an extra bit is appended so that every transmitted word carries an agreed parity and any single-bit error shows up at the receiver.
A K-map note: plotting an XOR function produces the familiar checkerboard, in which no two 1s are ever adjacent. That is why the expression cannot be simplified at all — every minterm is its own prime implicant, and a 4-variable XOR needs all eight product terms in SOP form, which is exactly why it is implemented with XOR gates rather than as sum of products.
Hence, the equivalent expressions are (a) and (c).
The Boolean expression \(AC+B\bar{C}\) is equivalent to :
The output of the circuit is given by :

In Boolean algebra, the term sum of products means
The value of \(\rm \overline{A+B}\) is :
The Boolean function Y = AB + CD is to be realized using only two-input NAND gates. The minimum number of gates required are:
The minimum number of 2-input NAND gates required to realize the logic function $Y = AB + \bar A \bar B$ is