functionele volledigheid

© h.hofstede (h.hofstede@hogeland.nl)

Functionele Volledigheid.

We zijn ons logische alfabet begonnen met het setje connectieven {¬ , ∧, ∨, ⇒, ⇔}.
Daarvan maakten we in deze les vijf waarheidstabellen, maar we zagen toen al dat er veel meer waarheidstabellen mogelijk zijn. Er zijn 16 twee-bij-twee tabellen met enen en nullen te maken. Dat betekent dat we ook best meer connectieven of anderen zouden kunnen gebruiken.

Zo bespraken we bijvoorbeeld ook al de exclusieve disjunctie (α a β). Dat was " OF α, OF β, maar niet beiden", weet je nog? We zagen ook dat die met behulp van de anderen is te definiëren (namelijk door (α ∨ β) ∧ ¬ (α ∧ β))

Definieerbaarheidsvragen.

Dat roept natuurlijk meteen de vraag op: "Zijn er misschien onder de gekozen vijf connectieven ook al sommigen met behulp van anderen te definiëren?" Als dat zo is, dan zouden we die namelijk kunnen dumpen, om zo tot een echt minimaal setje te komen.

Het antwoord op deze vraag is "JA".

Laten we er een paar proberen.

vraag: Is ∨ definieerbaar met ⇒ ?
Het antwoord is JA.
Bewijs: nou kijk maar: (α ∨ β) ⇔ ((α ⇒ β) ⇒ β)
Maak van beiden maar een waarheidstabel en je ziet dat die gelijk zijn.

vraag: Is ⇒ definieerbaar met ¬ en ⇔ ?
Het antwoord is NEE.
Het bewijs is erg simpel als je naar de waarheidstabellen kijkt.
¬ en ⇔ hebben beiden een even aantal enen/nullen in elke rij en kolom van de waarheidstabel. Door ze vaak achter elkaar toe te passen blijft dat aantal enen/nullen altijd even. Hoe vaak je het ook doet.
Maar ⇒ heeft dat niet!
Die is dus nooit te maken met alleen maar Ø en ⇔
Grappig bewijsje niet? Dat noemen we in de wiskunde een pariteitsbewijs.

Stelling:

{¬ , ∧, ∨} is een functioneel volledig stelsel connectieven

Met "functioneel volledig" wordt bedoeld dat je alle 16 waarheidstabellen ermee kunt fabriceren.
In normaal Nederlands zou deze stelling overigens zó kllinken:

"Elke geldige logische formule is óf een contradictie óf logisch equivalent met een inclusieve disjunctie van conjuncties
gevormd m.b.v. (negaties van) propositionele constanten"

Nou ja..... normáál Nederlands???

Kan het met nog minder?
JAZEKER!
Omdat geldt (α ∨ β) ⇔ ¬ (¬ α ∧ ¬ β) kan ∨ ook nog gedumpt worden, en volstaat het stelsel {¬ , ∧}

Kan het met nóg minder?
JAZEKER!
Maar daarvoor hebben we andere waarheidstabellen nodig. Er bestaan twee connectieven die zelfs in hun eentje al een volledig stelsel vormen, en dat zijn de Sheffer Stroke en de Quine Dagger.

(de Quine Dagger wordt ook wel als | genoteerd en heet ook wel Pierce's Arrow)

Omdat deze twee in hun eentje alles kunnen voortbrengen, zijn ze erg geliefd als logische schakeling in elektronische circuits.
Daar heet de Sheffer Stroke een NAND-poort en de Quine Dagger een NOR-poort. Met bijvoorbeeld alleen maar NAND-poorten kun je elke logische schakeling bouwen!


OPGAVEN


1.	Druk de volgende formules uit met alleen maar de Sheffer Stroke.

	a.	¬ α

	b.	α ∧ β

2.	Zelfde vraag als vraag 1, maar nu met de Quine Dagger.

3.	Druk de volgende formules uit met alleen maar de connectieven {¬ , ∧, ∨}

	a.	p₁ ⇒ p₂

	b.	(p₁ ⇒ p₂) ⇒ p₃

	c.	(p₁ ∨ p₂) ⇒ ¬ p₃