Logic Gates

|Name|Shape| |-|-| |AND|Like a “D”| |OR|Like a crescent| |NOT|Like a triangle with a dot| |NAND|Like and with a dot| |NOR|Like an OR with a dot| |XOR|Like OR with an extra crescent|

AND

|Input 1|Input 2|Output| |-|-|-| |0|0|0| |0|1|0| |1|0|0| |1|1|1|

OR

|Input 1|Input 2|Output| |-|-|-| |0|0|0| |0|1|1| |1|0|1| |1|1|1|

NOT

|Input 1|Output| |-|-| |0|1| |1|0|

NAND

AND + NOT

NOR

OR + NOT

XOR

OR, but 1 & 1 is 0.

XOR is also sometimes called the NEQ operator, meaning “not equivalent”. This is because you can also describe it as only being true if the operands differ.

XOR is probably the most popular logical operator in exams. The property that makes this useful is that XOR is like adding two binary numbers together in a single column:

| 0|   | 1|   | 1|
| 0|   | 0|   | 1|
|--|   |--|   |--|
| 0|   | 1|   | 0| (1 carried over)

Half-Adders

A one-bit binary adder. This means it can deal with adding two one-bit binary numbers together and dealing with carries.

They take two inputs:

• A, the first binary digit.
• B, the second binary digit.

And have two outputs:

• S, the sum of the two binary digits.
• C, the carry from the addition if there was one.

Full Adders

Full adders take three inputs:

• A, one bit
• B, one bit
• C in, a carry bit

They have two outputs:

• Sum, the result of adding the two bits and the carry (think “left hand column”)
• C out, the carry.

Notice how the truth table is just like adding three numbers together. You can think of a full adder as a half adder that then has to deal with a carry in bit too. There’s this really beautiful way that a full adder is actually just two half adders and an OR gate and it’s in my head but I can’t get it out.