Propositielogica

De propositielogica is een tak van logica die zich bezighoudt met geldige redeneringen in de vorm van proposities. Proposities zijn uitspraken of beweringen die ofwel waar, ofwel onwaar zijn. Voorbeelden hiervan zijn

De Winkler Prins is een encyclopedie

en

Wicky heeft een noormannenhelm op.

In de propositielogica kunnen uitspraken alleen waar of onwaar zijn, dit in tegenstelling tot meerwaardige logica's waarbij uitspraken ook andere waarden kunnen hebben, zoals bij de uitspraak

Wicky vindt De Winkler Prins een interessante encyclopedie.

In vergelijking met andere types van logica is de propositielogica eenvoudig van opbouw (structuur, grammatica) maar beperkt in uitdrukkingsmogelijkheid.

Proposities

Een propositie (betekenisvolle uitspraak of bewering) kan enkelvoudig zijn, maar ook samengesteld zijn uit twee of meer andere proposities. Proposities worden samengesteld met behulp van booleaanse operatoren, ook wel connectieven of junctoren genoemd. Een propositie zonder connectieven wordt een atoom genoemd.

Men kan proposities aanduiden met een letter, zoals:

A: Morgen schijnt de zon

B: We gaan morgen picknicken

In de samengestelde propositie

Als A, dan B

wordt de eerste propositie (A) de hypothese of antecedent genoemd en de tweede (daaropvolgende) propositie (B) de conclusie of consequent.

Connectieven

De propositielogica kent de volgende connectieven om proposities samen te stellen:

• negatie (ontkenning): ~A of ¬A (nietA)
• conjunctie: A <math>\land</math> B (A en B)
• disjunctie: A <math>\lor</math> B (A of B)
• implicatie (gevolgtrekking): A→B (als A, dan B)
• equivalentie (gelijkwaardigheid): A↔B (A dan en slechts dan als B)

Voorbeelden

A <math>\lor</math> B is de uitspraak: Morgen schijnt de zon of we gaan morgen picknicken

A <math>\land</math> B is de uitspraak: Morgen schijnt de zon en we gaan morgen picknicken

A → B is de uitspraak: Als morgen de zon schijnt, gaan we morgen picknicken

¬A is de uitspraak: Morgen schijnt de zon niet

De bewering A <math>\lor</math> B is waar als tenminste een van de twee beweringen waar is. De bewering is dus ook waar als beide beweringen waar zijn, iets wat in natuurlijke taal vaak niet zo bedoeld wordt. Dus er geldt:

"1=1" <math>\lor</math> "2=2" is waar,

"1=1" <math>\lor</math> "1=2" is waar, maar

"1=2" <math>\lor</math> "2=1" is niet waar.

De implicatie → heeft niets te maken met causaliteit. De formule A → B betekent niet dat we morgen gaan picknicken omdat de zon schijnt. Het beschrijft eerder een soort toevallige samenloop van omstandigheden. De formule hoeft niet eens waar te zijn. Het is niet meer dan een formule.

Logische wetten

Logische wetten zijn uitspraken die altijd waar zijn, onafhankelijk van of de atomaire proposities die erin voorkomen waar zijn. Bijvoorbeeld:

A → A (als morgen de zon schijnt, schijnt morgen de zon)

(A <math>\land</math> B)→(A <math>\lor</math> B) (als morgen de zon schijnt en we gaan morgen picknicken, dan gaan we morgen picknicken of schijnt morgen de zon).

Dit geldt natuurlijk niet alleen voor de bovengedefinieerde uitspraken A en B, maar voor elk tweetal uitspraken A en B. We noemen een dergelijke uitspraak bewijsbaar (of afleidbaar) en dit wordt symbolisch weergegeven door ├.

├ A→A

├ (A <math>\land</math> B)→(A <math>\lor</math> B)

├ A <math>\lor</math> ¬A (Wet van de uitgesloten derde, deze geldt bij de klassieke propositielogica, maar niet bij de intuitionistische propositielogica)

We kunnen voor de ├ ook een of meer proposities plaatsen; die gelden dan als hypothese, en {A,B,C}├ D betekent: uit de hypothesen A, B en C is D afleidbaar.

Enkele belangrijke logische wetten zijn de wetten van De Morgan:

¬(A <math>\land</math> B) ↔ (¬A <math>\lor</math> ¬B)

¬(A <math>\lor</math> B) ↔ (¬A <math>\land</math> ¬B)

Wet van de contrapositie:

(A → B) ↔ (¬B → ¬A)

Jan Łukasiewicz bewees in 1930 dat het mogelijk is om de bovenstaande wetten af te leiden op basis van slechts drie axioma's

A → (B → A)

(A → (B → C)) → ((A → B) → (A → C))

(¬A → ¬B) → (B → A)

in combinatie met de modus ponens-regel:

A, A → B ├ B

Bovendien geldt ook:

(A→B) ↔ (¬A <math>\lor</math> B)

Dit is gemakkelijk af te leiden uit de waarheidstabellen die hieronder staan beschreven. Wanneer we hier de eerste wet van De Morgan op toepassen, komen we op het bewijs uit het ongerijmde:

(A→B) ↔ ¬(A <math>\land</math> ¬B)

Onderzoeken en bewijzen van formules

Waarheidstabel

