Propositielogica

Propositielogica (wiskundige logica) is een middel waarmee de wiskunde zich uitdrukt. We komen haar tegen onder allerlei namen en in allerlei wiskundige stellingen.

Waar dient logica voor

Logica is de wetenschap die zich bezighoudt met redeneren, waarheid, bewijsbaarheid en weerlegbaarheid. In de logica gaat het daarbij alleen om de vorm van een mededeling. Wat er precies wordt gezegd, interesseert ons niet, net zomin als allerlei psychologische interpretaties en dergelijke.

Neem bijvoorbeeld de zin “het getal 2 is even en tegelijk oneven”. Hieruit kunnen we afleiden dat de hele zin niet waar is, omdat het getal 2 niet oneven is. Dit zijn de dingen waar de logica zich in het algemeen mee bezighoudt.

Uitspraak

De basis van de propositielogica is vanzelfsprekend de uitspraak. Een uitspraak is elke mededelende zin waarvan we de waarheidswaarde kunnen bepalen. Voorbeelden van eenvoudige uitspraken:

• Amsterdam is de hoofdstad van Nederland.
• Het natuurlijke getal vijf is een oneven getal.
• HTML is een programmeertaal.
• Twee plus drie is zes.

Dit zijn allemaal uitspraken. Ze zijn waar (de eerste twee) of onwaar (de laatste twee). Een vraagzin is bijvoorbeeld geen uitspraak, en ook een zin waarvan we de waarheidswaarde niet eenduidig kunnen bepalen niet. Nog een voorbeeld:

• Is Utrecht volgend jaar nog steeds de vierde stad van Nederland?
• Groen is de mooiste kleur.

De eerste zin kan geen uitspraak zijn, omdat het een vraagzin is. Bij de tweede zin kunnen we niet bepalen of de uitspraak waar of onwaar is. Zo'n zin noemen we een hypothese (vermoeden).

De klassieke wiskundige logica kan niet zo goed overweg met vage zinnen als “Daan is lang” of “Sophie is een goede zangeres”. Zulke uitspraken worden beter behandeld in bijvoorbeeld de fuzzy logica, die juist voor vaagheid is gemaakt.

Atomaire uitspraak

In het eerste hoofdstuk hadden we het voorbeeld van de uitspraak “het getal 2 is even en tegelijk oneven”. Zo'n uitspraak kunnen we samengesteld noemen, want in werkelijkheid verbindt ze twee kortere uitspraken: “het getal 2 is even” en “het getal 2 is oneven”. Die twee uitspraken zijn verbonden door het logische voegwoord “en”, ook wel “en tegelijk”.

Een atomaire uitspraak is dus een uitspraak die we niet verder kunnen opdelen. In zekere zin is het de eenvoudigste vaststelling. De voorgaande voorbeelden waren in feite atomaire uitspraken:

• Amsterdam is de hoofdstad van Nederland.
• Het natuurlijke getal vijf is een oneven getal.
• HTML is een programmeertaal.
• Twee plus drie is zes.

Atomaire uitspraken geven we verder aan met kleine letters van het alfabet, zoals gebruikelijk p, q, r, …, en we noemen ze propositiesymbolen.

Logische voegwoorden

In de wiskundige logica werken we gewoonlijk met een vaste set logische voegwoorden. Tot de basis horen vier binaire voegwoorden:

• p ∧ q is de conjunctie van uitspraken, we lezen “uitspraak p en (tegelijk) uitspraak q”
• p ∨ q is de disjunctie van uitspraken, we lezen “uitspraak p of uitspraak q”
• p ⇒ q is de implicatie, we lezen “als uitspraak p, dan uitspraak q”
• p ⇔ q is de equivalentie, we lezen “uitspraak p dan en slechts dan als uitspraak q”

Concrete voorbeelden van logische voegwoorden:

