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

Dit forum kan gratis blijven vanwege banners als deze. Door te registeren zal de onderstaande banner overigens verdwijnen.
Gebruikersavatar
Moderator
Berichten: 49.984

Re: [informatica] Functionele volledigheid

Opmerking moderator

Verplaatst naar Informatica en programmeren

Berichten: 232

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