Σημασιολογική συνέπεια και ισοδυναμία

Τι χρησιμοποιείται από το προηγούμενο μάθημα

Το μάθημα για τη σημασιολογία της προτασιακής λογικής έδωσε νόημα στους τύπους, και το παρόν μάθημα το θεωρεί γνωστό. Μια αποτίμηση είναι μια συνάρτηση $v\colon V \to \{0, 1\}$, που αναθέτει σε κάθε μεταβλητή μια τιμή αλήθειας, $1$ (αληθές) ή $0$ (ψευδές). Με το θεώρημα του ορισμού με αναδρομή πάνω στους τύπους, από το μάθημα για την επαγωγή, κάθε αποτίμηση επεκτείνεται με έναν μοναδικό τρόπο σε όλους τους τύπους μέσω του όρου της κοινής άρνησης, του μόνου που χρειάζεται, επειδή η γλώσσα έχει έναν μόνο σύνδεσμο:

Λόγω της μοναδικότητας της επέκτασης, γράφουμε $v(\varphi)$ και για την τιμή της επέκτασης· το γράμμα $v$ χωρίς δείκτη δηλώνει πάντοτε μια αποτίμηση (και τα $v'$, $w$, $u$, άλλες), ενώ οι μεταβλητές φέρουν πάντοτε τον δείκτη τους. Όπως στο μάθημα για την τυποποίηση, τα $p$, $q$, $r$, $s$ και $t$ ονομάζουν τις μεταβλητές $v_1$ έως $v_5$, και το $V(\varphi)$ είναι το σύνολο των μεταβλητών του $\varphi$. Λέμε ότι η $v$ ικανοποιεί τον $\varphi$, και γράφουμε $v \models \varphi$, όταν $v(\varphi) = 1$, και ότι τον διαψεύδει, $v \not\models \varphi$, όταν $v(\varphi) = 0$. Ένας τύπος είναι έγκυρος (ή ταυτολογία), και γράφουμε $\models \varphi$, αν κάθε αποτίμηση τον ικανοποιεί· ικανοποιήσιμος, αν κάποια τον ικανοποιεί· μη ικανοποιήσιμος (ή αντίφαση), αν καμία δεν τον ικανοποιεί· ενδεχομενικός, αν είναι ικανοποιήσιμος χωρίς να είναι έγκυρος. Μια αποτίμηση ικανοποιεί ένα σύνολο $\Gamma$ τύπων, $v \models \Gamma$, όταν ικανοποιεί καθέναν από αυτούς, και το $\Gamma$ είναι ικανοποιήσιμο αν κάποια αποτίμηση το ικανοποιεί και μη ικανοποιήσιμο στην αντίθετη περίπτωση. Τέλος, $\top := (v_1 \rightarrow v_1)$ και $\bot := \neg\top$, ώστε $v(\top) = 1$ και $v(\bot) = 0$ για κάθε αποτίμηση.

Από εκείνο το μάθημα χρησιμοποιούνται επιπλέον δύο αποτελέσματα. Το πρώτο είναι το λήμμα σύμπτωσης: αν δύο αποτιμήσεις συμπίπτουν στις μεταβλητές του $\varphi$, συμπίπτουν στον $\varphi$· εξαιτίας του, η τιμή ενός τύπου με $n$ μεταβλητές εξαρτάται μόνο από $2^{n}$ συνδυασμούς, και ο πίνακας αληθείας του είναι πεπερασμένος. Το δεύτερο είναι το θεώρημα των τιμών των παράγωγων συνδέσμων, που υπολογίζει από τις επίσημες συντομογραφίες την τιμή κάθε συνδέσμου ως πολυώνυμο στις τιμές των συνιστωσών. Αν $a = v(\varphi)$ και $b = v(\psi)$:

Οι αποδείξεις αυτού του μαθήματος συνίστανται, σχεδόν όλες, στη σύγκριση τιμών αλήθειας, και αυτά τα πολυώνυμα επιτρέπουν να γίνεται με έναν υπολογισμό αντί για μια διάσχιση περιπτώσεων. Ο μόνος πρόσθετος κανόνας τους είναι ότι οι $0$ και $1$ είναι οι μόνοι αριθμοί που συμπίπτουν με το τετράγωνό τους: αν ο $x$ ισούται με $0$ ή $1$, τότε $x^{2} = x$ και $x(1 - x) = 0$. Αξίζει, επιπλέον, να έχουμε πρόχειρες τρεις άλλες γραφές των ίδιων τιμών, που προκύπτουν αναπτύσσοντας τα γινόμενα:

Η πρώτη είναι ο όρος της κοινής άρνησης (το γινόμενο του $1 - a$ και του $1 - b$ ισούται με $1$ ακριβώς όταν $a = b = 0$)· η δεύτερη λέει ότι η διάζευξη ισούται με $0$ μόνο αν και οι δύο συνιστώσες ισούνται με $0$· η τρίτη, ότι η διπλή συνεπαγωγή ισούται με $1$ αν $a = b$ (επειδή $1 - 2a + 2a^{2} = 1$) και με $0$ αν $a \neq b$ (επειδή τότε $a + b = 1$ και $ab = 0$).