Πρόγραμμα σπουδών της Μαθηματικής λογικής I

Σκοπός

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

Αν αυτό ισχύει, ο κύκλος δεν είναι μια συλλογή κανόνων για τον χειρισμό συμβόλων, αλλά μια θεωρία με ένα κεντρικό αποτέλεσμα, το θεώρημα πληρότητας, που όλα τα προηγούμενα το προετοιμάζουν. Για ένα σύνολο τύπων $\Gamma$ και έναν τύπο $\varphi$, η παραγωγιμότητα $\Gamma \vdash \varphi$ λέει ότι υπάρχει μια πεπερασμένη ακολουθία τύπων, κατασκευασμένη με αξιώματα και κανόνες, που τελειώνει στον $\varphi$· η σημασιολογική συνέπεια $\Gamma \models \varphi$ λέει ότι κάθε αποτίμηση που κάνει αληθείς τους τύπους του $\Gamma$ κάνει αληθή τον $\varphi$. Οι δύο σχέσεις γεννιούνται από αντίθετες ιδέες, η μία συντακτική και υπαρξιακή, η άλλη σημασιολογική και καθολική· ο κύκλος αποδεικνύει, ωστόσο, ότι $\Gamma \vdash \varphi \Leftrightarrow \Gamma \models \varphi$. Από αυτό έπεται ότι κάθε ερώτημα για το τι έπεται από κάποιες υποθέσεις μπορεί να απαντηθεί από την πλευρά που αποδεικνύεται ευκολότερη: παρουσιάζοντας μια παραγωγή, διατρέχοντας έναν πίνακα ή, όπως διδάσκει το τελευταίο μάθημα περιεχομένου, διαψεύδοντας με επίλυση.

Σε ποιους απευθύνεται και προαπαιτούμενες γνώσεις

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

Είναι κύκλος μαθημάτων επιπέδου 1, χωρίς προαπαιτούμενα και αυτοτελής. Δεν προϋποθέτει να έχει μελετήσει κανείς λογική, ούτε να γνωρίζει θεωρία συνόλων, ούτε να έχει αποδείξει ποτέ θεώρημα. Ό,τι χρησιμοποιεί από τα σύνολα (το ανήκειν, τον εγκλεισμό, την ένωση, σύνολα τύπων), από τις συναρτήσεις (μια αποτίμηση είναι μια συνάρτηση από τις μεταβλητές στο $\{0, 1\}$), από τις συμβολοσειρές και από την επαγωγή το διδάσκει εκεί όπου το χρειάζεται: τα σύνολα και τις συμβολοσειρές, στο μάθημα της ενότητας 1 για τη γλώσσα, και την επαγωγή, στο επόμενο μάθημα, πριν τη χρησιμοποιήσει. Προϋποθέτει μόνο δύο πράγματα: προσεκτική ανάγνωση, επειδή σε μια τυπική γλώσσα ένα σύμβολο που προστίθεται ή παραλείπεται αλλάζει τη συμβολοσειρά, και τη στοιχειώδη αριθμητική των φυσικών αριθμών, που σε αυτόν τον κύκλο, όπως και στον υπόλοιπο ιστότοπο, αρχίζουν από το $1$.

Πού οδηγεί

Από τα παραπάνω έπεται η θέση του κύκλου στον ιστότοπο. Δεν έχει προαπαιτούμενα και είναι στόχος τριών προγραμμάτων σπουδών, Μαθηματικών, Πληροφορικής και Φιλοσοφίας, επειδή και στα τρία ο συλλογισμός είναι ταυτόχρονα εργαλείο και αντικείμενο. Έχει τρεις συμπληρωματικούς κύκλους, που μπορούν να ακολουθηθούν πριν, παράλληλα ή μετά, με οποιαδήποτε σειρά. Η Αριστοτελική λογική μελετά τη λογική των όρων και τον συλλογισμό, του οποίου η εγκυρότητα εξαρτάται από λέξεις όπως «όλα» και «κάποιο», που αυτός ο κύκλος αφήνει έξω, και δείχνει από ποια παράδοση φτάσαμε στον λογισμό. Η Άλγεβρα και γεωμετρία I υψώνει ένα παραγωγικό οικοδόμημα από τα αξιώματα του Πεάνο, και εφαρμόζει στην πράξη, πάνω στους αριθμούς, την αξιωματική μέθοδο και την επαγωγή που αυτός ο κύκλος μελετά ως αντικείμενο· το πρόγραμμά της συνιστά να έχει μελετηθεί πριν αυτός ο κύκλος ή να μελετάται παράλληλα. Ο Προγραμματισμός σε C++ I, τέλος, φέρνει στην πράξη ό,τι εδώ είναι θεωρία: το να αποφασίζεται αν μια συμβολοσειρά είναι καλά σχηματισμένη, να διατρέχεται ένας πίνακας αληθείας, να υπολογίζεται μια κανονική μορφή ή να αναζητείται μια διάψευση είναι διαδικασίες που μπορούν να γραφτούν ως προγράμματα.

