Most of mathematics (especially Axiomatic Set Theory and Number Theory) employs Classical (binary) logic — statements are either true or false. Electronic computers feature logic gates for the most primitive computations, using 0=false, 1=true. An infinite number of gates are possible; here are six of the most common:
Operations can be extended to bit strings. Examples
NOT(10110) = 01001 01101 01101 01101
AND 10100 OR 10100 XOR 10100
--------- --------- ---------
00100 11101 11001
Note the following useful formulas...
x AND 0 = 0 x OR 0 = x x XOR 0 = x
x AND 1 = x x OR 1 = 1 x XOR 1 = ~x
x AND x = x x OR x = x x XOR x = 0
...from which you can discover such tricks as
| A=0 B=0 |
A=0 B=1 |
A=1 B=0 |
A=1 B=1 |
Operation |
|---|---|---|---|---|
| 0 | 0 | 0 | 0 | 0 |
| 0 | 0 | 0 | 1 | A and B, A ∧ B |
| 0 | 0 | 1 | 0 | A andnot B, A ∧ ~B |
| 0 | 0 | 1 | 1 | A |
| 0 | 1 | 0 | 0 | ~A ∧ B |
| 0 | 1 | 0 | 1 | B |
| 0 | 1 | 1 | 0 | A xor B, ~(A = B), A ≠ B |
| 0 | 1 | 1 | 1 | A or B, A ∨ B |
| 1 | 0 | 0 | 0 | A nor B, ~(A ∨ B), (~A ∧ ~B) |
| 1 | 0 | 0 | 1 | A xnor B, ~(A xor B), A = B |
| 1 | 0 | 1 | 0 | not B, ~B, ¬B |
| 1 | 0 | 1 | 1 | A ornot B, A ∨ ~B, B implies A |
| 1 | 1 | 0 | 0 | not A, ~A, ¬A |
| 1 | 1 | 0 | 1 | ~A ∨ B, A implies B |
| 1 | 1 | 1 | 0 | A nand B, ~(A ∧ B), (¬A ∨ ¬B) |
| 1 | 1 | 1 | 1 | 1 |
An interesting intellectual exercise is to come up with what are known as complete sets of operations. A complete set is a set of operations from which all sixteen operations can be derived. For example {NOT, AND, OR} is complete, so is {NAND}. But {OR} is not complete.
Logic designers create circuits to do things that they want. They basically want to implement functions that take certain inputs into certain outputs. For example, here is a logic circuit that adds two four-bit integers.
How did anyone figure this out? First let's try the case where we only want to add two one bit numbers. Call the inputs x and y, and the outputs will be s (for sum) and c (for carry). Write down the behavior for all possible combinations of inputs:
x y | s c
------+------
0 0 | 0 0
0 1 | 1 0
1 0 | 1 0
1 1 | 0 1
Cool, so we see that s = x XOR y, and c = x AND y. So here is our half-adder:
Now to add multi-bit numbers, we have add the carries into the inputs as we move from right to left, like you learned in elementary school. Thus the full-adder has three inputs, x and y and the "carry in". Let's make the table and see what we should do:
x y cin | s cout
---------+---------
0 0 0 | 0 0
0 0 1 | 1 0
0 1 0 | 1 0
0 1 1 | 0 1
1 0 0 | 1 0
1 0 1 | 0 1
1 1 0 | 0 1
1 1 1 | 1 1
So s = x XOR y XOR cin and cout = (y AND cin) OR (x AND cin) OR (x AND y).
You can build a multibit adder by putting a half adder on the right and a sequence of full adders to its left, or just use full adders and force a zero into the rightmost carry in.
A read-only memory (ROM) is just a logic circuit whose input is an address and whose output is the data at that address! Make one by deciding what values go at what address and build the circuit however you need to.
What about a read-write memory? To read from memory, put the address you want to read from on the address lines, and set the read/write line to read. The value at that address will then appear on the data lines. To write, put the desired address on the address and the data to write on the data lines and set the read/write line to write.
But how do you "store" data? You probably use latches or something similar. A latch can "store" one bit. This is a latch:
The idea is when you set Freeze to 0, the input value goes into the latch. Then you set Freeze to 1. After that no matter what the input does, the output is always what got copied in, so we've "stored" a bit. At least until you unfreeze it.