ΧΕΙΜΕΡΙΝΟ ΕΞΑΜΗΝΟ 2019-1020

ΤΜΗΜΑ ΜΑΘΗΜΑΤΙΚΩΝ-ΕΚΠΑ

Διδάσκων: Κ. Πούλιος.

Επικοινωνία: costas314@gmail.com 

Γραφείο: 209. Ώρες γραφείου: Τρίτη 10:00-11:00 και Παρασκευή 11:00-12:00. 

Ώρες και αίθουσες διδασκαλίας: 

• Τρίτη 11:00-13:00, Αίθουσα Γ32.

• Παρασκευή 09:00-11:00, Αίθουσα Γ32.

Κύρια συγγράμματα:

1. Κ. Ι. Δημητρακόπουλος. Σημειώσεις Μαθηματικής Λογικής.

2. Herbert B. Enderton. Μια μαθηματική εισαγωγή στη λογική. Πανεπιστημιακές Εκδόσεις Κρήτης.

Βαθμολόγηση: Θα γίνει μια τελική εξέταση στο τέλος του εξαμήνου. Κατά τη διάρκεια των μαθημάτων θα δοθούν ασκήσεις, οι οποίες θα μετράνε στο τελικό βαθμό το πολύ μία μονάδα, εφόσον στην τελική εξέταση ο βαθμός σας είναι μεγαλύτερος ή ίσος του 5. Επίσης, θα γίνει παρουσίαση των ασκήσεων από τους φοιτητές και στη διάρκεια της παρουσίασης θα υπάρχει προφορική εξέταση.

ΑΝΑΚΟΙΝΩΣΕΙΣ.

Έναρξη μαθημάτων: Τρίτη 01 Οκτωβρίου 2019.

Αναπλήρωση μαθήματος: Την Τετάρτη 11 Δεκεμβρίου και ώρα 9-11 θα γίνει αναπλήρωση μαθήματος στην Αίθουσα Γ42.

Αναπλήρωση μαθήματος: Την Τετάρτη 22 Ιανουαρίου και ώρα 9-11 θα γίνει αναπλήρωση μαθήματος στην Αίθουσα Γ42.

Επαναληπτικό Μάθημα: Το Σάββατο 08 Φεβρουαρίου 2020, ώρα 11-13, στην Αίθουσα Γ32, θα γίνει επαναληπτικό μάθημα για την επίλυση αποριών και ασκήσεων.

ΑΞΙΟΛΟΓΗΣΗ.

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

ΗΜΕΡΟΛΟΓΙΟ ΜΑΘΗΜΑΤΟΣ

Εβδομάδα 30/09-06/10.

• Τρίτη 01/10: Στην αρχή του μαθήματος συζητήσαμε ορισμένα γενικά θέματα σχετικά με τη Μαθηματική Λογική και το μάθημα. Στην συνέχεια, ξεκινήσαμε να μελετάμε τη γλώσσα του προτασιακού λογισμού. Αναφέραμε ποια είναι τα σύμβολα (αλφάβητο) αυτής της γλώσσας (προτασιακές μεταβλητές, σύνδεσμοι και παρενθέσεις). Ορίσαμε τι είναι έκφραση στην γλώσσα και είπαμε ότι οι εκφράσεις που μας ενδιαφέρουν είναι οι προτασιακοί τύποι, τους οποίους και ορίσαμε με αναδρομικό τρόπο. Τέλος, αποδείξαμε την Αρχή της Επαγωγής για το σύνολο των προτασιακών τύπων.

• Παρασκευή 04/10: Στην αρχή του μαθήματος κάναμε μια άσκηση ως εφαρμογή της αρχής της επαγωγής για το σύνολο των προτασιακών τύπων. (Συγκεκριμένα, αποδείξαμε ότι σε κάθε προτασιακό τύπο το πλήθος των αριστερών παρενθέσεων ισούται με το πλήθος των δεξιών παρενθέσεων.) Έπειτα αποδείξαμε το Θεώρημα Μοναδικής Αναγνωσιμότητας, το οποίο (σε ελεύθερη μετάφραση) λέει ότι κάθε προτασιακός τύπος κατασκευάζεται με μοναδικό τρόπο από τις προτασιακές μεταβλητές και τους συνδέσμους (ή με άλλα λόγια ότι το δενδροδιάγραμμα κάθε προτασιακού τύπου είναι μοναδικό). Επίσης, αναφέραμε τους κανόνες απαλοιφής παρενθέσεων, οι οποίοι απλοποιούν αρκετά τη γραφή ενός προτασιακού τύπου, αφού μας απαλλάσσουν από αρκετές παρενθέσεις. Στην συνέχεια, ορίσαμε τι είναι αποτίμηση (ή εκτίμηση): είναι μια συνάρτηση με πεδίο ορισμού το σύνολο των προτασιακών μεταβλητών που παίρνει τιμές στο δισύνολο {Α,Ψ} (τα γράμματα αυτά αντιστοιχούν στις τιμές αλήθειας: Αληθής και Ψευδής). Αναφέραμε (χωρίς να το αποδείξουμε) ότι κάθε αποτίμηση επεκτείνεται με μοναδικό τρόπο σε μια συνάρτηση με πεδίο ορισμού το σύνολο των προτασιακών τύπων έτσι ώστε να ικανοποιούνται οι πίνακες αλήθειας των συνδέσμων. Οι πίνακες αυτοί επιβάλλονται από την ερμηνεία που δίνουμε στους συνδέσμους.  Τέλος, ορίσαμε τις ακόλουθες έννοιες:  πότε ένα σύνολο προτασιακών τύπων λέγεται ικανοποιήσιμο, πότε ένας προτασιακός τύπος είναι ταυτολογία και πότε αντίφαση, πότε ένα σύνολο προτασιακών τύπων συνεπάγεται ταυτολογικά έναν προτασιακό τύπο και πότε δύο τύποι λέγονται ταυτολογικά ισοδύναμοι.