Ωστόσο, ο κύκλος αφήνει ανοιχτό ένα ερώτημα εκφραστικότητας: η γλώσσα του δεν μπορεί να πει «όλα» ούτε «κάποιο», και η τυποποίηση επιχειρημάτων διατυπωμένων στα ελληνικά χάνει, από την ενότητα 1, τους ποσοδείκτες. Επομένως, η προβλεπόμενη συνέχειά του είναι ο κύκλος μαθημάτων Μαθηματική λογική II, αφιερωμένος στην κατηγορηματική λογική, που θα διατρέξει τον ίδιο δρόμο με ποσοδείκτες και μεταβλητές που διατρέχουν αντικείμενα: θα διατηρήσει την ορθότητα, την πληρότητα και τη συμπάγεια, με μεθόδους που αυτός ο κύκλος προλαμβάνει, αλλά σε αυτόν η σημασιολογική συνέπεια θα πάψει να είναι αποκρίσιμη.

Γενικοί μαθησιακοί στόχοι

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

1. Στόχος 1. Να διακρίνει τη γλώσσα-αντικείμενο από τη μεταγλώσσα, και να αποφασίζει με τους κανόνες σχηματισμού αν μια συμβολοσειρά είναι τύπος.
2. Στόχος 2. Να τυποποιεί αποφάνσεις και επιχειρήματα της φυσικής γλώσσας, επισημαίνοντας τι διατηρεί και τι χάνει η τυποποίηση.
3. Στόχος 3. Να κατασκευάζει παραγωγές στο σύστημα του κύκλου μαθημάτων (τα αξιώματα του Λουκασέβιτς, το modus ponens και την αντικατάσταση της διπλής άρνησης), συνδυάζοντας αξιώματα, πρωταρχικούς κανόνες και παράγωγους κανόνες.
4. Στόχος 4. Να αποδεικνύει μεταθεωρήματα με επαγωγή στους φυσικούς αριθμούς, στην πολυπλοκότητα των τύπων και στο μήκος των παραγωγών.
5. Στόχος 5. Να αποφασίζει για την εγκυρότητα, την ικανοποιησιμότητα, τη σημασιολογική συνέπεια και τη σημασιολογική ισοδυναμία, με πίνακες αληθείας και με ισοδυναμίες.
6. Στόχος 6. Να μετασχηματίζει τύπους σε κανονικές μορφές και να εκφράζει με αυτές συναρτήσεις αληθείας και κυκλώματα.
7. Στόχος 7. Να εξηγεί και να εφαρμόζει την ορθότητα, την πληρότητα και τη συμπάγεια, και να αποφασίζει τη μη ικανοποιησιμότητα με επίλυση.

Οι στόχοι 3 και 7 έχουν ο καθένας τη δική του ενότητα, τον συμπερασμό και τη μεταθεωρία· οι στόχοι 5 και 6 μοιράζονται την ενότητα της σημασιολογίας, ο πρώτος στο πρώτο μισό της, ο δεύτερος στο δεύτερο. Ο στόχος 2 έχει ένα δικό του μάθημα, εκείνο της τυποποίησης, και ασκείται έπειτα κάθε φορά που ένα πρόβλημα διατυπώνεται με λόγια. Οι στόχοι 1 και 4, αντιθέτως, είναι εγκάρσιοι: η διάκριση ανάμεσα σε ό,τι λέγεται μέσα στη γλώσσα και ό,τι λέγεται για αυτήν διατρέχει τις τέσσερις ενότητες, και η επαγωγή είναι η μορφή όλων των σημαντικών αποδείξεων του κύκλου, από τη μονοσήμαντη ανάγνωση των τύπων ως την ορθότητα του συστήματος και το λήμμα του Καλμάρ. Από αυτό έπεται ότι η επίτευξή τους δεν μπορεί να αποδοθεί σε ένα μόνο μάθημα, και ότι καλό είναι να καλλιεργούνται σε όλη τη διάρκεια του κύκλου.

