Methode 'Praktische Logica':
Bewijsmethode I voor Propositielogica:
de Waarheidswaarden-tabelmethode.
(de 'tabelmethode')
1. Inleiding
Het nut van logica ligt vooral in het toetsen en bewijzen van beweringen of betogen,
onafhankelijk van het onderwerp of het domein waar ze op betrekking hebben. Logische toetsing en bewijsvoering
zijn voor dat doel gebaseerd op formalisering. Een echt formeel bewijs is volledig navolgbaar en controleerbaar.
Dat wil zeggen volkomen expliciet (het vereist geen 'raden' of 'gedachten-lezen') en eenduidig
(elke uitdrukking heeft precies één mogelijke betekenis).
De eerste en fundamentele bewijsmethode in de formele logica maak gebruik van waarheidswaardetabellen die bekend zijn in
de propositielogica (PPL).
2. Aanpak.
De tabel kun je het beste opbouwen als volgt opbouwen:
Bekijk de bewering (formule) die je wilt bewijzen.
De elementaire proposities, of atomen {A,B,..} vormen de variabelen in de formule. Tel het aantal verschillende
variabelen in de formule, dit aantal is n.
Dit aantal bepaalt allereerst het aantal 'startkolommen': per variabele krijg je 1 startkolom.
Deze startkolommen lopen sequentieel, dus met (j:=1,n). Maak eerst kolommen voor
dan voor de binnenste/ diepste nestings, en van daaruit steeds de één trap hogere niveau's.
Het hoogste niveau is dat van de totale formule, die het 'hoofdconnectief' bevat.
Een kolom in een waarheidswaardentabel staat onder een bepaalde logische formule,
en is het interpretatiebereik van die logische formule.
Deze bestaat uit een geordende reeks waarheidswaarden, of waarheidswaardenpatroon.
Bij elke logische formule hoort dus, uitgaande van de principes van de waarheidswaardetabellen, een specifiek
interpretatiebereik.
We vullen de kolommen met waarheidswaarden als volgt. In een binair stelsel hebben we 2 waarheidswaarden: m=2.
De waarden lopen dus met (w:=1,m). We noteren meestal 'waar' als w[1] = '1', en 'onwaar' als w[2] = '2'.
Over de startkolommen laat je de waarheidswaarden systematisch variëren. Dus precies zoals je n loops genest laat lopen
met w[n] :='1', '0'.
Elke complete waarheidswaardentoekenning V!(j) : belichaamt één horizontale lijn in de waarheidswaardentabel.
Een horizontale lijn in een waarheidswaardentabel is een interpretatie, of één 'mogelijke wereld'
(dat wil zeggen mogelijke toestand of stand van zaken).
Deze bestaat uit een geordende reeks waarheidswaarden, of waarheidswaardenpatroon.
De omvang van deze reeks is afhankelijk van het aantal unieke atomaire formules binnen die formule.
Als we dit aantal 'n' noemen, dan is de omvang van de reeks in een tweewaardige logica gelijk aan
het aantal waarheidwaarden de n-de macht van 2; dus 2**n.
De volgorde van de elementen in het interpretatiebereik ligt, uiteraard, vast.
3. Waarheidswaardentoekenning aan proposities.
Interpretatiebereik.
'(..)': betekent in voorkomend geval "geordende reeks".
Bijvoorbeeld: "interpretatie", "interpretatiebereik", of "waarheidswaardepatroon".
Voorbeelden:
'A' heeft als interpretatiebereik: $(1,0).
'A  B' heeft als interpretatiebereik: $(1,0,1,1).
'A B C'
heeft als interpretatiebereik: $(1,0,1,1,1,0,1,0).
Voorbeelden.
(1) De startkolommen voor n=1 atomen: {A} lopen als volgt, met (j:=1,n):
j=1: A = (10).
(2) De startkolommen voor n=2 atomen: {A,B} lopen als volgt, met (j:=1,n);
zoals je n=2 loops genest laat lopen met (j :=1,2) en met (i [j] :=1,0):
j=1: A = $(1100).
j=2: B = $(1010).
Veel gebruikte waarheidswaardepatronen van twee-plaatsige proposities
in twee-plaatsige waarheidswaardetabellen.
(A  B) = $(1000).
(A  B) = $(1110).
(A B) = $(1011).
(3) De startkolommen voor n=3 atomen: {A,B,C} lopen als volgt, met (j:=1,n);
zoals je n=3 loops genest laat lopen met (j :=1,3) en met (i [j] :=1,0):
j=1: A = $(11110000).
j=2: B = $(11001100).
j=3: C = $(10101010).
Veel gebruikte waarheidswaardepatronen van twee-plaatsige proposities
in drie-plaatsige waarheidswaardetabellen.
(A B) = $(11000000).
(A C) = $(10100000).
(B C) = $(10001000).
(A B) = $(11111100).
(A C) = $(11111010).
(B C) = $(11101110).
(A B) = $(11001111).
(A C) = $(10101111).
(B C) = $(10111011).
(4) De startkolommen voor n=4 atomen: {A,B,C,D} lopen als volgt, met (j:=1,n);
zoals je n=4 loops genest laat lopen met (j :=1,4) en met (i [j] :=1,0):
j=1: A = $(1111111100000000).
j=2: B = $(1111000011110000).
j=3: C = $(1100110011001100).
j=4: D = $(1010101010101010).
Het kan handig zijn om èlke zogeheten atoom in de formule, dus behalve variabelen, zoals 'A', 'B', enz.., ook
constanten, zoals '0' en/of '1', een aparte kolom te geven.
Als volgt in een formule met 1 variabele:
1 = $(11).
0 = $(00).
Je hebt dan veel meer controle je hebt over wat precies binnen de formule in de logische relaties gebeurt
en welke waarden 'overerven' helemaal tot aan de laatste kolom (de meest rechtse kolom bevat de einduitkomst van het
bewijs).
4. Beoogde uitkomst van het bewijs
We hebben het hier over stellingen bewijzen. Wat maakt een waarheidswaardentabel tot bewijs?
Als hij logisch en compleet is opgebouwd, van de eerste tot de laatste kolom, en in de laatste kolom enkel '1'-en staan.
Dit laatste betekent: de te bewijzen formule blijkt onder alle mogelijke 'situaties' waar,
dus een logische wet (tautologie).
Voorbeeld van een zeer simpel tabelbewijs in PPL:
(4.1) Negatief-normaal conversie.
{¬¬A} ≡ A.
| (1) |
(2) |
(3) |
(4) |
| A |
¬(1) |
¬(2) |
(1 ≡ 3) |
| 1 |
0 |
1 |
1 |
| 0 |
1 |
0 |
1 |
5. Tabelbewijzen weergeven in gewone tekst
Je kunt de 'tabelbewijzen' in mooie spreadsheet tabellen maken, maar ook gewoon in tekst.
De tabel kun je als volgt in tekst opzetten.
In tekst-weergave wordt elke kolom horizontaal geschreven, dus als rij in een lijst.
Hierdoor kun je gemakkelijk nieuwe logische combinaties toevoegen onderaan de lijst.
Bijv.:
Bewijs 'A 1'.
j=1: A = $(10).
j=2: $1 = $(11).
j=3: $(11) : 'A $1'.
Altijd waar, dus een geldige logische wet.
Nu met bijv.:
'A 𠪪A'.
j=1: A = $(10).
j=2: $(01) : '¬A'.
j=3: $(10) : '¬{2}'.
j=4: $(11) : '{$1} ≡ {3}'; = 'A ≡ ¬¬A'.
Altijd waar, dus een geldige logische wet.
6. Beslisbaarheid van PPL.
Voor alle stellingen in PPL is het validiteitsprobleem beslisbaar. In principe zal de tabelmethode
voor de vraag de geldigheid van formules in de PPL altijd een definiet antwoord opleveren.
Wel wordt de tabelmethode bij formules met veel variabelen steeds lastiger: bij n variabelen is de omvang van het bewijs
meer dan exponentieel, nl. een meervoud van 2**n.
Handmatig gedaan levert dat bovendien meer foutkansen. En anders heb je daar flinke computerkracht voor nodig.
7. Bewijzen van elementaire wetten - via Waarheidswaardetabellen
Voorbeelden.
Conjunctief normaal vorm van Implicatie.
{(A B)} ≡ (¬A B).
| (1) |
(2) |
(3) |
(4) |
(5) |
(6) |
| A |
B |
¬(1) |
(3 2) |
(1 2) |
(4  5) |
| 1 |
1 |
0 |
1 |
1 |
1 |
| 1 |
0 |
0 |
0 |
0 |
1 |
| 0 |
1 |
1 |
1 |
1 |
1 |
| 0 |
0 |
1 |
1 |
1 |
1 |
(9.4c) Regel van Algemeen modus ponens.
Substitutie via Implicatie.
(9.4c.1) Bewijs via 'bevestigende wijs'.
Sluitrede, Modus ponens (MP), ' Material detachment'.
{(A B), A} B.
| (1) |
(2) |
(3) |
(4) |
(5) |
(6) |
(7) |
| A |
B |
(1 2) |
(1 3) |
(1 2) |
(4 5) |
(6 2) |
| 1 |
1 |
1 |
1 |
1 |
1 |
1 |
| 1 |
0 |
0 |
0 |
0 |
0 |
1 |
| 0 |
1 |
1 |
0 |
0 |
0 |
1 |
| 0 |
0 |
1 |
0 |
0 |
0 |
1 |
(4.2) Negatief-implicatie-normaal conversie.
{¬(A B)} ≡ (A ¬B).
| (1) |
(2) |
(3) |
(4) |
(5) |
(6) |
(7) |
| A |
B |
¬(2) |
(1 2) |
¬(4) |
(1 3) |
(5 ≡ 6) |
| 1 |
1 |
0 |
1 |
0 |
0 |
1 |
| 1 |
0 |
1 |
0 |
1 |
1 |
1 |
| 0 |
1 |
0 |
1 |
0 |
0 |
1 |
| 0 |
0 |
1 |
1 |
0 |
0 |
1 |
(4.3) Negatieve conjunctie normaal conversie.
{¬(A B)} ≡ (¬A ¬B).
| (1) |
(2) |
(3) |
(4) |
(5) |
(6) |
(7) |
(8) |
| A |
B |
¬(1) |
¬(2) |
(1 2) |
¬(5) |
(3 4) |
(6 ≡ 7) |
| 1 |
1 |
0 |
0 |
1 |
0 |
0 |
1 |
| 1 |
0 |
0 |
1 |
0 |
1 |
1 |
1 |
| 0 |
1 |
1 |
0 |
0 |
1 |
1 |
1 |
| 0 |
0 |
1 |
1 |
0 |
1 |
1 |
1 |
(4.4) Negatieve disjunctie normaal conversie.
{¬(A B)} ≡ (¬A ¬B).
| (1) |
(2) |
(3) |
(4) |
(5) |
(6) |
(7) |
(8) |
|
A |
B |
¬(1) |
¬(2) |
(1 2) |
¬(5) |
(3 4) |
(6 ≡ 7) |
| 1 |
1 |
0 |
0 |
1 |
0 |
0 |
1 |
| 1 |
0 |
0 |
1 |
1 |
0 |
0 |
1 |
| 0 |
1 |
1 |
0 |
1 |
0 |
0 |
1 |
| 0 |
0 |
1 |
1 |
0 |
1 |
1 |
1 |
(5.3) Implicatie-normaal conversie.
{A B} ≡ (¬A B).
| (1) |
(2) |
(3) |
(4) |
(5) |
(6) |
| A |
B |
(1 2) |
¬(1) |
(4 2) |
(3 ≡ 5) |
| 1 |
1 |
1 |
0 |
1 |
1 |
| 1 |
0 |
0 |
0 |
0 |
1 |
| 0 |
1 |
1 |
1 |
1 |
1 |
| 0 |
0 |
1 |
1 |
1 |
1 |
(5.6) Conjunct-normaal Distributie.
(7.1) Reductie wegens redundantie van literalen.
(7.1a) Reductie van (complexe) conjuncties.
(7.1a1) Wegwerken / elimineren van redundanties wegens equivalentie.
{A A} ≡ A.
| (1) |
(2) |
(3) |
| A |
(1 1) |
(2 ≡ 1) |
| 1 |
1 |
1 |
| 0 |
0 |
1 |
(7.1a2) Wegwerken / elimineren van redundaties wegens implicatie (subsumptie).
{A $1} ≡ A.
| (1) |
(2) |
(3) |
(4) |
| A |
$1 |
(1 2) |
(3 ≡ 1) |
| 1 |
1 |
1 |
1 |
| 0 |
1 |
0 |
1 |
(7.1b) Reductie van (complexe) disjuncties.
(7.1b1)
{A A} ≡ A.
| (1) |
(2) |
(3) |
| A |
(1 1) |
(2 ≡ 1) |
| 1 |
1 |
1 |
| 0 |
0 |
1 |
(7.1b2) Elimineren van 'zwakkere' elementen.
{A $0} ≡ A.
| (1) |
(2) |
(3) |
(4) |
| A |
$0 |
(1 2) |
(3 ≡ 1) |
| 1 |
0 |
1 |
1 |
| 0 |
0 |
0 |
1 |
(7.1b2) .
Zie ook (8.1).
| (1) |
(2) |
(3) |
(4) |
(5) |
(6) |
(7) |
(8) |
| A |
B |
¬(2) |
(2 3) |
(1 4) |
$0 |
(1 6) |
(6 ≡ 7) |
| 1 |
1 |
0 |
0 |
0 |
0 |
0 |
1 |
| 1 |
0 |
1 |
0 |
0 |
0 |
0 |
1 |
| 0 |
1 |
0 |
0 |
1 |
0 |
1 |
1 |
| 0 |
0 |
1 |
0 |
1 |
0 |
1 |
1 |
(7.2)
(7.2a) .
{A $1} ≡ $1.
| (1) |
(2) |
(3) |
(4) |
| A |
$1 |
(1 2) |
(3 ≡ 2) |
| 1 |
1 |
1 |
1 |
| 0 |
1 |
1 |
1 |
(7.2c) .
{(A B) B} ≡ B.
| (1) |
(2) |
(3) |
(4) |
(5) |
| A |
B |
(1 2) |
(3 2) |
(4 ≡ 2) |
| 1 |
1 |
1 |
1 |
1 |
| 1 |
0 |
1 |
0 |
1 |
| 0 |
1 |
1 |
1 |
1 |
| 0 |
0 |
0 |
0 |
1 |
(7.2d) .
| (1) |
(2) |
(3) |
(4) |
(5) |
(6) |
(7) |
| A |
B |
C |
(1 2) |
(1 2 3)
|
(4 5) |
(6 ≡ 4) |
| 1 |
1 |
1 |
1 |
1 |
1 |
1 |
| 1 |
1 |
0 |
1 |
1 |
1 |
1 |
| 1 |
0 |
1 |
1 |
1 |
1 |
1 |
| 1 |
0 |
0 |
1 |
1 |
1 |
1 |
| 0 |
1 |
1 |
1 |
1 |
1 |
1 |
| 0 |
1 |
0 |
1 |
1 |
1 |
1 |
| 0 |
0 |
1 |
0 |
1 |
0 |
1 |
| 0 |
0 |
0 |
0 |
0 |
0 |
1 |
(7.3)
(7.3a)
(7.3a1) Basale Contradictie.
{A ¬A} ≡ $0.
| (1) |
(2) |
(3) |
(4) |
(5) |
| A |
¬(1) |
$0 |
(1 2) |
(4 ≡ 3) |
| 1 |
0 |
0 |
0 |
1 |
| 0 |
1 |
0 |
0 |
1 |
(7.3a2) Basale contradictie. (wegens implicatie).
{A $0} ≡ $0.
| (1) |
(2) |
(3) |
(4) |
| A |
$0 |
(1 2) |
(3 ≡ 2) |
| 1 |
0 |
0 |
1 |
| 0 |
0 |
0 |
1 |
(7.3c)
(7.4) Samentrekken van disjuncties (contractie).
(7.5) Reductie via Absorptie.
(8.1) Fatale reductie.
{A $0} ≡ ¬A.
| (1) |
(2) |
(3) |
(4) |
(5) |
| A |
¬(1) |
$0 |
(1 3) |
(4 ≡ 2) |
| 1 |
0 |
0 |
0 |
1 |
| 0 |
1 |
0 |
1 |
1 |
(9.5) Weerlegging via Contrapositie.
| (1) |
(2) |
(3) |
(4) |
(5) |
(6) |
(7) |
| A |
B |
¬(1) |
¬(2) |
(1 2) |
(5 4) |
(6 3) |
| 1 |
1 |
0 |
0 |
1 |
0 |
1 |
| 1 |
0 |
0 |
1 |
0 |
0 |
1 |
| 0 |
1 |
1 |
0 |
1 |
0 |
1 |
| 0 |
0 |
1 |
1 |
1 |
1 |
1 |
(9.5-sub) Weerlegging via Evidente negatie.
{(A B) ¬A} ≡ ¬A.
| (1) |
(2) |
(3) |
(4) |
(5) |
(6) |
| A |
B |
¬(1) |
(1 2) |
(4 3) |
(5 ≡ 3) |
| 1 |
1 |
0 |
1 |
0 |
1 |
| 1 |
0 |
0 |
0 |
0 |
1 |
| 0 |
1 |
1 |
1 |
1 |
1 |
| 0 |
0 |
1 |
1 |
1 |
1 |
|