Challenge Problems: Applications of Boolean Algebra

These challenge problems test deeper understanding. Only final answers are provided — work through each problem on your own.

Challenge 1: Circuit Design from Word Problem

A security system has four sensors: Door ($D$), Window ($W$), Motion ($M$), and Glass-break ($G$). The alarm ($A$) should activate when:

The door sensor AND at least one other sensor are triggered, OR
Any three or more sensors are triggered simultaneously

Write the minimum SOP expression for the alarm output $A$.

Show Answer

$A = DW + DM + DG + WMG$

The first three terms cover "door AND at least one other." The last term covers "any three without door" (only $WMG$ is possible for three or more without $D$). The case of all four is covered by the first three terms already.

Challenge 2: Full Adder/Subtractor Combined Circuit

Design a combinational circuit that acts as both a full adder and a full subtractor, controlled by a mode signal $M$. When $M = 0$, it performs $A + B + C_{in}$; when $M = 1$, it performs $A - B - C_{in}$ (using two's complement). Give the expressions for the output ($Result$) and the carry/borrow ($C_{out}/B_{out}$).

Show Answer

$Result = A \oplus (B \oplus M) \oplus C_{in}$

\[C_{out}/B_{out} = (A \oplus M) \cdot (B \oplus M) + (B \oplus M) \cdot C_{in} + C_{in} \cdot (A \oplus M)\]

Equivalently, XOR $B$ and $C_{in}$ with $M$ before feeding them to a standard full adder:

\[Result = A \oplus B' \oplus C'_{in} \text{ where } B' = B \oplus M,\; C'_{in} = C_{in} \oplus M\]

\[C_{out} = A \cdot B' + B' \cdot C'_{in} + C'_{in} \cdot A\]

When $M = 1$, the initial carry-in should also be 1 to complete the two's complement.

Challenge 3: BCD-to-Excess-3 Converter

Construct the truth table for a BCD-to-Excess-3 code converter (4-bit input $B_3B_2B_1B_0$, 4-bit output $E_3E_2E_1E_0$). Write the minimum SOP expression for each output bit, using don't-care conditions for invalid BCD inputs (10-15).

Show Answer

BCD ($B_3B_2B_1B_0$)	Excess-3 ($E_3E_2E_1E_0$)
0000	0011
0001	0100
0010	0101
0011	0110
0100	0111
0101	1000
0110	1001
0111	1010
1000	1011
1001	1100

Minimum SOP (with don't cares for inputs 10-15):

\[E_3 = B_3 + B_2 B_1 + B_2 B_0\]

\[E_2 = \overline{B_2}\,B_1 + \overline{B_2}\,B_0 + B_2\,\overline{B_1}\,\overline{B_0}\]

\[E_1 = \overline{B_1}\,\overline{B_0} + B_1 B_0\]

\[E_0 = \overline{B_0}\]

Challenge 4: Parity Generator/Checker Design

Design an even-parity generator for a 7-bit ASCII input ($D_6 D_5 D_4 D_3 D_2 D_1 D_0$) that produces a parity bit $P$. Then design a parity checker circuit that takes the 8-bit code ($D_6 \ldots D_0, P$) and outputs an error signal $E$ that is 1 when a single-bit error is detected. Express both circuits using XOR gates and state the total gate count.

Show Answer

Parity generator:

\[P = D_6 \oplus D_5 \oplus D_4 \oplus D_3 \oplus D_2 \oplus D_1 \oplus D_0\]

Requires 6 XOR gates (cascaded).

Parity checker:

\[E = D_6 \oplus D_5 \oplus D_4 \oplus D_3 \oplus D_2 \oplus D_1 \oplus D_0 \oplus P\]

$E = 1$ indicates an error (odd number of 1s detected). Requires 7 XOR gates.

Total: 13 XOR gates (6 for generator + 7 for checker).

Challenge 5: Multi-Output Combinational Circuit Optimization

A combinational circuit has three inputs ($A$, $B$, $C$) and three outputs defined as:

$F_1 = \sum m(0, 2, 3, 5, 7)$
$F_2 = \sum m(0, 1, 4, 5, 6)$
$F_3 = \sum m(1, 2, 6, 7)$

Find the minimum two-level AND-OR implementation for all three outputs using shared product terms where possible. State the total gate count (AND gates + OR gates + inverters).

Show Answer

Minimum expressions:

\[F_1 = \overline{A}\,\overline{B} + \overline{A}\,C + BC\]

\[F_2 = \overline{B}\,\overline{C} + A\overline{C} + \overline{A}\,\overline{B}\]

\[F_3 = \overline{A}\,\overline{B}\,C + \overline{A}\,B\,\overline{C} + AB\overline{C} + ABC = AB + \overline{B}\,C + \overline{A}\,B\,\overline{C}\]

Shared term $\overline{A}\,\overline{B}$ appears in both $F_1$ and $F_2$.

Total: 8 AND gates, 3 OR gates, 3 inverters = 14 gates

Challenge 6: Carry-Lookahead Adder Design

For a 4-bit carry-lookahead adder, derive the expression for carry $C_3$ (the carry into bit position 3) directly in terms of the generate ($G$) and propagate ($P$) signals and the initial carry $C_0$. How many gate levels does your expression require?

Show Answer

Recursive carry equations: $C_{i+1} = G_i + P_i C_i$

$C_1 = G_0 + P_0 C_0$

$C_2 = G_1 + P_1 G_0 + P_1 P_0 C_0$

$C_3 = G_2 + P_2 G_1 + P_2 P_1 G_0 + P_2 P_1 P_0 C_0$

This requires only 2 gate levels (one AND level, one OR level) after the P and G signals are computed — compared to 6 levels for a ripple-carry adder.

Challenge 7: Seven-Segment Decoder with Don't Cares

Design the logic for segment $g$ of a BCD-to-seven-segment decoder. Segment $g$ is the middle horizontal bar, which lights for digits 2, 3, 4, 5, 6, 8, 9. Write the function with don't cares for invalid BCD inputs (10–15) and find the minimum SOP expression.

Show Answer

$g(A,B,C,D) = \Sigma m(2,3,4,5,6,8,9) + d(10,11,12,13,14,15)$

Using don't cares optimally on a K-map:

Minimum SOP: $g = A + B\overline{C} + \overline{B}C + C\overline{D}$
Simplified further: $g = A + B \oplus C + C\overline{D}$

Challenge 8: Overflow Detection Circuit

Design an overflow detection circuit for an 8-bit two's complement adder. The circuit receives the carry into the MSB position ($C_7$) and the carry out of the MSB position ($C_8$). Write the Boolean expression for the overflow flag $V$, draw the gate implementation, and explain why $V = C_7 \oplus C_8$ correctly detects overflow for both addition and subtraction.

Show Answer

$V = C_7 \oplus C_8$ (single XOR gate)

Why it works: Overflow occurs when the sign of the result is wrong. This happens only when:

- Two positive numbers produce a negative result: $C_7 = 1$ (carry into sign bit flips it), $C_8 = 0$ → $V = 1$

- Two negative numbers produce a positive result: $C_7 = 0$, $C_8 = 1$ → $V = 1$

When $C_7 = C_8$, the carries are consistent and the sign bit is correct, so $V = 0$. This works for subtraction because subtraction is implemented as addition with the two's complement of the subtrahend.