Εβδομάδα 07/10-13/10.

• Τρίτη 08/10: Την πρώτη ώρα, αποδείξαμε ότι κάθε αποτίμηση από τις προτασιακές μεταβλητές στο δισύνολο {Α,Ψ}, μπορεί να επεκταθεί με μοναδικό τρόπο σε μια συνάρτηση με πεδίο ορισμού το σύνολο όλων των προτασιακών τύπων, έτσι ώστε να ικανοποιούνται οι πίνακες αλήθειας των συνδέσμων.  Την δεύτερη ώρα ασχοληθήκαμε με το εξής ερώτημα: "Αν μας δώσουν ένα σύνολο Τ προτασιακών τύπων και έναν προτασιακό τύπο φ, μπορούμε να αποφανθούμε αν το Τ συνεπάγεται ταυτολογικά τον φ ή όχι; Είδαμε ότι, αν το Τ είναι πεπερασμένο, τότε υπάρχει αλγοριθμική διαδικασία που μας δίνει το αποτέλεσμα. Η διαδικασία αυτή στηρίζεται στο να κατασκευάσουμε έναν πίνακα στον οποίο να φαίνονται οι τιμές αλήθειας των τύπων του Τ και του φ. Κάναμε σχετικά παραδείγματα. Το πρόβλημα της μεθόδου είναι το εξής: αν στους προτασιακούς τύπους του Τ και στον φ εμφανίζονται n διαφορετικές προτασιακές μεταβλητές, τότε ο πίνακας πρέπει να έχει 2^n γραμμές και, για μεγάλες τιμές του n, είναι αδύνατο να ελεγχθούν όλες οι περιπτώσεις ακόμη και μέσω υπολογιστή! Τέλος, κάναμε μερικά παραδείγματα, στα οποία μπορούσαμε να αποφανθούμε αν το σύνολο Τ συνεπάγεται ταυτολογικά τον φ, χωρίς να χρειαστεί να κάνουμε τον πίνακα αλήθειας.

• Παρασκευή 11/10: Το μάθημα δεν έγινε λόγω της κατάληψης.

Εβδομάδα 14/10-20/10.

• Τρίτη 14/10: Στην αρχή του μαθήματος συμπληρώσαμε κάποια κομμάτια θεωρίας που μας έμειναν από τα προηγούμενα μαθήματα. Ειδικότερα, διατυπώσαμε και αποδείξαμε το Θεώρημα της εις άτοπο απαγωγής. Επίσης, διατυπώσαμε (χωρίς να αποδείξουμε) το Θεώρημα της Συμπάγειας. Τέλος, γράψαμε μια λίστα με γνωστές ταυτολογίες, τις οποίες ονομάσαμε νόμους της Προτασιακής Λογικής, και μπορούμε να τις χρησιμοποιούμε απευθείας, χωρίς να χρειαστεί να τις αποδεικνύουμε. Στο υπόλοιπο του μαθήματος ασχοληθήκαμε με ασκήσεις σχετικές με την ύλη που έχουμε καλύψει στα μέχρι τώρα μαθήματα.

• Παρασκευή 18/10: Σε αυτό το μάθημα ασχοληθήκαμε με τα εξής ερωτήματα: "Αν στους 5 αρχικούς συνδέσμους που έχουμε πάρει (άρνηση, σύζευξη, διάζευξη, συνεπαγωγή, ισοδυναμία), προσθέσουμε κάποιον (ή κάποιους) ακόμη, τότε θα κερδίσουμε κάτι? Η νέα γλώσσα που θα προκύψει θα έχει περισσότερες δυνατότητες?" Και ανάλογα, τίθεται και το εξής ερώτημα: "Αν από τους αρχικούς 5 συνδέσμους αφαιρέσουμε κάποιους, τότε θα χάσουμε κάτι? Δηλαδή η νέα γλώσσα θα έχει λιγότερες δυνατότητες?" Για να απαντήσουμε σε αυτά τα ερωτήματα, ορίσαμε τις συναρτήσεις Boole. Είδαμε ότι κάθε προτασιακός τύπος ορίζει (μέσω του πίνακα αλήθειας) μια συνάρτηση Boole. Ισχύει όμως και το αντίστροφο: κάθε συνάρτηση Boole υλοποιείται από έναν προτασιακό τύπο. Μάλιστα, αυτός ο τύπος μπορεί να γραφεί σε κανονική διαζευκτική μορφή. Αποδείξαμε το θεώρημα Κανονικής Διαζευκτικής Μορφής. Άμεση συνέπεια αυτού είναι ότι κάθε προτασιακός τύπος είναι ταυτολογικά ισοδύναμος με ένα προτασιακό τύπο που περιέχει μόνο τους συνδέσμους: άρνηση, διάζευξη, σύζευξη. Με άλλα λόγια το σύνολο αυτών των τριών συνδέσμων είναι πλήρες (ή επαρκές). Ορίσαμε ακριβώς πότε ένα σύνολο συνδέσμων είναι πλήρες και είδαμε μερικά παραδείγματα συνόλων που είναι πλήρη αλλά και παραδείγματα συνόλων που δεν είναι πλήρη. Με αυτά τα εργαλεία απαντήσαμε στα ερωτήματα που είχαμε θέσει αρχικά.

Εβδομάδα 21/10-27/10.

• Τρίτη 22/10: Αρχικά, είδαμε αναλυτικά τους n-θέσιους συνδέσμους που μπορούμε να θεωρήσουμε για n=0 ή 1 ή 2. Στη συνέχεια κάναμε μερικές ασκήσεις σχετικές με πλήρη σύνολα συνδέσμων.

• Παρασκευή 25/10: Το μάθημα δεν έγινε λόγω κατάληψης.

Εβδομάδα 28/10-03/11.

