Boolean Algebra Practice Questions

The circuit implements the arithmetic logic for subtracting bits $B$ and $C$ from bit $A$. The output of the top XOR gate generates the difference bit, $D = A \oplus (B \oplus C) = A \oplus B \oplus C$. The bottom network of gates (AND, OR, NOT) generates the borrow-out signal $B_{out} = A' \cdot (B \oplus C) + BC$, which simplifies to the standard full subtractor borrow expression $A'B + A'C + BC$. Since the circuit computes both the difference and the borrow output for a 3-input subtraction operation, it is a full subtractor.

The given expression is $Y=(A+\bar{B}+\bar{A}B)\bar{C}$.

To simplify, apply the Boolean identity $X + \bar{X}Y = X + Y$ to the term $(\bar{B} + \bar{A}B)$, where $X = \bar{B}$ and $Y = \bar{A}$:
$(\bar{B} + \bar{A}B) = (\bar{B} + \bar{A})$
Substitute this back into the original expression:
$Y = (A + \bar{B} + \bar{A})\bar{C}$
Apply the complement law $A + \bar{A} = 1$:
$Y = (1 + \bar{B})\bar{C}$
Since $1 + \bar{B} = 1$, the expression simplifies to:
$Y = 1 \cdot \bar{C} = \bar{C}$

For $n$ Boolean variables, there are $2^n$ distinct possible input combinations.
For each of these $2^n$ input combinations, a Boolean function can independently output either 0 or 1.
Thus, for each input combination, there are 2 possible output values.
Since there are $2^n$ input combinations, and each can have 2 independent output choices, the total number of different Boolean functions is:
$\underbrace{2 \times 2 \times \dots \times 2}_{2^n \text{ \times }} = 2^{2^n}$

To determine the logical function of the circuit, we analyze the two branches of logic gates:

1. Top Branch: The first NOR gate processes inputs $A$ and $B$ to produce $\overline{A+B}$. This output passes through an OR gate with input $C$, resulting in the expression $(\overline{A+B}) + C$.
2. Bottom Branch: The first NOR gate processes inputs $D$ and $E$ to produce $\overline{D+E}$. Applying De Morgan's Law, this simplifies to $\bar{D}\bar{E}$.
3. Final Stage: The outputs of the two branches, $(\overline{A+B} + C)$ and $(\bar{D}\bar{E})$, are combined by the final gate. Based on the options provided, the circuit performs an AND operation on these two terms.

Thus, the final function is $(\overline{A+B}+C)(\bar{D}\bar{E})$.

In standard TTL logic, the circuit operates with a supply voltage $V_{CC} = 5V$.
The output low voltage level ($V_{OL}$), representing a logic '0', is defined by the saturation voltage of the output transistor, typically around $0.6V$.
The output high voltage level ($V_{OH}$), representing a logic '1', is determined by the internal pull-up network of the output stage, resulting in an approximate value of $3.5V$.
Therefore, the output logic levels for the TTL family are approximately $0.6V$ and $3.5V$, which matches option B.

First, let's find a simplified sum-of-products expression for $f(w,x,y,z)=\Sigma (0,4,5,7,8,9,13,15)$ using a Karnaugh map.

Minterms:
$m_0 = 0000 = w'x'y'z'$
$m_4 = 0100 = w'xy'z'$
$m_5 = 0101 = w'xy'z$
$m_7 = 0111 = w'xyz$
$m_8 = 1000 = wx'y'z'$
$m_9 = 1001 = wx'y'z$
$m_{13} = 1101 = wxy'z$
$m_{15} = 1111 = wxyz$

K-map for $f$:

      yz
wx    00 01 11 10
-----------------
00 | 1  0  0  0   (m0)
01 | 1  1  1  0   (m4,m5,m7)
11 | 0  1  1  0   (m13,m15)
10 | 1  1  0  0   (m8,m9)

Grouping the 1s:

1. $w'y'z'$ covers $m_0, m_4$.
2. $wx'y'$ covers $m_8, m_9$.
3. $xz$ covers $m_5, m_7, m_{13}, m_{15}$ (as $xz = w'xz + wxz = w'y'z' + w'yz + wxy'z + wxyz$). More precisely, $xz = (x y' z + x y z)$ (from $w'$ and $w$ cells).
   $xz = xz(w'+w) = xz(w'y'+w'y+wy'+wy)$
   $xz = w'xy'z + w'xyz + wxy'z + wxyz = m_5 + m_7 + m_{13} + m_{15}$.

Thus, $f = w'y'z' + wx'y' + xz$. This is the simplified form of $f$.

Now, let's check each expression:

• (P) $x'y'z' + w'xy' + wy'z + xz$
  $x'y'z'$ covers $m_0(0000), m_8(1000)$.
  $w'xy'$ covers $m_4(0100), m_5(0101)$.
  $wy'z$ covers $m_9(1001), m_{13}(1101)$.
  $xz$ covers $m_5(0101), m_7(0111), m_{13}(1101), m_{15}(1111)$.
  All minterms of $f$ are covered: $\Sigma (0,4,5,7,8,9,13,15)$. So (P) is equivalent to $f$.

• (Q) $w'y'z' + wx'y' + xz$
  This is the simplified form we derived for $f$. So (Q) is equivalent to $f$.

• (R) $w'y'z' + wx'y' + xyz + xy'z$
  $w'y'z'$ covers $m_0(0000), m_4(0100)$.
  $wx'y'$ covers $m_8(1000), m_9(1001)$.
  $xyz$ covers $m_7(0111), m_{15}(1111)$.
  $xy'z$ covers $m_5(0101), m_{13}(1101)$.
  All minterms of $f$ are covered: $\Sigma (0,4,5,7,8,9,13,15)$. Note that $xyz + xy'z = xz(y+y') = xz$. So (R) is equivalent to (Q) and thus to $f$.

• (S) $x'y'z' + wx'y' + w'y$
  $x'y'z'$ covers $m_0(0000), m_8(1000)$.
  $wx'y'$ covers $m_8(1000), m_9(1001)$.
  $w'y$ covers $m_2(0010), m_3(0011), m_6(0110), m_7(0111)$.
  Combining these, (S) covers $\Sigma (0,2,3,6,7,8,9)$.
  This set of minterms is different from $f$'s minterms $\Sigma (0,4,5,7,8,9,13,15)$ because it includes $m_2, m_3, m_6$ (which are not in $f$) and misses $m_4, m_5, m_{13}, m_{15}$ (which are in $f$). Therefore, (S) is NOT equivalent to $f$.

The only expression not equivalent to $f$ is (S).

The carry output $c_{out}$ for a 3-bit adder (assuming carry-in $c_{\in} = 0$) is derived from the recursive carry equations $c_1 = a_0 b_0$, $c_2 = a_1 b_1 + (a_1 + b_1)c_1$, and $c_3 = a_2 b_2 + (a_2 + b_2)c_2$.
Substituting $c_1$ into $c_2$ yields $c_2 = a_1 b_1 + a_1 a_0 b_0 + b_1 a_0 b_0$.
Next, substituting $c_2$ into $c_3$ gives $c_3 = a_2 b_2 + (a_2 + b_2)(a_1 b_1 + a_1 a_0 b_0 + b_1 a_0 b_0)$.
Expanding this boolean expression results in $c_3 = a_2 b_2 + a_2 a_1 b_1 + a_2 a_1 a_0 b_0 + a_2 a_0 b_1 b_0 + a_1 b_2 b_1 + a_1 a_0 b_2 b_0 + a_0 b_2 b_1 b_0$.
This expanded form matches the expression provided in option A.

From the truth table, $A \square B$ is False only when $A$ is False and $B$ is True. This corresponds to the logical implication $B \rightarrow A$, which is equivalent to $\neg B \lor A$. We evaluate option D: $\neg (\neg A \square B)$. Using the definition $X \square Y \equiv \neg Y \lor X$ with $X = \neg A$ and $Y = B$, we find $\neg A \square B \equiv \neg B \lor \neg A$. Applying the outer negation gives $\neg (\neg B \lor \neg A)$. By De Morgan's law, this simplifies to $B \land A$, which is $A \land B$.

