Logica 2 voor Filosofie
Algemeen
Op deze pagina worden de vorderingen van het college Logica 2 voor Filosofen
bijgehouden. Ook zal een aantal opgaven via deze pagina worden gedistribueerd.
Het werkcollege is op de maandag (Zaalwijziging T1 123) en de woensdag (T1 123)
van 11:00-13:00 en wordt
gegeven door Joost Joosten. Op maandag is
er aansluitend (van 13:00-15:00) (T1 123)
een werkgroep die door Albert Visser zal worden begeleid. Hier zal
aanvullende literatuur worden behandeld en discussie over de
stof plaats hebben. Woensdag is er van 13:00-15:00 (Zaalwijziging T1 123)
een werkcollege waar de
aangeleerde technieken zullen worden geoefend. Het werkcollege
wordt begeleid door
Marijn Zwitserlood,zwitserlood@hotmail.com.
Joost is te vinden op kamer
438 in het bestuursgebouw en het telefoonnummer aldaar is 030-2535579.
Literatuur die in het college gebruikt gaat worden: Het hoorcollege
zal vaak verwijzen naar "Logic and Structure" van Dirk van Dalen. In de
werkgroep worden artikelen gelezen en zal uit het boek van Mark Sainsburry
"Logical Forms"
worden gewerkt. De artikelen die tijdens de werkgroep worden gebruikt en
eventuele aanvulling zijn opvraagbaar bij het onderwijsbureau.
Tentamenregeling
Het eindcijfer wordt bepaald door twee geleverde prestaties. Een
paper na aanleiding van de werkgroepen en een tentamen.
De student kan in zekere mate kiezen hoe zwaar welk onderdeel
meetelt. Er zijn twee mogelijke scenario's.
Scenario 1. De paper levert 15 punten op en het tentamen 85.
Scenario 2. De paper levert 30 punten op en het tentamen 70.
Voor aanvang van het tentamen wordt beslist voor welk scenario de
student gaat. De onderdelen kunnen los van elkaar worden herkanst.
Het tentamen is (wijzigingen voorbehouden)
woensdag 19 november van 9:00-12:00 in Tr1 114.
De tussentoets zal op een zekere wijze bonuspunten opleveren voor
alleen het tentamen. Een aantal mogelijke onderwerpen voor een paper
is gesuggereerd door
Albert Visser,Albert.Visser@phil.uu.nl en is ook in deze
pagina opgenomen:
Mogelijke onderwerpen voor een paper
[
Postscript|
Pdf formaat]
Week 1 maandag 29-10-01
In de eerste les is gesproken over de raakvlakken van logica met filosofie.
In het college zal ook een aantal technieken worden behandeld.
Als eerste techniek hebben we inductie behandeld. We hebben bewezen dat
er 2^n -1 zetten nodig zijn om een stapeltje van n stenen in "De torens van Hanoi"
te verplaatsen.
Enige punten uit les 1
[
Postscript|
Pdf formaat]
Deze samenvatting geeft in grote lijnen weer waarover wij gesproken heben.
Veel details zijn uiteraard weggelaten.
Week 1 woensdag 31-10-01
Er is meer gesproken over inductie. B.v. als we beginnen met een paaltje in de
grond te slaan en iedere meter verder weer een paaltje in de grond slaan
hebben we voor 100 meter 101 paaltjes nodig. De som van k=1 tot k=n van
1/(k(k+1)) is gelijk aan n/(n+1). Hoe kunnen universele uitspraken worden
bewezen. Als het domein waarover gekwantificeerd wordt een inductieve structuur
heeft hebben we dus de inductieve bewijsmethode tot onze beschikking.
Inductieve verzamelingen hebben atomen en genererende operatoren.
De verzameling van proposities is inductief gedefinieerd. We hebben dus formule
inductie. Iedere formule heeft een even aantal haakjes.
De semantiek van propositielogica is herhaald. Er is gesproken over
bedelingen en over valuatie's. Ook hebben we de semantische consekwentie
relatie gedefinieerd. Met inductie hebben we bewezen dat men "de Morgan's"
wetten kan uitbreiden naar meerdere conjuncten. In L&S (Logic and Structure
van nu af aan) hebben we ongeveer blz 7 t/m 21 behandeld.
Oefenopgaven week 1
[
Postscript|
Pdf formaat]
Opgaven 1,2,3 en 6 zijn in de werkgroep behandeld.
Week 2 maandag 5-11-01
We hebben de standaard mantra voor inductieve bewijzen iets preciezer vast
gesteld en een formele (inductieve) definitie gegeven van de
sigma ofwel sommatie notatie. Het geraamte van onze mantra ziet er als volgt uit.
Blobs is hier een inductief gedefinieerde verzameling met atomen {A_i}
en als
genererende operatoren G_1, ..., G_p. In het geval van de natuurlijke
getallen is er slechts een atoom namelijk het getal nul en de
enige genererende operator is "er 1 bij optellen". In het geval van de
formules van de propositie logica zijn er oneindig veel atomen, namelijk
de variabelen letters, en de genererende operatoren zijn de connectieven,
i.e. implicatie, conjunctie, disjunctie en negatie. Met A beven wij een
eigenschap aan.
Onze Mantra:
T.B. Alle Blobs zijn A
B. Het bewijs gaat met inductie naar Blobs.
-Basis: [Argument] Alle atomen zijn A. (krulletje)
-Inductie:
*Uitgaande van het feit dat de blobsen B_1,...,B_n de eigenschap A
hebben, moeten we laten zien dat G_1(B_1,...,B_n) eigenschap A heeft.
[Argument]
...
...
...
*Uitgaande van het feit dat de blobsen B_1,...,B_m de eigenschap A
hebben, moeten we laten zien dat G_p(B_1,...,B_m) eigenschap A heeft.
[Argument]
Q.E.D.
Over vorige week: iedere bedeling definieert een valuatie en andersom
iedere valuatie definieert een bedeling. Met inductie hebben we
stellingen bewezen zoals (A_0 /\ ... /\ A_n)\/ C is equivalent met
(A_0 \/ C)/\ ... /\ (A_n \/ C). Ook hebben we de stelling van Hannah bekeken
die zegt dat we in een formule een deel mogen vervangen door een equivalent
deel. (Soms wordt dit ook wel de substitutiestelling genoemd.)
We hebben conjunctieve- en disjunctieve-
normaalvormen gedefinieerd en enkele voorbeelden gegeven.
(We hadden dus eerst met inductie grote dis- en con- juncties geintroduceerd.)
Met behulp van
formule-inductie zijn we aan het bewijs begonnen dat ieder formule een equivalent
in DNV en in CNV heeft. (In Ls hebben we ongeveer blz 17 -26 gedaan.)
Uitwerking van oefenopgaven week 1
[
Postscript|
Pdf formaat]
Week 2 woensdag 7-11-01
We hebben het bewijs afgemaakt van de stelling dat iedere formule zowel
in DNV als in CNV kan worden geschreven. In de inductiestap die de
negatie behandelde zagen we dat het erg handig was om het bestaan van een
DNV en een CNV te gelijker tijd te behandelen. We hadden het volgende lemma
nodig
|= neg (A_0 /\ ... /\ A_n) <-
-> neg A_0 \/ ... \/ neg A_n .
Uiteraard is dit met inductie naar n bewezen. We hebben het gedrag van de
connectieven in ons redeneren bekeken. Deze observaties vormen de
legitimatie van de introductie van de verzameling B, van alle bewijzen.
De verzameling B was weer een inductief gedefinieerde verzameling.
We hebben natuurlijke deductie ingevoerd en duidelijk onderscheid gemaakt
tussen klassieke en intuitionistiche bewijzen. (Een intuitionistisch bewijs
is een klassiek bewijs waar RAA (reductio ad absurdum) niet in voor komt.)
We hebben de logische constante falsum
ingevoerd. De waarheidswaarde van dit symbool is constant en altijd gelijk aan
0,i.e. onwaar. We hebben falsum gebruikt om van de negatie af te komen.
(Wederom Hannah's stelling.) Er is een aantal bewijzen met
natuurlijke deductie geleverd. (In Ls hebben we ongeveer blz 29 t/m 39
behandeld. Omdat wij in ons systeem de regel voor disjunctie hebben
opgenomen hebben wij dus een iets ander systeem dan in Ls. Dat dit
verschil niet essentieel is kan worden nagelezen op blz 48 t/m 53.)
Oefenopgaven week 2
[
Postscript|
Pdf formaat]
In het werkcollege is som 6 uitgebreid aan bod gekomen en som 8 is
enigszinds besproken. Het is aan te raden om naar sommen 8 en 3 te kijken
dan kunnen deze volgende week tijdens het werkcollege vluchtig
behandeld worden.
Week 3 maandag 12-11-01
(Zaalwijziging T1 123)
In dit college hebben we een aantal afleidingen met natuurlijke deductie gegeven.
Een bewijs in natuurlijke deductie is ook constructief als er geen
RAA (reductio ad absurdum) wordt gebruikt. Dus het bewijs dat wij hebben
gegeven van (not not A -> A) is niet constructief. Later zullen we zien dat er
ook geen constructief bewijs van bestaat! Met inductie is bewezen dat voor alle n
geldt
|- ((A -> B_0) /\ ... /\ (A -> B_n)) ---> (A -> (B_0 /\ ... /\ B_n))
We hebben de definitie van V |- A en V |= A herhaald. Hier is V dus een
verzameling en A is een formule. De correctheidsstelling voor de propositie
logica zegt dus dat als V |- A dan geldt V |= A.
Er is gesproken over de filosofische gronden waarop zoiets als (not not A -> A)
kan worden weerlegd. De verzameling van alle bewijzen in de propositie
logica geven wij aan met B. Ook gebruiken we twee functie die een bewijs
als argument hebben. De verzameling aannamen die in een bewijs D gebruikt worden
(dus de aannamen die nog niet zijn ingetrokken) geven we aan met A(D).
Als er geen aannamen meer zijn is A(D) dus gelijk aan de lege verzameling!
Verder gebruiken we een functie C die bij elk bewijs D zegt wat de concusie ervan
is C(D), maw deze functie geeft de laatste formule, de formule helemaal onder
aan het bewijs, als functiewaarde.
Uitwerking van oefenopgaven week 2
[
Postscript|
Pdf formaat]
(Met dank (veel dank) aan Marijn en Joost!!)
Week 3 woensdag 14-11-01
We hebben een bewijs gegeven van A \/ not A en ook een bewijs van
(A --> B) \/ (B --> A). Dit zijn niet constructieve bewijzen en maken
dus essentieel gebruik van RAA.
Verder zijn tijdens het college zijn de volgende punten aan bod gekomen.
Deductielemma i.e., V |- A --> B <=
==> V,A |- B . Afzwakkingslemma's: Als de verzameling formules V bevat is in
de verzameling formules W dan geldt V |- A ==> W |- A , en ook
V |= A ==> W |= A .
De correctheisdsstelling voor propositielogica d.w.z.,
V |- A ==> V |= A. Dit was ons eerste bewijs met inductie naar
deductieve bewijzen van de propositielogica.
De structuur van het bewijs verliep iets anders dan in Ls. Hierdoor
komt duidelijker naar voren dat we een bewijs met inductie naar
deductieve bewijzen uitvoeren. We hebben bewezen dat voor elk
deductief bewijs D de conculsie van het bewijs, C(D), semantisch volgt
uit de aannnamen, A(D), van het bewijs, ofwel A(D) |= C(D). Met
het afzwakkingslemma krijgen we dan het gewenste resultaat.
In Ls is de correctheidsstelling geformuleerd en bewezen in
lemma 1.5.1. Merk op dat wij in ons bewijs drie stappen meer moesten
maken omdat wij regels hebben voor de \/ introductie (links en rechts)
en voor de \/ eliminatie. In het bewijs werd intensief gebruik gemaakt van
definitie 1.2.1. die valuatie's definieert.
Oefenopgaven week 3
[
Postscript|
Pdf formaat]
In het werkcollege zijn behandeld: opgave 1 (behalve 5), opgave 3 (merk op,
dit is een stap in het bewijs van de correctheidsstelling), opgave 4, en van
vorige week nog opgave 3.
Week 4 maandag 19-11-01
(Zaalwijziging T1 123)
De tussentoets zal gaan over alle college's tot dusver, dus ook het laatste college!
in principe wordt dus al deze kennis als bekend verondersteld. Nadruk kan
worden gelegd op de volgende punten. Uit het eerste college de formulering van de
grote stellingen (ondefinieerbaarheid van waarheidspredicaat, volledigheidsstelling,
onvolledigheidsstelling, ... ), de paradoxen en de noodzaak om axioma's te bestuderen.
Inductieve bewijzen, zowel inductie naar natuurlijke getallen, of formule-inductie
of inductie naar een andere willekeurige inductief gedefinieerde structuur. Verder
worden de belangrijkste definitie's tot dusver behandeld bekend verondersteld
(bedelingen, valuatie's, formules, bewijzen, inductieve definitie's, disjunctieve en
conjunctieve normaalvormen, intuitionistische bewijzen vs klassieke bewijzen,
A is bewijsbaar uit V, A is een semantische consequentie van V,
consistente zinsverzameling, et cetera.)
Verder is het handig om een aantal bewijsjes ofwel volledig uit het hoofd te
kennen (een deductief bewijs van de wet van de uitgesloten derde),
ofwel de structuur ervan te kennen (beslisbaarheid propositielogica,
correctheidsstelling, con- en disjunctieve- normaalvormen). Wellicht kan
ook de stelling van Hannah nuttig zijn om te kunnen formuleren.
Beslisbaarheid
van propositielogica. Dit wil zeggen we kunnen op een effectieve manier
beslissen of A bewijsbaar is uit V of niet. Namelijk probeer afwisselend
een bewijs te vinden of een valuatie die de bewijsbaarheid weerlegt.
Hier hebben we dus de correctheidsstelling voor nodig!
We hebben de definitie van een consistente zinsverzameling gegeven en lemma's
1.4.3. en 1.5.4. uit Ls bewezen.
!!!!!! TUSSENTOETS !!!!!!!!!!!!!!!!!
Voor het maken van de tussentoets is vijf kwartier de tijd. Daarna is er een
kwartierje pauze. Eventueel kunnen zij die de toets dan nog niet af hebben
tijdens de pauze doorwerken. Na de pauze is er nog zo'n twintig minuten les.
Uiteindelijk hebben we het gehele college gebruikt voor de tussentoets.
Er is dan ook afgesproken dat er een extra college zal worden
gehouden en wel donderdag 29 november van 13:00 - 15:00.
Uitwerking van oefenopgaven week 3
[
Postscript|
Pdf formaat]
Tussentoets
[
Postscript|
Pdf formaat]
Bij het nakijken van de toets heb ik min of meer de volgende criteria aangehouden.
Opgave 1,a,b en c 8pt(regels correct 2, structuur 5, annotatie 1). Opgave 2,
1=1,2=2,3=2; Inductie= 21 (mantra=9, basis=3, inductie =9). Opgave 3,
|- =7 (bewijs=3, aannamen =2, conclusie's= 2), |= = 8 (valuatie's =2,
v(Gamma)= 2, implicatie=2). Opgave 4,:15 (|=,|-, redelijk, voor alle, phi_T=3).
Opgave 5,:20 (D_0,D_2=2,structuur=10,regels=2,annotatie=3, aannamen=1).
Dit zijn richtlijnen geweest bij het nakijken. Het voorlopig resultaat valt hieronder
te vinden.
Voorlopige Uitslag Tussentoets
[
Postscript|
Pdf formaat]
Er wordt nog gekeken in welke mate de tussentoets zal meetellen in het eindcijfer.
Week 4 woensdag 21-11-01
We hebben gesproken over opsombaarheid van verschillende verzamelingen.
Zo hebben we gezien dat de verzameling van gehele getallen opsombaar is
maar ook de verzameling van formules en de verzameling van bewijzen is
opsombaar. De verzameling van reele getallen en de verzameling van alle
valuatie's zijn niet opsombaar.
We hebben een bewijsschets gegeven voor een beslissingsprocedure voor
afleidbaarheid in propositielogica. Dus propositielogica is
Beslisbaar! Dit is een belangrijk begrip in de logica.
Filosofische vragen komen aan de orde wanneer we het over onbeslisbaarheid
willen gaan hebben.
Er is een begin gemaakt met de volledigheidsstelling, dus V |= A ===>
V |- A. We hebben de notie van consitente zinsverzameling geintroduceerd.
en lemma's 1.5.3. en 1.5.4. bewezen. Maximaal consitente (MC's) zinsverzamelingen
zijn gedefinieerd en we hebben bewezen dat zij gesloten zijn onder
afleidbaarheid en dat zij groot zijn. Namelijk als V een MC is dan geldt
voor alle formules A dat ofwel A in V is of (not A) is in V.
Oefenopgaven week 4
[
Postscript|
Pdf formaat]
In het werkcollege zijn uitgenreid behandeld opgaven 1,3, 5 en 6. Opgave
4 is huiswerk en zal volgend werkcollege op het bord worden voorgemaakt.
Kijk ook even naar opgave 8, want die worddt wellicht ook voorgemaakt
volgend werkcollege.
Week 5 maandag 26-11-01
Het bewijs van de volledigheidsstelling van propositielogica is
afgemaakt. De structuur van het bewijs moet kunnen worden
gereproduceerd. Dus, we willen V |= A ==> V |- A. We werken
via contrapositie. Dus stel dat A niet bewijsbaar is uit V.
Dan is dus V tesamen met de negatie van A consistent en dan zijn
we klaar. Want Lindenbaum's stelling zegt dat iedere consistente
verzameling valt uit te breiden tot een maximaal consistente
verzameling. En we hebben gezien dat als we een maximaal consistente
verzameling W hebben dat we dan simpelweg een valuatie v_0
kunnen definieren door te stellen dat v_0(A)= 1 <===
==> (A is een element van W).
In Ls hebben we dus gedaan: lemma's 1.5.7. tot en met 1.5.13.
Uitwerking tussentoets
[
Postscript|
Pdf formaat]
(Zaalwijziging T1 123)
Week 5 woensdag 28-11-01
Semantiek voor intuitionistische propositielogica.
We hebben gesproken over semantiek voor intuitionistische propositielogica.
De motievatie voor deze semantiek was gestoeld op de
Brouwer-Heyting-Kolmogorov interpretatie van de propositielogica.
We hebben Kripke semantiek ingevoerd voor de propositielogica. In Ls staat
dit ook maar dan ook meteen voor predicatenlogica. De definitie die
wij hanteren is equivalent aan het propositionele deel van Ls. Voor de
duidelijkheid heb ik de definitie hieronder bijgevoegd. We hebben in twee
lemma's bekeken wat het betekent voor een formule not A om waar te zijn in
een wereld (knoop) en (dit was het hoofdpijn lemma) wat het betekent
om not not A waar te maken in een wereld. Dit laatste is het geval wanneer
we in iedere toekomstige wereld naar een eventueel verder toekomstige wereld
kunnen gaan waar A geldt. We hebben genoemd (niet bewezen) dat
intuitionistische afleidbaaheid correct is ten opzichte van de
Kripke semantiek d.w.z. alles wat constructief bewijsbaar is wordt
in ieder Kripke model geforceerd. De contrapositie van de
correctheidsstelling geeft ons weer een middel in handen om de niet
bewijsbaarheid in constructieve zin, aan te tonen. We moeten dan een
Kripke model geven die de niet bewijsbare zin niet forceert in k_0.
Volgens het gebruikelijke argument zien we dat ook afleidbaarheid
in constructieve zin een beslisbaar probleem is.
We hebben ook een volledigheidsstelling geformuleerd. Ook hier hebben we
geen bewijs gegeven. In Ls hebben we behandeld 5.1., en een deel van
5.3.
Oefenopgaven week 5
[
Postscript|
Pdf formaat]
Tijdens het werkcollege is behandeld som 4 van week 4 en verder is er veel
met Kripke-semantiek geoefend. Van som 7 van deze week hebben we tot en met
6 behandeld. Het huiswerk van Marijn is om van som 7 de delen 7 t/m 9 te
maken. Deze zullen dan kort behandeld worden in het volgende en tevens
laatste
werkcollege.
Enige definitie's
[
Postscript|
Pdf formaat]
Week 5 donderdag 29-11-01
!!!!!!!! EXTRA COLLEGE !!!!!!!!
TIJD: 13:00-15:00
ZAAL: Bestuursgebouw 467
Introductie tot de predicaten logica.
We hebben over de predicaten logica gesproken. Eerst in informele zin.
We hebben bekenen wat het betekent voor een zin om waar te zijn. (Maar we
hebben nog geen formele waarheidsdefinitie gegeven!)
De waarheid van een formule is altijd gerelateerd aan het model waarin
hij wordt geinterpreteerd. Dus als we willen inzien dat een zin niet
algemeen waar is, moeten we dus een model geven waarin hij niet waar is.
Het leek er op dat
het moeilijk is om algemene waarheden in de taal van de predicatenlogica
te geven. Deze algemene waarheden worden tautologien genoemd. In iedere
geval kunnen we een tautologie in de propositie logica nemen en voor de
delen van die tautologie op consequente wijze predikaat logische uitspraken
substitueren en weer een tautologie verkrijgen.
Maar er zijn meer tautologien die ook met de aard van de kwantoren te
maken hebben. Onze missie is om de klasse van alle tautologien te
klassificeren met behulp van een afleidbaarheidsbegrip |- en een
waarheidsbegrip |=. We moeten hierbij goed onderscheid maken tussen
syntax en semantiek.
We hebben de formele definitie gegeven van een taal in de eerste orde logica.
Ook zijn de precieze definitie van termen en formules aan bod gekomen.
(Ls 2.3.1 en 2.3.2). Er is gesproken over gebonden en vrije variabelen
van formules. In Ls hebben we dus behandeld paragraaf 2.3.1 en het
begin van 2.3.3.
Week 6 maandag 3-12-01
(Zaalwijziging T1 123)
We hebben nog even een aantal formele syntactische notie's behandeld.
Substitutie hebben we niet formeel gedefinieerd zoals dat in Ls 2.3.9 en 2.3.10
gebeurd. Wel hebben we besproken wat deze definitie's willen zeggen en
waar substitutie op neer komt. Ditzelfde geldt voor de drieplaatsige relatie
t is vrij voor x in A.
(Ls 2.3.12 en 2.3.13). We hebben de uitgebreide taal geintroduceerd door voor ieder
element in het domein een constante aan de taal toe te voegen. (cf Ls 2.3.16)
We hebben bekeken wat een model M voor een taal L precies is. De interpretatie
van een relatie in een model is precies de verzameling van de instantie's in dat model.
Dit is paragraaf 2.2 in Ls. We hebben de definitie van |= gegeven in de geest van
Tarski. Merk op dat dit in Ls een lemma is, (lemma 2.4.5 ) omdat daar met
een iets andere waarheids definitie wordt gewerkt. Verder hebben we gedefinieerd:
M |= A
|= A
M |= V (hier is V een zinsverzameling)
|= V (hier is V een zinsverzameling)
V |= A (hier is V een zinsverzameling)
We hebben als voorbeeld van redeneren met deze waarheids definitie gezien, stelling
2.5.1 uit Ls.
Vervolgens hebben we natuurlijke deductie voor predicatenlogica ingevoerd.
Dit was hetzelfde als natuurlijke deductie voor propositielogica
met vier nieuwe regels erbij. Introductie en eliminatie voor zowel de existentiele
als de universele
kwantor. In Ls wordt in eerste instantie alleen de universele kwantor behandeld in
2.8, maar in 2.9 worden ook de existentiele kwantor regels gegeven.
Week 6 woensdag 5-12-01
(Zaalwijziging T1 123)
In het laatste college hebben we de relatie tussen de notie's van
afleidbaarheid en waarheid verder onderzocht. Waar afleidbaarheid een
existentiele uitspraak is (er is een derivatie...) is semantische
geldigheid universeel van aard. (Voor alle modellen...) We hebben
nagedacht over hoe een universele uitspraak uberhaupt aangetoond kan
worden en kwamen met vijf mogelijkheden.
1.) Alle mogelijkheden proberen. (Eindige domeinen.)
2.) Via de structuur van het domein, bijvoorbeeld formule inductie.
3.) Generalisatie, dus als A(x) wordt ingezien zonder aannamen over x.
4.) RAA.
5.) Via een gerelateerde uitspraak liefst van een van de voorgaande vormen.
We hebben ook gezien hoe de BHK interpretatie een "guide-line" kan zijn
om wel of niet RAA te gaan gebruiken. Al deze metabeschouwingen kunnen
gebruikt worden in de praktijk. Wij hebben ze ook toegepast bij het zoeken
naar bewijzen.
Het laatste deel van het college gaf een algemene inleiding tot de inhoud
van het vak logische technieken dat ik in blok vier zal geven. We hebben
gesproken over de volledigheidsstelling voor predicatenlogica en hoe deze
zich verhoudt tot de eerste onvolledigheidsstelling. Verder hebben we gesproken
over Peano Rekenkunde en hoe PA over haar eigen "bewijsbaarheidsgedrag" kan
spreken en wat PA wel en niet ziet. We hebben gezien hoe er een link was met
modale logica. L"ob's stelling is geformuleerd en we hebben gezien hoe
Goedel's tweede onvolledigheidsstelling uit deze stelling volgt.
L"ob zegt dat
PA |- A indien PA |- ([]B --> B).
Als we voor B falsum substitueren dan krijgen we inderdaad Goedels tweede
onvolledigheidsstelling
Als PA consistent dan bewijst zij haar
eigen consistentie niet, i.e., PA bewijst "not [] falsum" niet.
De deductiestelling geeft dus dat PA + []falsum consstent is en dus
wegens de volledigheidsstelling voor predicatenlogica heeft het een model.
We hebben gezien hoe zo'n (non standaard) bewijs van falsum er uit zou kunnen
zien in zo'n model.
Oefenopgaven week 6
[
Postscript|
Pdf formaat]
In het werkcollege is behandeld: van week 5, het huiswerk en van week 6 de sommen
4 (1 t/m 4) en 5 (1 t/m 2).
De suggestie is om het proeftentamen bijvoorbeeld op maandag pas te maken en
dan ook kijken of het in drie en een half uur lukt. (Het proeftentamen is
een beetje meer dan het gewone tentamen, maar kwa moeilijkheid we
enigzins representatief, vanddar ook drie en een half uur in plaats van drie
uur.) Houdt ook vooral deze pagina in de gaten.
Week 7 woensdag 12-12-01
Vragenuur van Marijn Zwitserlood. Bespreking proeftentamen.
(Zaal T1 123)
(Tijd 13:00-15:00)
Proeftentamen
[
Postscript|
Pdf formaat]
Week 8 maandag 17-12-01
(Zaal 465)
(Tijd 15:00-17:00)
Vragenuur van Joost Joosten.
Week 8 woensdag 19-12-01
(Zaal Tr1 114)
(Tijd 9:00-12:00)
Tentamen.
Tentamen
[
Postscript|
Pdf formaat]
Tentamenuitslagen
[
Postscript|
Pdf formaat]
Nogmaals, het eindcijfer wordt bepaald door twee onderdelen. Het tentamen bij
Joost Joosten en een paper bij Albert Visser. Er kan ook voor gekozen worden
om een van beide onderdelen niet te doen. Hier wordt dan een nul voor gerekend.
Vraag en antwoord
Vraag
Beste Joost Hoewel ik braaf naar de colleges ben geweest, en recentelijk
Logica I heb gevolgd, moet mij van het hart, dat ik de grootste moeite
heb met het boek van van Dalen, met name de wiskundige Engelse taal, kost
mij nog eens extra veel werk. Woorden als "sequence"zie ik voor het
eerst een "formation sequence"zal wel een rekenkundige reeks zijn, maar
er kan ook bedoeld zijn een of andere vorm van een opeenvolgende reeks
(een beetje dubbelop lijkt me) blz. 11: hier zijn enkele voorbeelden van
definitie "by recursing" een repeterende breuk is "recurring", vloeken is
"to curse"maar wat met "recursion"wordt bedoeld is mij niet duidelijk.
"parsing" staat voor "ontledende" enz. enz.
Antwoord
Ik begrijp je probleem erg goed. Naast dat er conceptueel een boel wordt
behandeld wordt er eigenlijk ook een nieuwe taal geintroduceerd.
En die nieuwe taal speelt zich deels af binnen de wiskundige taal
maar ook in het Nederlands en in het boek dus in het Engels.
Ik kan het je dan ook zeker aanraden om mij bij twijfels te raadplegen.
Recursion: ook in het Nederlands kennen wij dit woord, recursie.
Wat in Ls een "definition by recursion" wordt genoemd, noemen
wij in het college vaak een inductieve definitie. Dit zijn dus
dezelfde begrippen. Het recurrende, zit hem er in dat
om te controleren of iets in een verzameling zit moet je kijken of de
kleinere delen er in zitten.
Sequence: is inderdaad hier een rijtje.
Formation sequence: dit is niet een standaard begrip, maar dit
wordt juist in definitie 1.4.1. gedefinieerd. Er volgt dan een
ingewikkelde definitie. Als je er wat langer naar kijkt blijkt er
gewoon te staan dat een "formatie rijtje" bestaat uit
propositie variabelen en uit complexere formules waarbij alle "delen"
van die complexere formule al eerder in het rijtje voorkomen.
Parsing: heeft te maken met de struktuur van een formule te bepalen.
In het college heb ik het vaak over het "connectief op het hoogste
nivo". Zo is ( A /\ B ) --> A op het hoogste nivo een implicatie.
Het antecedent is weer een conjunctie. Zo'n structuur analyse heet
"parseren".
Wat betreft de tussentoets kan ik aanraden om veel sommen te maken.
Ook het lijstje met kernbegrippen dat ik onder week 4 heb geplaatst
is aanbevolen lectuur.
Succes,
Joost
Vraag
Ik heb [na veel informatie] nog steeds niet helemaal een duidelijk
begrip
van wat een formeel systeem is en hoe ik vele andere termen daaromtrent
moet
categoriseren. Daarom hieronder een aantal vragen.
Is natuurlijke deductie een formeel systeem? Of is ND de basis van alle
formele systemen? Wat is het verschil tussen natuurlijke deductie [=
formeel
bewijssysteem?] en formele systemen? [Het verschil tussen een paard en
een
zoogdier...]
Bepaalt een axioma-stelsel het formele systeem? Of bepalen de logische
regels het formele systeem? Hoe dit in onderscheid met het deductieve
systeem te begrijpen?
Antwoord
Het systeem van natuurlijke deductie is tot dusverre het enige formele
systeem wat wij hebben gezien. Het is niet zo dat ND in ieder
formeel systeem is bevat. Maar in zekere zin is dit wel
wenselijk dat het een deel van ND bevat om over logische
gevolgtrekkingen te kunnen spreken. Maar dit hoeft niet per se in ND.
Een formeel systeem kan ook over heel iets
anders gaan dan basis propositie's,
bijvoorbeeld algebra. Een formeel systeem wordt door
drie zaken gekarakteriseerd, een taal, axioma's en regels. De taal
zegt je waar je over kunt praten. In het geval van ND zijn dat dus
formules die samengesteld zijn uit propositievariabelen. Er zijn in
ND geen axioma's alleen maar een boel regels. We zouden eventueel
onze afkortingen kunnen zien als axioma's. Die zeggen dan bv,
not A --> (A --> falsum ), en
(A --> falsum ) --> not A.
In de taal van ND kunnen we nog niet over bijvoorbeeld punten en lijnen
spreken. Andere formele systemen zijn bijvoorbeeld, algebra (denk aan
haakjes wegwerken),
meetkunde of predikatenlogica. Formele systemen worden ook wel
theorieen genoemd.
Vraag
Is algebra zelf [al] een [semi?]formeel systeem of is het een onderdeel
van
een formeel systeem?
Is de mathematische logica een formeel systeem?
Ik meen dat rekenkunde geen formeel systeem is, wat maakt dat het
geformaliseerd kan worden?
Antwoord
Het hangt er natuurlijk van af wat je bedoelt met algebra. Maar we kunnen
denken aan een formeel systeem dat algebra heet. De taal hiervan
zal variabelen voor getallen bevatten, constanten, zoals 0 en 1
en functies zoals + en *, en predicaten zoals = en <.
Verder zijn er azioma's gegeven. Hierin zitten bv
axioma's over het wegwerken van haakjes, maar het moet ook een minimale
hoeveelheid logica bevatten. Het zou dus wenselijk kunnen zijn om ND als
een subsysteem te zien. (Alleen zullen nu de zgn atomaire zinnen zoals bv
x < y de rol van propositievariabelen vervullen.)
Mathematische logica is meestal een verzamelnaam voor alle
activiteiten die zich in dit gebied en aan de rand daarvan afspelen en
is op zich dus nog geen formeel systeem. Verschillende delen van de
mathematische logica gebruiken bijvoorbeeld al een verschillende taal.
Deze twee opmerkingen gelden ook min of meer voor rekenkunde. In
de wiskunde gebruikt men vrijelijk allerlei soorten technieken door elkaar
heen zonder precies bij te houden wat er gebruikt wordt.
In de wiskundige logica bestaat er ook zo iets als rekenkunde. Nu
als formeel systeem. Dus wordt heel precies de taal vastgelegd (vrijwel
altijd eerste orde) en de axioma's. Als we het over rekenkunde hebben
zal er dus in zekere mate ook inductie in het axiomastelsel
zijn opgenomen. Dit brengt ons direct tot de volgende vraag.
Vraag
Is de methode van inductie een formeel systeem, of kunnen we via
inductie
uitspraken over formele systemen doen? Of kunnen we via deductie [als
zijnde
formeel bewijssysteem?] uitspraken doen over een formeel systeem [welk?]
Antwoord
We moeten oppassen dat we de woorden inductie en deductie niet
verwarren maar we hebben hier een heel erg goede en belangrijke vraag
aan de hand. Het brengt ons precies tot het onderscheid tussen het
redeneren binnen een formeel systeem (de toegestane regeltjes
toepassen) en op metaniveau. Bijvoorbeeld in de rekenkunde
(dit hebben we nog niet behandeld en valt ook enigzins buiten het bestek
van dit college) hebben we inductie axioma's. In het systeem zelf
kunnen we dus inductie toepassen. Maar vaak vindt inductief redeneren
ook op een meta niveau plaats. Dus inderdaad redeneren over een formeel
systeem. Een typisch voorbeeld hiervan hebben wij gezien in opgave
8 van week twee. Hier is overigens een uitgebreide uitwerking van te vinden
in week drie.
Vraag
Hoe moet ik de begrippen semantiek en syntax plaatsen bij een formeel
systeem?
Een formeel systeem werkt op de vorm van de symbolen, dus syntax bepaalt
werking [als symboolmanipulator als zijnde genererende operatoren]?
Wat doet een formeel systeem [de functie ervan] in onderscheid met de
functie van syntax? Wordt er een taak uitgevoerd, of vormt het een
raamwerk
waarbinnen taken uitgevoerd kunnen worden.Wat is de toevoeging aan een
systeem als het een formeel systeem is? Heeft het een representerende
functie of is het een voertuig van de symbolen die gemanipuleerd
worden,
via welke het mogelijk is.
Antwoord
Een formeel systeem, ofwel een theorie, speelt zich af op het nivo van
syntax. Maar ja, dan moet je in de meta-logica wel genoeg hebben om deze
syntax tot je beschikking te hebben. Ik denk dat we hier ook
langzamerhand een gebied beginnen te betreden waar de meningen
meer uiteenlopen. Wellicht zijn dit ook goede punten voor de
werkgroep.
Vraag
Is formaliseren zonder verzamelingenleer mogelijk?...
Antwoord
Deze vraag volgt inderdaad logisch oop de vorige. Er zijn
funderingen van de wiskunde die heten niet met verzamelingen
te werken zoals bijvoorbeeld de lambda-calculus of de categorieen
theorie, maar waar leeft dan je syntax? Ik ben dan ook geneigd om
te zeggen dat we niet zonder verzamelingen kunnen.
Vraag
Als het axioma-stelsel voor de rekenkunde van Peano formeel wordt
weergegeven in de Principia Mathematica van Russell en Whitehead, wat
gebeurt er dan tijdens het formaliseren nog eens met de axiomas die
Peano
heeft gestelt? [axiomas zijn toch onderdeel van een formeel systeem?
Axioma
s axiomatiseren? Peano's formele beschrijving van het telproces nog
eens
formaliseren of is het een kwestie slechts herformuleren?]
Antwoord
De axioma,s van Peano zijn in zekere zin gewoon opgenomen in
de Principia Mathematica. Zij maken dus deel uit van dit
formele systeem. Wel moet er bijvoorbeeld worden gesteld dat
natuurlijke inductie alleen op getallen wordt toegepast.
De grootste verdienste van de PM was om een systeem te formuleren
waarin de Russel paradox niet meer viel te formuleren door alle
objecten te typeren. Een verzameling is dan van een hoger type
dan al zijn objecten. Zodoende kan een verzameling nooit een element
van zichzelf zijn.
Vraag
Voor
de
precisie over genererende operatoren: jij zei, volgens mij dat
kinderen
krijgen een genererende operator was. Maar, voor de precisie, is dat
niet
het resultaat van het kinderen maken, welke dan de [echte] genererende
operator vormt.
M.a.w. A, B ---- met genererende operator Ù ---- heeft als resultaat AÙB
of
is AÙB in zn geheel de genererende operator, volgens jou?
Antwoord
In zekere zin heb je gelijk. Het is maar hoe precies je naar het proces
wilt kijken. Het systeem dat wij in de klas gebruikte maakte hier
gelukkig geen ondescheid tussen. Dit is dus meer een kwestie van hoe
precies je
de werkelijkheid wilt modelleren.
Vraag
Wat kunnen we in het tentamen verwachten?
Antwoord
Ik ben van plan om het tentamen te laten bestaan uit een zestal vragen.
1. ) Natuurlijke deductie propositie logica
2.) Natuurlijke deductie predicaten logica
3.) Kripke semantiek
4.) Maximaal consistente verzamelingen en technieken uit de volledig- en correct-
heidsstellingen.
5.) Kennis vragen over bv Goedel's stellingen.
6.) Varia zoals conjunctieve normaal vormen en om niet te vergeten: inductie.
Vraag
ik vertel het maar de symbolen zijn wat moeizaam: in het bewijs
A of niet A ga je via RAA naar falsum, je neemt dan
--(A of niet A) aan, dit kan je omzetten in niet A en A ; en
eliminatie links geeft niet A, en eliminatie rechts geeft A,
samen geeft dat falsum qed, het "bewijs"is dan m.i. simpeler dan
zoals jij het hebt gegeven, maar ik weet niet of het geoorloofd
is.
Antwoord
Een bewijs met natuurlijke inductie mag alleen maar de stapjes gebruiken
die gegeven zijn. Anders is het simpelweg geen bewijs!! Dan is het
gewoon in symbolen weergeven wat je gedachten zijn. Dus de vraag is
of van
not (B \/ C )
naar
not B /\ not C
gaan een regel is. En dit is niet zo. We zouden het natuurlijk als regel kunnen
toevoegen maar zolang we dat niet hebben gedaan, en we hebben het niet gedaan,
kun je die stap dus ook niet maken.
Vraag
Een ander geval: opgave 4 sommetje 2 van week 6: Bewijs Alle x
fi(x) dan niet alle x niet fi(x) ; dat laatste kan je ook heel
gemakkelijk schrijven als: er is een x fi(x), dan loopt het
bewijs super simpel zonder falsum, is dat geoorloofd?
Antwoord
NEE!!!!! Nogmaals: in een deductieve derivatie moet ieder stapje
een officlieel stapje zijn, dus ofwel
Een aanname
/\ Introductie
/\ Eliminatie links
/\ Eliminatie rechts
\/ Introductie links
\/ Introductie rechts
\/ Eliminatie
--> Introductie
--> Eliminatie
falsum regel
RAA
existentiele kwantor Introductie
existentiele kwantor Eliminatie
universele kwantor Introductie
universele kwantor Eliminatie
Je mag dus echt niets maar dan ook niets meer dan dit gebruiken. Iedere stap
die jij dus voorstelt moet je dus uitschrijven als het resultaat van deze kleine
stapjes.
Het tentamen duurt drie uur in totaal dus per vraag is er zo'n 25 minuten.
Joost Joosten
Last modified: Mon Jul 1 13:07:51 MET DST 2002