x + (y + z) = (x + y) + z
x + 0 = x
x + -x = 0
x + y = y + x
x * (y * z) = (x * y) * z
x * (y + z) = (x*y) + (x*z)
x * 1 = x
x * y = y * x
Let's define AND next:
a AND b = a * b
a AND 1 = a because x * 1 = x
a AND 0 = 0
x * 0 = 0 derives from
x * (y + z) = (x*y) + (x*z): call with z = 0 =>
x * (y+0) = (x * y) + (x * 0) <=>
x * y = (x * y) + (x * 0) <=>
x * 0 = 0
For 0 AND b = 0 and 1 AND b = b, apply x * y = y * x to the above.
Applying all the 0,1 combinations to AND we get the truth table:
0 AND 0 = 0
0 AND 1 = 0
1 AND 0 = 0
1 AND 1 = 1
Then NOT:
NOT a = 1 + -a
NOT 0 = 1 + -0, apply -0 = 0 and x + 0 = x
NOT 0 = 1
-0 = 0 because
(0 + -0) = 0, apply x + y = y + x
(-0 + 0) = 0, apply x + 0 = x
-0 = 0
NOT 1 = 1 + -1, apply x + -x = 0
NOT 1 = 0
When we combine NOT with AND, we get NAND:
a NAND b = NOT (a AND b)
NOT (0 AND 0) = 1
NOT (0 AND 1) = 1
NOT (1 AND 0) = 1
NOT (1 AND 1) = 0
Writing it out as an equation:
a NAND b = 1 + -(a * b)
NAND is functionally complete so we can write all the 16 possible (binary, binary) -> binary -functions using only NANDs.
No comments:
Post a Comment