\( \newcommand{\Ds}{\displaystyle} \newcommand{\PP}{{\mathbb P}} \newcommand{\RR}{{\mathbb R}} \newcommand{\KK}{{\mathbb K}} \newcommand{\CC}{{\mathbb C}} \newcommand{\ZZ}{{\mathbb Z}} \newcommand{\NN}{{\mathbb N}} \newcommand{\TT}{{\mathbb T}} \newcommand{\QQ}{{\mathbb Q}} \newcommand{\Abs}[1]{{\left|{#1}\right|}} \newcommand{\v}[1]{{{\mathbf #1}}} \newcommand{\Floor}[1]{{\left\lfloor{#1}\right\rfloor}} \newcommand{\Ceil}[1]{{\left\lceil{#1}\right\rceil}} \newcommand{\sgn}{{\rm sgn\,}} \newcommand{\Set}[1]{{\left\{{#1}\right\}}} \newcommand{\Norm}[1]{{\left\|{#1}\right\|}} \newcommand{\Prob}[1]{{{{\mathbb P}}\left[{#1}\right]}} \newcommand{\Mean}[1]{{{{\mathbb E}}\left[{#1}\right]}} \newcommand{\cis}{{\rm cis}\,} \newcommand{\one}{{\mathbf 1}} \renewcommand{\Re}{{\rm Re\,}} \renewcommand{\Im}{{\rm Im\,}} \renewcommand{\arg}{{\rm arg\,}} \renewcommand{\Arg}{{\rm Arg\,}} \renewcommand{\deg}{{\rm deg\,}} \newcommand{\ft}[1]{\widehat{#1}} \newcommand{\FT}[1]{\left(#1\right)^\wedge} \newcommand{\Lone}[1]{{\left\|{#1}\right\|_{1}}} \newcommand{\Linf}[1]{{\left\|{#1}\right\|_\infty}} \)

Λογική

Άνοιξη 2022-23

Τμήμα Μαθηματικών και Εφαρμοσμένων Μαθηματικών

Πανεπιστήμιο Κρήτης


Διδάσκων: Μιχάλης Κολουντζάκης

Πληροφορίες

Το μάθημα συνεχίζεται από 3/4/2023 με διδάσκοντα τον Μιχ. Κολουντζάκη. Μέχρι και την προηγούμενη εβδομάδα το δίδασκε ο Θαν. Φειδάς. Παλιά ιστοσελίδα εδώ.

Σημειώσεις

Ακολουθούμε τις σημειώσεις Δημητρακόπουλου.

Ωράριο

Δευτέρα (Α212) και Τετάρτη (Β208) 9-11

Για την περίοδο Ιουνίου 2023

Όλες οι ασκήσεις θα πρέπει να έχουν παραδοθεί είτε στο γραφείο μου είτε με email μέχρι και την Πέμπτη 22/6/2023. Όσοι φοιτητές δεν έχουν ήδη εξεταστεί προφορικά ή δεν έχουν ήδη κανονίσει το πότε θα εξεταστούν θα πρέπει να εξεταστούν την Παρασκευή, 23/6/2023, το πρωί μετά από συνεννόηση μαζί μου, αλλιώς η εξέταση θα πρέπει να γίνει την εβδομάδα της 3ης Ιουλίου 2023.

Όπως είπαμε και στο μάθημα θα πρέπει να παραδώσετε λυμένες τις μισές από τις ασκήσεις που φαίνονται παρακάτω. Αφού τις παραδώσετε θα έλθετε στο γραφείο μου για να εξεταστείτε προφορικά πάνω στις λύσεις σας. Αυτή η διαδικασία μπορεί να γίνει μέχρι και το τέλος της εξεταστικής περιόδου (23/6/2023) μετά από συνεννόηση με μένα και αφού έχετε ήδη παραδώσει λυμένες τις ασκήσεις.

Οι ασκήσεις που θα πρέπει να λύσετε είναι:

  1. Οι ασκήσεις 29, 32, 33, 35, 36, 37 του 3ου κεφαλαίου των σημειώσεων Δημητρακόπουλου.
  2. Δείξτε ότι αν το σύνολο $A \subseteq \NN$ είναι αναδρομικά απαριθμήσιμο και το $A^c = \NN\setminus A$ επίσης τότε το $A$ είναι αναδρομικό.
  3. Αποδείξτε ότι πρόβλημα τερματισμού δεν είναι αναδρομικό (υπολογίσιμο). Δείξτε δηλ. ότι δεν υπάρχει πρόγραμμα H(P, x) που να αποφασίζει αν το πρόγραμμα P εφαρμοσμένο στο input x τερματίζει ή όχι.
  4. Εξηγήστε γιατί το σύνολο των θεωρημάτων (αποδείξιμες προτάσεις) μιας πρωτοβάθμιας γλώσσας με αναδρομικό (υπολογίσιμο) σύνολο αξιωμάτων είναι αναδρομικά απαριθμήσιμο.
  5. Εξηγήστε γιατί αν μια πρωτοβάθμια γλώσσα είναι πλήρης και έχει αναδρομικό σύνολο αξιωμάτων τότε είναι και αποφασίσιμη, δηλ. το σύνολο των θεωρημάτων της είναι αναδρομικό.

Ημερολόγιο μαθήματος

Τετάρτη 17/5/2023

Σήμερα τελειώσαμε την απόδειξη της μη πληρότητας της πρωτοβάθμιας γλώσσας. Κατασκευάσαμε μια πρωτοβάθμια γλώσσα στην οποία το σύνολο των αποδείξιμων προτάσεων δεν είναι αναδρομικό (υπολογίσιμο). Ο τρόπος που το κάναμε αυτό είναι ότι για κάθε μηχανή Turing (για κάθε πρόγραμμα python αν προτιμάτε) κατασκευάσαμε μια πρόταση της γλώσσας (με αλγοριθμικό τρόπο δεδομένης της μηχανής Turing) η οποία είναι αποδείξιμη αν και μόνο αν η μηχανή Turing τερματίζει. Αφού γνωρίζουμε ότι το σύνολο των μηχανών Turing δεν είναι αναδρομικό το ίδιο ισχύει και για τις αποδείξιμες προτάσεις της γλώσσας μας (τα θεωρήματα της γλώσσας μας). Αν τώρα η γλώσσα μας ήταν πλήρης (δηλ. για κάθε πρόταση $p$ αποδεικνύεται είτε η $p$ είτε η $\neg p$) αυτό θα είχε ως συνέπεια τα θεωρήματα της γλώσσας μας να είναι αναδρομικό σύνολο (αφού πάντα τα θεωρήματα είναι αναδρομικά απαριθμήσιμα αλλά, λόγω της πληρότητας, και οι αρνήσεις τους είναι αναδρομικά απαριθμήσιμες).

Δευτέρα 15/5/2023

Η απόδειξη του θεωρήματος μη πληρότητας του Gödel που θα δούμε αυτή την εβδομάδα περνάει μέσα από τη μη υπολογισιμότητα του προβλήματος τερματισμού (Halting Problem) ενός προγράμματος. Κάναμε σήμερα λοιπόν μια γρήγορη εισαγωγή στην έννοια της υπολογισιμότητας, και στις σχετικές έννοιες των αναδρομικών και αναδρομικά απαριθμήσιμων συνόλων. Αποδείξαμε τη μη υπολογισιμότητα του προβλήματος τερματισμού.

Για τη σημερινή διάλεξη διαβάστε το Κεφ. 10 από το βιβλίο εδώ.

Δευτέρα 8/5/2023

Σήμερα είδαμε χωρίς απόδειξη μερικά από τα θεωρήματα της § 3.3 που αφορούν την αποδειξιμότητα στη γλώσσα $\mathcal{A}_1$ (θεωρήματα 3.3.1-3.3.6). Επίσης χωρίς απόδειξη είδαμε το θεώρημα εγκυρότητα (3.4.1) και το θεώρημα πληρότητας του Gödel (δεχτήκαμε το (α) και αποδείξαμε το (β) από αυτό και το θεώρημα εγκυρότητας). Είδαμε το Θεώρημα Συμπάγειας (3.4.3) και αναφέραμε κάποιες συνέπειές του όπως το Θεώρημα 3.4.4 και την Άσκ. 66 (ύπαρξη non-standard μοντέλου της θεωρία Peano). Δε θα ασχοληθούμε άλλο με το περιεχόμενο του Κεφ. 3 παρά θα προσπαθήσουμε την τελευταία εβδομάδα να μιλήσουμε για το θεώρημα μη πληρότητας του Gödel.

Τετάρτη 3/5/2023

Κάναμε μια μικρή επανάληψη στην έννοια της λογικής συνεπαγωγής και μετά αρχίσαμε να μιλάμε για τα αξιώματα (λογικά και μή) και τους κανόνες παραγωγής που προσθέτουμε σε μια πρωτοβάθμια γλώσσα με σκοπό να αποδεικνύουμε προτάσεις σε αυτή τη γλώσσα. Είδαμε αναλυτικά τα λογικά αξιώματα της πρωτοβάθμιας γλώσσας (αυτά που υπάρχουν πάντα δηλ.) και επίσης είδαμε τα (μη λογικά) αξιώματα Peano (στη γλώσσα της Θεωρίας Αριθμών) και κάποια από τα (μη λογικά) αξιώματα Zermelo-Fraenkel (στη γλώσσα τη Θεωρίας Συνόλων). Είδαμε επίσης αναλυτικά το παράδειγμα στο τέλος της σελ. 52 απόδειξης του τύπου $\forall x ( P(x) \to \exists y P(y))$ από τα λογικά αξιώματα της γλώσσας και τον κανόνα παραγωγής modus ponens.

Τετάρτη 26/4/2023

Σήμερα μιλήσαμε αρχικά για την έννοια της αποτίμησης σε μια δομή $\mathcal{A}$ της γλώσσας $\Gamma_1$. Αυτή είναι μια συνάρτηση $v$ από τις μεταβλητές της $\Gamma_1$ στο σύμπαν $\Abs{\mathcal{A}}$ της δομής. Αυτή η συνάρτηση $v$ επεκτείνεται και στους όρους της $\Gamma_1$ αλλά και δίνει και μια τιμή αλήθειας σε κάθε τύπο της $\Gamma_1$. Αν λοιπόν $\phi$ είναι ένας τύπος της $\Gamma_1$ ορίσαμε τι σημαίνει ότι ο τύπος $\phi$ αληθεύει για μια αποτίμηση $v$ της δομής $\mathcal{A}$ αυτό το συμβολίζουμε με $\mathcal{A} \models \phi [v]$. Αν ο $\phi$ δεν είναι απλά τύπος αλλά πρόταση (δηλ. δεν έχει ελεύθερες μεταβλητές) τότε $\mathcal{A} \models \phi [v]$ αν και μόνο αν $\mathcal{A} \models \phi [v]$ για οποιαδήποτε αποτίμηση $v$, αφού η $\phi$ δεν έχει ελεύθερες μεταβλητές. Αν η $\phi$ είναι λοιπόν πρόταση (ή σύνολο προτάσεων) τότε γράφουμε απλά $\mathcal{A} \models \phi$ χωρίς να αναφέρουμε μια αποτίμηση, και λέμε ότι η δομή $\mathcal{A}$ είναι μοντέλο της πρότασης $\phi$. Αν η $\phi$ είναι πρόταση τότε το να μην ισχύει $\mathcal{A} \models \phi$, να ισχύει δηλ. $\mathcal{A} \not\models \phi$, σημαίνει ότι υπάρχει αποτίμηση $v$ που να καθιστά την $\phi$ ψευδή, αλλά τότε αυτό σημαίνει ότι για κάθε αποτίμηση η πρόταση είναι ψευδής οπότε ισχύει $\mathcal{A} \models \neg \phi$. Στα δεξιά του συμβόλου $\models$ μπορούμε να βάλουμε και ένα σύνολο τύπων ή προτάσεων, με τον προφανή τρόπο να επεκτείνουμε το τι σημαίνει.

Αν $T$ είναι ένα σύνολο τύπων και $\phi$ τύπος τότε γράφουμε $T \models \phi$ αν για κάθε δομή $\mathcal{A}$ και αποτίμηση $v$ αν αληθεύει το $T$ για την $v$ αληθεύει και ο $\phi$. Το σύνολο $T$ μπορεί να είναι και κενό οπότε γράφουμε $\models \phi$ (και αυτό σημαίνει ότι για κάθε δομή $\mathcal{A}$ και αποτίμηση $v$ αληθεύει ο $\phi$).

Δευτέρα 24/4/2023

Μιλήσαμε σήμερα για τα διάφορα συστατικά μιας πρωτοβάθμιας γλώσσες (είδη από λέξεις που μπορούμε να φτιάξουμε με τα σύμβολα της γλώσσας). Είδαμε τις έννοιες της έκφρασης, του όρου, του τύπου και του ατομικού τύπου σε μια πρωτοβάθμια γλώσσα, τι σημαίνει για μια μεταβλητή να εμφανίζεται ελεύθερη ή δεσμευμένη σε ένα τύπο και τι σημαίνει πρόταση (τύπος με όλες τις μεταβλητές του δεσμευμένες). Είδαμε διάφορα παραδείγματα. Αρχίσαμε να μιλάμε για την έννοια της δομής ή ερμηνείας μιας πρωτοβάθμιας γλώσσας, που αποτελεί το πρώτο βήμα σύνδεσης των λέξεων της γλώσσας μας με την έννοια της αλήθειας και του ψεύδους, που μέχρι στιγμής δεν υπάρχει στη γλώσσα μας. Διαβάστε μέχρι και τη σελίδα 43 των σημειώσεων Δημητρακόπουλου.

Τετάρτη 5/4/2023

Σήμερα κάναμε την απόδειξη της συμπάγειας του προτασιακού λογισμού: αν ένα σύνολο τύπων είναι τέτοιο ώστε όλα τα πεπερασμένα υποσύνολά του να είναι ικανοποιήσιμα τότε όλο το σύνολο είναι ικανοποιήσιμο. Ισοδύναμα, αν ένα σύνολο τύπων δεν είναι ικανοποιήσιμο τότε κάποιο πεπερασμένο υποσύνολό του δεν είναι ικανοποιήσιμο (ένα σύνολο τύπων λέγεται ικανοποιήσιμο αν μπορούμε να δώσουμε μια λογική τιμή σε κάθε μεταβλητή που εμφανίζεται σε κάποιο τύπο του με τέτοιο τρόπο ώστε κάθε τύπος στο σύνολο να είναι αληθής). Είδαμε (ως κάποια απόδειξη που είναι κάπως παρεμφερής) το διαγώνιο επιχείρημα του Cantor για το ότι το διάστημα $(0, 1)$ δεν είναι αριθμήσιμο σύνολο. Κάναμε κάποια σχόλια για την υπολογιστική σημασία που έχει το πρόβλημα της ικανοποιησιμότητας ενός τύπου (satisfiability, NP-completeness). Τέλος, αρχίσαμε να μιλάμε για πρωτοβάθμιες γλώσσες. Είδαμε την τυπική τους δομή και αναφέραμε κάμποσα παραδείγματα γλωσσών (και αξιωμάτων) για τμήματα των Μαθηματικών (θεωρία γραμμικής διάταξης, θεωρία ομάδων, θεωρία αριθμών, θεωρία συνόλων).

Δευτέρα 3/4/2023

Σήμερα είδαμε μερικά πράγματα σχετικά με τον προτασιακό λογισμό, περισσότερο ως επανάληψη και ως δείγματα του πόσο έχει προχωρήσει το μάθημα μέχρι στιγμής. Είδαμε, π.χ., 1-2 τυπικές αποδείξεις στο αξιωματικό σύστημα $\mathcal{A}_0$ (που ορίζεται στη σελ. 25 των σημειώσεων). Επικεντρωθήκαμε κάπως στο θεώρημα της συμπάγειας (αν ένα σύνολο προτασιακών τύπων $S$ είναι τέτοιο ώστε κάθε πεπερασμένο υποσύνολό του είναι ικανοποιήσιμο τότε ολόκληρο το $S$ είναι ικανοποιήσιμο) και είδαμε ότι η συμπάγεια εμφανίζεται με διάφορες μορφές στα Μαθηματικά. Για παράδειγμα, μια έκφραση της συμπάγεις στην Ανάλυση είναι η πρόταση "κάθε ακολουθία $x_n \in [0, 1]$ έχει συγκλίνουσα υπακολουθία" (την αποδείξαμε αυτή την πρόταση). Μια άλλη μορφή που είδαμε είναι πώς, υποθέτοντας κανείς γνωστό το θεώρημα των 4ων χρωμάτων στη θεωρία γραφημάτων, το οποίο αναφέρεται σε χάρτες με πεπερασμένες στο πλήθος χώρες, μπορεί κανείς να αποδείξει το ίδιο αποτέλεσμα για χάρτες με άπειρες στο πλήθος χώρες. Αποδείξαμε και αυτό το θεώρημα με δύο τρόπους: στον πρώτο χρησιμοποιήσαμε το προηγούμενο (με τη συγκλίνουσα υπακολουθία) και στον δεύτερο κάναμε μια κατευθείαν απόδειξη.