• Τρίτη 29/10: Στην αρχή του μαθήματος είπαμε ότι, παρόλο που οι ταυτολογικές συνεπαγωγές δουλεύουν πολύ καλά, θέλουμε να τις αντικαταστήσουμε με έναν περισσότερο "τυπικό" (ή "μηχανικό") τρόπο αποδείξεων. Με άλλα λόγια, θέλουμε να αποδεικνύουμε ότι ένας προτασιακός τύπος έπεται από ένα σύνολο άλλων προτασιακών τύπων, χρησιμοποιώντας μόνο σύμβολα. Υπάρχουν διάφοροι λόγοι για τους οποίους θέλουμε να κάνουμε κάτι τέτοιο. Επιγραμματικά, μερικοί είναι: (1) οι λογικές συνεπαγωγές δεν δουλεύουν τόσο καλά εκτός Προτασιακού Λογισμού, (2) οι αποδείξεις στα μαθηματικά δεν γίνονται με απονομές αλήθειας κτλ. Για να πετύχουμε αυτόν τον στόχο, χρησιμοποιούμε ένα Αξιωματικό Σύστημα.  Ορίσαμε τι είναι ένα αξιωματικό σύστημα για τη γλώσσα του Προτασιακού λογισμού (ένα αξιωματικό σύστημα αποτελείται από ένα σύνολο προτασιακών τύπων (τα αξιώματα) και ένα σύνολο αποδεικτικών κανόνων). Επίσης ορίσαμε τι σημαίνει τυπική απόδειξη στα πλαίσια ενός αξιωματικού Συστήματος, από ένα σύνολο υποθέσεων Τ με ένα συμπέρασμα φ. Επίσης, ορίσαμε ποια είναι τα τυπικά θεωρήματα ενός αξιωματικού συστήματος (είναι οι προτασιακοί τύποι που μπορούν να αποδειχθούν χωρίς υποθέσεις, δηλαδή μόνο από τα αξιώματα και τους αποδεικτικούς κανόνες). Υπάρχουν διάφορα αξιωματικά συστήματα για τον Προτασιακό Λογισμό, όμως στο μάθημα επικεντρωθήκαμε σε ένα από αυτά, το λεγόμενο Αξιωματικό Σύστημα του Hilbert. Αποδείξαμε το Θεώρημα Απαγωγής και στη συνέχεια είδαμε παραδείγματα τυπικών αποδείξεων στο αξιωματικό μας σύστημα.

• Παρασκευή 01/11: Το μάθημα δεν έγινε λόγω κατάληψης.

Εβδομάδα 04/11-10/11.

• Τρίτη 05/11: Σε αυτό το μάθημα συνεχίσαμε τη μελέτη του Αξιωματικού Συστήματος του Hilbert. Ειδικότερα, αποδείξαμε αρχικά ορισμένα τυπικά θεωρήματα του αξιωματικού συστήματος και συνεχίσαμε με  το Θεώρημα Αντιθετοαντιστροφής και το Θεώρημα της εις Άτοπο Απαγωγής. Τέλος, αποδείξαμε το Θεώρημα Εγκυρότητας του Προτασιακού Λογισμού: αν ένα σύνολο προτασιακών τύπων Τ (υποθέσεις) αποδεικνύει τυπικά τον προτασιακό τύπο φ (συμπέρασμα), τότε το Τ συνεπάγεται και ταυτολογικά τον φ.

• Παρασκευή 08/11: Την πρώτη ώρα αποδείξαμε το Θεώρημα Πληρότητας του Προτασιακού Λογισμού: Αν ένας προτασιακός τύπος φ είναι ταυτολογία, τότε είναι και τυπικό θεώρημα. Αναφέραμε ότι ισχύει και ένα πιο γενικό αποτέλεσμα (την απόδειξη του οποίου αναβάλλουμε για τον κατηγορηματικό λογισμό): Αν ένα σύνολο προτασιακών τύπων Τ συνεπάγεται ταυτολογικά τον προτασιακό τύπο φ, τότε υπάρχει τυπική απόδειξη (στα πλαίσια του Αξιωματικού συστήματος του Hilbert) με υποθέσεις το Τ και συμπέρασμα τον φ. Το Θεώρημα εγκυρότητας μαζί με το Θεώρημα Πληρότητας μας λένε πώς ότι μπορούμε να κάνουμε με  "σημασιολογικές" αποδείξεις μπορούμε να το κάνουμε και με "τυπικές" αποδείξεις και αντίστροφα. Άρα,  "σημασιολογικές" και "τυπικές" αποδείξεις είναι δύο όψεις του ίδιου νομίσματος. Τη δεύτερη ώρα αποδείξαμε το Θεώρημα Συμπάγειας (κάναμε μια έμμεση απόδειξη, η οποία χρησιμοποιεί τα Θεωρήματα Εγκυρότητας και Πληρότητας). Στο υπόλοιπο της ώρας κάναμε ασκήσεις στον Προτασιακό Λογισμό.

Εβδομάδα 11/11-17/11.

