Boolean Algebra Practice Questions

First, determine the logical operation represented by $\square$.
From the truth table:
$P \square Q$ is True when $P$ is True (regardless of $Q$) or when $P$ is False and $Q$ is False.
This is equivalent to $P \vee \neg Q$.
Let's verify:
If $P=T, Q=T$: $T \vee \neg T = T \vee F = T$.
If $P=T, Q=F$: $T \vee \neg F = T \vee T = T$.
If $P=F, Q=T$: $F \vee \neg T = F \vee F = F$.
If $P=F, Q=F$: $F \vee \neg F = F \vee T = T$.
This matches the given truth table. So, $P \square Q \equiv P \vee \neg Q$.

Now, we need to find which option is equivalent to $P \vee Q$.
Let's evaluate option B: $P \square \neg Q$.
Using the definition $X \square Y \equiv X \vee \neg Y$, substitute $X=P$ and $Y=\neg Q$:
$P \square \neg Q \equiv P \vee \neg(\neg Q)$
$P \vee \neg(\neg Q) \equiv P \vee Q$
Thus, $P \square \neg Q$ is equivalent to $P \vee Q$.

By mapping the minterms $\Sigma(1,3,4,6,9,11,12,14)$ onto a 4-variable K-map, we group the terms as follows:
$f(w,x,y,z) = x'(w'+w)z + x(w'+w)z'$
Since $(w'+w) = 1$, the expression simplifies to $f = x'z + xz'$, which is equivalent to the XOR operation $x \oplus z$.
The resulting function $f(x,z) = x \oplus z$ depends solely on variables $x$ and $z$.
Consequently, the function is independent of the variables $w$ and $y$.

The Boolean function is $F = AB+C$.

1. Apply the distributive law $X+YZ = (X+Y)(X+Z)$ to the function:
   $F = (A+C)(B+C)$
2. Recall De Morgan's Law: $X \cdot Y = \overline{\overline{X}+\overline{Y}}$. We need to implement $X'Y'$ where $X'=A+C$ and $Y'=B+C$.
   $F = (A+C)(B+C) = \overline{\overline{(A+C)} + \overline{(B+C)}}$
3. The term $\overline{A+C}$ is implemented by a single 2-input NOR gate:
   $G_1 = \text{NOR}(A, C) = \overline{A+C} \quad \text{(1st gate)}$
4. The term $\overline{B+C}$ is implemented by another single 2-input NOR gate:
   $G_2 = \text{NOR}(B, C) = \overline{B+C} \quad \text{(2nd gate)}$
5. Finally, combine the outputs $G_1$ and $G_2$ using a third 2-input NOR gate:
   $G_3 = \text{NOR}(G_1, G_2) = \overline{G_1+G_2} = \overline{(\overline{A+C}) + (\overline{B+C})} \quad \text{(3rd gate)}$
   By De Morgan's Law, $G_3 = \overline{\overline{A+C}} \cdot \overline{\overline{B+C}} = (A+C)(B+C) = AB+C$.

Thus, a total of 3 NOR gates are required.

The given function is $f(A, B, C, D) = \Sigma(1, 4, 5, 9, 11, 12)$, which represents minterms $m_1(0001)$, $m_4(0100)$, $m_5(0101)$, $m_9(1001)$, $m_{11}(1011)$, and $m_{12}(1100)$.
Using a 4-variable K-map to simplify these terms:

1. Grouping $m_4(0100)$ and $m_{12}(1100)$ eliminates $A$, yielding $BC'D'$.
2. Grouping $m_1(0001)$ and $m_5(0101)$ eliminates $B$, yielding $A'C'D$.
3. Grouping $m_9(1001)$ and $m_{11}(1011)$ eliminates $C$, yielding $AB'D$.
   Summing these groups gives the simplified expression $f(A, B, C, D) = BC'D' + A'C'D + AB'D$.

For the expression $A(A+B)$, we can write the first term $A$ as $A+0$.
Applying the distributive law in Boolean algebra, where $(X+Y)(X+Z) = X + YZ$, we substitute $X=A, Y=0$, and $Z=B$:
$(A+0)(A+B) = A + (0 \cdot B)$
Since the product $0 \cdot B = 0$, the expression simplifies to $A + 0$.
By the identity law, $A + 0 = A$, therefore the final simplified expression is $A$.

The XOR ($\oplus$) operation returns $1$ if the inputs are different and $0$ if the inputs are identical.
Evaluating the given options:

• Option A: $0 \oplus 0 = 0$ is a valid rule.
• Option B: $1 \oplus 1$ results in $0$, meaning $1 \oplus 1 = 1$ is an invalid rule.
• Option C: $1 \oplus 0 = 1$ is a valid rule.
• Option D: Any value $B \oplus B = 0$ is a valid rule.
  incorrectly defines the output of identical inputs.

Based on the provided circuit diagram, the boolean output is given by the expression:
$f = (f_1 \cdot f_2) + f_3$
Substituting the given functions:
$\sum m(1, 6, 8, 15) = (f_1 \cdot f_2) + \sum m(1, 6, 15)$
To satisfy the equation, the term $(f_1 \cdot f_2)$ must contain minterm $8$ and exclude minterms $\{4, 5, 7\}$ (which are present in $f_1$ but not in $f$). Testing option C ($f_2 = \sum m(6, 8)$):
$f_1 \cdot f_2 = \sum m(4, 5, 6, 7, 8) \cdot \sum m(6, 8) = \sum m(6, 8)$
$(f_1 \cdot f_2) + f_3 = \sum m(6, 8) + \sum m(1, 6, 15) = \sum m(1, 6, 8, 15) = f$

A set of connectives is functionally complete if it can generate all Boolean functions. The sets $\{ \text{implication}, \neg \}$, $\{ \text{OR}, \neg \}$, and $\{ \text{NAND} \}$ are well-known to be functionally complete. However, the EX-NOR connective, defined as $x \odot y = x \oplus y \oplus 1$ over $GF(2)$, is an affine function. Any composition of affine functions is also an affine function of the form $f(x_1, \dots, x_n) = c_0 \oplus c_1 x_1 \oplus \dots \oplus c_n x_n$. Because non-linear operations like AND ($x \land y$) cannot be represented by affine functions, the set containing only EX-NOR is not functionally complete.

To simplify the Boolean expression $(A+\bar{C})(\bar{B} + \bar{C})$, we can use the distributive property of Boolean algebra, which states that $(X + Y)(X + Z) = X + YZ$.

By identifying the common term $X = \bar{C}$, $Y = A$, and $Z = \bar{B}$, we substitute these values into the identity:
$(\bar{C} + A)(\bar{C} + \bar{B}) = \bar{C} + A \cdot \bar{B}$

Thus, the simplified expression is $\bar{C} + A\bar{B}$, which matches option A.

The circuit consists of three cascaded XOR gates, where the second input of each gate is connected to the signal $X$. We determine the output of each gate as follows:

1. The first XOR gate has inputs $0$ and $X$, so its output is $0 \oplus X = X$.
2. The second XOR gate has inputs equal to the output of the first gate ($X$) and the signal $X$, yielding $X \oplus X = 0$.
3. The final XOR gate has inputs equal to the output of the second gate ($0$) and the signal $X$, yielding $0 \oplus X = X$.

Thus, the final output is $Y = X$.

The equation $AB + \bar{A}C + BC = AB + \bar{A}C$ represents the Consensus Theorem. The Principle of Duality states that any Boolean identity remains valid if OR ($+$) and AND ($\bullet$) operators are swapped. By applying this principle to the given expression:

• The left-hand side $AB + \bar{A}C + BC$ transforms into $(A+B) \bullet (\bar{A}+C) \bullet (B+C)$.
• The right-hand side $AB + \bar{A}C$ transforms into $(A+B) \bullet (\bar{A}+C)$.
  Equating these results yields the dual expression: $(A+B) \bullet (\bar{A}+C) \bullet (B+C) = (A+B) \bullet (\bar{A}+C)$.

The given Boolean function is $f(A, B, C, D) = \sum(2, 3, 6, 7, 8, 9, 10, 11, 12, 13)$.
Mapping the minterms to binary: $2(0010), 3(0011), 6(0110), 7(0111), 8(1000), 9(1001), 10(1010), 11(1011), 12(1100), 13(1101)$.
Observe that for each pair of minterms, the variable $D$ takes both values $0$ and $1$ while $(A, B, C)$ remain constant:
$f = (001X) + (011X) + (100X) + (101X) + (110X) = A'C + AB' + ABC'$.
Simplifying the expression: $f = A'C + A(B' + BC') = A'C + A(B' + C') = A'C + AB' + AC'$.
Since the final simplified expression involves only $A, B,$ and $C$, the function is independent of the variable $D$.
The function depends on the other three variables, confirming it is independent of only one variable.

To find the minimal form, we group the '1's in the Karnaugh map, utilizing 'X' (don't care) terms to create the largest possible groups. The K-map variables are $a, b$ (columns) and $c, d$ (rows).

1. Group 1: Observe the cells where $a=0$ (first two columns) and $d=0$ (first and fourth rows). This covers the cells $(00,00)$, $(01,00)$, $(00,10)$, and $(01,10)$. The boolean expression for this group is $\bar{a}\cdot \bar{d}$.
2. Group 2: Observe the cells where $b=0$ (first and fourth columns) and $d=0$ (first and fourth rows). This covers the cells $(00,00)$, $(10,00)$, $(00,10)$, and the don't care term at $(10,10)$. The boolean expression for this group is $\bar{b}\cdot \bar{d}$.
3. Result: Combining these groups, the minimal form of the function is the sum of these products: $\bar{b}\cdot \bar{d} + \bar{a}\cdot \bar{d}$.

This expression covers all '1's in the map without including any '0's.

Given the expression: $E = (P+\bar{Q})(P.\bar{Q}+P.R)(\bar{P}.\bar{R}+\bar{Q})$
First, factor the second term: $(P.\bar{Q}+P.R) = P.(\bar{Q}+R)$.
Using the absorption law, $(P+\bar{Q})P = P$, so the expression simplifies to:
$E = P(\bar{Q}+R)(\bar{P}.\bar{R}+\bar{Q})$
Expanding the terms inside the parentheses: $P(\bar{Q}\bar{P}\bar{R} + \bar{Q} + R\bar{P}\bar{R} + R\bar{Q}) = P(\bar{P}\bar{Q}\bar{R} + \bar{Q} + 0 + R\bar{Q})$.
Since $\bar{Q}(1+R) = \bar{Q}$, the bracket reduces to $(\bar{P}\bar{Q}\bar{R} + \bar{Q})$, which further simplifies to $\bar{Q}(1+\bar{P}\bar{R}) = \bar{Q}$.
Thus, $E = P.\bar{Q}$.

Replacing each 2-input AND gate ($\cdot$) with a NAND gate ($\overline{x \cdot y} = x' + y'$), the expression becomes:
$F = \overline{(\overline{a \cdot b}) \cdot c} + \overline{(\overline{a' \cdot c}) \cdot d} + \overline{(\overline{b \cdot c}) \cdot d} + \overline{a \cdot d}$
Applying De Morgan's Law to each term:
$F = (a \cdot b + c') + (a' \cdot c + d') + (b \cdot c + d') + (a' + d')$
Grouping terms and using Boolean simplification ($a \cdot b + a' = a' + b$):
$F = a \cdot b + a' + c' + d' + a' \cdot c + b \cdot c$
Since $a' + a' \cdot c = a'$ and $b + b \cdot c = b$, the expression simplifies to:
$F = a' + b + c' + d'$

To detect a stuck-at-0 fault on line $T$, we must find an input $(X_1, X_2, X_3, X_4)$ such that the fault-free output $F_{correct}$ differs from the faulty output $F_{faulty}$. The output of the circuit is given by $F = \overline{O + T}$, where $O = \overline{X_1 X_2 X_3} + X_4$ is the OR gate output and $T = X_3 \cdot X_4$.

1. For a stuck-at-0 fault, $F_{correct} = \overline{O + T}$ and $F_{faulty} = \overline{O + 0} = \overline{O}$.
2. The fault is detected only if $F_{correct} \neq F_{faulty}$, which occurs when $O=0$ and $T=1$.
3. The condition $O = \overline{X_1 X_2 X_3} + X_4 = 0$ requires $X_1=1, X_2=1, X_3=1$ and $X_4=0$.
4. Substituting these into the expression for $T$, we get $T = X_3 \cdot X_4 = 1 \cdot 0 = 0$.
5. Since $T$ cannot be 1 when $O=0$, it is impossible to satisfy the detection condition. Thus, the fault cannot be detected by any input.

To identify the correct Karnaugh Map, we first determine the minterms (combinations where the output is 1) for the given expression:
$f(a,b,c,d) = a\bar{d} + \bar{a}\bar{c} + b\bar{c}d$

We evaluate the function for each term:

1. $a\bar{d}$: True when $a=1$ and $d=0$. This corresponds to the rows where $a=1$ (the bottom two rows) and the columns where $d=0$ (the 2nd and 4th columns, given the labels $\bar{c}\bar{d}$ and $c\bar{d}$).
2. $\bar{a}\bar{c}$: True when $a=0$ and $c=0$. This corresponds to the rows where $a=0$ (the top two rows) and the columns where $c=0$ (the 1st and 2nd columns, given the labels $\bar{c}d$ and $\bar{c}\bar{d}$).
3. $b\bar{c}d$: True when $b=1, c=0,$ and $d=1$. This corresponds to the row where $a=0, b=1$ (row 2) and the column where $c=0, d=1$ (column 1). Also includes row $a=1, b=1$ (row 3) and column $\bar{c}d$ (column 1).

Mapping these conditions onto the grid in option A correctly covers all these minterms ($a\bar{d}$ covers the specific cells in rows 3 and 4; $\bar{a}\bar{c}$ covers rows 1 and 2; and $b\bar{c}d$ covers the cell in row 2 and 3 at column 1). is the correct representation.

To simplify the Boolean function $f(w, x, y, z)=\Sigma (1,3,4,6,9,11,12,14)$, we use a Karnaugh Map (K-map).

The minterms are:
$m_1 = 0001$
$m_3 = 0011$
$m_4 = 0100$
$m_6 = 0110$
$m_9 = 1001$
$m_{11} = 1011$
$m_{12} = 1100$
$m_{14} = 1110$

Let's plot these on a 4-variable K-map (w,x rows; y,z columns):

Now, we group the adjacent 1s:

1. Group the four 1s: $m_1 (0001)$, $m_3 (0011)$, $m_9 (1001)$, $m_{11} (1011)$.
   These minterms correspond to $\bar{w}\bar{x}\bar{y}z$, $\bar{w}\bar{x}yz$, $w\bar{x}\bar{y}z$, $w\bar{x}yz$.
   Comparing these, we see that $w$ and $y$ change, while $\bar{x}z$ remains constant.
   This group simplifies to $\bar{x}z$.

2. Group the four 1s: $m_4 (0100)$, $m_6 (0110)$, $m_{12} (1100)$, $m_{14} (1110)$.
   These minterms correspond to $\bar{w}x\bar{y}\bar{z}$, $\bar{w}xy\bar{z}$, $wx\bar{y}\bar{z}$, $wxy\bar{z}$.
   Comparing these, we see that $w$ and $y$ change, while $x\bar{z}$ remains constant.
   This group simplifies to $x\bar{z}$.

All minterms are covered. The simplified Boolean function is:
$f(w, x, y, z) = \bar{x}z + x\bar{z}$
This expression only contains the variables $x$ and $z$. Variables $w$ and $y$ are not present in the simplified function. Therefore, the function is independent of two variables ($w$ and $y$).

The final answer is $\boxed{B}$

The given expression is $F = a\bar{d} + \bar{a}\bar{c} + b\bar{c}d$. Converting this into minterms on a 4-variable K-map (variables $abcd$):
$a\bar{d} = 1x0x \implies \{8, 10, 12, 14\}$
$\bar{a}\bar{c} = 0x0x \implies \{0, 1, 4, 5\}$
$b\bar{c}d = x101 \implies \{5, 13\}$
The sum of these minterms is $F = \sum m(0, 1, 4, 5, 8, 10, 12, 13, 14)$. Evaluating the options, we see that Option C includes the term $\bar{c}d$, which represents the minterms $\{1, 3, 5, 7, 9, 11, 13, 15\}$. This set introduces minterms like $3, 7, 9, 11,$ and $15$, which are not part of the original expression's K-map. is not equivalent to the given expression.