NAND Gate Completeness: Understanding Functionally Complete Sets

This question asks us to identify which of the given sets of logic gates is functionally complete. A set of logic gates is considered functionally complete if it's possible to realize any other logic gate (like AND, OR, XOR, etc.) using only the gates within that set. These sets are also known as universal gates.

Analysing NAND Gate Universality

Let's look at the first option, the NAND gate:

• The NAND gate (Not-AND) outputs a 0 only when all its inputs are 1; otherwise, it outputs 1.
• It is a well-established fact in digital logic design that the NAND gate by itself is functionally complete. This means we can create all other basic logic gates using only NAND gates:
  • NOT Gate: A NOT gate can be implemented by connecting the inputs of a NAND gate together. So, $A'$ = NAND(A, A).
  • AND Gate: An AND gate can be implemented by using a NAND gate followed by a NOT gate (which is also a NAND gate). So, $A \cdot B$ = NAND(NAND(A, B), NAND(A, B)).
  • OR Gate: An OR gate can be implemented using De Morgan's laws. $A + B = (A' \cdot B')'$ = NAND(NAND(A, A), NAND(B, B)).
• Since we can construct NOT, AND, and OR gates (and thus any other gate) using only NAND gates, the set containing just the NAND gate is functionally complete.

Analysing NOT Gate Completeness

Now let's consider the second option, the NOT gate:

• The NOT gate (also called an inverter) simply inverts the input signal. If the input is 1, the output is 0, and if the input is 0, the output is 1.
• Can we create an AND gate using only NOT gates? No. An AND gate requires two inputs and produces an output based on the logical AND operation ($A \cdot B$). A NOT gate only operates on a single input and performs inversion. We cannot replicate the AND or OR function using only inversion.
• Therefore, the set containing only the NOT gate is not functionally complete.

Evaluating the Options

Based on the analysis:

• Set (i) {NAND} is functionally complete.
• Set (ii) {NOT} is not functionally complete.

Let's examine the given options:

• Option 1: I but not II - This states that NAND is functionally complete, but NOT is not. This matches our findings.
• Option 2: II but not I - This states NOT is complete, and NAND is not. This is incorrect.
• Option 3: Neither I not II - This states neither set is complete. This is incorrect.
• Option 4: Both I and II - This states both sets are complete. This is incorrect.

Thus, the only correct statement is that the NAND gate alone is functionally complete, while the NOT gate alone is not.