Section outline
-
ΠεριγραφήΔιαλέξεις: Τρίτη 17:15-19:00 και Τετάρτη 12:45-14:30, στην αίθουσα 13 των νέων κτ. ΗΜΜΥ
Η πρώτη διάλεξη για το εαρινό εξάμηνο του 2025 θα γίνει την Τρίτη 11 Φεβρουαρίου, 17:15.
Διδάσκοντες: Γιώργος Κολέτσος, Πέτρος ΠοτίκαςΠεριεχόμενο Μαθήματος/Διδακτέα Ύλη
Προτασιακός Λογισμός: Γλώσσα, Μοναδική αναγνωσιμότητα, Λογικοί σύνδεσμοι, απονομές αλήθειας, σημασιολογικές έννοιες, επάρκεια συνδέσμων, διαζευκτική και συζευκτική κανονική μορφή, θεώρημα συμπάγειας προτασιακού λογισμού, εφαρμογές.
Πρωτοβάθμιος κατηγορηματικός λογισμός: Γλώσσα, μεταβλητές, έννοιες ελεύθερης και δεσμευμένης μεταβλητής, αντικατάσταση, αναλογία με τον προγραμματισμό, η έννοια της δομής, ερμηνεία της γλώσσας, ορισμός της αλήθειας κατά Tarski.
Αξιωματικοποίηση της πρωτοβάθμιας Λογικής: Η έννοια του αξιωματικού συστήματος, Τυπικά αξιωματικά συστήματα τύπου Hilbert και Gentzen, Μοντέλα θεωριών, η έννοια της συνέπειας και τα θεωρήματα της ορθότητας και πληρότητας του Gödel, τα θεωρήματα συμπάγειας και Löwenheim-Skolem, εφαρμογές.
Υπολογισιμότητα και μή-πληρότητα: Αναλογίες με αλγοριθμικές έννοιες, Αποκρισιμότητα, το Entscheidungsproblem του Hilbert, Εισαγωγή στη θεωρία αναδρομικών συναρτήσεων, το αίτημα του Church, Το θεώρημα μη-πληρότητας του Gödel και της αναποκρισιμότητας των Gödel-Church.
Βιβλίο μαθήματος:
ΕργασίεςΣτην ενότητα 'Ασκήσεις' αναρτώνται σειρές ασκήσεων κάθε μία εβδομάδα με σκοπό την εμβάθυνση στη θεωρία. Οι εργασίες έχουν αυστηρές προθεσμίες υποβολής και προσμετρώνται στον τελικό βαθμό του μαθήματος.
Βαθμολογία:Η βαθμολογία γίνεται ως εξής:
- Ι: βαθμός τελ. εξέτασης με άριστα 10
- ΙΙ: βαθμός ασκήσεων με άριστα 2
- ΙΙΙ: παρουσίαση θέματος
Τελικός βαθμός = 0.5*min{Ι*(1+ ΙΙ/10), 10}+0.5*ΙΙΙΠροτεινόμενα θέματα για παρουσίαση
Ενδεικτικά αναφέρονται οι ακόλουθες θεματικές περιοχές.
1. Τυπικά αποδεικτικά συστήματα Gentzen. Λογισμός ακολουθητών (sequent calculus) και συστήματα φυσικής απαγωγής (natural deduction systems). Το θεώρημα της απαλοιφής των τομών (cut elimination) ή η απαλοιφή των redexes με εφαρμογές.2. Η έννοια της υπολογισιμότητας και οι αναδρομικές συναρτήσεις (computability and recursive functions). Κάποια θεωρήματα αναποκρισιμότητας (undecidability results). 3. Παρουσίαση των πλευρών του θεωρήματος μη-πληρότητας του Goedel (Goedel's incompleteness theorem).4. Το σύστημα απλών τύπων του Church (Church's system of simple types) και ο ισομορφισμός Curry-Howard.5. Η θεωρία αλήθειας του Tarski, π.χ. π.χ. το άρθρο του "The concept of truth in formalized languages" αλλά και άλλα σχετικά με αυτό και περισσότερο εξηγητικά.6. Και βέβαια οποιοδήποτε άλλο θέμα, σχετικό με τη θεματική του μαθήματος, που σας έχει ελκύσει το ενδιαφέρον και μπορείτε να το αναπτύξετε.Μπορείτε να εργαστείτε κατά μόνας αλλά και συνεργατικά, οπότε θα καλύψετε ευρύτερη περιοχή και θα κάνετε με επιμερισμό και ευρύτερη παρουσίαση.