• Τρίτη 12/11: Στην αρχή του μαθήματος σχολιάσαμε τα μειονεκτήματα που έχει το μοντέλο του Προτασιακού Λογισμού.  Το μοντέλο αυτό είναι τόσο χονδροειδές που σε κάποιες περιπτώσεις αποτυγχάνει να περιγράψει κάποιες (ακόμη και απλές) αποδείξεις. Στην συνέχεια, αρχίσαμε τη μελέτη του δεύτερου μοντέλου που θα κατασκευάσουμε για τη μελέτη των αποδείξεων και είναι το μοντέλο του Κατηγορηματικού Λογισμού.  Στο μοντέλο αυτό δεν έχουμε μία μόνο γλώσσα, αλλά περισσότερες, τις οποίες ονομάζουμε πρωτοτάξιες (ή πρωτοβάθμιες) γλώσσες. Είδαμε ποια είναι τα σύμβολα που έχει μια τέτοια γλώσσα. Επίσης, μελετήσαμε εκτενώς δύο βασικά παραδείγματα, την πρωτοτάξια γλώσσα της Θεωρίας Συνόλων και την πρωτοτάξια γλώσσα της Θεωρίας Αριθμών. Στη συνέχεια ασχοληθήκαμε με τις εκφράσεις μιας γλώσσας. Έκφραση μιας πρωτοτάξιας γλώσσας είναι μια πεπερασμένη ακολουθία από σύμβολα. Δεν μας ενδιαφέρουν όμως όλες οι εκφράσεις, αλλά κάποιες από αυτές. Σε αντίθεση με τον προτασιακό Λογισμό, όπου οι μόνες εκφράσεις με νόημα ήταν οι προτασιακοί τύποι, στην κατηγορηματική λογική έχουμε τους όρους και τους τύπους. Δώσαμε τους σχετικούς ορισμούς των όρων και των τύπων. Οι ορισμοί αυτοί είναι αναδρομικοί. Αυτό έχει ως συνέπεια να ισχύει η αρχή της επαγωγής για τους όρους και αντίστοιχα η αρχή της επαγωγής για τύπους, τις οποίες διατυπώσαμε χωρίς όμως να αποδείξουμε.

• Παρασκευή 15/11: Το μάθημα δεν έγινε λόγω κατάληψης.

Εβδομάδα 18/11-24/11.

• Τρίτη 19/11: Σε αυτό το μάθημα συνεχίσαμε τη μελέτη του "συντακτικού" μιας πρωτοτάξιας γλώσσας. Διατυπώσαμε, χωρίς να αποδείξουμε, το Θεώρημα Μοναδικής Αναγνωσιμότητας για όρους και το αντίστοιχο Θεώρημα για τύπους. Δώσαμε τον (πολύ σημαντικό) ορισμό πότε μια μεταβλητή εμφανίζεται ελεύθερη σε έναν τύπο και πότε είναι δεσμευμένη. Επίσης, ορίσαμε τι ονομάζουμε πρόταση (είναι ένας τύπος στον οποίο κάθε μεταβλητή είναι δεσμευμένη). Κάναμε σχετικές ασκήσεις. Τέλος, είδαμε μερικές ασκήσεις, για το πώς μετατρέπουμε μια πρόταση της φυσικής γλώσσας σε μια έκφραση μιας πρωτοβάθμιας γλώσσας.

• Παρασκευή 22/11: Το μάθημα δεν έγινε λόγω κατάληψης.

Εβδομάδα 25/11-01/12.

• Τρίτη 26/11: Σε αυτό το μάθημα αντιμετωπίσαμε μια μεγάλη πρόκληση: να αποδώσουμε τιμή αλήθειας στους τύπους μιας πρωτοτάξιας γλώσσας. Είδαμε ότι για να γίνει αυτό, χρειαζόμαστε 3 βήματα. (1) Πρέπει καταρχάς να "μετατρέψουμε" τα "άψυχα" σύμβολα μιας γλώσσας σε κάτι πιο χειροπιαστό, κάτι που να έχει νόημα και να μπορούμε να το δουλέψουμε. Αυτό επιτυγχάνεται μέσω μιας δομής. Μια δομή για μια πρωτοβάθμια γλώσσα αποτελείται από ένα μη κενό σύνολο (το σύμπαν ή πεδίο ορισμού της δομής), σε κάθε σύμβολο κατηγορήματος αντιστοιχεί μία σχέση στο σύνολο αυτό, σε κάθε σύμβολο συνάρτησης αντιστοιχεί μία συνάρτηση στο σύμπαν και σε κάθε σύμβολο σταθεράς αντιστοιχεί ένα στοιχείο του σύμπαντος. Επομένως, μια δομή δίνει νόημα στις προτάσεις μιας πρωτοβάθμιας γλώσσας. Είδαμε τις πιο συνηθισμένες δομές για τη γλώσσα της Θεωρίας Συνόλων και της Θεωρίας Αριθμών. (2) Ορίσαμε τι είναι αποτίμηση σε μια δομή. Είναι μια απεικόνιση από τις μεταβλητές στο σύμπαν της δομής. Επισημάναμε (χωρίς να δώσουμε αυστηρή απόδειξη) ότι κάθε αποτίμηση μπορεί να επεκταθεί με μοναδικό τρόπο σε όλους τους όρους της γλώσσας. (3) Τέλος, φτάσαμε στο στόχο μας, δηλαδή να δώσουμε τον ορισμό αλήθειας του Tarski. Δοθείσης μιας γλώσσας, μιας δομής και μιας αποτίμησης σε αυτήν, ορίσαμε πότε θα λέμε ότι ένας τύπος της γλώσσας αληθεύει στην δομή για τη δοθείσα αποτίμηση (εναλλακτικά, θα λέμε πολλές φορές και ότι η δομή ικανοποιεί τον τύπο με τη συγκεκριμένη αποτίμηση). 

• Τετάρτη 27/11 (αναπλήρωση μαθήματος): Σε αυτό το μάθημα κάναμε πολλές εφαρμογές και παραδείγματα σχετικά με τις έννοιες που ορίσαμε στο προηγούμενο μάθημα και κυρίως στον ορισμό αλήθειας του Tarski. Τα παραδείγματα ήταν κυρίως αυτής της μορφής: Μας δίνονταν μια γλώσσα, μια δομή και μια αποτίμηση για αυτήν την γλώσσα και θέλαμε να δούμε αν ένας συγκεκριμένος τύπος αληθεύει στη δοθείσα δομή με τη δοθείσα αποτίμηση.

• Παρασκευή 22/11: Το μάθημα δεν έγινε λόγω κατάληψης.

Εβδομάδα 02/12-08/12.