Een handige manier om een logische formule te bewijzen, is het opstellen van een waarheidstabel waarbij we iedere combinatie van waarheidswaarden van de variabelen afzonderlijk bekijken. Een logische wet is er een formule die bij elke combinatie de waarheidswaarde waar heeft. De variabelen voor formules geven we hier aan met de hoofdletters A, B, C, ... en de mogelijke waarheidswaarden van deze variabelen zijn waar (T voor true) en onwaar (F voor false). De waarheidswaarden 0 (de propositie is onwaar) en 1 (de propositie is waar) kunnen ook gehanteerd worden. Vandaar dat men spreekt van de binaire logica. Meerdere proposities kunnen dezelfde waarheidstabel opleveren. In dat geval spreekt men van logisch equivalentie (naar analogie met gelijkheid in de verzamelingenleer).

A	¬ A
T	F
F	T

A	B	A <math>\land</math> B	A <math>\lor</math> B	A <math>\rightarrow</math> B	A <math>\leftrightarrow</math> B
F	F	F	F	T	T
F	T	F	T	T	F
T	F	F	T	F	F
T	T	T	T	T	T

Een nadeel van een waarheidstabel bij het onderzoeken van een complexe logische stelling zoals A → (B ∧ ¬C) is dat het aantal mogelijke combinaties van de verschillende variabelen (hier A, B en C) exponentieel toeneemt met het aantal variabelen in de stelling. De waarheidstabel van een stelling met 8 variabelen zou 2⁸=256 rijen tellen.

Hieronder volgt een uitgewerkt voorbeeld waarbij we de proposities A (Morgen schijnt de zon) en B (We gaan morgen picknicken) gebruiken:

Omstandigheden met invloed op bewering	Bewering	Negatie
	A	niet A ¬A
	Morgen schijnt de zon	Morgen schijnt de zon niet
	Onwaar. De bewering "morgen schijnt de zon" is niet waar. De zon schijnt immers niet.	Waar. De bewering "morgen schijnt de zon niet" is waar. De zon schijnt inderdaad niet.
zon	Waar. De bewering "morgen schijnt de zon" is waar. De zon schijnt.	Onwaar. De bewering "morgen schijnt de zon niet" is niet waar. De zon schijnt

Omstandigheden met invloed op bewering	Bewering	Bewering	Conjunctie	Disjunctie	Implicatie	Equivalentie
	A	B	A en B A <math>\land</math>B	A of/en B A <math>\lor</math> B	Als A dan B A <math>\rightarrow</math> B	A dan en slechts dan als B A <math>\leftrightarrow</math> B
	Morgen schijnt de zon	We gaan morgen picknicken	Morgen schijnt de zon en gaan we picknicken	Morgen schijnt de zon of gaan we picknicken	Als morgen de zon schijnt gaan we picknicken	We picknicken morgen uitsluitend als de zon schijnt
	onwaar	onwaar	onwaar	onwaar	waar	waar
picknick	onwaar	waar	onwaar	waar	waar	onwaar
zon	waar	onwaar	onwaar	waar	onwaar	onwaar
zonpicknick	waar	waar	waar	waar	waar	waar

Semantisch Tableau

Een semantisch tableau onderzoekt een stelling door de implicaties van een stelling te ontleden. Als een stelling waar is, wat betekent dat voor de waarheidswaarde van de variabelen in de stelling? Als A∧B waar is, dan moeten zowel A als B waar zijn. Als A→B waar is, dan moeten A en B allebei waar zijn, of A is niet waar en de waarde van B maakt niet uit. Op deze manier kan een boom getekend worden die een complexe formule opsplitst in steeds kleinere delen, totdat duidelijk is welke waarden de variabelen aan moeten nemen om de stelling waar te maken. Semantische tableaus worden vaak gebruikt in combinatie met het bewijs uit het ongerijmde om te bewijzen dat een stelling volgt uit een aantal hypothesen.

Valkuilen van de implicatie

Stel dat gegeven zijn de uitspraken A→B en A. Hieruit valt B te concluderen. Immers, als gegeven is dat we morgen gaan picknicken, in het geval dat morgen de zon schijnt (A→B) en bovendien dat morgen de zon schijnt, is de conclusie dat we morgen gaan picknicken.

Stel nu dat gegeven zijn de uitspraken A→B en ¬B. Hieruit valt ¬A te concluderen. Immers, stel dat morgen de zon schijnt. Gegeven is dat áls morgen de zon schijnt, dat we dan gaan picknicken morgen. Dus we gaan morgen picknicken. Het was echter ook gegeven dat we morgen niet gaan picknicken (¬B). Hier hebben we blijkbaar te maken met een tegenspraak. De aanname dat morgen de zon schijnt is hier foutief. De geldige conclusie is dus ¬A. Deze manier van bewijzen wordt overigens een 'bewijs uit het ongerijmde' genoemd.

Conversationele implicatuur

Stel dat gegeven zijn de uitspraken A→B en ¬A. Hieruit valt logisch gezien niets te concluderen. Het is een misverstand te denken dat A→B impliceert dat ¬A → ¬B. In het dagelijkse taalgebruik echter, is dat vaak wel zo. Bijvoorbeeld als een vader tegen zijn kind zegt: "Als je je gedraagt, krijg je een snoepje". Hiermee bedoelt de vader doorgaans ook: "Als je je niet gedraagt, krijg je geen snoepje". In de formele logica is dat echter niet zo. A→B zegt niet meer dan dat A B impliceert.

Een dergelijke gevolgtrekking die niet geldig is in de propositielogica, maar in het alledaagse taalgebruik wel gangbaar is, wordt een conversationale implicatuur genoemd.