Το σύστημα του κύκλου και οι αποφάσεις του

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

Μια γλώσσα κύκλων και δίσκων

Η γλώσσα του κύκλου έχει ένα αλφάβητο μόνο δύο συμβόλων, τον κύκλο $\sigO$ και τον δίσκο $\sigI$. Η $n$-οστή μεταβλητή είναι η συμβολοσειρά από $n$ κύκλους ακολουθούμενους από έναν δίσκο, $v_{n} = \sigO^{n}\sigI$, ώστε $v_{1} = \sigO\sigI$ και $v_{2} = \sigO\sigO\sigI$· και υπάρχει ένας μόνο κανόνας σχηματισμού: αν οι $\varphi$ και $\psi$ είναι τύποι, είναι τύπος και ο $\sigI\varphi\psi$, που συντομογραφείται $(\varphi \downarrow \psi)$ και διαβάζεται «ούτε $\varphi$ ούτε $\psi$». Η κοινή άρνηση $\downarrow$ είναι, επομένως, ο μόνος πρωταρχικός σύνδεσμος, και όλοι οι άλλοι είναι συντομογραφίες που ορίζονται μία μόνο φορά: ο $\neg\varphi$ είναι ο $(\varphi \downarrow \varphi)$, η διάζευξη $(\varphi \vee \psi)$ είναι ο $\neg(\varphi \downarrow \psi)$, και από αυτές ορίζονται η σύζευξη, η συνεπαγωγή, η διπλή συνεπαγωγή και η αποκλειστική διάζευξη. Κάθε άλλος τρόπος γραφής τους είναι θεώρημα, που αποδεικνύεται, και όχι ορισμός.

Η επιλογή έχει ένα τίμημα, την αναγνωσιμότητα, που ο κύκλος το πληρώνει στη μεταγλώσσα: κανείς δεν γράφει καθημερινά συμβολοσειρές κύκλων και δίσκων, αλλά τα συντομογραφημένα ονόματά τους, που μπορούν ανά πάσα στιγμή να αναπτυχθούν ως τη συμβολοσειρά που δηλώνουν. Ωστόσο, το τίμημα αποπληρώνεται πολλές φορές. Δύο σύμβολα αρκούν για άπειρες μεταβλητές, ώστε κάθε τύπος είναι μια πεπερασμένη συμβολοσειρά πάνω σε ένα αλφάβητο δύο στοιχείων. Ο σύνδεσμος γράφεται μπροστά από τα ορίσματά του, και γι' αυτό δεν χρειάζονται παρενθέσεις: η μονοσήμαντη ανάγνωση αποδεικνύεται με ένα επιχείρημα βάρους, που αποδίδει $+1$ σε κάθε μεταβλητή και $-1$ σε κάθε συνδετικό δίσκο. Και επειδή κάθε σύνθετος τύπος είναι μια κοινή άρνηση, κάθε απόδειξη με επαγωγή στην πολυπλοκότητα έχει μία μόνο σύνθετη περίπτωση, πράγμα που συντομεύει όλες τις αποδείξεις των επόμενων ενοτήτων. Το ότι ένας μόνο σύνδεσμος αρκεί για να εκφράσει οποιονδήποτε άλλο δεν υποτίθεται: η ενότητα της σημασιολογίας το αποδεικνύει.

Ένας δεύτερος πρωταρχικός κανόνας

