[informatica] Functionele volledigheid
-
- Berichten: 206
[informatica] Functionele volledigheid
Over functionele volledigheid staat het volgende geschreven op http://www.hhofstede.nl/modules/volledigheid.htm
Maar ik begrijp niet zo goed hoe functionele volledigheid bewezen kan worden aan de hand van waarheidstabellen.
Wilt iemand dit verduidelijken alstublieft?
Alvast bedankt.
Maar ik begrijp niet zo goed hoe functionele volledigheid bewezen kan worden aan de hand van waarheidstabellen.
Wilt iemand dit verduidelijken alstublieft?
Alvast bedankt.
- Moderator
- Berichten: 51.270
Re: [informatica] Functionele volledigheid
Opmerking moderator
Verplaatst naar Informatica en programmeren
-
- Berichten: 463
Re: [informatica] Functionele volledigheid
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
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
-
- Berichten: 206
Re: [informatica] Functionele volledigheid
Ontzettend bedankt!
Uw heldere uitleg heeft alle onduidelijkheden weggenomen.
Uw heldere uitleg heeft alle onduidelijkheden weggenomen.