Μεταθεωρία: εισαγωγή

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

1. Ερώτηση 1Από προηγούμενες ενότητεςΤι σημαίνει $\Gamma \models \varphi$;

   Ότι κάθε αποτίμηση που ικανοποιεί όλους τους τύπους του $\Gamma$ ικανοποιεί τον $\varphi$.

   Ότι υπάρχει μια παραγωγή του $\varphi$ από το $\Gamma$.

   Ότι κάποια αποτίμηση ικανοποιεί ταυτόχρονα το $\Gamma$ και τον $\varphi$.

   Ότι ο $\varphi$ είναι συνέπεια κάποιου τύπου του $\Gamma$ παρμένου μόνου του.

2. Ερώτηση 2Από προηγούμενες ενότητεςΠοιος από τους παρακάτω ισχυρισμούς είναι ισοδύναμος με το $\Gamma \models \varphi$;

   Ότι το $\Gamma \cup \{\neg\varphi\}$ είναι μη ικανοποιήσιμο.

   Ότι το $\Gamma \cup \{\varphi\}$ είναι ικανοποιήσιμο.

   Ότι το $\Gamma \cup \{\neg\varphi\}$ είναι ικανοποιήσιμο.

   Ότι ο $\neg\varphi$ είναι μη ικανοποιήσιμος.

3. Ερώτηση 3Από προηγούμενες ενότητεςΑν μια αποτίμηση $v$ δίνει στον $\alpha$ την τιμή $1$, ποια τιμή δίνει στον $(\alpha \downarrow \beta)$;

   $0$, όποια κι αν είναι η τιμή του $\beta$.

   Εξαρτάται από τον $\beta$: έχει τιμή $1$ αν ο $\beta$ έχει τιμή $0$.

   $1 - v(\beta)$.

   $1$, γιατί μία από τις συνιστώσες είναι αληθής.

4. Ερώτηση 4Από προηγούμενες ενότητεςΟι μεταβλητές του $\varphi$ είναι οι $v_{2}$ και $v_{7}$. Δύο αποτιμήσεις $v$ και $w$ δίνουν τις ίδιες τιμές στη $v_{2}$ και στη $v_{7}$, και αντίθετες τιμές σε όλες τις άλλες μεταβλητές. Αν $v(\varphi) = 1$, τι μπορεί να βεβαιωθεί για την $w(\varphi)$;

   Ότι $w(\varphi) = 1$.

   Τίποτα, γιατί οι $v$ και $w$ διαφέρουν σε άπειρες μεταβλητές.

   Ότι $w(\varphi) = 0$, γιατί η $w$ αντιστρέφει σχεδόν όλες τις τιμές της $v$.

   Ότι $w(\varphi) = 1$ μόνο αν οι $v$ και $w$ συμπίπτουν επίσης στις $v_{1}, \ldots, v_{6}$.

5. Ερώτηση 5Από προηγούμενες ενότητεςΈστω $\Gamma$ ένα άπειρο σύνολο τύπων τέτοιο ώστε $\Gamma \vdash \varphi$. Τι μπορεί να βεβαιωθεί;

   Ότι κάποιο πεπερασμένο υποσύνολο του $\Gamma$ παράγει τον $\varphi$.

   Ότι ο $\varphi$ είναι θεώρημα.

   Ότι η παραγωγή χρησιμοποιεί όλους τους τύπους του $\Gamma$.

   Τίποτα χωρίς το θεώρημα της συμπάγειας, γιατί το $\Gamma$ είναι άπειρο.

6. Ερώτηση 6Από προηγούμενες ενότητεςΓνωρίζουμε ότι $\Gamma \cup \{p\} \vdash \chi$ και ότι $\Gamma \cup \{\neg p\} \vdash \chi$. Τι επιτρέπει να συμπεράνουμε η απόδειξη κατά περιπτώσεις;

   Ότι $\Gamma \vdash \chi$.

   Τίποτα, όσο δεν γνωρίζουμε αν το $\Gamma$ παράγει τον $p$ ή παράγει τον $\neg p$.

   Ότι $\Gamma \vdash (p \leftrightarrow \chi)$.

   Μόνο ότι $\Gamma \cup \{p, \neg p\} \vdash \chi$.

7. Ερώτηση 7Το σύστημα του κύκλου μαθημάτων είναι ορθό. Τι βεβαιώνει αυτή η ιδιότητα;

   Ότι, για κάθε σύνολο $\Gamma$, αν $\Gamma \vdash \varphi$, τότε $\Gamma \models \varphi$.

   Ότι αν $\Gamma \models \varphi$, τότε $\Gamma \vdash \varphi$.

   Ότι δεν υπάρχει κανένας τύπος $\varphi$ με $\vdash \varphi$ και $\vdash \neg\varphi$.

   Ότι κάθε αληθής τύπος είναι θεώρημα.

