Μετάβαση στο περιεχόμενο
Topos Uranos
Ελληνικά

Γενικευμένοι νόμοι του Ντε Μόργκαν και επιμεριστικοί νόμοι

Περίληψη

Οι νόμοι του Ντε Μόργκαν και οι επιμεριστικοί νόμοι διατυπώθηκαν ως εδώ για δύο όρους· οι κανονικές μορφές, αντίθετα, συγκεντρώνουν συζεύξεις και διαζεύξεις οποιουδήποτε πλήθους όρων, και τους απαιτούν σε αυτή τη γενικότητα. Αυτό το μάθημα ορίζει με αναδρομή τη σύζευξη και τη διάζευξη μιας λίστας τύπων (φ1,…,φn)(\varphi_1, \ldots, \varphi_n), που γράφονται ⋀i=1nφi\bigwedge_{i=1}^{n} \varphi_i και ⋁i=1nφi\bigvee_{i=1}^{n} \varphi_i, με προσεταιρισμό από αριστερά, και αποδεικνύει με επαγωγή στο πλήθος των όρων το λήμμα της τιμής (μια σύζευξη είναι αληθής αν και μόνο αν είναι αληθείς όλοι οι όροι της· μια διάζευξη, αν και μόνο αν είναι αληθής κάποιος), τη γενικευμένη προσεταιριστικότητα, που επιτρέπει την αναομαδοποίηση, την ανεξαρτησία από τη σειρά και από τις επαναλήψεις, τους γενικευμένους νόμους του Ντε Μόργκαν και τη γενικευμένη επιμεριστικότητα στη μορφή που θα χρησιμοποιήσει το μάθημα των κανονικών μορφών: η σύζευξη δύο διαζεύξεων, με nn και με mm όρους, είναι ισοδύναμη με τη διάζευξη των nmnm συζεύξεων ενός όρου από την καθεμία, και δυϊκά. Τα προβλήματα μετρούν αποτιμήσεις, εντοπίζουν το σφάλμα μιας απόδειξης που παρουσιάζει μια αναομαδοποίηση ως ορισμό, μετρούν την αύξηση που προκαλεί ένας επιμερισμός και αντλούν από αυτόν μια ταυτολογία 2n2^n όρων.

Μαθησιακοί στόχοι

  1. Να γράφει συζεύξεις και διαζεύξεις nn όρων με τον συμβολισμό ⋀\bigwedge και ⋁\bigvee, να τις αναπτύσσει ως συμβολοσειρές με προσεταιρισμό από αριστερά και να υπολογίζει την τιμή αλήθειάς τους με το λήμμα της τιμής.
  2. Να αποδεικνύει με επαγωγή στο πλήθος των όρων τη γενικευμένη προσεταιριστικότητα, την ανεξαρτησία από τη σειρά και από τις επαναλήψεις και τους γενικευμένους νόμους του Ντε Μόργκαν, διακρίνοντας σε κάθε βήμα την ταυτότητα συμβολοσειρών από τη σημασιολογική ισοδυναμία.
  3. Να αποδεικνύει τη γενικευμένη επιμεριστικότητα και τη δυϊκή της, οργανώνοντας την επαγωγή σε δύο δείκτες, και να μετρά τους όρους που παράγει ένας επιμερισμός.
  4. Να εντοπίζει το σφάλμα μιας απόδειξης με επαγωγή της οποίας η βάση είναι λάθος γραμμένη ή της οποίας το βήμα κρύβει μια αναομαδοποίηση, και να τη διορθώνει.

Νόμοι για οποιοδήποτε πλήθος όρων

Το μάθημα για τη σημασιολογική συνέπεια και ισοδυναμία καθιέρωσε τους νόμους ισοδυναμίας για δύο όρους: ανάμεσά τους, την αντιμεταθετικότητα και την προσεταιριστικότητα της ∧\wedge και της ∨\vee, τους νόμους του Ντε Μόργκαν και τις δύο επιμεριστικότητες. Ωστόσο, ένας τύπος σε διαζευκτική κανονική μορφή είναι μια διάζευξη συζεύξεων, η καθεμία με όσους όρους χρειάζονται, και η μετατροπή ενός τύπου σε αυτή τη μορφή απαιτεί να αρνούμαστε, να αναομαδοποιούμε και να επιμερίζουμε συζεύξεις και διαζεύξεις οποιουδήποτε μήκους. Αν αυτό ισχύει, οι δυαδικοί νόμοι δεν αρκούν όπως είναι: πρέπει να επεκταθούν σε nn όρους, και αυτό να γίνει μονομιάς για όλα τα nn.