Το παραγωγικό σύστημα ξεκινά από εκείνο του Γιαν Λουκασέβιτς: τρία αξιωματικά σχήματα, γραμμένα με την άρνηση και τη συνεπαγωγή, και το modus ponens ως μοναδικό κανόνα. Τα σχήματα αυτά διατυπώθηκαν για γλώσσες των οποίων οι πρωταρχικοί σύνδεσμοι είναι η άρνηση και η συνεπαγωγή· στη γλώσσα των κύκλων και των δίσκων, ένας τύπος όπως ο $(v_{1} \downarrow v_{2})$ δεν είναι ούτε το ένα ούτε το άλλο, και για τα αξιώματα είναι αδιαφανής. Το πρώτο μάθημα της ενότητας του συμπερασμού αποδεικνύει, με μια σήμανση που έχουν όλα τα αξιώματα, που το modus ponens τη διατηρεί και που ο τύπος δεν την έχει, ότι το σύστημα του Λουκασέβιτς δεν παράγει τον $((v_{1} \downarrow v_{2}) \rightarrow \neg v_{1})$.

Αν αυτό ισχύει, το σύστημα πρέπει να συμπληρωθεί, και η φυσική θεραπεία μοιάζει να είναι η απόδειξη της διπλής άρνησης, $\varphi \dashv\vdash \neg\neg\varphi$, που το δεύτερο μάθημα την παράγει από τα τρία σχήματα. Η σήμανση δείχνει ότι δεν αρκεί: τα θεωρήματα της διπλής άρνησης τη διατηρούν και, ωστόσο, ούτε καν με αυτά δεν αντικαθίσταται ο $v_{1}$ με τον $\neg\neg v_{1}$ μέσα σε μια κοινή άρνηση. Επομένως, αφού αποδείξει τη διπλή άρνηση, το δεύτερο μάθημα προσθέτει έναν δεύτερο πρωταρχικό κανόνα, την αντικατάσταση της διπλής άρνησης: από έναν τύπο $\chi$ συνάγεται εκείνος που προκύπτει αν αντικατασταθεί σε αυτόν μια εμφάνιση ενός υποτύπου $\theta$ με τον $\neg\neg\theta$, ή μια εμφάνιση του $\neg\neg\theta$ με τον $\theta$. Το σύστημα του κύκλου μαθημάτων αποτελείται, λοιπόν, από τα τρία σχήματα του Λουκασέβιτς, το modus ponens και αυτόν τον κανόνα.

Άλλα συστήματα για την κοινή άρνηση επιτυγχάνουν το ίδιο με αξιωματικά σχήματα φτιαγμένα στα μέτρα τους. Ο κύκλος προτιμά έναν κανόνα για δύο λόγους: είναι ακόμη απλούστερος από το modus ponens, επειδή παίρνει μία μόνο γραμμή και αλλάζει μία μόνο εμφάνιση, και δεν έχει τίποτα τεχνητό, επειδή εκφράζει ό,τι λέει ήδη η διπλή άρνηση, ότι οι $\theta$ και $\neg\neg\theta$ είναι εναλλάξιμοι, επεκταμένο σε κάθε θέση ενός τύπου. Είναι, επιπλέον, ορθός, επειδή διατηρεί την τιμή αληθείας κάθε γραμμής, και διατηρεί το θεώρημα της απαγωγής, με μία περίπτωση παραπάνω στην απόδειξή του. Το ότι με αυτόν αρκεί για να παραχθεί ό,τι πρέπει να παραχθεί είναι το θεώρημα πληρότητας της τελευταίας ενότητας.

Η συμπάγεια πριν από την ισχυρή πληρότητα

Η πληρότητα δέχεται τρεις βαθμούς: η ασθενής λέει ότι κάθε ταυτολογία είναι θεώρημα· η πληρότητα για πεπερασμένα σύνολα, ότι κάθε σημασιολογική συνέπεια ενός πεπερασμένου συνόλου υποθέσεων παράγεται από αυτό· η ισχυρή, ότι το ίδιο ισχύει για ένα οποιοδήποτε σύνολο, και άπειρο. Η μέθοδος του κύκλου, το λήμμα του Καλμάρ, δουλεύει με τις πεπερασμένες μεταβλητές ενός τύπου και με πεπερασμένες υποθέσεις, και γι' αυτό φτάνει στους δύο πρώτους βαθμούς και όχι στον τρίτο. Για να φτάσει κανείς σε αυτόν αρκεί, αν $\Gamma \models \varphi$, κάποιο πεπερασμένο μέρος $\Gamma_{0}$ του $\Gamma$ να ικανοποιεί ήδη $\Gamma_{0} \models \varphi$· ωστόσο, αυτό ακριβώς βεβαιώνει το θεώρημα της συμπάγειας.

