art with code

2013-04-27

Boolean Algebra, the crunchy version

First some ring axioms:
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:

Blog Archive