Για κάθε σταθερό nn, ο νόμος του Ντε Μόργκαν με nn όρους θα μπορούσε να επαληθευτεί με έναν πίνακα αληθείας 2n2^n γραμμών, γραμμένο με nn μεταβλητές, και η ομοιόμορφη υποκατάσταση του προηγούμενου μαθήματος, εφαρμοσμένη στη διπλή συνεπαγωγή ανάμεσα στα δύο μέλη, θα τον επέκτεινε σε οποιουσδήποτε τύπους. Όμως οι τιμές του nn είναι άπειρες, και κανένα πλήθος πινάκων δεν τις εξαντλεί. Έπεται ότι ο ισχυρισμός «για κάθε nn» δεν είναι μια ισοδυναμία ανάμεσα σε δύο τύπους, αλλά μια πρόταση για άπειρες ισοδυναμίες, διατυπωμένη στη μεταγλώσσα· η απόδειξή του είναι, όπως εκείνες του μαθήματος για την επαγωγή στους φυσικούς αριθμούς και στους τύπους, μια εξωτερική απόδειξη, και το εργαλείο της είναι η επαγωγή στο πλήθος των όρων. Ο συμβολισμός ⋀i=1nφi\bigwedge_{i=1}^{n} \varphi_i ανήκει επίσης στη μεταγλώσσα: δεν είναι ένα νέο σύμβολο της γλώσσας, αλλά ένα όνομα για μια συμβολοσειρά κύκλων και δίσκων, όπως ακριβώς είναι και ο (φ∧ψ)(\varphi \wedge \psi).

Αξίζει να καθοριστούν από τώρα τρεις σχέσεις που δεν πρέπει να συγχέονται. Η ισότητα α=β\alpha = \beta λέει ότι οι α\alpha και β\beta είναι η ίδια συμβολοσειρά· οι ορισμοί, που γράφονται με :=:=, εισάγουν ονόματα για συμβολοσειρές, και ό,τι προκύπτει από την ανάπτυξη ενός ορισμού είναι ίσο, όχι απλώς ισοδύναμο. Η σημασιολογική ισοδυναμία α≡β\alpha \eqsem \beta λέει ότι v(α)=v(β)v(\alpha) = v(\beta) για κάθε αποτίμηση vv. Η αποδείξιμη ισοδυναμία α⊣⊢β\alpha \dashv\vdash \beta της ενότητας του συμπερασμού λέει ότι καθένας από τους δύο τύπους παράγεται από τον άλλον. Αυτό το μάθημα δουλεύει με τις δύο πρώτες· η τρίτη εμφανίζεται μόνο σε ένα σχόλιο.

Τι χρησιμοποιείται

Από το μάθημα για τη σημασιολογία της προτασιακής λογικής λαμβάνονται οι αποτιμήσεις, συναρτήσεις από τις μεταβλητές v1,v2,…v_1, v_2, \ldots στο {0,1}\{0, 1\}, και η επέκτασή τους σε όλους τους τύπους, που γράφεται με το ίδιο γράμμα vv· η τιμή των παράγωγων συνδέσμων, υπολογισμένη από τις επίσημες συντομογραφίες: v(¬φ)=1−v(φ)v(\neg\varphi) = 1 - v(\varphi), v((φ∧ψ))=v(φ) v(ψ)v((\varphi \wedge \psi)) = v(\varphi)\,v(\psi), ώστε η σύζευξη παίρνει την τιμή 11 αν και μόνο αν παίρνουν την τιμή 11 και οι δύο συνιστώσες της, και v((φ∨ψ))=1v((\varphi \vee \psi)) = 1 αν και μόνο αν v(φ)=1v(\varphi) = 1 ή v(ψ)=1v(\psi) = 1· το λήμμα σύμπτωσης (αν δύο αποτιμήσεις συμπίπτουν στις μεταβλητές ενός τύπου, συμπίπτουν στον τύπο)· και οι τύποι ⊤\top και ⊥\bot, μια σταθερή ταυτολογία και μια σταθερή αντίφαση. Από το μάθημα για τη σημασιολογική συνέπεια και ισοδυναμία λαμβάνονται το ότι η ≡\eqsem είναι ανακλαστική, συμμετρική και μεταβατική, το θεώρημα σημασιολογικής αντικατάστασης και ο κατάλογος των νόμων με τα ονόματά τους: αντιμεταθετικότητα, (φ∧ψ)≡(ψ∧φ)(\varphi \wedge \psi) \eqsem (\psi \wedge \varphi) και (φ∨ψ)≡(ψ∨φ)(\varphi \vee \psi) \eqsem (\psi \vee \varphi)· προσεταιριστικότητα, (φ∧(ψ∧χ))≡((φ∧ψ)∧χ)(\varphi \wedge (\psi \wedge \chi)) \eqsem ((\varphi \wedge \psi) \wedge \chi) και ο ανάλογος νόμος για τη ∨\vee· Ντε Μόργκαν, ¬(φ∧ψ)≡(¬φ∨¬ψ)\neg(\varphi \wedge \psi) \eqsem (\neg\varphi \vee \neg\psi) και ¬(φ∨ψ)≡(¬φ∧¬ψ)\neg(\varphi \vee \psi) \eqsem (\neg\varphi \wedge \neg\psi)· επιμεριστικότητα, (φ∧(ψ∨χ))≡((φ∧ψ)∨(φ∧χ))(\varphi \wedge (\psi \vee \chi)) \eqsem ((\varphi \wedge \psi) \vee (\varphi \wedge \chi)) και (φ∨(ψ∧χ))≡((φ∨ψ)∧(φ∨χ))(\varphi \vee (\psi \wedge \chi)) \eqsem ((\varphi \vee \psi) \wedge (\varphi \vee \chi))· διπλή άρνηση, ¬¬φ≡φ\neg\neg\varphi \eqsem \varphi· ταυτοδυναμία, (φ∨φ)≡φ(\varphi \vee \varphi) \eqsem \varphi· ταυτότητα, (φ∧⊤)≡φ(\varphi \wedge \top) \eqsem \varphi· και αποκλειόμενο τρίτο, ⊨(φ∨¬φ)\models (\varphi \vee \neg\varphi). Οι νόμοι ισχύουν για οποιουσδήποτε τύπους φ\varphi, ψ\psi, χ\chi, που είναι μεταμεταβλητές.