Πολλά κείμενα αποδεικνύουν πρώτα την ισχυρή πληρότητα με άλλη μέθοδο και συνάγουν από αυτήν τη συμπάγεια. Σε αυτόν τον κύκλο, αντιθέτως, η ισχυρή πληρότητα είναι αυτό που αναζητείται, και η απόκτηση της συμπάγειας από αυτήν θα ήταν κυκλική. Επομένως, η σειρά αντιστρέφεται: το μάθημα για τη συμπάγεια την αποδεικνύει μέσα στη σημασιολογία, χωρίς να αναφέρει καμία παραγωγή, σταθεροποιώντας μία προς μία τις τιμές των $v_{1}, v_{2}, \ldots$, και μόνο ύστερα, σε τρεις γραμμές, λαμβάνει την ισχυρή πληρότητα, δηλαδή $\Gamma \models \varphi \Rightarrow \Gamma \vdash \varphi$ για κάθε σύνολο $\Gamma$.

Περιεχόμενα

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

Ενότητα 0. Παρουσίαση του μαθήματος

Αποτελείται από αυτό το μάθημα, που ορίζει τον σκοπό, τους γενικούς στόχους, τις αποφάσεις, τα περιεχόμενα, τον φόρτο και τον σχεδιασμό του κύκλου.

Ενότητα 1. Γλώσσα

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

1. Γλώσσα: εισαγωγή.
2. Τι είναι η μαθηματική λογική: η εγκυρότητα απέναντι στην αλήθεια, το αντιπαράδειγμα, τα παράδοξα και η διάκριση ανάμεσα στη γλώσσα-αντικείμενο και τη μεταγλώσσα.
3. Η γλώσσα της προτασιακής λογικής: σύνολα και συμβολοσειρές, η γλώσσα των κύκλων και των δίσκων, ο κανόνας σχηματισμού της και οι συντομογραφίες της.
4. Επαγωγή στους φυσικούς αριθμούς και στους τύπους: απλή, ισχυρή και δομική επαγωγή, το λήμμα του βάρους, η μονοσήμαντη ανάγνωση και οι ορισμοί με αναδρομή.
5. Τυποποίηση της φυσικής γλώσσας: το λεξικό, η μετάφραση αποφάνσεων και επιχειρημάτων, και ό,τι χάνει η υλική συνεπαγωγή.
6. Γλώσσα: σύνθεση και προκλήσεις.

Ενότητα 2. Συμπερασμός

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

1. Συμπερασμός: εισαγωγή.
2. Τυπικά παραγωγικά συστήματα: το σύστημα του Λουκασέβιτς, η παραγωγή με υποθέσεις, το θεώρημα της απαγωγής και η σήμανση που δείχνει το όριό του.
3. Τέσσερις τεχνικές παραγωγής: ο υποθετικός συλλογισμός, η εναλλαγή υποθέσεων, η διπλή άρνηση, η αντιθετοαντιστροφή και η αντικατάσταση της διπλής άρνησης.
4. Οι συμμετρίες των συνδέσμων: το θεμελιώδες λήμμα της κοινής άρνησης, η αντικατάσταση ισοδυνάμων, οι ισοδύναμες μορφές των συνδέσμων και οι πέντε συμμετρίες τους.
5. Οι τεχνικές της κλασικής λογικής: οι κανόνες κάθε συνδέσμου, το αποκλειόμενο τρίτο, η απόδειξη κατά περιπτώσεις και η απαγωγή σε άτοπο, με υποθέσεις.
6. Νόμοι του Ντε Μόργκαν και επιμεριστικοί νόμοι: οι αποδείξεις τους και προς τις δύο κατευθύνσεις και η αντικατάσταση ισοδυνάμων μέσα σε άλλους τύπους.
7. Συμπερασμός: σύνθεση και προκλήσεις.

Ενότητα 3. Σημασιολογία

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

