Σημασιολογία: εισαγωγή

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

1. Ερώτηση 1Από προηγούμενες ενότητεςΜια συνάρτηση πάνω στους τύπους ορίζεται αν δοθεί η τιμή της σε κάθε μεταβλητή και ένας κανόνας που υπολογίζει την τιμή της στον $\sigI\varphi\psi$ από τον $\varphi$, από τον $\psi$ και από τις τιμές της και στους δύο. Τι εξασφαλίζει ότι έτσι ορίζεται ακριβώς μία συνάρτηση;

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

   Ότι ο κανόνας επιστρέφει πάντοτε $0$ ή $1$.

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

   Ότι και οι συντομογραφίες $\neg$, $\vee$ και $\wedge$ έχουν μονοσήμαντη ανάγνωση.

2. Ερώτηση 2Από προηγούμενες ενότητεςΜε τις επίσημες συντομογραφίες του κύκλου μαθημάτων, ποιος τύπος είναι ο $(\varphi \vee \varphi)$;

   Η ίδια συμβολοσειρά με τον $\neg\neg\varphi$.

   Ο ίδιος ο $\varphi$, λόγω της ταυτοδυναμίας.

   $(\varphi \downarrow \varphi)$.

   Κανένας: μια διάζευξη απαιτεί δύο διαφορετικούς τύπους.

3. Ερώτηση 3Από προηγούμενες ενότητεςΓια να αποδειχθεί με επαγωγή στην πολυπλοκότητα ότι όλοι οι τύποι έχουν μια ορισμένη ιδιότητα, ποιες περιπτώσεις πρέπει να εξεταστούν;

   Οι μεταβλητές και ο μοναδικός κανόνας σχηματισμού, $\sigI\varphi\psi$, δηλαδή $(\varphi \downarrow \psi)$.

   Οι μεταβλητές, η άρνηση, η σύζευξη και η διάζευξη.

   Μόνο ο κανόνας $(\varphi \downarrow \psi)$: οι μεταβλητές είναι μια ειδική περίπτωσή του.

   Οι μεταβλητές και οι έξι σύνδεσμοι $\neg$, $\vee$, $\wedge$, $\rightarrow$, $\leftrightarrow$ και $\veebar$.

4. Ερώτηση 4Από προηγούμενες ενότητεςΌταν υποκαθιστούμε τον τύπο $\alpha$ με τον τύπο $\beta$ στον $\varphi$, σύμφωνα με τον ορισμό του μαθήματος για την επαγωγή, ποιες εμφανίσεις του $\alpha$ αλλάζουν;

   Όλες οι εμφανίσεις του ως υποτύπου, ταυτόχρονα.

   Μόνο η πρώτη, αν διαβάσουμε τη συμβολοσειρά από αριστερά προς τα δεξιά.

   Μόνο όσες φαίνονται στη συντομευμένη γραφή.

   Οι εμφανίσεις του $\alpha$ και, έπειτα, όσες εμφανιστούν στα αντίγραφα του $\beta$.

5. Ερώτηση 5Μια αποτίμηση δίνει στην $p$ την τιμή $0$ και στην $q$ την τιμή $1$. Αν ο $(\varphi \downarrow \psi)$ έχει τιμή $1$ ακριβώς όταν οι $\varphi$ και $\psi$ έχουν τιμή $0$, ποια τιμή παίρνει ο τύπος $(p \downarrow (q \downarrow p))$;

   $1$.

   $0$, γιατί η $q$ έχει τιμή $1$.

   Δεν μπορεί να υπολογιστεί χωρίς να γνωρίζουμε τις τιμές των άλλων μεταβλητών.

   Εξαρτάται από το πώς ομαδοποιούνται οι συνιστώσες.

6. Ερώτηση 6Τι σημαίνει $\not\models \varphi$;

   Ότι κάποια αποτίμηση δίνει στον $\varphi$ την τιμή $0$: ο $\varphi$ δεν είναι έγκυρος.

   Ότι ο $\varphi$ είναι αντίφαση.

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

   Ότι ο $\varphi$ δεν είναι παραγώγιμος στο σύστημα του κύκλου μαθημάτων.

7. Ερώτηση 7Γνωρίζουμε ότι $\Gamma \cup \{\varphi\} \models \psi$: κάθε αποτίμηση που ικανοποιεί το $\Gamma$ και τον $\varphi$ ικανοποιεί τον $\psi$. Τι έπεται;

   $\Gamma \models (\varphi \rightarrow \psi)$.

   $\Gamma \models \psi$.

   $\Gamma \models (\psi \rightarrow \varphi)$.

   $\models (\varphi \rightarrow \psi)$.

