Nieuwe pagina 1

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

De taal der logica.

Wat in de normale wereld een spreker of schrijver een "zin" noemt, noemen we vanaf nu een propositie.
Nou kun je door bepaalde koppelwoorden proposities omzetten of samenstellen tot nieuwe proposities.
Bijvoorbeeld de zin "er bestaat een grootste geheel getal" is door het woord "niet" eenvoudig om te zetten naar "er bestaat niet een grootste geheel getal".
In de logica doen we dat trouwens liever zó: "Niet (er bestaat een grootste geheel getal)"
Ook met de veelgebruikte koppelwoorden OF, ALS, EN zijn zinnen samen te stellen.
We zullen gaan bekijken hoe zulke koppelwoorden gebruikt mogen worden zodat uit geldige beweringen weer nieuwe geldige beweringen volgen.

Notatie.

Het alfabet van de propositielogica heeft maar 9 symbolen!

Dat tweede symbool: het accent, wordt gebruikt om proposities te nummeren, zodat je het kunt hebben over p' , p'' , p''' enz., maar het mag ook wel gewoon met een index: p₁, p₂, p₃,...
(Een echte logicus vindt accenten mooier omdat zij dan inderdaad maar 9 symbolen nodig heeft. Ikzelf heb die afwijking niet en werk rustig met een index).

Na het alfabet gaan we naar de grammatica.
Met deze negen symbolen worden nu formules gemaakt. Om een geldige formule te maken mag je zo vaak als je wilt drie dingen doen (ik geef formules aan met Griekse letters), en dat zijn de volgende constructiestappen:

symbool	betekenis
p	propositie
'	nummering
¬	niet
∧	en
∨	of
⇒	als... dan...
⇔	dan en slechts dan als
(
)

elke p_i is een formule.

als α een formule is, dan is ook ¬ α een formule.

als α en β formules zijn, dan zijn ook.
(α ∧ β), (α ∨ β), (α ⇒ β),(α ⇔ β) formules.

Bij een langere rij symbolen kun je met behulp van een zogenaamde constructieboom handig testen of het een geldige formule is.
Hiernaast zie je er eentje voor de formule: (p₁ ⇒ (¬ p₂ ⇒ p₁)).
Elke stap erin is van boven naar beneden toegepast door één van de drie constructiestappen hierboven te gebruiken.

Bedenk goed dat zit nog helemaal niets zegt over het WAAR of NIET WAAR zijn van een formule. Het zegt ons alleen of een formule een geldige formule is.

Examenopgave VWO, wiskunde C, 2019-I

Een kunstenaar gaat een schilderij met 17 vlakken, zoals weergegeven in de figuur, inkleuren.

De kunstenaar wil het schilderij van de figuur inkleuren met de drie kleuren: rood, blauw en wit.

Daarnaast besluit hij, dat twee aan elkaar grenzende vlakken niet dezelfde kleur mogen hebben.

We kunnen de kleuring van de verschillende vlakken weergeven met de volgende notatie: W₅ betekent “vlak nummer 5 is wit gekleurd” en B₁₂ betekent “vlak nummer 12 is blauw gekleurd”.

De kunstenaar begint met vlak nummer 1 rood te kleuren. Tegen zijn vriend zegt hij “Vlak nummer 1 is rood, dus vlak nummer 4 is blauw of wit”.

Vertaal de uitspraak van de kunstenaar in logische symbolen, gebruik makend van bovenstaande notatie.

De kunstenaar kiest ervoor om vlak nummer 4 wit te kleuren. Het gevolg daarvan voor een deel van de rest van het schilderij kan worden weergegeven met de volgende logische redenering, bestaande uit vier redeneerstappen:

•   (R₁ ∧ W₄) ⇒ B₃
•   B₃ ⇒ (¬ B₅ ∧ ¬ B₂)
•   (R₁ ∧ ¬ B₂) ⇒ W₂
• (W₂ ∧ B₃) ⇒ R₆

Geef de vier stappen van deze redenering in gewone zinnen.

Geef een redenering, weergegeven met de hierboven beschreven notatie en logische symbolen, bestaande uit een aantal redeneerstappen, voor vlak nummer 5 en leg daarmee uit waarom de kunstenaar er niet in zal slagen vlak nummer 5 een kleur te geven.

Laat door het maken van een constructieboom zien dat de volgende rijtjes symbolen geldige formules zijn.

((¬ p₁ ⇒ ¬ p₂) ⇒ (p₁⇒ p₁))

((p₁ ⇒ (p₂ ⇒ p₃)) ⇒ ((p₁ ⇒ p₂) ⇒ (p₁ ⇒ p₃)))

Welke van de volgende rijtjes symbolen zijn geldige formules?

(¬ p₁ ⇒ (p₁ ⇒ p₂))

((p₁ ∧ p₃) ⇒ (p₃ ∨ p₁))

p₁ ⇒ p₁

(p₂ ⇔ p₁)₃

(p₁ ⇒ p₂ ∨p₁)