1. Σημασιολογία: εισαγωγή.
2. Σημασιολογία της προτασιακής λογικής: οι αποτιμήσεις και η επέκτασή τους με αναδρομή, το λήμμα σύμπτωσης, οι πίνακες αληθείας, η εγκυρότητα και η ικανοποιησιμότητα.
3. Σημασιολογική συνέπεια και ισοδυναμία: η σημασιολογική συνέπεια από σύνολα, το σημασιολογικό θεώρημα της απαγωγής, η αντικατάσταση και η ομοιόμορφη υποκατάσταση.
4. Γενικευμένοι νόμοι του Ντε Μόργκαν και επιμεριστικοί νόμοι: συζεύξεις και διαζεύξεις $n$ όρων και οι νόμοι τους, με επαγωγή.
5. Συναρτησιακή πληρότητα: κάθε συνάρτηση αληθείας έχει έναν τύπο, η κοινή άρνηση αρκεί μόνη της, και τα επαρκή σύνολα συνδέσμων.
6. Κανονικές μορφές: λεκτικά, φράσεις, διαζευκτική και συζευκτική μορφή, η δυϊκότητά τους και η ύπαρξή τους.
7. Ο αλγόριθμος των κανονικών μορφών και οι εφαρμογές του: ένας αλγόριθμος ορθός και τερματίζων, και ο σχεδιασμός και η απλοποίηση κυκλωμάτων διακοπτών.
8. Σημασιολογία: σύνθεση και προκλήσεις.

Ενότητα 4. Μεταθεωρία

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

1. Μεταθεωρία: εισαγωγή.
2. Ορθότητα και πληρότητα: η ορθότητα με επαγωγή στις γραμμές, η μη αντιφατικότητα, το λήμμα του Καλμάρ και η ασθενής πληρότητα και η πληρότητα για πεπερασμένα σύνολα.
3. Το θεώρημα της συμπάγειας: η σημασιολογική απόδειξή του, οι ισοδύναμες μορφές του, η ισχυρή πληρότητα που έπεται από αυτό και οι συνδυαστικές εφαρμογές του.
4. Η μέθοδος της επίλυσης: η μορφή φράσεων, ο κανόνας της επίλυσης, η ορθότητά του και η πληρότητα διάψευσής του, και το κόστος του.
5. Μεταθεωρία: σύνθεση και προκλήσεις.

Ενότητα 5. Ολοκλήρωση του μαθήματος

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

Φόρτος εργασίας και πιστωτικές μονάδες

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

Αποτελέσματα

Τα μαθήματα του κύκλου περιέχουν συνολικά $90$ λυμένα προβλήματα, $90$ προτεινόμενα προβλήματα και $24$ προκλήσεις, καθώς και οκτώ αξιολογήσεις ενότητας. Ο εκτιμώμενος φόρτος ανά ενότητα, στρογγυλεμένος στην ώρα, είναι ο εξής:

• Ενότητα 0, παρουσίαση του μαθήματος: λιγότερο από $1$ ώρα.
• Ενότητα 1, γλώσσα: $30$ ώρες.
• Ενότητα 2, συμπερασμός: $36$ ώρες.
• Ενότητα 3, σημασιολογία: $43$ ώρες.
• Ενότητα 4, μεταθεωρία: $25$ ώρες.
• Ενότητα 5, ολοκλήρωση του μαθήματος: λιγότερο από $1$ ώρα.

Το σύνολο είναι περίπου $137$ ώρες εργασίας. Τον αριθμό αυτόν πρέπει να τον διαβάζει κανείς ως αυτό που είναι: μια εκτίμηση για όποιον μελετά όλες τις αποδείξεις και λύνει όλα τα προβλήματα και τις προκλήσεις. Όποιος έχει ήδη μελετήσει λογική, ή περιορίζεται στα προτεινόμενα προβλήματα χωρίς να καταπιάνεται με τις προκλήσεις, θα χρειαστεί αρκετά λιγότερο· όποιος δεν έχει αποδείξει ποτέ θεώρημα μπορεί να χρειαστεί περισσότερο, κυρίως στις ενότητες του συμπερασμού και της σημασιολογίας, που είναι επίσης οι εκτενέστερες.

