Μαθηματική Λογική

Εαρινό Εξάμηνο 2018

Το μάθημα διδάσκεται στο 8ο εξάμηνο της Σχολής Εφαρμοσμένων Μαθηματικών και Φυσικών Επιστημών ΣΕΜΦΕ και στο 6ο εξάμηνο της Σχολής Ηλεκτρολόγων Μηχανικών και Μηχανικών Υπολογιστών ΣΗΜΜΥ του ΕΜΠ.

Διδάσκων: Γ. Κολέτσος

Πρόγραμμα/Ωράριο Παραδόσεων

Γίνονται 4 ώρες εβδομαδιαίως (2 δίωρα).
Τρίτη 17.15--19.00 Αίθουσα 012 Νέα Κτ. Ηλεκτρολόγων, ΕΜΠ και Τετάρτη 17.15--19.00, Αίθουσα 012 Νέα Κτ. Ηλεκτρολόγων, ΕΜΠ.

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

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

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

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

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

Σημειώσεις Παραδόσεων

Το βιβλίο του μαθήματος σε PDF εδώ

Ασκήσεις:

Οι ασκήσεις και οι λύσεις θα αναρτώνται στη σελίδα.

Ασκήσεις 1: PDF

Ασκήσεις 2: PDF

Ασκήσεις 3: Όλες οι ασκήσεις 4.3 (1 έως 13) σελ. 61, 62, 63 των  σημειώσεων. Παράδοση στις 18 Απριλίου 2018. 

Λύσεις

Άσκηση 1: PDF

Άσκηση 2: PDF

Οι σημειώσεις που θα δίδονται θα καλύπτουν ένα μεγάλο μέρος τού μαθήματος. Θα πρέπει να χρησιμοποιούνται μόνο σε συνδυασμό με την παρακολούθηση του μαθήματος, την οποία σε καμία περίπτωση δεν μπορούν να υποκαταστήσουν. Θα εμπλουτίζονται με ασκήσεις και πρόσθετες σημειώσεις ανάλογα με την πορεία διεξαγωγής τού μαθήματος.

 

 

 

 

 

 

 

 

 

 


Valid HTML 4.01! mailto:webmaster@math.ntua.gr