Inleiding

Het menselijk denken bestaat uit allerlei redeneringen we kunnen bijvoorbeeld zeggen:

Maar dit soort redeneringen kan ook fouten veroorzaken:

Bv.

Maar hier is er eigenlijk een probleem: we gebruiken “kan in” op twee verschillende manieren.

Met de eerste uitdrukking bedoelen we eigenlijk dat ik in de jas pas en met de tweede bedoelen we dat ik de jas in de koffer kan steken.

Mensen gaan van nature dit soort redeneringsfouten maken; daarom gaan we in de logica een formeel systeem bedenken om deze fouten te vermijden.

Verder hebben we nog twee belangrijke soorten logica:

Logica

We gaan in de logica daarom een formeel systeem introduceren:

Propositie en predicatenlogica

Propositielogica is het meest eenvoudige redeneringssysteem.

Het bestaat uit uitspraken (ook wel beweringen of proposities genoemd) die alleen waar of onwaar kunnen zijn niets tussenin.

We kunnen deze propositie dan met elkaar verbinden door middel van de zogenaamde logische conjectieven

Die bestaan uit:

Bv.

Propositie: het regent Propositie: de zon schijnt

Dan zijn samengestelde uitspraken:

Het regent EN de zon schijnt Het regent OF de zon schijnt Als het regent dan schijnt de zon …

We gaan later kunnen berekenen of deze samengestelde uitspraken waar of onwaar zijn.

Tenslotte hebben we nog de predicatenlogica, dit is meer complexer. Een voorbeeld van predicatenlogica was onze kat Pluche. Predicatenlogica gaat eigenlijk iets zeggen over de eigenschap van individuen en daaruit dan redeneringen maken.

Deel 1: propositielogica

Syntaxis en semantiek

Formele taal

Inleiding

Zoals eerder gezegd in de menselijk of natuurlijke taal kwetsbaar voor redeningsfouten omdat uitspraken niet eenduidig kunnen worden geintrepreteerd.

Daarom gaan we die beweringen of proposities voorstellen door symbolen, merk op dat deze proposities atomair zijn ze zijn niet verder opdeelbaar in andere proposities.

Voorbeeld: het regent: r de zon schijnt: z ik lust koffie: k …

Door dit op deze manier op te schrijven beletten we juist de intrepratie van de natuurlijke taal.

Deze nieuwe taal wordt de formele taal genoemd.

Proposities kunnen waar of onwaar zijn en kunnen aaneengeschakeld worden door connectieven.

Voor deze connectieven gaan we ook symbolen gebruiken.

$$ niet: \neg $$ $$ en: \wedge $$ $$ of: \vee $$

$$ als-dan: \rightarrow $$

$$ dan-en-slechts-dan-als: \leftrightarrow $$

Met deze symbolen kunnen we uitspraken uit de natuurlijke taal omzetten naar formele taal:

Aanname: Als je ziek bent dan lust je geen koffie Aanname: je lust koffie Conclusie: je bent niet ziek

Proposities: p: je ben ziek q: je lust koffie

De uitsprak in symbolen wordt dan:

$$ p \rightarrow \neg q $$

Componenten van een taal

Drie aspecten van een formele taal zijn belangrijk:

Alfabet

De symbolen van de propositielogica bstaan uit een verzameling van propositieletters, de logische symbolen (en, of, niet,…) en de hulpsymbolen “(” en “)”.

We kunnen de symbolen uit het alfabet combineren tot grotere complexere structuren, formules genaamd. Deze worden aangeduid door Griekse letters.

Een formule is onderhevig aan de onderstaande definitie:

De griekse symbolen noemt men ook wel formulevariabelen omdat je daar alles kan invullen wat je maar wilt. Formules zijn dus niet atomair zoals proposities, want je kan ze nog in andere proposities opdelen.

Terminologie
Inductieve definitie

De definitie van een formulier is inductief gedefineerd.

Een inductieve definitie bestaat uit de volgende elementen:

Formuleschemas en instanties

Zoals eerder gezegd worden Griekse letters gebruikt als formulevariabelen we kunnen ze gebruiken om een abstracte vorm te vormen van een formule ook wel een formuleschema genoemd.