Ωστόσο, ο αριθμός είναι ονομαστικός: αυτός καθορίζει τις πιστωτικές μονάδες του κύκλου, και προϋποθέτει ανάγνωση με σταθερό ρυθμό και τρία τέταρτα της ώρας ανά πρόκληση. Όσο δεν έχει μετρηθεί με πραγματικούς φοιτητές, καλό είναι να συνοδεύεται από ένα ρεαλιστικό εύρος. Αν η ανάγνωση προχωρούσε με το μισό του υποτιθέμενου ρυθμού, όπως συμβαίνει όταν κάθε παραγωγή αντιγράφεται με χαρτί και μολύβι και κάθε συμβολοσειρά κύκλων και δίσκων αναλύεται με το χέρι, και κάθε πρόκληση απαιτούσε εβδομήντα πέντε λεπτά αντί για σαράντα πέντε, η ίδια μέθοδος θα έδινε περίπου $174$ ώρες. Επομένως, ο αναμενόμενος φόρτος βρίσκεται ανάμεσα σε περίπου $137$ και περίπου $174$ ώρες. Το ανώτερο άκρο είναι ένα συνετό φράγμα, όχι μέτρηση· το εύρος θα διορθωθεί όταν γίνει γνωστός ο χρόνος που αφιερώνουν όσοι μελετούν τον κύκλο, και ως τότε οι πιστωτικές μονάδες υπολογίζονται με τον ονομαστικό αριθμό.

Προτεινόμενος ρυθμός

Για να ονομάσει τους ρυθμούς, αυτό το πρόγραμμα χρησιμοποιεί το ίδιο κριτήριο με τα άλλα προγράμματα του ιστότοπου: η πλήρης φοίτηση είναι ένα ακαδημαϊκό έτος $60$ πιστωτικών μονάδων, περίπου $1650$ ώρες μοιρασμένες σε περίπου σαράντα εβδομάδες, δηλαδή περίπου $40$ ώρες την εβδομάδα, και η μερική φοίτηση είναι το μισό, περίπου $20$ ώρες την εβδομάδα. Από αυτό προκύπτει ένας προτεινόμενος ρυθμός ενός εξαμήνου δεκαέξι εβδομάδων, με περίπου $8$ ή $9$ ώρες μελέτης την εβδομάδα, λίγο περισσότερο από το ένα πέμπτο της πλήρους φοίτησης· με το ρεαλιστικό εύρος, από $9$ έως $11$ ώρες την εβδομάδα. Το εξάμηνο αυτό μπορεί να μοιραστεί με την Άλγεβρα και γεωμετρία I, της οποίας οι αποδείξεις διαβάζονται καλύτερα όταν η παραγωγή είναι ήδη ένα γνωστό αντικείμενο.

Ένας εντατικός ρυθμός, περίπου $20$ ωρών την εβδομάδα, δηλαδή μερικής φοίτησης, ολοκληρώνει τον κύκλο σε επτά εβδομάδες. Ένας πιο χαλαρός ρυθμός, περίπου $4$ ή $5$ ωρών την εβδομάδα, τον εκτείνει σε δύο εξάμηνα, που μοιράζονται σχεδόν στη μέση: οι ενότητες 0 έως 2, η γλώσσα και ο συμπερασμός, καταλαμβάνουν περίπου $67$ ώρες, και οι ενότητες 3 έως 5, η σημασιολογία, η μεταθεωρία και η ολοκλήρωση, περίπου $69$.

Αντιστοιχία σε μεταφερόμενες πιστωτικές μονάδες

Τα συστήματα μεταφερόμενων πιστωτικών μονάδων μετρούν έναν κύκλο μαθημάτων με τη συνολική εργασία που απαιτεί από όποιον τον παρακολουθεί, και όχι με τις ώρες διδασκαλίας με φυσική παρουσία, ώστε οι σπουδές που πραγματοποιήθηκαν σε ένα ίδρυμα να μπορούν να αναγνωριστούν σε άλλο. Το Ευρωπαϊκό Σύστημα Μεταφοράς και Συσσώρευσης Πιστωτικών Μονάδων, που υιοθέτησαν τα ευρωπαϊκά πανεπιστήμια μετά τη Διακήρυξη της Μπολόνια, αποδίδει $60$ πιστωτικές μονάδες σε ένα ακαδημαϊκό έτος πλήρους φοίτησης, και ορίζει κάθε μονάδα μεταξύ $25$ και $30$ ωρών εργασίας. Το Σύστημα Μεταφερόμενων Πιστωτικών Μονάδων της Χιλής, που υιοθέτησαν τα χιλιανά πανεπιστήμια με ανάλογο σχεδιασμό, αποδίδει επίσης $60$ μονάδες στο ακαδημαϊκό έτος και ορίζει κάθε μονάδα μεταξύ $24$ και $31$ ωρών εργασίας.