8. Ερώτηση 8Ο τύπος $(v_{1} \vee \neg v_{1})$ είναι έγκυρος. Ποιος από τους ακόλουθους τύπους είναι έγκυρος λόγω του θεωρήματος ομοιόμορφης υποκατάστασης;

   $(\neg v_{2} \vee \neg\neg v_{2})$.

   $(v_{1} \vee \neg v_{2})$.

   $(\neg v_{2} \vee \neg v_{3})$.

   Κανένας: η ομοιόμορφη υποκατάσταση επιτρέπει μόνο να αλλάζουν κάποιες μεταβλητές με άλλες.

9. Ερώτηση 9Σύμφωνα με τη σύμβαση του κύκλου μαθημάτων, ποιον τύπο δηλώνει η έκφραση $v_{1} \wedge v_{2} \wedge v_{3}$, γραμμένη χωρίς παρενθέσεις;

   $((v_{1} \wedge v_{2}) \wedge v_{3})$.

   $(v_{1} \wedge (v_{2} \wedge v_{3}))$.

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

   Κανένας: χωρίς παρενθέσεις η έκφραση δεν δηλώνει τίποτα.

10. Ερώτηση 10Μια συνάρτηση αληθείας δύο ορισμάτων αποδίδει μια τιμή, $0$ ή $1$, σε καθεμία από τις τέσσερις γραμμές $(1, 1)$, $(1, 0)$, $(0, 1)$ και $(0, 0)$. Πόσες συναρτήσεις αληθείας δύο ορισμάτων υπάρχουν;

11. Ερώτηση 11Μπορεί ένας τύπος γραμμένος μόνο με $\wedge$ και $\vee$ από τις μεταβλητές να έχει τιμή $0$ στην αποτίμηση που δίνει $1$ σε όλες τις μεταβλητές;

    Όχι: κάθε τύπος γραμμένος μόνο με $\wedge$ και $\vee$ έχει τιμή $1$ σε αυτή την αποτίμηση.

    Ναι, αν φωλιαστούν αρκετές συζεύξεις και διαζεύξεις.

    Ναι: αφού η κοινή άρνηση αρκεί μόνη της, αρκούν και η σύζευξη και η διάζευξη.

    Δεν μπορεί να το ξέρει κανείς χωρίς να γράψει τον πίνακα κάθε τύπου.

12. Ερώτηση 12Ένα λεκτικό είναι μια μεταβλητή ή η άρνηση μιας μεταβλητής. Ποιος από τους ακόλουθους τύπους είναι λεκτικό;

    $\neg v_{2}$.

    $\neg\neg v_{1}$.

    $(v_{1} \wedge v_{2})$.

    $\top$.

13. Ερώτηση 13Είναι έγκυρη η συζευκτική κανονική μορφή $(\neg v_{1} \vee v_{2} \vee v_{1}) \wedge (v_{3} \vee \neg v_{2})$;

    Όχι: η δεύτερη φράση δεν περιέχει κανένα συμπληρωματικό ζεύγος, και η αποτίμηση που δίνει $0$ στην $v_{3}$ και $1$ στην $v_{2}$ τη διαψεύδει.

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

    Ναι, γιατί είναι ικανοποιήσιμη.

    Δεν μπορεί να κριθεί χωρίς έναν πίνακα οκτώ γραμμών.

14. Ερώτηση 14Για να φέρουμε έναν τύπο σε διαζευκτική κανονική μορφή, επιμερίζουμε τη σύζευξη ως προς τη διάζευξη. Ποιος είναι ο σωστός κανόνας;

    $(\varphi \wedge (\psi \vee \chi)) \longmapsto ((\varphi \wedge \psi) \vee (\varphi \wedge \chi))$.

    $(\varphi \wedge (\psi \vee \chi)) \longmapsto ((\varphi \wedge \psi) \vee (\varphi \vee \chi))$.

    $(\varphi \wedge (\psi \vee \chi)) \longmapsto ((\varphi \vee \psi) \wedge (\varphi \vee \chi))$.

    $(\varphi \wedge (\psi \vee \chi)) \longmapsto ((\varphi \wedge \psi) \vee \chi)$.

15. Ερώτηση 15Ένα κύκλωμα έχει δύο ευθείς διακόπτες, των μοχλών $p$ και $q$, συνδεδεμένους σε σειρά, και αυτό το μπλοκ είναι συνδεδεμένο παράλληλα με έναν ευθύ διακόπτη του μοχλού $r$. Ποιος τύπος λέει πότε άγει;

    $((p \wedge q) \vee r)$.

    $((p \vee q) \wedge r)$.

    $((p \wedge q) \wedge r)$.

    $((p \vee q) \vee r)$.