TU/e
Mike Boldy en Hans Cuypers

Quantificeren

Quantoren

Tot nu toe hebben we maar één manier om van een predicaat p(x) een propositie te maken, namelijk door de variabele x te vervangen door een waarde. Maar je kunt ook kijken of een predicaat waar is door quantificeren.

Definitie

De symbolen \forall en \exists heten quantoren. Quantificeren is het proces waarbij predicaten worden voorzien van quantoren.

Het universum

De bewering x>0 heeft geen betekenis als x een verzameling is. Daarom moet je bij de quantificatie \forall x[x>0] de uitspraak ``voor iedere'' beperken tot een zinvolle verzameling. Deze verzameling noemen we het universum. Het universum is meestal niet nauwkeurig omschreven. Net zoals bij verzamelingen moet je vaak uit de context halen wat het universum is. Als je precies wilt zijn met het aangeven van het universum U kun je dit in de notatie aangeven:

\forall_{x\in U}[p(x)].
In de praktijk kom je allerlei varianten tegen:
\forall_{x\geq0}[\left(\sqrt{x}\right)^2=x].
Het universum bestaat kennelijk uit alle niet-negatieve reële getallen.

Een leeg universum

Het komt niet vaak voor, maar af en toe gebeurt het toch: het universum is leeg. Uit de definitie kun je niet afleiden wat je moet doen, daarom spreken we af wat je moet doen.

Definitie

Als het universum leeg is de bewering \forall_x[p(x)] waar en de bewering \exists_x[p(x)] onwaar.

Let op: dit geldt voor ieder predicaat p.

Dat \exists_x[p(x)] onwaar is voor een leeg universum is logisch: Er zijn geen x-en, dus er zijn zeker geen x-en waarvoor p(x) waar is. Dat \forall_x[p(x)] waar is voor een leeg universum klinkt minder logisch. Toch blijk het handig te zijn om het zo te doen. We komen hierop nog terug bij de logische wetten voor predicaten.

Quantoren in de wiskunde

Quantoren zitten vaak impliciet verstopt in allerlei definities, rekenregels en stellingen. Denk maar aan de gonioformules. De verdubbelingsformule voor de sinus luidt:

\sin(2\varphi)=2\sin(\varphi)\cos(\varphi).
Eigenlijk zou je moeten schrijven:
\forall_{\varphi}[\sin(2\varphi)=2\sin(\varphi)\cos(\varphi)].
De quantor wordt vaak weggelaten om de regel beter leesbaar te maken. Er wordt aangenomen dat de lezer begrijpt dat de verdubbelingsformule geldt voor ieder getal \varphi.

In de meeste wiskundeboeken kom je de \forall en \exists-symbolen niet tegen. Als quantificatie echt nodig is, wordt doorgaans gebruik gemaakt van geschreven taal:

Voor ieder getal \varphi geldt \sin(2\varphi)=2\sin(\varphi)\cos(\varphi).

Voorbeeld

De \forall en \exists quantor lijken in veel opzichten op de \wedge en \vee. Neem een universum met precies twee elementen: U=\{a,b\}, en een predicaat p op U. Dan geldt

\forall_{x\in U}[p(x)]\Leftrightarrow p(a)\wedge p(b)
en
\exists_{x\in U}[p(x)]\Leftrightarrow p(a)\vee p(b)

Voorbeeld

Hier zie je een aantal voorbeelden waarin quantificatie prominent naar buiten treedt:

Voorbeeld

Eén manier om aan quantoren te denken is met behulp van het zogenaamde schakelaarmodel.

Met iedere x_1,x_2,\ldots,x_n correspondeert een schakelaar. Als p(x_i) waar is, is de schakelaar gesloten, en kan er stroom door vloeien. Als p(x_i) onwaar is, is de schakelaar open, en wordt de stroom geblokkeerd.
De \forall-quantor krijg je door alle schakelaars p(x_i) in serie te schakelen. De schakeling laat alleen dan stroom door als alle schakelaars gesloten zijn.
De \exists-quantor krijg je door alle schakelaars p(x_i) parallel te schakelen. Deze schakeling laat stroom door als er tenminste één schakelaar gesloten is. Er mogen meer gesloten schakelaars zijn, maar dat hoeft niet.

Bedenk dat dit model gebaseerd is op een eindig universum. Ook nu zie je goed het verband tussen de \forall quantor en \wedge:

\forall_{x}[p(x)]\Leftrightarrow p(x_1)\wedge p(x_2)\wedge\cdots\wedge p(x_n).
En voor de \exists quantor en \vee:
\exists_{x}[p(x)]\Leftrightarrow p(x_1)\vee p(x_2)\vee\cdots\vee p(x_n).