Κανονικές μορφές

Στα προηγούμενα μαθήματα αυτής της ενότητας δόθηκε σημασία στους τύπους: το μάθημα για τη σημασιολογία της προτασιακής λογικής επέκτεινε κάθε αποτίμηση σε όλους τους τύπους· το μάθημα για τη σημασιολογική συνέπεια και ισοδυναμία όρισε την ισοδυναμία $\varphi \eqsem \psi$ και απέδειξε τη σημασιολογική αντικατάσταση· το μάθημα για τους γενικευμένους νόμους του Ντε Μόργκαν και τους επιμεριστικούς νόμους επέκτεινε αυτούς τους νόμους σε συζεύξεις και διαζεύξεις $n$ τύπων· και το μάθημα για τη συναρτησιακή πληρότητα έδειξε ότι κάθε συνάρτηση αληθείας παριστάνεται από κάποιον τύπο. Ωστόσο, μια συνάρτηση αληθείας παριστάνεται από άπειρους τύπους, που μπορεί να διαφέρουν πολύ μεταξύ τους: οι $(v_1 \rightarrow v_2)$, $\neg(v_1 \wedge \neg v_2)$ και $(((v_1 \downarrow v_1) \downarrow v_2) \downarrow ((v_1 \downarrow v_1) \downarrow v_2))$ είναι τρία ονόματα του ίδιου πράγματος. Αν αυτό ισχύει, συμφέρει να επιλέξουμε σε κάθε κλάση ισοδυναμίας έναν αντιπρόσωπο σταθερής μορφής, που να διαβάζεται χωρίς κόπο και με τον οποίο ορισμένα ερωτήματα να απαντώνται με μια ματιά. Αυτό είναι οι κανονικές μορφές.

Λεκτικά, φράσεις και κανονικές μορφές

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

Στο ίδιο μάθημα αποδείχθηκε ότι η σειρά και η ομαδοποίηση των όρων δεν αλλάζουν τον τύπο, με την επιφύλαξη της ισοδυναμίας (γενικευμένη προσεταιριστικότητα και ανεξαρτησία από τη σειρά και από τις επαναλήψεις)· γι’ αυτό θα γράφουμε επίσης $\varphi_1 \wedge \varphi_2 \wedge \cdots \wedge \varphi_n$ χωρίς παρενθέσεις, εννοώντας την ομαδοποίηση από αριστερά.

Ένα λεκτικό είναι μια μεταβλητή $v_n$, που λέγεται θετικό λεκτικό, ή η άρνηση $\neg v_n$ μιας μεταβλητής, που λέγεται αρνητικό λεκτικό. Το αντίθετο ενός λεκτικού $\ell$, που το γράφουμε $\ell^{*}$, είναι το λεκτικό της ίδιας μεταβλητής με το άλλο πρόσημο:

Από τον ορισμό έπεται ότι $(\ell^{*})^{*} = \ell$. Δύο λεκτικά σχηματίζουν ένα συμπληρωματικό ζεύγος αν το ένα είναι το αντίθετο του άλλου, όπως τα $v_3$ και $\neg v_3$.

Μια φράση είναι μια διάζευξη λεκτικών, $\bigvee_{j=1}^{k} \ell_j$, και μια στοιχειώδης σύζευξη είναι μια σύζευξη λεκτικών, $\bigwedge_{j=1}^{k} \ell_j$, με $k \geq 1$ και στις δύο περιπτώσεις· ένα λεκτικό μόνο του είναι, επομένως, ταυτόχρονα φράση και στοιχειώδης σύζευξη. Λέμε ότι ένα λεκτικό βρίσκεται σε μια φράση ή σε μια στοιχειώδη σύζευξη αν είναι ένα από τα $\ell_j$ της.

Ένας τύπος βρίσκεται σε διαζευκτική κανονική μορφή αν είναι διάζευξη στοιχειωδών συζεύξεων, και σε συζευκτική κανονική μορφή αν είναι σύζευξη φράσεων· δηλαδή, αν είναι, αντίστοιχα, της μιας από τις δύο παρακάτω μορφές, όπου οι $m$ και $k_1, \ldots, k_m$ είναι φυσικοί αριθμοί και κάθε $\ell_{i,j}$ είναι λεκτικό:

Θα λέμε ότι ο $\Phi$ είναι μια διαζευκτική κανονική μορφή του $\varphi$ αν βρίσκεται σε διαζευκτική κανονική μορφή και $\varphi \eqsem \Phi$, και ομοίως για τη συζευκτική. Τα μήκη $k_i$ μπορεί να διαφέρουν από μια σύζευξη (ή φράση) σε άλλη: αν απαιτούσαμε τον ίδιο αριθμό λεκτικών σε όλες, θα έπρεπε να συμπληρώνουμε με επαναλήψεις, χωρίς να προσθέτουμε τίποτα.

Αξίζει να σταθούμε σε ό,τι σημαίνει «βρίσκομαι σε κανονική μορφή». Είναι ιδιότητα της συμβολοσειράς κύκλων και δίσκων, όχι της σημασίας της: το μάθημα για την επαγωγή στους φυσικούς αριθμούς και στους τύπους απέδειξε τη μονοσήμαντη ανάγνωση, ώστε το ερώτημα αν ένας τύπος είναι διάζευξη, και ποιων τύπων, έχει μία μόνο απάντηση. Ωστόσο, οι επίσημες συντομογραφίες κάνουν ορισμένους τύπους να βρίσκονται σε κανονική μορφή χωρίς να το δείχνουν. Η συνεπαγωγή $(v_1 \rightarrow v_2)$ ορίζεται ως $(\neg v_1 \vee v_2)$: δεν είναι ότι είναι ισοδύναμη με αυτή τη φράση, αλλά ότι είναι η ίδια αυτή συμβολοσειρά, και επομένως βρίσκεται ήδη σε κανονική μορφή. Πιο αιφνιδιαστική είναι η διπλή άρνηση. Από τους ορισμούς του $\neg$ και του $\vee$, η συμβολοσειρά $(\varphi \vee \varphi)$ είναι η $\neg(\varphi \downarrow \varphi)$, δηλαδή η $\neg\neg\varphi$· επομένως ο $\neg\neg v_1$ δεν είναι λεκτικό, αλλά είναι, γράμμα προς γράμμα, η φράση $(v_1 \vee v_1)$.

Η τιμή των συζεύξεων και των διαζεύξεων

Από το μάθημα για τη σημασιολογία λαμβάνονται οι τιμές των παράγωγων συνδέσμων: $v(\neg\varphi) = 1 - v(\varphi)$· $v(\varphi \wedge \psi) = v(\varphi)\,v(\psi)$, που παίρνει την τιμή $1$ αν και μόνο αν και οι δύο παίρνουν την τιμή $1$· και $v(\varphi \vee \psi) = 0$ αν και μόνο αν και οι δύο παίρνουν την τιμή $0$. Το μάθημα για τους γενικευμένους νόμους του Ντε Μόργκαν και τους επιμεριστικούς νόμους τις επέκτεινε σε $n$ τύπους, με επαγωγή στο πλήθος των όρων, στο λήμμα της τιμής: για κάθε αποτίμηση $v$, η σύζευξη $\bigwedge_{i=1}^{n} \varphi_i$ παίρνει την τιμή $1$ στην $v$ αν και μόνο αν κάθε $\varphi_i$ παίρνει την τιμή $1$ στην $v$, και η διάζευξη $\bigvee_{i=1}^{n} \varphi_i$ παίρνει την τιμή $1$ στην $v$ αν και μόνο αν κάποιος $\varphi_i$ παίρνει την τιμή $1$ στην $v$. Αυτό το λήμμα, που εδώ παραθέτεται χωρίς να επαναληφθεί η απόδειξή του, είναι το εργαλείο με το οποίο υπολογίζεται η τιμή οποιασδήποτε κανονικής μορφής.

Η δεύτερη περίπτωση εύκολα παραβλέπεται: όταν αρνούμαστε μια κανονική μορφή, τείνουμε να γράφουμε $\neg\ell_{i,j}$ στη θέση ενός λεκτικού, και ο $\neg\neg v_n$ δεν είναι λεκτικό. Η διπλή άρνηση είναι εκείνη που επιστρέφει το αποτέλεσμα στο καλούπι.