• Τρίτη 03/12: Αποδείξαμε αναλυτικά το εξής αποτέλεσμα: αν φ είναι ένας τύπος και έχουμε μια δομή για τη γλώσσα μας και δύο αποτιμήσεις στη δομή οι οποίες συμφωνούν στις ελεύθερες μεταβλητές του φ, τότε ο τύπος αληθεύει ως προς τη μία αποτίμηση αν και μόνο αν αληθεύει ως προς την άλλη. Με άλλα λόγια, το αν αληθεύει ένας τύπος σε μία δομή με μια αποτίμηση, εξαρτάται από την τιμή που δίνει η αποτίμηση μόνο στις μεταβλητές που εμφανίζονται ελεύθερες στον τύπο, ενώ οι δεσμευμένες μεταβλητές δεν παίζουν κάποιο ρόλο. Ειδικότερα, αν ο τύπος είναι πρόταση (δηλαδή όλες οι μεταβλητές είναι δεσμευμένες), τότε δοθείσης μιας δομής, μπορεί να συμβούν δύο πράγματα: (1) είτε η δομή ικανοποιεί την πρόταση φ με κάθε αποτίμηση, είτε (2) η δομή δεν ικανοποιεί την πρόταση με οποιαδήποτε αποτίμηση. Αν συμβαίνει η πρώτη περίπτωση, τότε λέμε ότι η δομή είναι ένα μοντέλο της πρότασης. Αν συμβαίνει το (2), τότε λέμε ότι η πρόταση είναι ψευδής στην δομή. Τέλος, είδαμε μερικά παραδείγματα, σχετικά με προτάσεις μιας πρωτοβάθμιας γλώσσας και μοντέλα αυτών.

• Παρασκευή 06/12: Το μάθημα δεν έγινε λόγω κατάληψης.

Εβδομάδα 09/12-15/12.

• Τρίτη 10/12: Με τις πρωτοβάθμιες γλώσσες, τις οποίες έχουμε μελετήσει στα προηγούμενα μαθήματα, ο στόχος μας είναι να μελετήσουμε αποδείξεις. Όπως και στον Προτασιακό Λογισμό, αυτή η μελέτη αποδείξεων μπορεί να γίνει με δύο τρόπους: τον σημασιολογικό (ο οποίος στηρίζεται στην απόδοση τιμής αλήθειας στους τύπους) και τον συντακτικό. Σε αυτό το μάθημα αρχίσαμε να βλέπουμε τις σημασιολογικές αποδείξεις. Δώσαμε αρχικά τον ορισμό της λογικής συνεπαγωγής: ένα σύνολο τύπων Τ συνεπάγεται λογικά έναν τύπο φ όταν για κάθε δομή και κάθε αποτίμηση σε αυτήν την δομή τέτοιες ώστε να ικανοποιείται το Τ, έχουμε ότι και ο τύπος φ αληθεύει στην εν λόγω δομή και με τη συγκεκριμένη αποτίμηση. Επίσης, ορίσαμε πότε ένας τύπος λέγεται έγκυρος ή λογικά αληθής.  Λέμε ότι ο φ είναι έγκυρος (ή λογικά αληθής) όταν είναι λογική συνεπαγωγή του κενού συνόλου. Αυτό είναι ισοδύναμο με το να πούμε ότι ο τύπος φ αληθεύει σε κάθε δομή και με κάθε αποτίμηση. Επιπλέον, ορίσαμε πότε δύο τύποι λέγονται λογικά ισοδύναμοι. Διατυπώσαμε το Θεώρημα της εις άτοπο απαγωγής. (Την απόδειξη την αφήσαμε ως άσκηση, καθώς είναι παρόμοια με την αντίστοιχη απόδειξη του Προτασιακού Λογισμού.) Τέλος, κάναμε αρκετά παραδείγματα πάνω σε αυτές τις έννοιες και είδαμε πώς αποδεικνύουμε ότι ένα σύνολο τύπων Τ συνεπάγεται λογικά έναν τύπο φ και πώς αποδεικνύουμε ότι το Τ δεν συνεπάγεται λογικά τον φ. 

• Τετάρτη 11/12 (αναπλήρωση μαθήματος): Την πρώτη ώρα συνεχίσαμε τη μελέτη των λογικών συνεπαγωγών. Γράψαμε μια λίστα με τύπους που είναι έγκυροι (δηλαδή αληθεύουν για οποιαδήποτε δομή και με οποιαδήποτε αποτίμηση), τους οποίους ονομάζουμε συνήθως "νόμους της κατηγορηματικής λογικής". Για ορισμένους από αυτούς, κάναμε την απόδειξη ότι είναι έγκυροι τύποι ενώ για τους υπόλοιπους αφήσαμε την απόδειξη ως άσκηση. Τη δεύτερη ώρα, σχολιάσαμε το γεγονός ότι στον κατηγορηματικό λογισμό δεν υπάρχει αλγόριθμος που να μας επιτρέπει να αποφανθούμε αν ένα σύνολο τύπων Τ συνεπάγεται λογικά κάποιον τύπο φ,  ακόμη και στην περίπτωση που το Τ είναι πεπερασμένο. (Αντίθετα στον Προτασιακό Λογισμό υπάρχει τέτοιος αλγόριθμος και δίνεται ουσιαστικά από τους πίνακες αλήθειας. Ο αλγόριθμος αυτός δεν είναι υπολογιστικά χρήσιμος όταν έχουμε πάρα πολλές προτασιακές μεταβλητές, ωστόσο ο αλγόριθμος υπάρχει.) Έτσι λοιπόν, αφού οι σημασιολογικές αποδείξεις δεν δουλεύουν τόσο καλά όσο στον προτασιακό λογισμό, δεν συνεχίσαμε τη μελέτη τους, αλλά στραφήκαμε στις λεγόμενες "συντακτικές αποδείξεις". Ορίσαμε τι είναι ένα αξιωματικό σύστημα για τον Κατηγορηματικό Λογισμό και τι σημαίνει τυπική απόδειξη στα πλαίσια ενός αξιωματικού συστήματος. (Οι ορισμοί είναι παρόμοιοι με τους αντίστοιχους από τον Προτασιακό Λογισμό.) Εν γένει υπάρχουν πολλά αξιωματικά συστήματα για τον Κατηγορηματικό Λογισμό, ωστόσο στο μάθημα θα επικεντρωθούμε σε ένα από αυτά. Αυτό το αξιωματικό σύστημα έχει έναν αποδεικτικό κανόνα, τον γνωστό μας (από την Προτασιακή Λογική) Modus Ponens. Στη συνέχεια, αναφερθήκαμε (όσο προλάβαμε) στα Λογικά Αξιώματα αυτού του Αξιωματικού συστήματος. Η μελέτη του συστήματος αυτού θα συνεχιστεί στο επόμενο μάθημα.

