mycourses .ntua.gr
Μαθηματική Λογική για Υπολογιστές

Γενικά στοιχεία

 

Περιγραφή
Ύλη

Περιεχόμενο Μαθήματος/Διδακτέα Ύλη

Προτασιακός Λογισμός: Γλώσσα, Μοναδική αναγνωσιμότητα, Λογικοί σύνδεσμοι, απονομές αλήθειας, σημασιολογικές έννοιες, επάρκεια συνδέσμων, διαζευκτική και συζευκτική κανονική μορφή, θεώρημα συμπάγειας προτασιακού λογισμού, εφαρμογές.

Πρωτοβάθμιος κατηγορηματικός λογισμός: Γλώσσα, μεταβλητές, έννοιες ελεύθερης και δεσμευμένης μεταβλητής, αντικατάσταση, αναλογία με τον προγραμματισμό, η έννοια της δομής, ερμηνεία της γλώσσας, ορισμός τής αλήθειας κατά Tarski.

Αξιωματικοποίηση της πρωτοβάθμιας Λογικής: Η έννοια του αξιωματικού συστήματος, Τυπικά αξιωματικά συστήματα τύπου Hilbert και Gentzen, Μοντέλα θεωριών, η έννοια της συνέπειας και τα θεωρήματα της ορθότητας και  πληρότητας του Gödel,  τα θεωρήματα συμπάγειας και Löwenheim-Skolem, εφαρμογές.

Υπολογισιμότητα και μή-πληρότητα: Αναλογίες με αλγοριθμικές έννοιες, Αποκρισιμότητα, το Entscheidungsproblem του Hilbert,  Εισαγωγή στη θεωρία αναδρομικών συναρτήσεων, το αίτημα του Church, Το θεώρημα μη-πληρότητας του  Gödel και της αναποκρισιμότητας των Gödel-Church.

Βιβλίο μαθήματος: 

https://repository.kallipos.gr/handle/11419/2299

Εργασίες
Στην ενότητα 'Εργασίες' αναρτώνται σειρές ασκήσεων κάθε δύο εβδομάδες με σκοπό την εμβάθυνση στη θεωρία. Οι εργασίες έχουν αυστηρές προθεσμίες υποβολής και προσμετρώνται στον τελικό βαθμό του μαθήματος.