unit1.2 Boolean function

Any boolean function can be represented using an expression contains AND and NOT operation 

 

proof : 

(x OR y) = NOT(NOT(x) AND NOT(y))

 

 

definition : x NAND y = NOT (x AND y) 

Any boolean function can be represented using an expression contains only NAND operation 

 

proof : 

NOT(x) = x NAND x

x AND y = NOT ( x NAND y) = ( x NAND y) NAND ( x NAND y)