• Παρασκευή 13/12: Στην αρχή του μαθήματος, αναφέραμε πάλι τα Λογικά Αξιώματα μιας γλώσσας του Κατηγορηματικού Λογισμού και ορίσαμε πότε μια μεταβλητή x είναι αντικαταστάσιμη από τον όρο t στο τύπο φ. Δώσαμε έναν άτυπο ορισμό, ο οποίος είναι χρήσιμος όταν έχουμε κάποιο συγκεκριμένο τύπο και θέλουμε να δούμε αν μια μεταβλητή είναι αντικαταστάσιμη από έναν όρο. Επίσης, δώσαμε έναν πιο τυπικό (επαγωγικό) ορισμό, ο οποίος θα είναι πιο χρήσιμος σε θεωρητικά αποτελέσματα. Στη συνέχεια, σχολιάσαμε ότι κάθε γλώσσα συνοδεύεται από ένα σύνολο (πιθανόν κενό) από μη λογικά αξιώματα, τα οποία ονομάζονται έτσι διότι καθορίζουν τον ρόλο των μη λογικών συμβόλων, δηλαδή των κατηγορημάτων και των συμβόλων συναρτήσεων. Επειδή αυτά τα σύμβολα διαφέρουν από γλώσσα σε γλώσσα και τα αντίστοιχα αξιώματα θα διαφέρουν από γλώσσα σε γλώσσα. Εμείς όμως δεν θα ασχοληθούμε περισσότερο με τα μη λογικά αξιώματα. Θα μείνουμε στα Λογικά Αξιώματα, οπότε ότι αναφέρουμε στο μάθημα θα ισχύει σε οποιαδήποτε γλώσσα και αν έχουμε. (Εξάλλου, αν έχουμε μια τυπική απόδειξη που περιέχει μη λογικά αξιώματα, τότε αυτά μπορούμε να τα θεωρήσουμε ως υποθέσεις). Έπειτα, αναφέραμε δύο παραδείγματα τυπικών αποδείξεων και είδαμε τη δυσκολία που έχουν. Για το λόγο αυτό, χρειάζεται να αναπτύξουμε τεχνικές οι οποίες θα μας βοηθούν στις τυπικές αποδείξεις. Οι τεχνικές αυτές βασίζονται στα Θεωρήματα Γενίκευσης, Απαγωγής, Αντιθετοαντιστροφής και Εις Άτοπο Απαγωγής. Διατυπώσαμε μόνο το Θεώρημα Γενίκευσης χωρίς απόδειξη (η οποία θα γίνει στο επόμενο μάθημα).

 Εβδομάδα 16/12-22/12.

• Τρίτη 17/12: Την πρώτη ώρα του μαθήματος επαναλάβαμε το Θεώρημα Γενίκευσης και κάναμε αναλυτικά την απόδειξή του. Στη συνέχεια διατυπώσαμε το Θεώρημα Απαγωγής. (Δεν κάναμε την απόδειξη, η οποία όμως είναι παρόμοια με την αντίστοιχη απόδειξη του Προτασιακού Λογισμού.) Στην συνέχεια διατυπώσαμε και αποδείξαμε το Θεώρημα Αντιθετοαντιστροφής. Τέλος, ορίσαμε πότε ένα σύνολο τύπων είναι συνεπές και πότε αντιφατικό (οι ορισμοί είναι ίδιοι με τους αντίστοιχους του Προτασιακού Λογισμού) και αποδείξαμε το Θεώρημα της Εις Άτοπο Απαγωγής. Τη δεύτερη ώρα, χρησιμοποιήσαμε όλα αυτά τα εργαλεία σε τυπικές αποδείξεις. Είδαμε μερικά παραδείγματα, στα οποία από ένα σύνολο τύπων (πιθανόν κενό), προσπαθούσαμε να αποδείξουμε τυπικά έναν τύπο φ.

• Παρασκευή 20/12: Την πρώτη ώρα συνεχίσαμε με παραδείγματα τυπικών αποδείξεων, με εφαρμογή των θεωρημάτων Γενίκευσης και Απαγωγής. Στη συνέχεια, τη δεύτερη ώρα διατυπώσαμε και αποδείξαμε αναλυτικά το Θεώρημα Γενίκευσης σε Σταθερές.

21/12 έως και 06/01: Διακοπές Χριστουγέννων-Πρωτοχρονιάς.

Εβδομάδα 07/01-12/01.

