Animated Solution for Physics - Semiconductors: Truth table for system of four NAND gates as shown in figure is

Imagine you are stranded on a desert island, and you need to build a computer. You don't have AND gates, OR gates, or XOR gates. All you have is a box of NAND gates. Could you do it? Yes! The NAND gate is a universal gate, meaning you can construct any logical operation in the universe using just this one component.

In this problem, we are given a beautiful, symmetric arrangement of four NAND gates. Our goal is to find the final truth table. While we could plug in 0s and 1s and trace them through, let's flex our Boolean algebra muscles and find the general expression.

Let's label the intermediate outputs. The first gate simply takes $A$ and $B$, giving us $Y_1=\overline{A\cdot B}$.

The second gate takes $A$ and $Y_1$, so its output is $Y_2=\overline{A\cdot \overline{A\cdot B}}$.

The third gate takes $B$ and $Y_1$, giving $Y_3=\overline{B\cdot \overline{A\cdot B}}$.

Finally, the last gate combines $Y_2$ and $Y_3$, resulting in our master equation:

I know this expression looks terrifying, but let's take a breath. We have a powerful weapon: De-Morgan's Law, which states that $\overline{X\cdot Y}=\overline{X}+\overline{Y}$.

Applying this to the outermost bar, the double negations cancel out like magic:

Now, we apply De-Morgan's law again to the inner $\overline{A\cdot B}$ term:

Let's distribute the terms. Remember, in Boolean algebra, a variable ANDed with its complement is always zero ($A\cdot \overline{A}=0$). It's like saying 'I am both inside and outside the room at the same time'—impossible!

This elegant final expression is the exact definition of an XOR (Exclusive OR) gate. It fires a 1 only when the inputs are different. Looking at our options, the truth table that perfectly matches this behavior is option (a).