8. Ερώτηση 8Έστω $v$ η αποτίμηση που δίνει $1$ στη $p$ και $0$ στη $q$. Τι βεβαιώνει το λήμμα του Καλμάρ, με τις μεταβλητές $p$ και $q$, για τον τύπο $(p \leftrightarrow q)$;

   Ότι $\{p, \neg q\} \vdash \neg(p \leftrightarrow q)$.

   Ότι $\{p, \neg q\} \vdash (p \leftrightarrow q)$.

   Ότι $\{p, q\} \vdash \neg(p \leftrightarrow q)$.

   Ότι $\vdash \neg(p \leftrightarrow q)$.

9. Ερώτηση 9Μπορεί ένα παραγωγικό σύστημα να είναι ορθό χωρίς να είναι πλήρες;

   Ναι: το σύστημα του Λουκασέβιτς, χωρίς τον κανόνα ΑΔΑ, είναι ορθό και δεν παράγει την ταυτολογία $((v_{1} \downarrow v_{2}) \rightarrow \neg v_{1})$.

   Όχι: η ορθότητα και η πληρότητα συνάγονται η μία από την άλλη.

   Όχι: ένα σύστημα του οποίου τα αξιώματα είναι ταυτολογίες παράγει όλες τις ταυτολογίες.

   Ναι, αλλά μόνο αν το σύστημα είναι αντιφατικό.

10. Ερώτηση 10Τι βεβαιώνει το θεώρημα της συμπάγειας;

    Ότι ένα σύνολο τύπων είναι ικανοποιήσιμο αν και μόνο αν κάθε πεπερασμένο υποσύνολό του είναι ικανοποιήσιμο.

    Ότι ένα σύνολο τύπων είναι ικανοποιήσιμο αν και μόνο αν καθένας από τους τύπους του είναι ικανοποιήσιμος.

    Ότι κάθε άπειρο σύνολο τύπων είναι ικανοποιήσιμο.

    Ότι ένα σύνολο είναι ικανοποιήσιμο αν κάποιο πεπερασμένο υποσύνολό του είναι.

11. Ερώτηση 11Έστω $\Gamma$ ένα άπειρο σύνολο τύπων τέτοιο ώστε $\Gamma \models \varphi$. Τι εξασφαλίζει η συμπάγεια;

    Ότι $\Gamma_{0} \models \varphi$ για κάποιο πεπερασμένο υποσύνολο $\Gamma_{0}$ του $\Gamma$.

    Ότι ο $\varphi$ είναι συνέπεια κάποιου τύπου του $\Gamma$ παρμένου μόνου του.

    Ότι ο $\varphi$ είναι συνέπεια κάθε πεπερασμένου υποσυνόλου του $\Gamma$.

    Ότι ο $\varphi$ είναι έγκυρος.

12. Ερώτηση 12Το πρώτο μάθημα αποδεικνύει την πληρότητα για πεπερασμένα σύνολα υποθέσεων. Γιατί δεν αρκεί ο πεπερασμένος χαρακτήρας της παραγωγής για να την επεκτείνει σε ένα άπειρο σύνολο $\Gamma$;

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

    Αρκεί: αν $\Gamma \models \varphi$, ο πεπερασμένος χαρακτήρας δίνει ένα πεπερασμένο $\Gamma_{0}$ με $\Gamma_{0} \models \varphi$.

    Γιατί το λήμμα του Καλμάρ δεν ισχύει για τύπους με άπειρες μεταβλητές.

    Γιατί η πληρότητα είναι ψευδής για άπειρα σύνολα υποθέσεων.

13. Ερώτηση 13Ποια είναι η επιλύουσα των φράσεων $\{p, \neg q, r\}$ και $\{q, s\}$;

    $\{p, r, s\}$.

    $\{p, \neg q, r, q, s\}$.

    $\{p, r\}$.

    Δεν έχουν επιλύουσα, γιατί δεν έχουν κανένα κοινό λεκτικό.

14. Ερώτηση 14Για να αποφασίσουμε με επίλυση αν $\{(p \vee q), \neg p\} \models q$, ποιο σύνολο φράσεων προσπαθούμε να διαψεύσουμε;

    $\{\{p, q\}, \{\neg p\}, \{\neg q\}\}$.

    $\{\{p, q\}, \{\neg p\}, \{q\}\}$.

    $\{\{p, q\}, \{\neg p\}\}$.

    $\{\{\neg p, \neg q\}, \{p\}, \{\neg q\}\}$.

15. Ερώτηση 15Μπορεί να συναχθεί με επίλυση η κενή φράση $\Box$ από το σύνολο $\{\{p, q\}, \{\neg p, \neg q\}\}$;

    Όχι: το σύνολο είναι ικανοποιήσιμο, και η επίλυση είναι ορθή.

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

    Ναι, σε δύο βήματα: πρώτα ως προς $p$ και έπειτα ως προς $q$.

    Όχι, γιατί καμία από τις δύο φράσεις δεν είναι μοναδιαία.