| Kursusnavn (dansk): | Logik og beregnelighed |
| Kursusnavn (engelsk): | Logic and Computability |
| Semester: | Forår 2002 |
| Udbydes under: | cand.it., internet- og softwareteknologi (int) |
| Omfang i ECTS: | 7,50 |
| Kursussprog: | Engelsk |
| Kursushjemmeside: | https://learnit.itu.dk |
| Min. antal deltagere: | 5 |
| Forventet antal deltagere: | 0 |
| Maks. antal deltagere: | 40 |
| Formelle forudsætninger: | The students should be able to
- work with sets and functions
- work with integer and real numbers
- perform mathematical proofs
|
| Læringsmål: | After the course the student will be able to:
- verify validity of propositional and 1st order formulas
- prove completeness theorems for propositional and 1st order logic
- work with models of 1st order languages and 1st order theories
- construct models with prescribed properties
- apply quantifier elimination techniques
- distinguish between decidable and undecidable problems
- construct key examples of sets and functions with extremal
algorithmic properties
- evaluate the complexity of algorithmic problems
|
| Fagligt indhold: | The subject of logic is inspired by questions of some generality:
What is the relation between the language of mayhematical science and the
objects it talks about?
How adequate are our methods of gaining mathematical knowledge?
Is my computer better than yours?
Mathematical logic attempts to answer these questions while remaining an exact
science.
This course will offer a reasonably comprehensive introduction to topics
and methods of the subject. In particular, we intend to cover the
following topics:
- basic logical calculi;
- models and theories;
- elements of recursion theory;
- G"odel incompleteness.
|
| Læringsaktiviteter: | Lectures 3 x 45 minutes a week and exercise classes
3 x 45 minutes. |
| Eksamensform og -beskrivelse: | X. experimental examination form (7-scale; external exam), 13-skala, Intern censur During the course there will be given a set of hand-in exercises which will be graded with a score. A sufficient total score for the hand-in exercises is a prerequisite to be admitted to the exam.
There will be a 30 minutes individual oral exam without preparation, graded on the 13-scale. The course material will be available at the exam. External censor.
|
| Litteratur udover forskningsartikler: | The course will be based on notes, handed out during the course. The following books contains most of the material covered
- J.L.Bell & M.Machover. A Course in Mathematical Logic. (North-Holland 1977)
- C.C.Chang & H.J.Keisler. Model Theory. 3rd ed. (North-Holland 1990)
- P.Odifreddi. Classical Recursion Theory. (North-Holland 1989)
- J.R.Shoenfield. Mathematical Logic (Addison-Wesley 1967; reprinted
A K Peters / Association for Symbolic Logic 2001)
|
| | |
Kursusoversigt