Een voorbeeld hiervan is: $$ (\phi \leftrightarrow \psi) $$

De bovenstaande formule is dus een formuleschema. Wanneer we de formulevariabelen zouden vervangen door concrete formules noemen we de formule een instantie van het formuleschema.

Een voorbeeld, met bovenstaande formule:

$$ (p \leftrightarrow q) $$

$$ ((p \wedge q) \leftrightarrow q) $$

$$ (p \leftrightarrow \neg q) $$

zijn allemaal instanties van $(\phi \leftrightarrow \psi)$

In elk geval vervangen we $\psi$ en $\phi$ steeds met een concrete formule met propositieletters.

Substitutie

In een formule kunnen we ook letters gaan vervangen. Ten eerste kunnen we een bepaalde letter door een andere letter vervangen zolang deze overal wordt vervangen.

Maar er gelden nog meer definities, daarover straks meer.

Stel we hebben een formule $\phi$ en we willen de letter “p” vervangen door de formulie $\psi$, hieruit ontstaat een nieuwe formule.

In symbolen:

$$ [\psi/p]\phi $$

Definitie van substitutie

1.

2.

Deze definitie vertoond gelijkenissen met de inductieve definitie van een formule.

Constructieboom

We kunnen een formule ook als een constructieboom voorstellen. We beginnen in de wortel (vanboven geplaast) steeds met de hele formule en delen het dan op in andere samengestelde uitspraken tot als we bij de atomaire deeltjes komen: de propositieletters.

Om terug bij de oorspronkelijke formule te komen lezen we steeds van onder naar boven.

Voorbeeld constructieboom

Van elke welbepaalde logische formule is steeds slechts één constructieboom dit wilt zeggen dat elke formule eenduidig begrepen kan worden.

Om eenduidig vastlegbaar te zijn zijn de haakjes in een formule van uiterst belang!

Een voorbeeld vanuit de natuurlijke taal:

Als de baby niet huilt en trappelt, dan is ze gelukkig.

Dit heeft meerdere betekenissen:

In de propositielogica zouden de drie betekenissen als volgt vastgelegd worden.

Eerste definieren we de propositieletters:

p: baby huilt
q: baby trappelt
r: babby is gelukkig

Zonder haakjes zou de logische formule gelijk zijn aan de dubbelzinnige zin uit het voorbeeld uit de natuurlijke taal, meerdere constructiebomen zouden bestaan en dit is slecht om redeneringen te maken.

Semantiek

Bij de semantiek in een taal willen we de betekenis achterhalen van wat er geschreven is. Een geldige formule heeft maar twee betekenissen of waarheidswaarden namelijk: waar en onwaar.

We kunnen deze waarheidswaarden ook in 0 en 1 voorstellen. 0 voor onwaar en 1 voor waar. De waarheidswaarde van atomen (propositieletters) zijn gegeven of worden aangenomen, de waarheidswaarde van een samengestelde formule moet afgeleid worden door middel van een waarheidstabel van de connectieven.

In een waarheidstabel gaan we alle mogelijke combinaties van waarheidswaarden van de atomen (propositieletters) opsommen en dan een uitspraak doen over de samengestelde formule.

Neem bijvoorbeeld het volgende: p: de zon schijnt q: het regent

En de volgende samengestelde formule $(p \wedge q)$

Dan volgt daar de volgende waarheidstabel uit:

p q $(p \wedge q)$
0 0 0
0 1 0
1 0 0
1 1 1

Zoals te zien is in de bovenstaande tabel is samengestelde formule met een “en” connectief alleen maar waar als beide atomen waar is.

Elke rij van de tabel staat voor een bepaalde situatie of waardering. Laten we bijvoorbeeld de eerste rij nemen.

Daar is de waarde van p onder de situatie of waarderng van de eerste rij (V) gelijk aan 0. We noteren V(p) = 0

