Logikk og Bevisstrukturer
Denne siden inneholder følgende overskrifter:
Innhold
Undervisningen
Forelesningsplan
Antikronologisk liste over forelesninger og oppgaver
Eksamensopplysninger
Innhold
Dette 4-vektallsemnet er en innføring i matematisk logikk. Når man studerer vektorrom i stedet for reelle vektorer i to eller tre dimensjoner, eller når man studerer grupper i stedet for forskjellige symetrier i planet, foretar man abstraksjoner. En måte å oppfatte matematisk logikk på er at vi studerer slike abstraksjoner på et generelt grunnlag, vi abstraherer det som er felles ved abstraksjonene.
MA 250 gir en innføring i utsagnslogikk og første ordens logikk. Vi lager en matematisk modell for en del av den matematiske praksis ved at vi formaliserer begreper som matematisk utsagn og bevis. Vi etablerer sammenhengen mellom disse formelle utsagnene, den formelle teorien og den virkelighetsoppfatning normale matematikere vil ha. Dette kalles sunnhet av den logiske teorien.
I denne korte introduksjonen trekker vi frem bare to av de sentrale resultatene.
Kompletthetsteoremet sier at alle utsagn som er generelt sanne ut fra en mer ovenfra betraktning faktisk vil være bevisbare i de formelle systemene vi studerer.
Ufullstendighetsteoremet sier at systemene våre ikke vil være sterke nok til å fange opp sannhet over en spesiell matematisk struktur som de naturlige tallene. Spissformulert viser vi at tallteori faktisk ikke lar seg formalisere slik at alle mulige matematiske erkjennelser fanges opp.
Undervisningen
Pensum tar utgangspunkt i et eget kompendium:
Fenstad og Normann INNFØRING I MATEMATISK LOGIKK, 3. utgave (1990).
Dette kompendiet er nå lovet fra trykkeriet 21/1-03
I utgangspunktet er hele kompendiet pensum.
Som en forberedelse til neste års omlegging av undervisningen, vil vi bruke boken A friendly Introduction to Mathematical Logic av Christopher C. Leary for de delene av pensumet som er dekket av boken. Denne boken er utgitt på Prentice Hall.
Det undervises to dobbeltimer pr. uke, forelesninger og oppgaveregning litt om hverandre.
Mandag og tirsdag 12.15 - 14.00 i seminarrom B 62, NHA.
Se forelesningskatalogen for start-tidspunkt.
Foreleser og sideansvarlig er Dag Normann, dnormann@math.uio.no, B 828, interntelefon 55953.
Uforpliktende forelesningsplan
FN := Fenstad og Normann Innføring i logikk 3. utgave
L := Christopher C. Leary A Friendly Introduction to Mathematical Logic
20/1 - 04/2 - FN Kapittel 1
10/1 - 25/2 - L Chapter 1
03/3 - 18/3 - L Chapter 2
24/3 - 01/4 - L Chapter 3
07/4 - 08/4 - FN Avsnitt 4.5
PÅSKE
28/4 - 13/5 - L Chapter 4
19/5 - 27/5 - L Chapter 5
02/6 - 03/6 - Repetisjon
PINSE
11/6 - EKSAMEN
Forelesninger og oppgaver
Her vil jeg fortløpende orientere om den planlagde fremdriften i forelesningene og om hvilke oppgaver jeg planlegger å gjennomføre.
Informasjonen vil bli gitt antikronologisk, det vil si at den eldste informasjonen står nederst. Jeg daterer hvert avsnitt med datoen jeg skriver det. Normalt vil et avsnitt inneholde informasjon om hva jeg planlegger å snakke om påfølgende uke og hvilke oppgaver jeg gir til uken etter der igjen.
27.05.03
Mandag 2/6, tirsdag 3/6 og tirsdag 10/6 skal vi gå igjennom eksamensettene fra 1993 og 1997.
3/6 avslutter vi etter en time, på grunn av utdelingen av Abelprisen.
23.05.03
Mandag 26/5 skal vi fullføre beviset for Gödels ufullstendighetsteorem.
Når vi betrakter oss som ferdige med å gjennomgå pensum, vil vi fortsette med å regne oppgaver.
Tirsdag 27/5 diskuterer vi hvordan vi legger opp resten av undervisningstiden frem til eksamen. Det blir tid for repetisjon og mer oppgaveregning.
16.05.03
Mandag 19/5 skal vi se på Gödel-nummerering, og på hvordan vi kan oversette substitusjon til rekursive funksjoner på Gödeltall, og komme så langt som rimelig er. Neste uke vil vi trolig bli ferdige med pensum.
Oppgaver til neste uke:
Eksamen 15/6-92, hele settet.
09.05.03
Mandag 12/5 skal vi etter avtale definere de μ-rekursive funksjonene, og vise at alle μ-rekursive funksjoner er representerbare.
Etableringen av noen av egenskapene til de μ-rekursive funksjonene vil være repetisjon av de egenskapene vi viste for Δ-mengder, og vil bli gitt som oppgaver til neste uke.
Vi kommer til å vise at de μ-rekursive funksjonene er lukket under det som heter primitiv rekursjon. Dette vil gjøre noen av resonementene rundt Gödelnummereringen enklere enn slik Leary fremstiller dem.
Siktemålet er å dekke stoffet i Leary frem til og med avsnitt 4.10 på en litt fri måte.
Oppgaver til neste uke:
Bevis Lemmaene 5.3.4 og og 5.3.5 fra Fenstad og Normann.
Fullfør eksamen 14/6-01, oppgaver 1 - 4, og fortsett med eksamen 14/6-02 hele settet.
02.05.03
Mandag 5/5 skal vi starte på kapittel 4 i boka til Leary. Jeg tar sikte på å gå igjennom avsnittene 4.1 - 4.6.
Avsnitt 4.4 er rent lesestoff uten noe skikkelig teoretisk innhold, og det vil jeg forbigå i nesten taushet.
Jeg vil bruke betegnelsen representerbarhet der boka bruker recursive, ikke fordi det er en riktig oversettelse til norsk, men fordi det historisk sett er riktig terminologi.
Oppgaver til neste uke:
Leary:
Avsnitt 4.3, oppgaver 1, 2, 3, 4 og 6.
Avsnitt 4.6 oppgave 1.
Eksamen 14/6-01, oppgaver 1 - 4.
25.04.03
Mandag 28/4 skal vi fullføre Herbrands analyse av bevisbarhet. Deretter skal vi gå igjennom beviset i avsnitt 5.2 om avgjørbarhet av teorien for likhet.
Oppgaver til neste uke: Oppgavene er fra Fenstad og Normanns kompendium.
Avsnitt 4.5 oppgave 10
Avsnitt 5.2 oppgaver 1, 2 og 3.
Jeg antar i skrivende stund at det vil være nok igjen av eksamensoppgavesettet fra 1994 til at vi har nok å gjøre med å bli ferdige med det.
04.04.03
Mandag 7/4 henter vi stoffet fra Fenstad og Normanns kompendium.
Vi skal prøve å komme igjennom avsnitt 3.4 om preneksoperasjoner og avsnitt 4.5 om Herbrandteori.
Oppgaver til etter påske: Oppgavene er fra Fenstad og Normann.
Avsnitt 3.4, oppgaver 1, 2 og 3.
Avsnitt 4.5, oppgaver 1, 2, 3 og 4.
I tillegg vil vi se på eksamensoppgavene i MA 231 fra 13/6-94, vi vil gå igjennom alle oppgavene etterhvert som vi rekker det.
28.03.03
Mandag 31/3 vil jeg starte med en oppsummering av beviset for komletthetsteoremet. Deretter beviser vi kompakthetsteoremet og gir noen anvendelser.
I den andre timen vil vi se på elementære delstrukturer og beviset for Löwenheim-Skolems teorem, versjon nedover. Hvis vi (mot formodning) rekker noe mer, skal vi se på den ikke-tellbare versjonen av kompletthetsteoremet.
Oppgaver til neste uke:
Avsnitt 3.3 oppgaver 1, 3, 4, 5, 8c og d, 9 og 10.
Avsnitt 3.4 oppgaver 1, 2, 3 og 4.
21.03.03
Mandag 24/3 går vi igjennom avsnittene 3.1 og 3.2 i Leary, det vil si at vi beviser kompletthetsteoremet for tellbare språk.
Jeg kommer til å basere meg på fremstillingen i boka, men stokke litt om på rekkefølgen vi gjør ting i.
Oppgaver til neste uke:
Vi kommer til å gå igjennom alle oppgavene under avsnitt 3.2. Noen av dem vil være repetisjon av det jeg sier på forelesningen, andre vil representere detaljer jeg har utelatt.
I praksis blir den oppgavegjennomgåelsen en repetisjon/utdyping av beviset for kompletthetsteoremet.
14.03.03
Mandag 17/3 går jeg igjennom avsnitt 2.8 om ikke-logiske aksiomer.
Vi skal se på noen eksempler på hvordan vi kan formulere kjente teorier fra algebra og tallteori som første ordens logikker.
Hvis det blir tid, skal vi se litt på en skisse av beviset for kompletthetsteoremet. Det beviset skal vi ta skikkelig neste uke.
Tirsdag kan bli litt amputert, ettersom jeg er innkalt til et seminar i forbindelse med kvalitetsreformen fra kl. 13.15 av.
Jeg gir litt få oppgaver til uken etter, og vi får drøfte hva vi vil gjøre.
Oppgaver til neste uke:
Avsnitt 2.8, oppgaver 4, 5, 6, 7 og 8.
I oppgave 5 vil det være punktene 6 og 7 som står til rest etter mandagens forelesning.
07.03.03
Mandag 10/3 satser jeg på å gå igjennom avsnittene 2.5, 2.6 og 2.7.
I avsnitt 2.5, viser vi sunnhet av logikken, det vil si at vi ikke kan gi formelle bevis for formler som ikke er gyldige.
I avsnitt 2.6 beviser vi to kjedelige lemmaer, hvor den store utfordringen er å forstå formuleringen av dem.
I avsnitt 2.6 beviser vi deduksjonsteoremet for første ordens logikk, som sier at setninger kan spille samme rolle som logiske aksiomer i en teori og premisser i en implikasjon.
Tirsdag 11/3 blir det ingen oppgaveregning, ettersom jeg er på et heldagsmøte i forbindelse med kvalitetsreformen.
Oppgaver til neste uke:
Avsnitt 2.2 oppgaver 1 og 4.
Avsnitt 2.4 oppgaver 1, 2 og 5.
Avsnitt 2.5 oppgaver 1 og 4.
Avsnitt 2.7 oppgaver 1, 3, 4, 5, 6 og 7.
27.02.03
Mandag 3/3 begynner vi på kapittel 2 i Leary. Den naturlige stoppen er mellom avsnittene 2.4 og 2.5, og jeg vil nå så langt før vi begynner på oppgavene.
Oppgaver neste uke. Neste tirsdag (11/3) er jeg borte på et heldagseminar om kvalitetsreformen. Relevante oppgaver fra L. fra det som skal gjennomgåes denne uken er:
Avsnitt 2.2 oppgaver 1 og 4.
Avsnitt 2.4 oppgaver 1, 2 og 5.
Disse vil vi se på uken etter.
21.02.03
Mandag 24/2 vil vi repetere det vi har sagt om første ordens språk og strukturer. Vi skal illustrere problemet med å avgjøre hva som er logiske konsekvenser og ikke ved et eksempel om binære tall og binære sekvenser, et eksempel jeg med vilje ikke har tenkt igjennom svaret på.
Vi vil gå igjennom avsnittet om substitusjon og substituerbarhet, og utdype det som er sagt om logisk konsekvens og logisk gyldighet.
Tirsdag 11/3 blir det trolig ingen oppgaveregning, ettersom jeg er innkalt av rektor og direktør til et heldagseminar om den nye studieordningen.
Oppgaver til neste uke: Alle oppgaver er fra L.
Avsnitt 1.7 oppgave 5.
Avsnitt 1.8 oppgaver 1, 2, 3, 4, 5 og 6.
Avsnitt 1.9 oppgaver 1, 2, 3 og 4.
14.02.03
Mandag 17/2 vil vi ta for oss avsnittene 1.6 og 1.7 i Leary. Disse henger så nøye sammen at vi fullfører gjennomgangen selv om vi må bruke litt av tirsdagen.
Oppgaver til neste uke: Alle oppgavene er fra L.
Avsnitt 1.5 oppgaver 1, 2, 3, 4, 5 og 6.
Avsnitt 1.6 oppgaver 1, 5 og 7.
Avsnitt 1.7 oppgaver 1, 3, 4 og 7.
06.02.03
Mandag10/2 begynner vi på første ordens språk og første ordens teorier.
Jeg vil forelese med utgangspunkt i boka til Leary, og tar sikte på å dekke avsnittene 1.1 - 1.5.
Avsnitt 1.4 om induksjon er for en stor del lesestoff, ettersom jeg regner med at studentene kjenner til induksjonsbevis fra før. Vi vil imidlertid se på et par av de relevante anvendelsene beskrevet i avsnittet.
Oppgaver til neste uke: Alle oppgavene er fra L.
Avsnitt 1.2 oppgaver 2, 4, 5 og 6.
Avsnitt 1.3 oppgaver 3 og 4.
Avsnitt 1.4 oppgaver 4, 7 og 8.
31.01.03
Mandag 3/2 sluttfører vi beviset for kompletthetsteoremet for utsagnslogikk og viser hvordan vi kan analysere utsagn på svak normalform.
Deretter går vi igjennom avsnitt 1.7 om klausaler og Horn-klausaler. Jeg velger å ikke snakke om kompletthetsteoremet for Horn-klausaler.
Når vi er ferdige med det, tar vi fatt på oppgavene.
Oppgaver til neste uke: Alle oppgavene er fra FN.
Avsnitt 1.6 oppgaver 3 og 5.
Avsnitt 1.7 oppgaver 1 og 2.
24.01.03
Mandag 27/1 nøster vi først opp noen løse tråder fra forrige uke, og deretter starter vi på avsnitt 1.6 om bevis-systemer.
Når vi har vist kompletthetsteoremet for utsagnslogikk (sent mandag eller tidlig tirsdag) går vi over til å gjennomgå oppgaver.
Siste delen av avsnitt 1.6, samt avsnitt 1.7 planlegges for uken etter.
Oppgaver til neste uke Alle oppgavene er fra FN.
Avsnitt 1.4, oppgaver 6, 7, 8, 9 og 10.
Avsnitt 1.5, oppgaver 1 og 2.
Avsnitt 1.6, oppgaver 1 og 2.
17.01.03
Mandag 20/1 tar vi for oss avsnittene 1.1 og 1.2 i FN. Vi ser på motivasjonen for å studere logikk, hva vi ønsker å oppnå og hva vi ikke ønsker å oppnå, forholdet mellom formelle og uformelle språk og vi gir en definisjon av språket for utsagnslogikk og av hvordan utsagnene kan tolkes som sannhetsverdifunksjoner.
Tirsdag 21/1 tar vi for oss avsnittene 1.3 og 1.4 i FN. Vi ser på begreper som tautologi og ekvivalens, men vil legge mest vekt på beviset for at alle sannhetsverdifunksjoner kan uttrykkes ved hjelp av negasjon, konjunksjon og disjunksjon, og de normalformsteoremene vi kan trekke ut av det.
Vi får trolig også tid til å se på avsnitt 1.5 om metoder for å avgjøre om et utsagn er en tautologi, en kontradiksjon eller ingen av delene. Disse metodene virker ofte ganske raskt, men ikke alltid.
Oppgaver til tirsdag 28/1:
Avsnitt 1.2 oppgaver 2 og 3.
Avsnitt 1.3 oppgaver 1, 2, 6, 7 og 8.
Avsnitt 1.4 Oppgaver 1, 2, 3 og 4.
Eksamen
Eksamen er skriftlig og på seks timer. Eksamensdato 11/6-03.
Utkast til løsninger finnes i postscript-format og i pdf-format.
Denne siden er redigert av Dag Normann, Matematisk Institutt.
Sist oppdatert 11 - 06 - 03
Tilbake til toppen.