Boolean Function Realization with NAND Gates

Understanding how to implement a given Boolean function using only universal gates like NAND gates is a fundamental concept in digital electronics. A universal gate is one that can be used to construct all other logic gates (AND, OR, NOT).

Understanding Universal Gates and NAND Gate Equivalents

A two-input NAND gate produces an output that is the complement of the AND operation of its inputs. The truth table for a NAND gate is:

Here's how other basic gates can be realized using only NAND gates:

• NOT Gate (Inverter): A NAND gate with both inputs tied together acts as a NOT gate. If input is \(A\), output is \(\overline{A \cdot A} = \overline{A}\).
• AND Gate: An AND gate can be realized by taking the output of a NAND gate (\(\overline{AB}\)) and passing it through another NAND gate configured as an inverter. So, \(\overline{\overline{AB}} = AB\). This requires two NAND gates.
• OR Gate: An OR gate (\(A+B\)) can be realized using three NAND gates based on De Morgan's theorem. \(A+B = \overline{\overline{(A+B)}}\). Applying De Morgan's to the inner part: \(A+B = \overline{\overline{A} \cdot \overline{B}}\). This means invert A, invert B, then NAND the inverted outputs. This requires three NAND gates.

Realizing the Boolean Function Y = AB + CD

The given Boolean function is \(Y = AB + CD\). Our goal is to implement this using the minimum number of two-input NAND gates.

We can use De Morgan's theorem to transform the expression into a form directly implementable with NAND gates. The theorem states:

• \(\overline{X + Y} = \overline{X} \cdot \overline{Y}\)
• \(\overline{X \cdot Y} = \overline{X} + \overline{Y}\)

Let's take the given function \(Y = AB + CD\).

Step 1: Apply double negation.

Any expression \(Z\) can be written as \(\overline{\overline{Z}}\). So, \(Y = \overline{\overline{(AB + CD)}}\).

Step 2: Apply De Morgan's theorem to the inner complement.

We have \(\overline{AB + CD}\). Let \(X = AB\) and \(Y = CD\). Then this becomes \(\overline{X + Y}\), which, by De Morgan's, is equal to \(\overline{X} \cdot \overline{Y}\).

So, \(Y = \overline{\overline{(AB)} \cdot \overline{(CD)}}\).

Step 3: Implement using NAND gates.

The expression \(Y = \overline{\overline{(AB)} \cdot \overline{(CD)}}\) directly translates to a structure using NAND gates:

1. First NAND gate: Takes inputs \(A\) and \(B\). The output will be \(\overline{AB}\).
2. Second NAND gate: Takes inputs \(C\) and \(D\). The output will be \(\overline{CD}\).
3. Third NAND gate: Takes the outputs of the first two NAND gates (\(\overline{AB}\) and \(\overline{CD}\)) as its inputs. The output will be \(\overline{(\overline{AB}) \cdot (\overline{CD})}\).

According to De Morgan's theorem, \(\overline{(\overline{AB}) \cdot (\overline{CD})} = \overline{\overline{AB}} + \overline{\overline{CD}} = AB + CD\). This is exactly our target function \(Y\).

Therefore, only 3 two-input NAND gates are required to realize the Boolean function \(Y = AB + CD\).