• In het centrum van Utrecht regent het en tegelijk schijnt de zon. (conjunctie)
• In het centrum van Utrecht regent het of de zon schijnt. (disjunctie)
• Een kat heeft vier poten en een vogel heeft twee poten. (conjunctie)
• Als je een bak ijs in één keer opeet, dan krijg je al snel buikpijn. (implicatie)
• Als het getal x deelbaar is door vier, dan is het ook deelbaar door twee. (implicatie)
• Lotte is aardig en tegelijk slim. (conjunctie)
• Zangers zijn succesvol dan en slechts dan als ze mooi zingen. (equivalentie)
• Als het niet regent, worden we niet nat. (implicatie)
• Als Bram kan vliegen, dan ben ik de koning van Nederland. (implicatie)

Er is nog één gangbaar logisch voegwoord: de negatie (ontkenning). De negatie schrijven we met een accent p′ of met het symbool ¬p.

Formule

Met propositiesymbolen (atomaire uitspraken) en logische voegwoorden kunnen we een ingewikkelder uitspraak samenstellen, die we een formule noemen. Alle voorbeelden in de vorige lijst waren in feite formules, want we hadden twee atomaire formules, bijvoorbeeld “In het centrum van Utrecht regent het” en “de zon schijnt”, en die hebben we met logische voegwoorden verbonden. In het eerste geval verbonden we ze met het voegwoord “en tegelijk” en kregen we de formule “In het centrum van Utrecht regent het en tegelijk schijnt de zon”, in het tweede geval gebruikten we “of” en kregen we de formule “In het centrum van Utrecht regent het of de zon schijnt”.

Formeel definiëren we een formule zo:

• Elk propositiesymbool (elke atomaire uitspraak) is een formule (nauwkeuriger: een atomaire formule).
• Als A en B formules zijn, dan zijn ook ¬A, (A ∧ B), (A ∨ B), (A ⇒ B) en (A ⇔ B) formules.

De definitie is logisch: in het eerste punt zeggen we dat elke atomaire uitspraak ook een formule is. Als we dus twee atomaire uitspraken hebben, bijvoorbeeld “In het centrum van Utrecht regent het” en “de zon schijnt”, dan hebben we ook twee formules. Nu kunnen we het tweede punt toepassen en een ingewikkelder formule opbouwen, bijvoorbeeld zo:

• In het centrum van Utrecht regent het en tegelijk schijnt de zon.
• In het centrum van Utrecht regent het of de zon schijnt.
• Als in het centrum van Utrecht de zon schijnt, dan regent het.
• In het centrum van Utrecht schijnt de zon dan en slechts dan als het regent.

Formules hoeven natuurlijk niet per se waar te zijn. We hebben nu een nieuwe verzameling formules, dus we kunnen nog ingewikkelder formules samenstellen. Noemen we A = “In het centrum van Utrecht schijnt de zon of het regent.” (we weten al dat dit een formule is) en B = “er is een regenboog te zien” (laten we aannemen dat dit ook in het centrum van Utrecht is, zodat we het niet steeds hoeven te herhalen), dan kunnen we nieuwe formules maken. De haakjes in de zinnen geven alleen aan op welke delen een voegwoord betrekking heeft.

• A ∧ B: (In het centrum van Utrecht schijnt de zon of het regent) en tegelijk (er is een regenboog te zien).
• A ∨ B: (In het centrum van Utrecht schijnt de zon of het regent) of (er is een regenboog te zien).
• A ⇒ B: (Als in het centrum van Utrecht de zon schijnt of het regent), dan (is er een regenboog te zien).
• A ⇔ B: (In het centrum van Utrecht schijnt de zon of het regent) dan en slechts dan als (er een regenboog te zien is).

Dit zijn allemaal formules. We kunnen dus opnieuw een van deze formules nemen en er een andere formule aan koppelen. Zo kunnen we bijvoorbeeld de wirwar “Als in het centrum van Utrecht de zon schijnt of het regent of er een regenboog te zien is, dan schijnt de zon of regent het dan en slechts dan als er een regenboog te zien is.” maken.

In het volgende deel onderzoeken we de waarheid van formules.