Beweren en bewijzen/de zuilen/Zekerheid/2. Stelling en bewijs
literatuur
*)I.p.v. het boek van Van Benthem kun je ook elk ander logicaboek bijv. Logica voor alfa's en informatici of het dictaat van Formeel Denken raadplegen. |
Stellingen
De eenvoudigste vorm van een stelling is één ware bewering B, bijv. 0=0.
In het algemeen is een stelling gebaseerd op een aantal aannames b1, b2, ..., bn. De conclusie B hoeft dan alleen waar te zijn indien b1, b2, ..., bn allemaal waar zijn. "Onder de aannames x>0 en y>0 geldt: x*y>0."
(Bij de stelling 0=0 is n=0: de stelling kent geen aannames.)
In de logica schrijven we stellingen op in de vorm b1, b2, ..., bn ⊨ B, bijv. x>0, y>0 ⊨ x*y>0. Streng genomen hadden we ons eerste voorbeeld voor een stelling zo moeten opschrijven: ⊨ 0=0.
In deze cursus interesseren ons vooral stellingen over de fysieke realiteit (Beweren en bewijzen/de zuilen/Formalisering). De correctheidsstelling voor systemen (Beweren en bewijzen/de zuilen/Formalisering/4. Correctheidsstelling) is een speciaal geval.
Wie stellig iets stelt geeft niet altijd zijn uitgangspunten even duidelijk aan. Uitdaging: de impliciete aannames (onuitgesproken veronderstellingen) van een stelling achterhalen.
Waarheid en geldig gevolg
Een bewering die zonder aannames altijd waar is, noemen we tautologie.
Een stelling b1, b2, ..., bn ⊨ B klopt als de B een geldig gevolg van de b1, b2, ..., bn is (Van Benthem, 3.1 en 7.4).
De logische implicatie (→) zit zo in elkaar dat een stelling
b1, b2, ..., bn ⊨ B
dan en alleen dan klopt als de aannameloze stelling
⊨ (b1 ∧ b2 ∧ ... ∧ bn) → B
klopt, m.a.w. als (b1 ∧ b2 ∧ ... ∧ bn) → B een tautologie is. Je kunt dus een stelling op twee manieren opschrijven. Voor het bewijzen maakt het weinig uit.
Bewijzen
Een sluitende argumentatie dat B een geldig gevolg van de b1, b2, ..., bn is, noemen we bewijs van de stelling b1, b2, ..., bn ⊨ B.
Bij de poging een stelling te bewijzen kan duidelijk worden dat men aannames vergeten was. Het bewijzen is een goed middel onuitgesproken veronderstellingen boven water te krijgen.
Er zijn verschillende manieren om stellingen te bewijzen. We vergelijken er vier:
| waarheidstabellen | tableaus | deductie | transformaties | |
|---|---|---|---|---|
| aanpak | uitputtend | uitputtend, maar met slimme strategie | redenerend | herschrijvend |
| literatuur | V. Benthem hoofdst. 2 | V. Benthem hoofdst. 3 | V. Benthem hoofdst. 4 en 10 | V. Benthem hoofdst. 4.4 en 10.2 |
| idee | waarheidstabel langs constructieboom van de formule | systematische constructie van een tegenvoorbeeld, indien mogelijk | constructie van een volledig bewijs | formules herschrijven met behoud van betekenis |
| correctheid van systemen | uitputtende test | verantwoorde slimme test | correctheidsbewijs | transformatie |
| propositielogica | eindig, eenvoudig, inefficiënt | eindig, slim, efficiënt | beslisbaar, backtrack | beslisbaar |
| predikaatlogica | n.v.t. | onbeslisbaar, backtrack, creatief |
Deductie hebben we al leren kennen in het hoofdstuk Overtuigen. De geformaliseerde versie van dit proces heet natuurlijke deductie.
