I started implementing the logic gates in JS for the heck of it. In the process I figured out an interesting algebra for logic circuits. Let's start off with writing some basic JS logic to simulate an abstract transistor. This crummy transistor should give out a 1 when its two input pins are 1. And if either of those is 0 it should return a 0. Let's see:
Transistor = function(control, input) {
if (control) {
return input;
} else {
return 0;
}
};
Hmm, well, that does work but it's a bit ugly. And if you know about transistors, they're not really like that. You can use a transistor to amplify a signal. Hook up a faint signal to the control and a powerful input and the transistor scales the input by the control signal. Hey, it's like multiplication!
Transistor = function(control, input) {
return control * input;
};
Ok, so a transistor is the multiplication operator. How does that work with binary logic? If we take the set {0, 1} as the type of the inputs for both control and input, all works fine: a 1 in the control passes the input through unchanged, a 0 in the control makes the input 0. From that you can see that 1 is the multiplicative identity and multiplying by 0 annihilates the other operand.
To make a NAND gate we need a bit more than just a transistor though. We either need inverse transistors (for a CMOS NAND) or a ground wire (for a NMOS NAND). The NMOS version is a bit simpler so let's write a ground function for it next. A grounded circuit returns a 0 if the ground wire is connected, otherwise it passes the input through untouched.
Ground = function(ground, input) {
if (ground) {
return 0;
} else {
return input;
}
};
Again, that's a bit ugly. Let's turn that into an arithmetic representation on our {0, 1} algebra.
Ground = function(ground, input) {
return (1-ground)*input;
};
Right, it seems we had to introduce a few new concepts there. Algebra-wise 1-ground is shorthand for 1 + -ground. Which means that we need a second operator for our algebra: the addition. And we also have the additive inverse, thanks to the minus sign there. And as 1-0 should return 1, we also get the additive identity. Add 0 to any input and what you get is the input, unchanged.
The algebra we have now has addition, additive identity, additive inverse, multiplication and a multiplicative identity. I think we also have to expand our set to include the additive inverses, netting us the set {-1, 0, 1}. I haven't found a use for the negative numbers in the binary logic though. The alternative would be to turn (1-x) into an axiomatic operation of some sort, I guess.
Oh, also, the inverse transistor has the same formula as the ground operator (if a different wiring implementation).
ITransistor = function(control, input) {
return (1-ground)*input;
};
Ok, enough setup, let's make a NAND gate! A NAND gate takes two inputs and outputs a 0 if both its inputs are 1, in other cases it outputs a 1. An NMOS NAND gate has two transistors controlled between a voltage source and ground, with the idea that if both transistors are on, the source is connected to the ground and the output signal is zero. And if either of the transistors is off, the source is not connected to the ground and the output signal is the source voltage.
NAND = function(a, b) {
return Ground(Transistor(b, Transistor(a, 1)), 1);
};
The thing about the NAND gate is that it's functionally complete. You can implement any of the other binary logic gates using NAND gates. Don't believe me? Watch this!
NOT = function(v) {
return NAND(v, v);
};
BUFFER = function(v) {
return NOT(NOT(v));
};
AND = function(a, b) {
return NOT(NAND(a, b));
};
Got that? NAND with the same signal to both inputs is a 1 if the signal is 0 and a 0 if the signal is a 1. And AND is the inverse of NAND. Still not enough? Let's do OR, NOR and XOR as well.
NOR = function(a, b) {
return AND(NOT(a), NOT(b));
};
OR = function(a, b) {
return NOT(NOR(a, b));
};
XOR = function(a, b) {
return AND(OR(a, b), NAND(a, b));
};
With that we have functions to generate the truth tables 1110, 0001, 0111, 1000 and 0110 (I'm writing the entries as the outputs for the 2-bit numbers 00, 01, 10 and 11. So 1110 means the function returns the following: 00 -> 1, 01 -> 1, 10 -> 1, 11 -> 0.) But hey, there are 16 different permutations for those truth tables. Let's write more functions.
// 0000
ZERO = function(a, b) {
return AND(AND(a, b), NAND(a, b));
};
// 0001 = AND
// 0010
XLEFT = function(a, b) {
return AND(a, NOT(b));
};
// 0011
LEFT = function(a, b) {
return AND(a, ONE(b, b));
};
// 0100
XRIGHT = function(a, b) {
return AND(b, NOT(a));
};
// 0101
RIGHT = function(a, b) {
return AND(b, ONE(a, a));
};
// 0110 = XOR
// 0111 = OR
// 1000 = NOR
// 1001
XNOR = function(a, b) {
return NOT(XOR(a, b));
};
// 1010
NRIGHT = function(a, b) {
return NOT(RIGHT(a, b));
};
// 1011
XNRIGHT = function(a, b) {
return NOT(XRIGHT(a, b));
};
// 1100
NLEFT = function(a, b) {
return NOT(LEFT(a, b));
};
// 1101
XNLEFT = function(a, b) {
return NOT(XLEFT(a, b));
};
// 1110 = NAND
// 1111
ONE = function(a, b) {
return OR(AND(a, b), NAND(a, b));
};
As you can see from the above, you can implement all the binary functions in {0, 1} using only NAND gates. And since our definition of NAND is in terms of a transistor and a ground operator, which are grounded in some basic arithmetic operations, you can actually write the gates as arithmetic functions.
NAND = function(a, b) {
// (1 - (b * (a * 1)) * 1
// = 1 - (b * a)
return 1 - b*a;
};
NOT = function(v) {
// 1 - v*v (v*v = 0 when v = 0, v*v = 1 when v = 1)
// so in {0,1}, 1-v*v = 1-v
return 1 - v;
};
AND = function(a, b) {
// 1 - (1 - b*a)
// = 1 - 1 + b*a
return b*a;
};
NOR = function(a, b) {
// (1-b) * (1-a)
return (1-b) * (1-a);
};
OR = function(a, b) {
// 1 - ((1-b) * (1-a))
// = 1 - (1*1 + 1*-a + -b*1 + -b*-a)
// = 1 - (1 - a - b + ba)
// = 1 - 1 + a + b - ba
// = a + b - ba
return a+b - b*a;
};
XOR = function(a,b) {
// (1-ba)*(a+b-ba)
return (1-b*a)*(a+b-b*a);
};
And so forth.
Oh, and one more thing. You know the CPU inside your computer? It's made up of NAND gates. Lots and lots of NAND gates hooked up together to compose all the logic in the CPU. And if you think of each NAND as the equation 1-ab, you could think of the CPU as one humongous equation etched onto a silicon chip.
I've got the code for the logic gates and some adder generator code up on GitHub.
