A universal gate is a gate or a group of gates which can implement any Boolean function without the need to use any other types of gates.

Universal gates satisfy 2 conditions:

    1. They should be able to block the input propagation. For example, if one input of an AND gate is 0, then the output of the AND gate stays at 0, i.e., the other input is blocked
    2. They should be able to form an inverter. For example, if both inputs of a NAND gate are tied to the same value, the output of the NAND gate will be inverted, i.e., NAND gate can form an inverter

Based on the criteria above, we can say OR/AND gates are not universal gates, and the following are universal gates:

    1. NAND gate
    2. NOR gate
    3. MUX
    4. AND gate + INV gate
    5. OR gate + INV gate

Obviously, we have not exhausted all combinations. We encourage interviewees to explore by themselves.

It is not uncommon that, interviewers ask questions about how to use NAND or NOR gates to form other gates. We list a few sample questions below:

  1. How to use NAND gates to form the AND function?
    • AND function is a NAND gate concatenated with an inverter, and an inverter can be derived from another NAND gate. Thus this requires 2 NAND gates
  2. How to use NAND gates to form the NOR function?
    • !(A | B) = !A & !B
    • Thus this requires 4 NAND gates: 2 NAND gates to form !A and !B functions respectively, and the other 2 NAND gates to form AND function
  3. How to use NAND gates to form the XOR function?
    • XOR(A, B) = (!A & B) | (A & !B) = (A | B) & (!A | !B) = (A | B) & !(A & B)
    • Let’s say !(A & B) = C, then XOR(A, B)  = (A | B) & C = A & C | B & C = !(!(A & C | B & C)) = !(!(A & C) & !(B & C))
    • Thus this requires 4 NAND gates: 1st NAND gate to form C, 2 NAND gates to form !(A & C) and !(B & C) respectively, and the 4th NAND gate to form the outermost NAND function
  4. How to use NOR gates to form an inverter?
    • Similar to NAND gates, if both inputs of a NOR gate are tied to the same value, the output of the NOR gate will be inverted, i.e., the NOR gate can form an inverter
  5. How to use NOR gates to form the OR function?
    • OR function is a NOR gate concatenated with an inverter, and an inverter can be derived from another NOR gate. Thus this requires 2 NOR gates
  6. How to use NOR gates to form the NAND function?
    • !(A & B) = !A | !B
    • Thus this requires 4 NOR gates: 2 OR gates to form !A and !B functions respectively, and the other 2 NOR gates to form OR function
  7. How to use NOR gates to form the XOR function?
    • XOR(A, B)  = (!A & B) | (A & !B) = (A | B) & (!A | !B) = !(!((A | B) & (!A | !B))) = !((!(A | B)) | (!(!A | !B)))
    • Thus this requires 5 NOR gates: first 2 NOR gates to form !A and !B functions, the 3rd NOR gate to form !(A | B) function, while the 4th NOR gate to form !(!A | !B) function. The last NOR gate is to form the outermost NOR function

Leave a Reply

This site uses Akismet to reduce spam. Learn how your comment data is processed.