Show that the NOR is functionally complete (aka a combination of NOR gates can replace any other logic gate) by implementing a NOT, a two-input AND, and a two-input OR using only two-input NORs.
The correct answer and explanation is:
Answer:
To show that NOR is functionally complete, we must demonstrate that we can build the basic logic gates (NOT, AND, and OR) using only two-input NOR gates.
1. NOT Gate using NOR:
Let input be A. NOT(A)=A↓A=A+A‾=A‾\text{NOT}(A) = A \downarrow A = \overline{A + A} = \overline{A}
✅ NOT(A) = A NOR A
2. OR Gate using NOR:
Let inputs be A and B.
Step 1: Get NOT(A) and NOT(B) A′=A↓A,B′=B↓BA’ = A \downarrow A,\quad B’ = B \downarrow B
Step 2: NOR the results A+B=(A↓A)↓(B↓B)A + B = (A \downarrow A) \downarrow (B \downarrow B)
✅ OR(A, B) = (A NOR A) NOR (B NOR B)
3. AND Gate using NOR:
Let inputs be A and B.
Step 1: Compute A NOR B A↓B=A+B‾A \downarrow B = \overline{A + B}
Step 2: NOT(A NOR B) A+B‾‾=A+B\overline{\overline{A + B}} = A + B
Step 3: Use DeMorgan’s law: A⋅B=A‾+B‾‾A \cdot B = \overline{\overline{A} + \overline{B}}
So:
- NOT(A) = A NOR A
- NOT(B) = B NOR B
- AND = (A’ NOR B’) = (A NOR A) NOR (B NOR B)
Then apply NOR again: A⋅B=[(A↓A)↓(B↓B)]↓[(A↓A)↓(B↓B)]A \cdot B = \left[ (A \downarrow A) \downarrow (B \downarrow B) \right] \downarrow \left[ (A \downarrow A) \downarrow (B \downarrow B) \right]
✅ AND(A, B) = [ (A NOR A) NOR (B NOR B) ] NOR [ (A NOR A) NOR (B NOR B) ]
Explanation (Approx. 300 Words):
In digital logic, a functionally complete gate can be used to construct any Boolean expression. The NOR gate, which stands for “NOT OR,” is one such gate. It outputs true only when all inputs are false. To prove its functional completeness, we must show that we can recreate the three fundamental logic operations: NOT, OR, and AND using only NOR gates.
Starting with NOT, if you input the same variable into both inputs of a NOR gate (i.e., A NOR A), it becomes NOT A, because the NOR operation on the same input gives the inversion.
Next, to construct an OR gate using NORs, we apply DeMorgan’s Law. We first create the inverses of both inputs using the NOT method described above, and then NOR those inverted signals. This effectively gives us the OR function using only NOR gates.
For the AND gate, we rely on the identity that A AND B = NOT(NOT A OR NOT B). Again using DeMorgan’s Law and the previously built NOT and OR equivalents from NOR gates, we can construct AND with only NORs. By combining these steps correctly, we get the required AND logic.
Because any digital logic function can be built from combinations of NOT, AND, and OR gates, and we’ve shown how to build all three using only NOR gates, it follows that NOR gates alone are functionally complete. This makes them powerful tools in digital circuit design, especially in systems where gate types must be minimized for simplicity or cost.