((p₁ ⇒ p₂) ⇒ p₂) ⇒ (p₂ ∨ p₁)

Een paar beweringen over formules.

Bewering 1: Elke geldige formule bevat evenveel linker- als rechterhaakjes.

Bewijs:
Elke beginconstante p_iheeft nul haakjes.
Als een formule α evenveel linker- als rechterhaakjes heeft, dan heeft ¬ α dat ook (namelijk evenveel).
Als formules α en β beiden evenveel haakjes hebben dan hebben (α Ù β), (α Ú β), (α ⇒ β),(α ⇔ β) dat ook.
Ofwel: tijdens alle constructiestappen blijft het aantal linker- en rechterhaakjes gelijk.

(het valt je misschien op dat dit een soort van inductie-bewijs is?)

Bewering 2: Een willekeurig beginstuk van een geldige formule met haakjes, heeft meer linker- dan rechterhaakjes.

Bewijs: (op dezelfde manier als hierboven)
Voor een beginconstante p_i is de bewering niet van toepassing want die heeft geen haakjes.
Als een beginstuk van formule α meer linkerhaakjes heeft, dan heeft een beginstuk van Øα dat ook.
Als de beginstukken van formules α en β beiden meer linkerhaakjes bevatten, dan zijn er voor het beginstuk van
(α Ù β) verschillende mogelijkheden voor dit beginstuk:
- het is (
- het is (x met als x een beginstuk van α
- het is (α
- het is (α Ù
- het is (α Ù x met als x een beginstuk van β
- het is (α Ù β
Ga zelf maar na dat in al deze gevallen dat hele beginstuk weer meer linkerhaakjes heeft.
En wat voor (α Ù β) geldt, geldt op precies dezelfde manier ook voor (α Ú β) en (α ⇒ β) en (α ⇔ β).

Bewering 3: Een beginstuk van een geldige formule waar haakjes in voorkomen is nooit zelf een geldige formule.

Bewijs:
Volgt direct uit de beweringen 1 en 2 hierboven !!

Bewering 4. Elke geldige formule heeft precies één constructieboom.

Wacht even.... deze bewering is eigenlijk de belangrijkste van allemaal en volgt ook uit alle vorigen. Laten we het daarom maar een stelling noemen.

Stelling: Elke geldige formule heeft precies één constructieboom.

Bewijs:
Een beginconstante p_i heeft uiteraard maar één constructieboom.
Als formule α maar één constructieboom heeft, dan heeft ⌐α dat ook
Hoe zit het met (α Ù β)?
Daarvoor zijn er drie verschillende mogelijkheden voor hoe die Ù in de boom tevoorschijn is gekomen:
- het was ontstaan door (α₁ Ù α₂ Ù β) met α₁ een beginstuk van α (α bestaat nu uit α₁Ùα₂).
- het was inderdaad (α Ù β).
- het was ontstaan door (α Ù β₁ Ù β₂) met β₁ een beginstuk van β (β bestaat uit β₁ Ù β₂).
De eerste mogelijkheid kan niet, want dat zou α₁ een geldige formule zijn geweest, en bewering 3 hierboven zegt dat een beginstuk niet zelf een geldige formule kan zijn.
De derde mogelijkheid kan ook niet, want dan zou α een beginstuk van α Ù β₁) zijn, en weer zegt bewering 3 hierboven dat dat niet kan.
Kortom, er is maar één mogelijkheid: de constructiestap was inderdaad (α Ù β).

En wat voor (α Ù β) geldt, geldt op precies dezelfde manier ook voor (α Ú β) en (α ⇒ β) en (α ⇔ β).

Dit heet ook wel de stelling van de "Unieke leesbaarheid". In de gewone taalkunde heeft men lang gezocht naar een methode om grammaticaal correcte zinnen te midden van alle zinnen op te sporen. Zo'n methode bestaat hoogstwaarschijnlijk niet voor de gewone natuurlijke taal. Maar voor onze formele taal gelukkig dus wel.
Zet een willekeurig aantal tekens achter, dan is het is het éénduidig te bepalen of dat een correcte formule is. Een machine zou het kunnen bepalen (door bijvoorbeeld gewoon alle mogelijke bomen langs te lopen; dat is een eindig aantal).

Voor ons stervelingen met beperkte tijd is het meestal makkelijk bij de binnenste haakjes te beginnen (er moeten ergens twee haakjes zijn waartussen geen andere haakjes meer staan). Kijk dan eerst of tussen die haakjes een geldige formule staat, en vervang dan dat hele deel (inclusief die twee haakjes) door p_i, en ga dan opnieuw op zoek naar de volgende binnenste haakjes.....

Het kan ook door alle haakjes te gaan nummeren (of ze mooi te kleuren als je dat leuk vindt):

Voor de echte minimalisten: De Poolse logicus J. Łukasiewikz verzon een notatie waarin ook haakjes niet meer nodig zijn, en die ook voor elke geldige formule een unieke constructieboom oplevert! Nieuwsgierig? Dan met je hier maar verder lezen, wij gaan intussen verder naar de semantiek.