To ensure a hazard-free realization, every pair of adjacent minterms (differing by one bit) in the function $f(w,x,y,z) = \Sigma(5, 7, 11, 12, 13, 15)$ must be covered by at least one common cube. The adjacent minterm pairs are $(5,7), (5,13), (7,15), (11,15), (12,13),$ and $(13,15)$.

Option D includes the following cubes:

• $wx\bar{y}$ covers $(12, 13)$
• $wyz$ covers $(11, 15)$
• $wxz$ covers $(13, 15)$
• $\bar{w}xz$ covers $(5, 7)$
• $x\bar{y}z$ covers $(5, 13)$
• $xyz$ covers $(7, 15)$

Since Option D provides a common cube for every adjacent pair of minterms, the function remains true during all valid input transitions, successfully eliminating hazards.

The majority function is expressed as $f(x, y, z) = xy + xz + yz$. Factoring by the variable $x$, we obtain:
$f = x(y + z) + \bar{x}(yz)$
A 2-to-1 multiplexer with select line $x$ produces output $f = x \cdot P + \bar{x} \cdot Q$. By comparing these expressions, we identify $P = y + z$, which is the logic for an OR gate, and $Q = y \cdot z$, which is the logic for an AND gate.

Options A and B represent the tautology $f = f(x_i + x_i') = x_i f + x_i' f$, which is valid for any variable $x_i$.
Option C is the Shannon Expansion Theorem, which states that any boolean function can be decomposed as $f(x_1, \dots, x_n) = x_n' f|_{x_n=0} + x_n f|_{x_n=1}$, which is true.
Option D is incorrect; it suggests that a function equals the OR sum of its partial evaluations at $x_1=0$ and $x_1=1$.
To disprove D, consider $f(x_1) = x_1$.
The left side is $f(x_1) = x_1$, while the right side is $f(0) + f(1) = 0 + 1 = 1$.
Since $x_1 \neq 1$ for all $x_1$, the equation is not true.

The output $f$ is determined by two multiplexers (MUX).

1. First MUX: The inputs are $x$ (at 0) and $\bar{y}$ (at 1) with select $z$. The output is:
   $M_1 = \bar{z} \cdot x + z \cdot \bar{y} = x\bar{z} + \bar{y}z$

2. Second MUX: The inputs are $M_1$ (at 0) and $x$ (at 1) with select $y$. The final output is:
   $f = \bar{y} \cdot M_1 + y \cdot x$

3. Substitution and Simplification:
   $f = \bar{y}(x\bar{z} + \bar{y}z) + xy = x\bar{y}\bar{z} + \bar{y}z + xy$
   Using the Boolean identity $A + \bar{A}B = A + B$, we simplify the expression $xy + x\bar{y}\bar{z}$:
   $xy + x\bar{y}\bar{z} = x(y + \bar{y}\bar{z}) = x(y + \bar{y})(y + \bar{z}) = x(y + \bar{z}) = xy + x\bar{z}$
   Substituting this back into the equation for $f$:
   $f = xy + x\bar{z} + \bar{y}z$

This expression matches Option A.

The top gate is a NAND gate with inputs $X$ and $\bar{Y}$, producing output $\overline{X \cdot \bar{Y}} = \bar{X} + Y$.
The bottom gate is an AND gate with inputs $Y$ and $Z$, producing output $Y \cdot Z$.
The final NAND gate output is $f = \overline{(\bar{X} + Y) \cdot (Y \cdot Z)}$.
Expanding the expression: $f = \overline{\bar{X} \cdot Y \cdot Z + Y \cdot Y \cdot Z} = \overline{\bar{X}YZ + YZ}$.
Factoring out $YZ$ gives $f = \overline{YZ(\bar{X} + 1)} = \overline{YZ(1)} = \overline{YZ}$.
Since the final expression $f = \overline{YZ}$ does not contain $X$, the function $f$ is independent of $X$.

The circuit allows current to flow (bulb lights up) when the switches $S_1$ and $S_2$ are in the same position, effectively completing the path between the terminals. Specifically, if $S_1 = 1$ and $S_2 = 1$, the current flows through path $a_1 \to b_1 \to b_2 \to a_2$; if $S_1 = 0$ and $S_2 = 0$, it flows through path $a_1 \to c_1 \to c_2 \to a_2$.

This logic is summarized by the table where the output is $1$ if $S_1 = S_2$ and $0$ if $S_1 \neq S_2$. This operation is equivalent to the XNOR gate. The boolean expression for an XNOR operation between $S_1$ and $S_2$ is $\overline{S_1 \oplus S_2}$.

The function is given by the minterms $f(A,B,C,D) = \Sigma(1, 4, 5, 9, 11, 12)$.
Expanding the terms in Option A ($BC'D' + A'C'D + AB'D$):

• $BC'D'$ covers $m_4 (0100)$ and $m_{12} (1100)$, where $A$ can be $0$ or $1$.
• $A'C'D$ covers $m_1 (0001)$ and $m_5 (0101)$, where $A=0$ and $C'=1, D=1$.
• $AB'D$ covers $m_9 (1001)$ and $m_{11} (1011)$, where $A=1$ and $B'=1, D=1$.
  Combining these subsets yields exactly $\{1, 4, 5, 9, 11, 12\}$, which matches the given function.

The expression $(A \oplus B) \oplus C$ represents the 3-input XOR function, which equals $1$ if an odd number of inputs are $1$, corresponding to the minterms $ABC + \bar{A}\bar{B}C + \bar{A}B\bar{C} + A\bar{B}\bar{C}$.
Expanding Option C: $ABC + \bar{A}(B \oplus C) + \bar{B}(A \oplus C) = ABC + \bar{A}(B\bar{C} + \bar{B}C) + \bar{B}(A\bar{C} + \bar{A}C)$.
Distributing the variables gives: $ABC + \bar{A}B\bar{C} + \bar{A}\bar{B}C + A\bar{B}\bar{C} + \bar{A}\bar{B}C$.
Applying the idempotent law ($X + X = X$), the redundant term $\bar{A}\bar{B}C$ simplifies to a single term.
The result is $ABC + \bar{A}B\bar{C} + \bar{A}\bar{B}C + A\bar{B}\bar{C}$, which is identical to the XOR minterms.

Given the expression $F = x'y' + xy + x'y$, factor $x'$ from the terms $x'y'$ and $x'y$:
$F = x'(y' + y) + xy$
Since $y' + y = 1$, the expression simplifies to:
$F = x'(1) + xy = x' + xy$
Apply the distributive law $A + BC = (A + B)(A + C)$ where $A = x'$, $B = 1$ (implicit), $C = y$:
$F = (x' + x)(x' + y) = (1)(x' + y) = x' + y$

The Boolean function $f(a, b, c) = a'c + ac' + b'c$ includes minterms $m_1(001), m_3(011), m_4(100), m_5(101),$ and $m_6(110)$.
The prime implicants of the function are $a'c$ (covering $\{m_1, m_3\}$), $ac'$ (covering $\{m_4, m_6\}$), $b'c$ (covering $\{m_1, m_5\}$), and $ab'$ (covering $\{m_4, m_5\}$).
A prime implicant is essential if it covers a minterm that no other prime implicant covers.
The minterm $m_3$ is covered only by $a'c$, and $m_6$ is covered only by $ac'$, making both $a'c$ and $ac'$ essential.
The remaining prime implicants $b'c$ and $ab'$ are not essential because all their minterms ($m_1, m_5$) are covered by $a'c$ or $ac'$ combined with other implicants.
Thus, the essential prime implicants are $a'c$ and $ac'$.

Given the Boolean expression $F = A \bar B C + \bar A B C + A B \bar C + \bar A \bar B C + A \bar B \bar C$, we can rearrange and group terms as follows:
$F = (A \bar B C + A \bar B \bar C) + (A B \bar C) + (\bar A B C + \bar A \bar B C)$
Factoring common variables leads to:
$F = A \bar B (C + \bar C) + A B \bar C + \bar A C (B + \bar B)$
Since $X + \bar X = 1$, the expression simplifies to:
$F = A \bar B + A B \bar C + \bar A C$
Applying the distributive law $A \bar B + A B \bar C = A (\bar B + B \bar C) = A (\bar B + B)(\bar B + \bar C) = A(\bar B + \bar C) = A \bar B + A \bar C$:
$F = A \bar B + A \bar C + \bar A C$