Logic Gate

   Logic gate is a basic element of [1]logic circuits, a simple device that
   implements a [2]Boolean function, i.e. it takes a number of [3]binary (1
   or 0) input values and transforms them into an output binary value. Logic
   gates are kind of "small boxes" that eat 1s and 0s and spit out other 1s
   and 0s. Strictly speaking a logic gate must implement a mathematical
   function, so e.g. [4]flip-flops don't fall under logic gates because they
   have an internal state/[5]memory.

   Logic gates are to logic circuits kind of what [6]resistors,
   [7]transistors etc. are for electronic circuits. They implement basic
   functions that in the realm of boolean logic are equivalents of addition,
   multiplication etc.

   Behavior of logic gates is, just as with logic circuits, commonly
   expressed with so called [8]truth tables, i.e. a tables that show the
   gate's output for any possible combination of inputs. But it can also be
   written as some kind of equation etc.

   There are 2 possible logic gates with one input and one output:

     * [9]identity (buffer): Output equals the input. This doesn't have any
       function from the logic perspective but can e.g. be used as a
       placeholder or to introduce intentional delay in the physical circuit
       etc.
     * [10]NOT: Negates the input (0 to 1, 1 to 0).

   There are 16 possible logic gates with two inputs and one output (logic
   table of 4 rows can have 2^4 possible output values), however only some of
   them are commonly used and have their own names. These are:

     * [11]OR: Gives 1 if at least one input is 1, otherwise 0.
     * [12]AND: Gives 1 if both inputs are 1, otherwise 0.
     * [13]XOR (exclusive OR): Gives 1 if inputs differ, otherwise 0.
     * [14]NOR: Negation of OR.
     * [15]NAND: Negation of AND.
     * [16]XNOR: Negative XOR (equality).

   The truth table of these gates is as follows:

   x y x OR y x AND y x XOR y x NOR y x NAND y x XNOR y 
   0 0 0      0       0       1       1        1        
   0 1 1      0       1       0       1        0        
   1 0 1      0       1       0       1        0        
   1 1 1      1       0       0       0        1        

     ___             ___              _____            _____
  ---\  ''-.      ---\  ''-.      ---|     '.      ---|     '.     
      )     )---      )     )O--     |       )---     |       )O--
  ---/__..-'      ---/__..-'      ---|_____.'      ---|_____.'
      OR              NOR             AND              NAND
     ___             ___             .                .
  --\\  ''-.      --\\  ''-.         |'.              |'.
     ))     )---     ))     )O--  ---|  >---       ---|  >O--
  --//__..-'      --//__..-'         |.'              |.'
      XOR             XNOR           ' BUFFER         ' NOT

  alternatively:
      ____          ____          ____          ____
  ---|=> 1|     ---| &  |     ---|= 1 |        | 1  |
     |    |---     |    |---     |    |---  ---|    |o--
  ---|____|     ---|____|     ---|____|        |____|
      OR            AND           XOR           NOT
    
  or even:
     ___        ___        ___        ___
  --|OR |--  --|AND|--  --|XOR|--  --|NOT|--
  --|___|    --|___|    --|___|      |___| 

   symbols often used for logic gates

   Functions NAND and NOR are so called [17]functionally complete which means
   we can implement any other gate with only one of these gates. For example
   NOT(x) = NAND(x,x), AND(x,y) = NAND(NAND(x,y),NAND(x,y)), OR(x,y) =
   NAND(NAND(x,x),NAND(y,y)) etc. Similarly NOT(x) = NOR(x,x), OR(x,y) =
   NOR(NOR(x,y),NOR(x,y)) etc.

See Also

     * [18]logic circuit
     * [19]quantum gate

Links:
1. logic_circuit.md
2. bool.md
3. binary.md
4. flip_flop.md
5. memory.md
6. resistor.md
7. transistor.md
8. truth_table.md
9. identity.md
10. not.md
11. or.md
12. and.md
13. xor.md
14. nor.md
15. nand.md
16. xnor.md
17. functional_completeness.md
18. logic_circuit.md
19. quantum_gate.md