Boolean Algebra Practice Questions

Operations like AND, OR, and EX-OR are both commutative and associative.
For NAND ($\uparrow$), commutativity holds: $A \uparrow B = \overline{AB} = \overline{BA} = B \uparrow A$.
However, associativity fails: $(A \uparrow B) \uparrow C = \overline{\overline{AB} \cdot C} = AB + \overline{C}$, whereas $A \uparrow (B \uparrow C) = \overline{A \cdot \overline{BC}} = \overline{A} + BC$.
Since $AB + \overline{C} \neq \overline{A} + BC$, the NAND operation is not associative.
Thus, NAND is the only operation listed that is commutative but not associative.

Multiplexers are universal logic elements because any Boolean function of $n$ variables can be implemented using a $2^{n-1}:1$ MUX by connecting input variables to the selection lines. A half adder is also functionally complete as it provides the operations $Sum = A \oplus B$ and $Carry = A \cdot B$. By tying one XOR input to logic $1$, one obtains the NOT operation, $A \oplus 1 = \bar{A}$. With both AND and NOT gates available, one can synthesize any logic function, including the NAND gate. Conversely, individual OR or Ex-OR gates cannot perform negation or conjunction and are not universal.

[CORRECT_OPTION: B, C]

The outputs of the individual NAND gates are $Y_1 = \overline{ABC}$ and $Y_2 = \overline{DE}$. When open-collector outputs are tied together, they perform a "wired-AND" operation, meaning the final output $Y$ is the logical AND of the individual gate outputs:
$Y = Y_1 \cdot Y_2 = (\overline{ABC}) \cdot (\overline{DE})$
Applying De Morgan's Law, which states that $\overline{X} \cdot \overline{Y} = \overline{X + Y}$, we simplify the expression:
$Y = \overline{ABC + DE}$
Thus, the circuit implements the logic function $Y = \overline{ABC + DE}$.

The given expression is $A \oplus B \oplus A$.
Using the commutative property of XOR, we can rearrange the terms as $A \oplus A \oplus B$.
Applying the associative property, we group the terms as $(A \oplus A) \oplus B$.
Since XORing any variable with itself results in 0, we have $A \oplus A = 0$.
The expression simplifies to $0 \oplus B$.
Because XORing any variable with 0 yields the variable itself, $0 \oplus B = B$.

A Boolean function with $n$ variables has $2^n$ possible input combinations, as each variable can take values $0$ or $1$. For each of these $2^n$ combinations, the output can be assigned one of $2$ possible values ($0$ or $1$). Therefore, the total number of distinct Boolean functions that can be formed is given by the formula $2^{(2^n)}$. Substituting $n = 4$ into this formula yields $2^{(2^4)} = 2^{16}$. Calculating $2^{16}$ results in $65,536$.

The K-map corresponds to the Boolean function $f(a, b, c) = \sum m(2, 3, 5, 6, 7)$. Simplifying this expression using Boolean algebra gives:
$f = a\bar{c} + ac + bc = a(\bar{c} + c) + bc = a + bc$.
Analyzing the circuit in option (D), the inputs to the first two NOR gates are $a, b$ and $a, c$.
The output of the first gate is $\overline{a+b}$ and the second is $\overline{a+c}$.
The final NOR gate outputs $f = \overline{\overline{a+b} + \overline{a+c}}$.
Applying De Morgan's theorem, $f = (a+b) \cdot (a+c) = a^2 + ac + ab + bc = a(1+c+b) + bc = a + bc$.
This matches the derived Boolean function $f = a + bc$.

Apply DeMorgan: $\overline{AB + \overline{A}C} = \overline{AB} \cdot \overline{\overline{A}C} = (\overline{A}+\overline{B}) \cdot (A + \overline{C})$.

Plot the K-map for 3 variables. Minterms: 000,001,010,100,101,110. Grouping yields two pairs: m0+m1 gives $\overline{A}\overline{B}$, m0+m2 gives $\overline{A}\overline{C}$, m4+m5 gives $A\overline{B}$, m4+m6 gives $A\overline{C}$. Combining, the minimal SOP is $\overline{B} + \overline{C}$.

Minterm1 = 001, minterm4 = 100. They differ in two bits (A and C). In a 3-variable K-map, cells are adjacent if they differ in exactly one bit. So they are not adjacent. Answer B.

Group terms with A and $\overline{A}$: $\overline{A}(\overline{B}\overline{C}+BC) + A(\overline{B}\overline{C}+BC) = (\overline{A}+A)(\overline{B}\overline{C}+BC) = \overline{B}\overline{C}+BC$, which is the XNOR of B and C, also equal to $A \odot B \odot C$ when A is ? Actually $A \odot B \odot C$ equals parity of 1's even? Let's check: For A=0, B=0, C=0: XNOR =1, expression =1. For A=1, B=0, C=0: XNOR=1, expression =1. So it's independent of A. So $F = B \odot C$, which is also $A \odot B \odot C$ only when A is constant? No. Actually $A \odot B \odot C = A \oplus B \oplus C$ complemented? Not exactly. The correct interpretation: The expression simplifies to $\overline{B}\overline{C}+BC$, which is XNOR of B and C. That is not equal to three-input XNOR unless A is 0 or 1. But among options, A says $\overline{B}\overline{C}+BC$ and C says $A \odot B \odot C$ - that would be different. Let's recalc: Three-input XNOR (equivalence) is 1 when all bits are same (000,111). Our function is 1 for (0,0,0), (0,1,1), (1,0,0), (1,1,1) - that's actually true when B and C are equal, regardless of A. So it's $B \odot C$, not $A \odot B \odot C$. So only option A is correct. But D says both A and C - that may be false. I'll adjust: The correct answer should be A. Many GATE questions have this: $F = \overline{B}\overline{C}+BC$. So answer A.

XOR $A \oplus B = \overline{A}B + A\overline{B}$ can be implemented with 4 NAND gates: first three NANDs for intermediate signals, fourth as output.

Minterms: 000,001,010,100. The missing minterms (3,5,6,7) correspond to maxterms. Simplify using K-map for POS. The result is $(\overline{A}+B)(\overline{A}+C)$.

Cells m0 (0000), m1 (0001), m4 (0100), m5 (0101) have A=0, C=0, while B and D vary. So term = $\overline{A}\overline{C}$.

B is the Consensus Theorem. C is the Transposition Theorem. A can be verified by K-map or simplification.

Let $X = A \oplus B$. Then the expression is $X \cdot \overline{X} = 0$. So it always evaluates to 0.

Groups must be in sizes of 2^n (1,2,4,8...) for simplification.

Corners (m0,m2,m8,m10) form $\overline{B}\overline{D}$. Center cells (m5,m7,m13,m15) form $BD$. Both are essential because each covers minterms (e.g., m0 only in first, m5 only in second).

A XOR B requires 4 NAND gates in a standard cross-coupled configuration.

All minterms have D=0. So $F = \overline{D}$.