Eveneens kunnen we zo q onder deze waardering bepalen: V(q) = 0. Door deze vastgelegde waarden kan ook V($(p \wedge q)$ bepaald worden en deze is gelijk aan 0.

We noteren V($(p \wedge q)$) = 0

Wanneer we meerdere waarderingen hebben zoals in de tabel is het handig om de waarderingen een nummer te geven zoals $V_1, V_2 \ldots$

Waarheidstabellen: een overzicht
$\phi$ $\neg \phi$
0 1
1 0

Een negatie draait gewoon de waarheidswaarde om.

$\phi$ $\psi$ $(\phi \wedge \psi)$
0 0 0
1 0 0
0 1 0
1 1 1

Het “en” connectief is alleen waar wanneer beide proposities waar zijn.

$\phi$ $\psi$ $(\phi \vee \psi)$
0 0 0
0 1 1
1 0 1
1 1 1

Het “of” connectief is waar wanneer één van de twee verbonden proposities waar zijn.

$\phi$ $\psi$ $(\phi \rightarrow \psi)$
0 0 1
0 1 1
1 0 0
1 1 1

Het “als-dan” connectief is waar wanneer beide propositieletters waar zijn of wanneer de eerste propositieletter onwaar is.

Dit is misschien wat counter-intituitief maar zo is het afgesproken in de propositielogica.

$\phi$ $\psi$ $(\phi \leftrightarrow \psi)$
0 0 1
0 1 0
1 0 0
1 1 1

Het “als-dan-en-slecht-als” is waar wanneer beide propositieletters oftewel waar zijn oftewel onwaar zijn.

Waarheidstabellen van een complexere samnegestelde formule

Nu hebben we alleen nog formules gezien met slechts twee propositieletters, stel dat er nu drie zijn en dat de samengestelde formule een iets complexere vorm heeft.

Bv.

$$ ((h \wedge s) \rightarrow \neg u) $$

Om deze waarheidstabel te kunnen bepalen moeten we deze formule opdelen in kleinere delen zoals we dat deden in de constructieboom.

Onze waarheidstabel gaat er dan zo uitzien:

h s u $\neg u$ $(h \wedge s)$ $((h \wedge s) \rightarrow \neg u)$
0 0 0 1 0 1
0 0 1 0 0 1
0 1 0 1 0 1
1 0 0 1 0 1
0 1 1 0 0 1
1 0 1 0 0 1
1 1 0 1 1 1
1 1 1 0 1 0
Complexiteit van waarheidstabellen

Een formule $\phi$ met $n$ aantal atomen (propositieletters) zal altijd $2^n$ aantal rijen hebben dit komt doordat elke propositieletter twee mogelijkheden heeft en vanuit de combinatoriek kunnnen we besluiten dat er voor een $n$ aantal proposities een $2^n$ aantal combinaties mogelijk zijn.

Waardering

Definitie: een waardering is een functie van alle propositielettersnaar waarheidswaarden waar waar gelijk is aan 1 en onwaar aan 0.

We kunnen met een gegeven waardering ook de waarheidswaarde van een formule $\phi$ vinden, dit komt doordat de waardering de propositiesletters naar 0 of 1 omzet, en formules bestaan uit deze propositiesletters.

Model

Een waardering is een model van een formule $\phi$ als $V(\phi) = 1$. In onze laatste tabel zijn dat alle rijen behalve de laatste.

We noteren ook de verzameling van modellen als:

$$ MOD(\phi) = {V | V(\phi) = 1 } $$

Een waardering V kan ook een model zijn van een formuleverzaming $\sum$ als ze het model is van elke formule $\phi \in \sum$.

De verzaming van modellen van $\sum$ wordt genoteerd als $MOD(\sum)$

Modelelimenatie

Neem nu het volgende voorbeeld:

  1. Jan komt als Marieke of Anne komt ($((q \vee r) \rightarrow p)$)
  2. Anne komt als Marieke niet komt ($(\neg q \rightarrow r)$)
  3. Jan komt niet als Anne komt ($(r \rightarrow \neg p)$)

Kan hieruit afgeleid worden wie er allemaal gaat komen? We kunnen deze uitspraken gaan voorstellen via een waarheidstabel.

p: jan komt
q: marieke komt
r: anne komt

p q r $\neg q$ $\neg p$ $((q \vee r) \rightarrow p)$ $(\neg q \rightarrow r)$ $(r \rightarrow \neg p)$
0 0 0 1 1 0 1 0 (s)
0 0 1 1 1 1 0 (s)
0 1 0 0 1 1 0 (s)
1 0 0 1 0 0 1 0 (s)
0 1 1 0 1 1 0 (s) 0 (s)
1 1 0 0 0 1 1 1 1
1 0 1 1 0 1 1 1 0 (s)
1 1 1 0 0 1 1 1 0 (s)

Het enige model van de formumeverzameling {1,2,3} is voor V(p) = 1 , V(q) = 1, V(r) = 0, dus de enige mogelijke gasten die komen naar dit feestje zijn Jan en Marieke.

Tautologie

Een tautologie is wanneer elke waardering een model is van een formule $\phi$. Dus elke waardering van de formule is waar.

Voorbeeld:

Elke formule van de vorm $(\phi \vee \neg \phi)

$\phi$ $\neg \phi$ $(\phi \vee \neg \phi)$
1 0 1
0 1 1

Elke situatie of waardering heeft dus als waarde 1 of is een model van de formule $(\phi \vee \neg \phi) is dus een tautologie.

Logische equivantie

Twee formules $\phi$ en $\psi$ zijn logisch equivalent wanneer $\phi \leftrightarrow \psi$ een tautologie is.

Voorbeelden van logische equivalente formules:

Deze laatste equivalentie zorgt ervoor dat we de haakjes vaak kunnen weglaten wanneer we met dezelfde connectieven werken.

De wetten van De Morgan:

Functioneel volledig

Een verzaming connectieven C heet functioneel volledigalls elke formule $\phi$ logisch equivalent is met de formule $\psi$ die enkel connectieven uit C bevat.

Voorbeelden van functioneel volledig connectieve verzamelingen:

{$\neg$, $\wedge$, $\vee$}

maar ook

{$\neg, \wedge$} omdat we $\wedge$ kunnen omvormen naar $\vee$ door de formules van De Morgan

Disjunctieve normaalvorm

Een formule is een disjunctieve normaalvorm wanneer ze geschreven is als een een aaneenschakeling van conjuncties aaneengeschakeld door disjuncties, bestaande uit atomen of negaties van atomen.

Elke formule kan in deze vorm geschreven worden!

Redeneren: geldig gevolg
Voorbeeld

Jan is een goede schaker en Karin is een goede dammer.

Hieruit is intuitief te concluderen: Jan is een goede schaker.

We kunnen dit ook controleren via een waarheidstabel:

p: jan is een goede schaker
q: karin is een goede dammer

p q $(p \wedge q)$
0 0 0
0 1 0
1 0 0
1 1 1

Als we dus kijken naar de uitspraak $(p \wedge q)$ en dan kijken wat de waarden van p en q zijn bij het waar zijn van deze uitspraak blijkt dat de enige mogelijke conclusie is dat Jan een goede schaker is (p).

Algemeen geldt voor geldig gevolg het volgende: als het uitgangspunt waar is, dan is de conclusie ook waar

Geldig gevolg

Definitie: een formule $\phi$ heet een geldig gevolg van de verzameling formules $\sum$ als elk model van $\sum$ ook een model is van $\phi$.

Het bovenstaande wordt ook als volgt in symbolen genoteerd:

$\sum \models \phi$.

Bijvoorbeeld:

$p, p \rightarrow q \models q$

Waarheidstabel:

p q $(p \rightarrow q)$ q
0 0 1 0
1 0 0 0
0 1 1 1
1 1 1 1

V(p) = 1 en V(q) = 1 is alleen maar een geldig gevolg omdat we als verzameling van formules in de opgave $p$ en $p \rightarrow q$ gegeven hadden en bij V(p) = 0 en V(q) = 1 is “p” niet waar dus is het geen model, dit betekent volgens de definitie dat die waardering geen geldig gevolg kan zijn.

Iets kan ook geen geldig gevolg zijn:

Dat wordt dan zo genoteerd:

$q, p \rightarrow q \not\models p$

Bewijs volgt uit de waarheidstabel:

p q $(p \rightarrow q)$ p
0 0 1 0
0 1 1 0 (geen model)
1 0 0 1
1 1 1 1

Voor V(p) = 0 en V(q) = 1 is er een model voor q en een model voor $(p \rightarrow q)$ maar om een geldig gevolg te zijn moet dat ook een model zijn van p maar vanuit de tabel blijkt dat dit niet zo is, dus is dit geen geldig gevolg.

Let op gevolgtrekking betekent niet dat de uitspraken altijd waar zijn!

Bekende geldige gevolgen
Semantisch tableau

Om uit te zoeken of iets een geldig gevolg is kunnen we ofwel een waarheidstabel opstellen en kijken of de moddellen van $\sum$ ook modellen zijn van $\phi$, als dit niet zo is dan is het geen geldig gevolg.

Het zoeken van een waardering bij deze voorwaarden noemen we een tegenvoorbeeld zoeken.

Om een tegenvoorbeeld zonder waarheidstabel te vinden gaan we gebruik maken van deze semantische tableaus om gebruiken te maken van deze moeten we eerst een nieuwe term introduceren: het sequent.

Het sequent is een rijtje van de vorm:

$$ \phi_1, \phi_2, \ldots, \phi_n \quad o \quad \psi_1, \psi_2, \ldots , \psi_n $$

Wat betekent: alles wat links staat is waar en alles wat rechts staat is onwaar.

Dit heeft een verband met het tegenvoorbeeld van het geldig verband:

$$ \phi_n \models \psi_n $$

Waarvoor we zoeken:

$$ V(\phi_n) = 1 $$

$$ V(\psi_n) = 0 $$

V steeds verwijzend naar dezelfde waardering.

Dus als we $\phi_n$ links plaatsen en $psi_n$ rechts dan is het zoeken naar een tegenvoorbeeld van een sequent hetzelfde als een tegenvoorbeeld zoeken van een geldig gevolg.

Om dit tegenvoorbeeld te zoeken gaan we gebruik maken van een schema waarbij we het sequent terugbrengen (reduceren) naar een eenvoudiger sequent.

Een voorbeeld:

$$ p \vee q, \neg q \models p $$

Heeft dit geldig gevolg een tegenvoorbeeld en is het dus een geldig voorbeeld of niet?

Laten we het eerst opschrijven als een sequent:

$$ p \vee q, \neg q \quad o \quad p $$

We zien dat $\neg q$ waar moet zijn, dat betekent dat $q$ zelf dus onwaar moet zijn. Daarom kunnen we q aan de rechterkant plaatsen:

$$ p \vee q \quad o \quad p, q $$

Tenslotte hebben we nog $p \vee q$ en dat moet ook waar zijn. Deze formule is enkel waar wanneer of $p$ of $q$ of beide waar zijn.

$$ p \quad o \quad p, q $$

Nu zien we dat in dit geval p zowel waar of onwaar moet zijn en dat is uiteraard onmogelijk dus dit sequent is gesloten we hebben er geen tegenvoorbeeld voor.

Tenslotte hebben we nog het geval waarbij $q$ waar moet zijn.

$$ q \quad o \quad p,q $$

Analoog met het vorige voorbeeld kan $q$ niet tegelijk waar en onwaar zijn, dit sequent is dus ook gesloten en er bestaat geen tegenvoorbeeld.

We hebben nu alle gevolgen overlopen dit betekent dat het tableau ook gesloten is en het inderdaad een geldig gevolg is.

Schematisch

We kunnen dit ook voorstellen door middel van een boomstructuur.

Wanneer een tak of een sequent gesloten is plaatsen we een “=” teken eronder.

Gesloten of open semantisch tableau

Een tak is gesloten wanneer er aan de beide kanten dezelfde formule staat oftewel dat er een contradictie ontstaat omdat dezelfde formule zowel waar als onwaar moet zijn.

Een tak is open wanneer ze niet gesloten is en wanneer er geen reductieregels meer kunnen wordne toegepast.

Een tableau is gesloten wanneer alle takken gesloten zijn.

Een tableau is open wanneer er tenminste één tak niet gesloten of open is.

Semantisch consistent

Definitie: een formuleverzamling $\sum$ is semantisch consistent als $\sum$ een model heeft.

Dus dat betekent dat de formuleverzameling minstens één waardering moet hebben die waar is om semantisch consistent te zijn.

We kunnen dit ook noteren met sequenten:

$$ \sum \quad o \quad $$

Het sequenet betekent niets meer dan “de formuleverzameling is waar”, er staat momenteel niets achter de “o” dus er zijn geen voorwaarden van formules die onwaar moeten zijn.

Dan rest ons alleen nog de taak om een tegenvoorbeeld voor dit sequent te vinden. Als dit tegenvoorbeeld bestaat en als het sequent een open tableau heeft dan is de formule semantisch consitent.

De waarden van de propositieletters in de formuleverzameling zal dan te bepalen zijn via de uitkomst van het tegenvoorbeeld.

Tautologie testen met semantische tableaus

Een formule $\phi$ is een tautologie als alle waarderingen van de formule een model zijn.

Met andere woorden als er geen waardering te vinden is waarvoor geldt V($\phi$) = 0.

We kunnen dit ook noteren als:

$$ o \quad \phi $$

Hiervan willen we juist geen tegenvoorbeeld vinden want $V(\phi)$ mag niet onwaar zijn voor een tautologie.

Dus een formule is een tautologie wanneer er geen tegenvoorbeeld bestaat en het tableau dus gesloten is.

Wiskundige bewijstechnieken

Rechtstreeks bewijzen

Bij een rechtstreeks bewijs proberen we te bewijzen dat als p waar is dan ook q waar is.

Dit zijn bewijzen van de vorm:

$$ p \rightarrow q $$

We kunnen ook door middel van tussenstappen tot het bewijs komen:

$$ p \rightarrow p1 $$

$$ p1 \rightarrow p2 $$

$$ pn \rightarrow q $$

Bewijs door contrapositie

We kunnen rechtstreekse bewijzen van het type:

$$ p \rightarrow q $$

ook omvormen naar

$$ \neg q \rightarrow \neg p $$

Dit komt omdat $p \rightarrow q$ logisch equivalent is met $\neg q \rightarrow \neg p$.

Een voorbeeld:

Te bewijzen: als $a^2 < b^2$ dan is $a < b$

Het is lastig om vanuit $a^2 < b^2$ te vertrekken dus we passen het bewijs door contrapositie toe.

p: $a^2 < b^2$ q: $a < b$

Dan:

$a \geq b \rightarrow a^2 \geq b^2$

is hetgeen wat we moeten bewijzen.

Vertrekkende vanuit $\neg q$:

$$ a \geq b $$

daaruit volgt dat:

$$ a \cdot a \geq a \cdot b $$

en

$$ a \cdot b \geq b \cdot b $$

Als $a \cdot b $ groter is dan $b \cdot b$ en $a \cdot a$ groter is dan $a \cdot b$ betekent dat dat $a \cdot a$ groter is dan $b \cdot b$.

Dus:

$$ a^2 \geq b^2 $$

Hiermee is de implicatie waar en is de stelling ook bewezen.

Bewijs uit het ongerijmde

Een bewijs uit het ongerijmende of een bewijs door contradictie is een bewijs waarbij we het tegengestelde van een stelling p als waar aanemen en hieruit een eigenschap q proberen af te leiden die in strijd is met andere eigenschappen of axiomas.

Het feit dat dit werkt heeft met de volgende uitspraak te maken:

$$ \neg p \rightarrow q $$

Als we weten dat q onwaar is (in strijd is met gekende eigenschappen of axiomas) dan moet volgens de waarheidstabel $\neg p$ ook onwaar zijn om de implicatie waar te maken.

Daaruit volgt dat $p$ waar moet zijn en de stelling $p$ dus bewezen is.

Op die manier kunnen we ook stellingen van het type

$$ p \rightarrow q $$

bewijzen.

We willen dus gebruik maken van het volgende:

$$ \neg (p \rightarrow q) \rightarrow t $$

$\neg (p \rightarrow q)$ is logisch equivalent met $(p \wedge \neg q).

Dus dan hoeven we alleen het bewijs vanuit het ongerijmde toe te passen op:

$$ (p \wedge \neg q) \rightarrow t $$

Dus we moeten een tegenspraak in de uitspraak van t vinden waardoor (p \wedge \neq q) wel onwaar moet zijn $\neg (p \rightarrow q)$ ook onwaar moet zijn en dus $p \rightarrow q$ waar moet zijn.

Stellingen van het type $p \leftrightarrow q$

Als we een logische equivalentie willen bewijzen moeten we alleen het volgende bewijzen:

$$ (p \rightarrow q) \wedge (q \rightarrow p) $$

Bewijs per inductie

Een bewijs per inductie wordt gebruikt voor een oneindig aantal gevallen te bewijzen.

In het algemeen ziet zo’n bewijs er als volgt uit.

We hebben een verzameling uitspraken {$p_n | n \in N$} zodat

(a) p_0 waar is
(b) $\forall k \in N$ : als $p_k$ waar is dan is $p_{k+1}$ ook waar

Dan is $p_n$ voor alle $n \in N$ ook waar

Dus met andere woorden als we aantonen dat het eerste geval waar is, vervolgens aannemen dat voor een willekeurig geval k het ook waar is en dan kunnen aantonen dat het voor het volgende geval ook waar is we hebben bewezen dat het voor alle gevallen waar is.

Principe bewijs per inductie

Het bewijs per inductie is op de volgende stelling gebasseerd:

Zij S een deelverzameling van N zodat

  1. $0 \in N$
  2. $\forall k \in N: $ als $k \in S$ dan $k+1 \in S$
    Dan is S = N

Hieruit kunnen we ook de stelling van het bewijs per inductie bewijzen.

Stelling

We hebben een verzameling uitspraken {$p_n | n \in N$} zodat

(a) p_0 waar is
(b) $\forall k \in N$ : als $p_k$ waar is dan is $p_{k+1}$ ook waar

Dan is $p_n$ voor alle $n \in N$ ook waar

Bewijs

Veronderstel dat $p_0$, $p_1$, $p_2$,… voldoen aan (a) en (b) Zij S = {$n \in N | p_n is waar$}

Uit (a) volgt dat $0 \in S$ en uit (b) volgt dat: $\forall k \in S$: als $k \in S$ dan $k+1 \in S$.

Dan is S = N, dat wil zeggen dat alle $p_n$ waar zijn voor alle N.

Afleidingen

In het deel van geldig gevolg hebben we gekeken naar de semantische logische geldigheid nu gaan we het op een syntactische manier benaderen.

We gaan altijd vertrekken van een aantal aannames om daaruit conclusies te trekken.

Een voorbeeld:

  1. Jan vertelt een verhaal en piet leest de krant
  2. Als Jan een verhaal vertelt, dan lacht Marie.
  3. Als Piet de krant leest, kijkt Wilma televisie.

Uit 1 kunnen we concluderen dat Jan een verhaal vertelt. Want als 1. waar is moeten beide uitspraken van de conjunctie waar zijn.

Uit 2 kunnen we concluderen dat Marie lacht want Jan vertelt een verhaal. Tenslotte kunnen we uit 1. concluderen dat Piet de krant leest en dat Wilma dus televisie kijkt.

We kunnen dit ook voorstellen door middel van propositieletters en een afleidingsboom.

j: jan vertelt een verhaal p: piet leest de krant m: marie lacht w: wilma kijkt televisie.

$\dfrac{j \wedge p}{\frac{j \qquad j \rightarrow m}{m}}$

We gaan het dus altijd noteren als:

$$ \dfrac{\phi_1 \ldots \phi_n}{\psi} $$

Waar bovenaan de streep de aanname staat en onderaan de afleiding of conclusie.

We hebben hierboven twee eleminitieregels gebruikt, voor meer informatie over deze afleidingsregels van de natuurlijke deductie verwijs ik naar p. 50 in het handboek.