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. 

Post a Comment

About Me

My photo

Built art installations, web sites, graphics libraries, web browsers, mobile apps, desktop apps, media player themes, many nutty prototypes, much bad code, much bad art.

Have freelanced for Verizon, Google, Mozilla, Warner Bros, Sony Pictures, Yahoo!, Microsoft, Valve Software, TDK Electronics.

Ex-Chrome Developer Relations.