Code: Selecteer alles
a b | A B C D E F G H I J K L M N O P
----+---------------------------------
0 0 | 0 0 0 0 0 0 0 0 1 1 1 1 1 1 1 1
0 1 | 0 0 0 0 1 1 1 1 0 0 0 0 1 1 1 1
1 0 | 0 0 1 1 0 0 1 1 0 0 1 1 0 0 1 1
1 1 | 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1
Hierboven alle 16 mogelijke waarheidstabellen voor connectieven (= operatoren = logische functies) A t/m P, die werken op de variabelen a en b.
operator B is de EN functie: a B b = a ∧ b
operator H is de OF functie: a H b = a ∨ b
operator J is de equivalentie: a J b = a ↔ b
Nu kiezen we een verzameling operatoren, bijvoorbeeld { B, D, G, K }.
De vraag is: als we alleen operatoren uit deze verzameling mogen gebruiken (naast een onbeperkt aantal keren de variabelen a en b), kunnen we dan met formules (die je zo lang mag maken als je zelf wilt) alle 16 waarheidstabellen construeren?
Zo ja, dan is deze verzameling operatoren functioneel volledig.
Voorbeeld: de NAND functie: a O b = a ⊼ b:
hiermee kunnen we de 3 functies van de disjunctieve normaalvorm maken:
¬a = a ⊼ a
a ∧ b = (a ⊼ b) ⊼ (a ⊼ b)
a ∨ b = (a ⊼ a) ⊼ (b ⊼ b)
(werk van deze 3 formules zelf vooral de waarheidstabellen uit)
Verder hadden we al bewezen dat deze normaalvorm elke waarheidstabel (= alle 16) kan vormen,
waarmee { ¬, ∧, ∨ } functioneel volledig is.
De verzameling { NAND } is dus ook functioneel volledig: met NAND bouw je eerst de NOT, AND en OR functie, die op hun beurt elke andere functie kunnen bouwen:
a A b = a ∧ ¬a = (a ⊼ (a ⊼ a)) ⊼ (a ⊼ (a ⊼ a))
a B b = a ∧ b = (a ⊼ b) ⊼ (a ⊼ b)
a C b = a ∧ ¬b = (a ⊼ (b ⊼ b)) ⊼ (a ⊼ (b ⊼ b))
a D B = a
... etc. t/m a P b
