TU/e
Mike Boldy en Hans Cuypers

Propositielogica en wiskunde

Wiskundige stellingen, rekenregels en eigenschappen bestaan uit beweringen. Daarom kun je vaak handig gebruik maken van de propositielogica. We lichten dit toe aan de hand van een voorbeeld. We gebruiken een rekenregel uit de verzamelingentheorie.

Als A\subset B en B\subset C, dan A\subset C.
Veel stellingen en regels hebben de vorm van een implicatie. Er zijn voorwaarden (ook wel premissen genaamd), en er is een conclusie. In het voorbeeld is de voorwaarde A\subset B en B\subset C, en de conslusie is A\subset C.

In het hoofdstuk over implicaties hebben we gezien dat er altijd twee aspecten zijn waar we rekening mee moeten te houden: implicaties kun je bewijzen en gebruiken. Voor stellingen geldt hetzelfde

Stellingen bewijzen

Een stelling bewijzen hoef je slechts één keer te doen. Als je dat leuk vindt, kun je voor de sport een stelling op meerdere manieren bewijzen, maar nodig is dit niet. Er zijn meerdere manieren om een stelling te bewijzen.

Direct bewijs

Om een stelling van de vorm p\rightarrow q te bewijzen begin je met aan te nemen dat aan de voorwaarde p is voldaan. Voor de voorbeeldstelling zou je dit als volgt kunnen formuleren:
Stel dat A\subset B en B\subset C.
Het gaat er niet om of dit waar is of niet, je neemt het gewoon aan. Uit deze aanname tracht je dan de conclusie af te leiden:
A\subset C.
Zo'n bewijs gaat bijvoorbeeld als volgt:
Stel x\in A. Uit aanname A\subset B volgt dat x\in B. En uit aanname B\subset C volgt dat x\in C.
Je hebt laten zien dat iedere x die in A zit ook in C zit. Dus A\subset C. Merk op dat je voor het bewijs de aannames echt nodig hebt. Als dat niet zo zou zijn had je de stelling kunnen `versterken' door de overbodige aannames weg te laten.

Opmerking

Eigenlijk is er maar één aanname: A\subset B\wedge B\subset C. Vanwege de logische regels p\wedge q\Rightarrow p en p\wedge q\Rightarrow q kun je ook met beide aannames A\subset B en B\subset C apart aan de slag.

Stellingen toepassen

Een stelling kun je willekeurig vaak toepassen. Om een stelling toe te passen moet je er eerst voor zorgen dat aan de voorwaarden is voldaan, Pas dan kun je de conclusie trekken. Deze manier van werken lijkt op de modus ponens regel:

p\wedge(p\rightarrow q)\Rightarrow q.
In ons voorbeeld zouden we bijvoorbeeld kunnen stellen:
\mathbb N\subset \mathbb Z en \mathbb Z\subset \mathbb Q, dus \mathbb N\subset \mathbb Q.

Je kunt een stelling ook andersom gebruiken. Regel 17 van de rekenregels voor logica zegt dat p\rightarrow q\Leftrightarrow\neg q\rightarrow\neg p. De propositie \neg q\rightarrow\neg p heet de contrapositie van p\rightarrow q. Je ziet dit bijvoorbeeld vaak toegepast worden bij de volgende stelling:

Iedere differentieerbare functie is continu.
Er staat eigenlijk
(f is differentieerbaar)\rightarrow(f is continu).
De contrapositie van deze stelling is:
(f is niet continu)\rightarrow(f is niet differentieerbaar).
oftewel
Als een functie niet continu is, is ze ook niet differentieerbaar.
Opmerking

Een veel gemaakt fout is de valse contrapositie. Daarbij verwisselt men zonder pardon de voorwaarden en de conclusie.

Iedere continue functie is differentieerbaar.
Dit is uiteraard niet waar. Denk bijvoorbeeld maar aan de continue functie f(x)=|x|, die niet differentieerbaar is in 0.

Bewijs uit het ongerijmde

Voor stellingen wordt soms gebruik gemaakt van een bewijs uit het ongerijmde. De structuur van een dergelijk bewijs is

(p\wedge\neg q)\rightarrow 0.
De 0 staat hier voor een tegenspraak. Je stelt dat aan de voorwaarde p is voldaan en neemt aan dat q onwaar is. Hieruit leid je een tegenspraak af. De conclusie is dat q waar moet zijn. Dat deze redenering in orde is volgt uit de logische equivalentie van (p\wedge\neg q)\rightarrow 0 en p\rightarrow q:
\begin{array}{lll} (p\wedge\neg q)\rightarrow 0 & \Leftrightarrow & \neg(p\wedge\neg q)\vee 0 \\ & \Leftrightarrow & \neg(p\wedge\neg q) \\ & \Leftrightarrow & \neg p\vee\neg\neg q \\ & \Leftrightarrow & \neg p\vee q \\ & \Leftrightarrow & p\rightarrow q \end{array}

Een variant op deze redenering krijg je als de stelling de vorm p\rightarrow\neg q heeft. In dat geval bewijs je

(p\wedge q)\rightarrow 0.

Voorbeelden

Voorbeeld

Een logische equivalentie is een conjuctie van twee implicaties (regel 18):

p\leftrightarrow q\Leftrightarrow(p\rightarrow q)\wedge(q\rightarrow p)
Omdat p en q vaak ook weer bestaan uit implicaties kunnen wiskundige bewijzen behoorlijk gecompliceerd worden. Goed opschrijven wordt dan erg belangrijk.

Bekijk bijvoorbeeld de complementstelling

\overline{A}=B\Leftrightarrow A\cap B=\emptyset\wedge A\cup B=U.
Het bewijs bestaat uit twee implicaties:
\overline{A}=B\Rightarrow A\cap B=\emptyset\wedge A\cup B=U
en
A\cap B=\emptyset\wedge A\cup B=U\Rightarrow \overline{A}=B.
Het bewijs van de eerste bewering bestaat uit twee delen: je moet zowel A\cap B=\emptyset als A\cup B=U. bewijzen. Voor het bewijs van de tweede implicatie hoef je maar één gelijkheid te bewijzen.

Bedenk dat ieder gelijkheidsbewijs van verzamelingen uit twee delen bestaat: om V=W aan te tonen moet je bewijzen dat V\subset W en W\subset V.

Voorbeeld

We willen de volgende regel bewijzen:

A\subset B\Rightarrow\overline{B}\subset\overline{A}.
Je kunt dit direct bewijzen, maar we doen het uit het ongerijmde. Stel dat A\subset B, maar \overline{B}\not\subset\overline{A}. Het laatste betekent dat er een x bestaat zodat x\in\overline{B} maar x\not\in\overline{A}. De bewering x\not\in\overline{A} betekent hetzelfde als x\in A. Uit de aanname A\subset B volgt dan dat x\in B. Dit is in tegenspraak met x\in\overline{B}.

Voorbeeld

Een fraai voorbeeld van een bewijs uit het ongerijmde vind je bij de volgende stelling, toegeschreven aan Euclides:

Er zijn oneindig veel priemgetallen.
Bij een direct bewijs zou je de vezameling van alle priemgetallen op de een of andere manier moeten beschrijven, een onmogelijke opgave. Bij het bewijs uit het ongerijmde ga je als volgt te werk: stel dat er slechts eindig veel priemgetallen zijn. Hieruit leid je dan een tegenspraak af.

Er zijn meer manieren om dit te doen. Je kunt bijvoorbeeld het volgende doen: stel \mathbb P=\{p_1,p_2,\ldots,p_n\} is de verzameling van alle priemgetallen. Dan kun je aantonen dat het getal p=1 + p_1\cdot p_2\cdots p_n een priemgetal is dat niet in \mathbb P voorkomt. Hetgeen niet kan, want \mathbb P is de verzameling van alle priemgetallen.

Merk op dat bij deze stelling kennelijk geen voorwaarden zijn geformuleerd. Hij is van de vorm 1\rightarrow q.