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.