[Math] Obtain the Boolean expression from the given circuit diagram

boolean-algebra

Circuit Diagram

Currently having trouble understanding how to write out the boolean expression up to the exclusive or gate. Up to the third NAND gate I solved it to be AB+CD. But I get stumped on how to write out the fourth gate. Would it be 0 (+) AB+CD then? If so how would I expand this expression further?

Best Answer

The lesson here, I think, is how you deal with a logic gate when one or more inputs of the gate have been wired to a constant $0$ or $1$. This may seem like a silly thing to do, but it has at least two very practical applications I can think of:

  1. When you have to use an off-the-shelf part rather than being able to specify a circuit with exactly the gates you want and no others, you may end up with some superfluous gates (or superfluous inputs to some gates) and you have to "tie off" the extra inputs to something that will allow the circuit to function the way you want despite the unwanted logic.

  2. When there is a manufacturing defect in a digital logic circuit, it often manifests as if one of the outputs of a gate is shorted either to the "$0$" voltage source (e.g., ground) or shorted to the "$1$" voltage source. If you want to devise tests to detect whether such a defect has happened, you have to figure out how the device will behave differently with this constant $0$ or $1$ input to some of its gates instead of the usual logic inputs. Whole textbooks have been written on this problem.

The basic rules are actually quite simple. For example, here's the logic table for a two-input NAND gate with inputs $X$ and $Y$:

$$\begin{array}{ccc} X & Y & \mbox{output} \\ \hline 0 & 0 & 1 \\ 1 & 0 & 1 \\ 0 & 1 & 1 \\ 1 & 1 & 0 \end{array}$$

Now what happens if we short $Y$ to the $1$ voltage source is that $Y$ is never $0$, so the first two lines of the table above become irrelevant. We're left with

$$\begin{array}{ccc} X & Y & \mbox{output} \\ \hline 0 & 1 & 1 \\ 1 & 1 & 0 \end{array}$$

So $X\ \mathrm{NAND}\ 1 = X'$, that is, the NAND gate becomes a simple inverter for the remaining non-shorted input.

To see the implications for an XOR gate (or any other logic element), you can write out a similar logic table. In this case one of the inputs is shorted to $0$, so you can scratch out the lines where that input is $1$ and see what's left.

Related Question