• Τρίτη 07/01: Στην αρχή του μαθήματος αποδείξαμε το Λήμμα Επαναντικατάστασης: Έστω ότι στον τύπο φ δεν εμφανίζεται καθόλου η μεταβλητή y. Αν στον φ αντικαταστήσω τις ελεύθερες εμφανίσεις της μεταβλητής x με την y και, στον τύπο που προκύψει, αντικαταστήσω τις ελεύθερες εμφανίσεις της y με x, τότε παίρνω πάλι τον τύπο φ. (Αυτό δεν είναι σωστό, εν γένει, αν η μεταβλητή y εμφανίζεται στον φ.) Στην συνέχεια, θυμηθήκαμε το Θεώρημα Γενίκευσης σε Σταθερές και αποδείξαμε ένα πόρισμα αυτού. Χρησιμοποιώντας το πόρισμα αποδείξαμε το Θεώρημα Υπαρξιακής Σταθεροποίησης (ή Υπαρξιακής Πραγμάτωσης). Στο τέλος του μαθήματος, αρχίσαμε να μιλάμε για αλφαβητικές παραλλαγές. Είδαμε, μέσω ενός παραδείγματος, πώς εκμεταλλευόμαστε τις αλφαβητικές παραλλαγές. Η βασική τους χρήση είναι η εξής: αν σε μια τυπική απόδειξη θέλουμε να χρησιμοποιήσουμε το Αξιωματικό Σχήμα 2, αλλά η μεταβλητή x δεν είναι αντικαταστάσιμη από τον όρο t στον τύπο φ, τότε μπορούμε πάντα να ξεπεράσουμε αυτό το πρόβλημα "μαγειρεύοντας" τις δεσμευμένες μεταβλητές και παίρνοντας στην ουσία μια αλφαβητική παραλλαγή του τύπου φ. Η διατύπωση του θεωρήματος αλφαβητικών παραλλαγών και η απόδειξή του θα γίνει στο επόμενο μάθημα.

• Παρασκευή 10/01: Στην αρχή του μαθήματος διατυπώσαμε και αποδείξαμε το Θεώρημα Αλφαβητικών Παραλλαγών. Στην συνέχεια ορίσαμε πότε ένας τύπος μιας πρωτοβάθμιας γλώσσας είναι σε Κανονική Ποσοδεικτική Μορφή (συντομογραφικά ΚΠΜ). Αποδείξαμε ότι κάθε τύπος είναι λογικά ισοδύναμος με έναν τύπο σε ΚΠΜ. Επίσης, κάναμε αρκετά παραδείγματα στα οποία, δοθέντος ενός τύπου, βρίσκαμε έναν τύπο λογικά ισοδύναμο με τον αρχικό σε ΚΠΜ. Τέλος, αρχίσαμε να μιλάμε για το Θεώρημα Εγκυρότητας (ή Αξιοπιστίας) του Κατηγορηματικού Λογισμού: Αν ένα σύνολο τύπων Τ αποδεικνύει τυπικά τον τύπο φ, τότε το Τ συνεπάγεται λογικά τον φ. (Άρα, το Αξιωματικό σύστημα, παρόλο που φαινομενικά επιλέχθηκε αυθαίρετα, οδηγεί σε "ορθά" συμπεράσματα.) Η απόδειξη του θεωρήματος Εγκυρότητας βασίζεται στο ότι τα λογικά αξιώματα είναι έγκυροι τύποι και ότι ο κανόνας Modus Ponens διατηρεί τη λογική συνεπαγωγή. Με αυτά τα δεδομένα, αποδείξαμε το θεώρημα εγκυρότητας (η απόδειξη είναι ίδια με την απόδειξη του αντίστοιχου θεωρήματος του Προτασιακού Λογισμού). Στο επόμενο μάθημα, μένει να δείξουμε ότι τα αξιώματα είναι έγκυροι τύποι.

Εβδομάδα 13/01-19/01.

• Τρίτη 14/01: Στο μάθημα αυτό αποδείξαμε αναλυτικά ότι όλα τα λογικά αξιώματα είναι έγκυροι τύποι. Κατά συνέπεια, η απόδειξη του Θεωρήματος Εγκυρότητας είναι πλέον πλήρης.

• Παρασκευή 10/01: Στην αρχή του μαθήματος διατυπώσαμε το Θεώρημα Πληρότητας, χωρίς να το αποδείξουμε (η απόδειξη θα γίνει την επόμενη βδομάδα). Επίσης, διατυπώσαμε και αποδείξαμε το Θεώρημα Συμπάγειας. Στην συνέχεια, αρχίσαμε να μελετάμε τις δομές ως μαθηματικά αντικείμενα. Μέχρι τώρα, ο ρόλος μιας δομής ήταν βοηθητικός και τις χρησιμοποιούσαμε προκειμένου να αποδώσουμε τιμή αλήθειας σε κάποιον τύπο. Ωστόσο, οι δομές είναι συνήθως μαθηματικά αντικείμενα που παρουσιάζουν ενδιαφέρον. Άρα, σε αυτό το μάθημα (και θα συνεχίσουμε και στο επόμενο) η δομή γίνεται ο πρωταγωνιστής. Είδαμε ότι ένας τύπος μιας πρωτοβάθμιας γλώσσας με n ελεύθερες μεταβλητές καθορίζει μια n-μελή σχέση στο σύμπαν της δομής. Έτσι, καταλήξαμε στον ορισμό πότε μια σχέση μιας δομής είναι ορίσιμη ή όχι. Τέλος, είδαμε ότι ένα σύνολο προτάσεων της πρωτοβάθμιας γλώσσας μας ορίζει μια κλάση (πιθανώς κενή) από δομές. Έτσι, καταλήξαμε στον ορισμό της στοιχειώδους κλάσης δομών (ΣΚ) και της στοιχειώδους κλάσης με την ευρεία έννοια.

Εβδομάδα 20/01-26/01.

• Τρίτη 21/01: Σε αυτό το μάθημα συνεχίσαμε την μελέτη των δομών ως μαθηματικά αντικείμενα. Ειδικότερα, ορίσαμε την έννοια του ομομορφισμού μεταξύ δύο δομών: ένας ομομορφισμός είναι μια συνάρτηση από το σύμπαν της μίας δομής στο σύμπαν της άλλης, η οποία διατηρεί τις σχέσεις, τις πράξεις και τις σταθερές. Επιπλέον, ορίσαμε πότε δύο δομές είναι ισόμορφες: όταν υπάρχει ένας ομομορφισμός από τη μία στην άλλη, ο οποίος είναι 1-1 και επί. Τέλος, αποδείξαμε το Θεώρημα Ομομορφισμού.  Άμεση συνέπεια του θεωρήματος είναι ότι αν δύο δομές είναι ισόμορφες, τότε αυτές συμπεριφέρονται με τον ίδιο τρόπο όσον αφορά την απόδοση τιμής αλήθειας σε τύπους. Άρα, αν φ είναι μια πρόταση της γλώσσας, τότε η μια δομή είναι μοντέλο της φ αν και μόνο αν η άλλη δομή είναι μοντέλο της φ.

