[informatica] Functionele volledigheid

Moderators: jkien, Xilvo

Reageer
Berichten: 206

[informatica] Functionele volledigheid

Over functionele volledigheid staat het volgende geschreven op http://www.hhofstede.nl/modules/volledigheid.htm
functionele volledigheid.PNG
Maar ik begrijp niet zo goed hoe functionele volledigheid bewezen kan worden aan de hand van waarheidstabellen.

Wilt iemand dit verduidelijken alstublieft?

Alvast bedankt.

Gebruikersavatar
Moderator
Berichten: 51.259

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
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

Berichten: 206

Re: [informatica] Functionele volledigheid

Ontzettend bedankt!

Uw heldere uitleg heeft alle onduidelijkheden weggenomen.

Reageer