Ωστόσο, αν διαιρέσουμε τις $137$ εκτιμώμενες ώρες με τα άκρα κάθε διαστήματος, ο κύκλος ισοδυναμεί με περίπου $5$ ευρωπαϊκές πιστωτικές μονάδες (από 4,6 έως 5,5), και με $4$ έως $6$ χιλιανές μεταφερόμενες πιστωτικές μονάδες (από 4,4 έως 5,7). Αν πάρουμε ως αναφορά την κεντρική τιμή και των δύο διαστημάτων, 27,5 ώρες ανά μονάδα, προκύπτει και στα δύο συστήματα ο ίδιος αριθμός, 4,98, που στρογγυλεύεται σε 5. Για τις ευρωπαϊκές μονάδες, ο αριθμός $C$ των μονάδων φράσσεται ως εξής:

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

Σχεδιασμός του κύκλου

Μορφή

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

Η δομή ενός μαθήματος

Όλα τα μαθήματα περιεχομένου ακολουθούν την ίδια δομή. Αρχίζουν με μια περίληψη και με έναν κατάλογο δικών τους μαθησιακών στόχων, διατυπωμένων ως παρατηρήσιμες επιδόσεις. Ακολουθεί η θεωρία, με τους ορισμούς, τα αποτελέσματα διατυπωμένα με ακρίβεια και τις αποδείξεις τους, και τα παραδείγματα. Οι αποδείξεις παρουσιάζονται ως αναπαραγωγείς βημάτων: κάθε βήμα γράφει μια γραμμή, φωτίζει ό,τι αλλάζει και, όταν στηρίζεται σε προηγούμενο αποτέλεσμα, επιστρέφει σε αυτό. Οι παραγωγές του συστήματος γράφονται με αριθμημένες γραμμές και με την αιτιολόγηση καθεμιάς στα δεξιά (ένα αξίωμα, μια υπόθεση, το modus ponens με τις γραμμές που χρησιμοποιεί, ή ένας παράγωγος κανόνας), και καθώς προχωρούν φωτίζονται οι γραμμές που παρατίθενται. Το μάθημα κλείνει με πέντε λυμένα προβλήματα, με τη λύση τους βήμα προς βήμα, και πέντε προτεινόμενα προβλήματα, το καθένα με μια διπλωμένη υπόδειξη και, μετά, την τελική απάντηση· τα προτεινόμενα προβλήματα απόδειξης προσθέτουν, διπλωμένη μετά την απάντηση, μια αναλυτική λύση, που καλό είναι να ανοίγεται μόνο αφού έχει γραφτεί η δική μας.

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

Αξιολόγηση

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

Πώς να μελετήσετε αυτόν τον κύκλο

Ο κύκλος είναι σχεδιασμένος για να μελετηθεί με τη σειρά. Κάθε ενότητα προϋποθέτει τις προηγούμενες: ο συμπερασμός γράφεται με τη γλώσσα της πρώτης, η σημασιολογία δίνει τιμή στους τύπους της, και η μεταθεωρία συγκρίνει τη δεύτερη με την τρίτη· η παράλειψη ενός μαθήματος αναγκάζει, αργά ή γρήγορα, να επιστρέψει κανείς σε αυτό.

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

Τέλος, καλό είναι να διακρίνει κανείς πάντα σε ποιο επίπεδο ανήκει κάθε ισχυρισμός: αν λέει κάτι μέσα στη γλώσσα, όπως ένας τύπος, ή κάτι για αυτήν, όπως το $\Gamma \vdash \varphi$ ή το $\Gamma \models \varphi$. Αυτή η διάκριση, που είναι ο πρώτος από τους στόχους του κύκλου, είναι επίσης εκείνη που επιτρέπει να κατανοηθεί το κεντρικό αποτέλεσμά του, που μπορεί να διατυπωθεί μόνο στη μεταγλώσσα.