Είσοδος

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

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

 

 
Περιγραφή

Ύλη

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

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

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

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

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

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

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

Εργασίες

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


 
Συγχρηματοδότηση
από την Ε.Ε.