Σε κάθε βήμα των αποδείξεων που ακολουθούν αντικαθίσταται ένα μέρος ενός τύπου με ένα άλλο ισοδύναμο. Το θεώρημα σημασιολογικής αντικατάστασης το επιτρέπει για μία εμφάνιση κάθε φορά· το λήμμα που ακολουθεί, που είναι ειδική περίπτωσή του, το δίνει μονομιάς για τα μέρη μιας άρνησης, μιας σύζευξης ή μιας διάζευξης. Πρέπει να σημειωθεί ότι δεν είναι μια συντακτική τετριμμένη παρατήρηση: ο ¬α\neg\alpha είναι η συμβολοσειρά (α↓α)(\alpha \downarrow \alpha), στην οποία ο α\alpha εμφανίζεται δύο φορές, και ο (α∧β)(\alpha \wedge \beta) περιέχει, επομένως, οκτώ εμφανίσεις του α\alpha και οκτώ του β\beta.

ΛήμμαΣυμβατότητα των συνδέσμων με την ισοδυναμία

Αν α≡α′\alpha \eqsem \alpha' και β≡β′\beta \eqsem \beta', τότε ¬α≡¬α′\neg\alpha \eqsem \neg\alpha', (α∧β)≡(α′∧β′)(\alpha \wedge \beta) \eqsem (\alpha' \wedge \beta') και (α∨β)≡(α′∨β′)(\alpha \vee \beta) \eqsem (\alpha' \vee \beta').

Απόδειξη

  1. v(α)=v(α′),v(β)=v(β′)\dato{h}{v(\alpha) = v(\alpha'), \qquad v(\beta) = v(\beta')}

    Έστω vv μια οποιαδήποτε αποτίμηση. Από την παραδοχή, οι α\alpha και α′\alpha' έχουν την ίδια τιμή, και το ίδιο οι β\beta και β′\beta'.

  2. v(¬α)=1−v(α)=1−v(α′)=v(¬α′),v((α∧β))=v(α) v(β)=v(α′) v(β′)=v((α′∧β′))v(\neg\alpha) = 1 - \resaltar{v(\alpha)} = 1 - \resaltar{v(\alpha')} = v(\neg\alpha'), \qquad v((\alpha \wedge \beta)) = \resaltar{v(\alpha)\,v(\beta)} = \resaltar{v(\alpha')\,v(\beta')} = v((\alpha' \wedge \beta'))

    Η τιμή μιας άρνησης και η τιμή μιας σύζευξης εξαρτώνται μόνο από τις τιμές των συνιστωσών τους.

  3. v((α∨β))=1  ⇔  v(α)+v(β)≥1  ⇔  v(α′)+v(β′)≥1  ⇔  v((α′∨β′))=1v((\alpha \vee \beta)) = 1 \;\Leftrightarrow\; v(\alpha) + v(\beta) \geq 1 \;\Leftrightarrow\; v(\alpha') + v(\beta') \geq 1 \;\Leftrightarrow\; v((\alpha' \vee \beta')) = 1

    Το ίδιο συμβαίνει με τη διάζευξη: παίρνει την τιμή 11 αν και μόνο αν κάποια συνιστώσα παίρνει την τιμή 11, και οι συνιστώσες έχουν τις ίδιες τιμές στα δύο μέλη.

  4. ¬α≡¬α′,(α∧β)≡(α′∧β′),(α∨β)≡(α′∨β′)\neg\alpha \eqsem \neg\alpha', \qquad (\alpha \wedge \beta) \eqsem (\alpha' \wedge \beta'), \qquad (\alpha \vee \beta) \eqsem (\alpha' \vee \beta')

    Καθώς η vv ήταν οποιαδήποτε, οι τρεις ισοδυναμίες ισχύουν.