Stelling Elke Boolese functie kan gedefinieerd worden m.b.v. de "logische" Boolese functies and, or en not.
Bewijs
Laat f een willekeurige n-plaatsige Boolese functie zijn, en
definieer nu X = {(x1,...,xn) | f(x1,...,xn) = 1}, de rijtjes die
door f afgebeeld worden op 1.
Indien X leeg is, kunnen we f vervangen door
and(x,not(x)).
Stel nu dat X niet leeg is. Voor elk element z van X = {z1,...zn}
definiëren we fz = and(y1,...,yn) waarbij yi =
xi indien xi= 1, en yi = not(xi) indien xi = 0.
Nu kan f vervangen worden door
or(fz1(x1,...,xn),...,fzm(x1,...,xn))
waarbij z1,....,zm een opsomming van de elementen van X is.
Na wat gecijfer kan je inzien dat deze functie inderdaad hetzelfde doet als f.