• Τετάρτη 22/01: Την πρώτη ώρα αποδείξαμε ένα πόρισμα του Θεωρήματος ομομορφισμού, το οποίο σε κάποιες περιπτώσεις μας βοηθά να αποδείξουμε ότι μια σχέση σε μία δομή δεν είναι ορίσιμη. Στη συνέχεια, ασχοληθήκαμε λίγο με το μέγεθος των μοντέλων μιας πρότασης. Συγκεκριμένα, αποδείξαμε ότι: αν ένα σύνολο προτάσεων έχει πεπερασμένα μοντέλα με οσοδήποτε μεγάλο πληθάριθμο, τότε αναγκαστικά θα έχει άπειρο μοντέλο. (Ισοδύναμα, αν ένα σύνολο προτάσεων έχει μόνο πεπερασμένα μοντέλα, τότε θα υπάρχει άνω φράγμα για τον πληθάριθμό τους.) Άμεση συνέπεια του αποτελέσματος αυτού είναι ότι η κλάση των πεπερασμένων δομών δεν είναι στοιχειώδης κλάση με την ευρύτερη έννοια. Αντίθετα, η κλάση των άπειρων δομών είναι στοιχειώδης κλάση με την ευρύτερη έννοια, αλλά δεν είναι ΣΚ.  Τέλος, την δεύτερη ώρα αρχίσαμε την απόδειξη του Θεωρήματος Πληρότητας: αν ένα σύνολο τύπων Τ είναι συνεπές, τότε είναι και ικανοποιήσιμο. Περιγράψαμε τα βασικά βήματα της απόδειξης: (1) Επεκτείνουμε το σύνολο Τ σε ένα σύνολο Σ, το οποίο είναι συνεπές, μεγιστιαίο και έχει μία επιπλέον ιδιότητα. (2) Χρησιμοποιώντας το Σ ορίζουμε μια δομή και μια αποτίμηση που ικανοποιούν κάθε τύπο του Σ εκτός από αυτούς που περιέχουν το σύμβολο της ισότητας. (3) Τροποποιούμε λίγο την κατασκευή ώστε να πάρουμε μια δομή και μια αποτίμηση που ικανοποιούν κάθε τύπο του Σ. Άρα, το Σ είναι ικανοποιήσιμο και, αφού Τ περιέχεται στο Σ, έχουμε ότι και Τ είναι ικανοποιήσιμο. Τέλος, αρχίσαμε να βλέπουμε την απόδειξη του βήματος (1). Η απόδειξη του Θεωρήματος Πληρότητας θα ολοκληρωθεί στο επόμενο (και τελευταίο) μάθημα.

• Παρασκευή 24/01: Σε αυτό το μάθημα ολοκληρώσαμε την απόδειξη του Θεωρήματος Πληρότητας.

ΤΕΛΟΣ ΜΑΘΗΜΑΤΩΝ.

ΕΓΓΡΑΦΑ ΜΑΘΗΜΑΤΟΣ

• 18/10/2019. Αναρτήθηκε το πρώτο πακέτο ασκήσεων. Παράδοση μέχρι 08-11-2019. 

• 12/11/2019. Αναρτήθηκε το δεύτερο πακέτο ασκήσεων. Παράδοση μέχρι 30-11-2019.

• 13/12/2019. Αναρτήθηκε το τρίτο πακέτο ασκήσεων. Παράδοση μέχρι 07-01-2020.

• 18/12/2019. Το τρίτο πακέτο ασκήσεων περιείχε ένα τυπογραφικό λάθος (στην άσκηση 14), το οποίο και διορθώθηκε. Ευχαριστώ τον Άλκη που επισήμανε το λάθος αυτό.

• 14/01/2020. Αναρτήθηκε το τέταρτο (και τελευταίο) πακέτο ασκήσεων. Παράδοση μέχρι την ημέρα των εξετάσεων. Με την παράδοση των ασκήσεων θα γίνεται προφορική εξέταση στις ασκήσεις όλης της ύλης.

• 21/01/2020. Άρχισε η ανάρτηση ενδεικτικών λύσεων σε τυχαία επιλεγμένες ασκήσεις. Το αρχείο αυτό θα βρίσκεται σε συνεχή ανανέωση. Η επιλογή των ασκήσεων γίνεται τυχαία και σε καμία περίπτωση δεν πρέπει να θεωρηθούν SOS. Επειδή οι λύσεις γράφονται υπό πίεση χρόνου, ενδέχεται να υπάρχουν αρκετά λάθη.

• 23/01/2020. Το τέταρτο φυλλάδιο είχε ένα μικρό τυπογραφικό λάθος στην άσκηση 3, το οποίο και διορθώθηκε. Ευχαριστώ όσους μου το επισήμαναν.

ΤΕΛΙΚΗ ΕΞΕΤΑΣΗ

• 02/03/2020. Αναρτήθηκαν τα αποτελέσματα της Εξεταστικής του Φεβρουαρίου 2020. Οι βαθμοί είναι τελικοί, δηλαδή έχουν ληφθεί υπόψιν και οι ασκήσεις. Όποιος επιθυμεί να δει το γραπτό του, μπορεί να προσέλθει την Παρασκευή 06 Μαρτίου 2020, στο Γραφείο 209 και ώρα 10:00-12:00.

• 02/03/2020. Αναρτήθηκε επίσης η κατάσταση των φοιτητών που παρέδωσαν ασκήσεις στο μάθημα της Λογικής (513). Αν δεν βλέπετε τον Αριθμό μητρώου σας στην κατάσταση αυτή, τότε επικοινωνήστε μαζί μου.