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

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

Περίληψη

Αυτό το μάθημα κλείνει την ενότητα του συμπερασμού με δύο οικογένειες ισοδυναμιών που χρησιμοποιούν όλα τα μαθηματικά: τους νόμους του Ντε Μόργκαν, που λένε πώς η άρνηση διασχίζει μια σύζευξη ή μια διάζευξη, και τους επιμεριστικούς νόμους, που λένε πώς μια σύζευξη επιμερίζεται ως προς μια διάζευξη και μια διάζευξη ως προς μια σύζευξη. Πριν αποδειχθούν, διευκρινίζεται μια διάκριση από την οποία εξαρτώνται: δύο εκφράσεις που δηλώνουν την ίδια συμβολοσειρά μπορούν να τεθούν η μία στη θέση της άλλης χωρίς άλλο, επειδή είναι ο ίδιος τύπος· δύο τύποι απλώς ισοδύναμοι, αντίθετα, μπορούν να αντικατασταθούν μέσα σε έναν άλλο τύπο μόνο με την αντικατάσταση ισοδυνάμων, στρώμα προς στρώμα. Με αυτή την προφύλαξη αποδεικνύονται με παραγωγή οι δύο νόμοι του Ντε Μόργκαν, οι παραλλαγές τους (ανάμεσά τους, η άρνηση μιας συνεπαγωγής) και οι δύο επιμεριστικοί νόμοι, ο καθένας και στις δύο κατευθύνσεις του. Τα προβλήματα τους χρησιμοποιούν για να λάβουν την ταυτοδυναμία, την απορρόφηση και την προσεταιριστικότητα, απλές κανονικές μορφές και παραγωγές που συνδυάζουν τον Ντε Μόργκαν με την αντιθετοαντιστροφή.

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

  1. Να διακρίνει την ταυτότητα συμβολοσειρών, που επιτρέπει να αντικατασταθεί μια συντομογραφία με την ανάπτυξή της σε οποιοδήποτε σημείο, από την αποδείξιμη ισοδυναμία, που επιτρέπει αντικατάσταση μέσα σε έναν τύπο μόνο μέσω της αντικατάστασης ισοδυνάμων, και να αλυσιδώνει ισοδυναμίες σε μια παραγωγή.
  2. Να αποδεικνύει με παραγωγή τους δύο νόμους του Ντε Μόργκαν και τις παραλλαγές τους, μαζί με την άρνηση μιας συνεπαγωγής, και να αναγνωρίζει σε αυτούς τον ρόλο του κανόνα της αντικατάστασης της διπλής άρνησης.
  3. Να αποδεικνύει και στις δύο κατευθύνσεις την επιμεριστικότητα της σύζευξης ως προς τη διάζευξη και της διάζευξης ως προς τη σύζευξη, επιλέγοντας σε κάθε περίπτωση την κατάλληλη απόδειξη κατά περιπτώσεις.
  4. Να μετασχηματίζει τύπους σε απλές κανονικές μορφές μέσω μιας αλυσίδας ισοδυναμιών αιτιολογημένης βήμα προς βήμα, και να λαμβάνει με παραγωγή τους νόμους της ταυτοδυναμίας, της απορρόφησης και της προσεταιριστικότητας.
  5. Να κατασκευάζει παραγωγές με υποθέσεις που συνδυάζουν τους νόμους του Ντε Μόργκαν με την αντιθετοαντιστροφή και με τους κανόνες εισαγωγής και απαλοιφής των συνδέσμων.

Τα προηγούμενα μαθήματα αυτής της ενότητας κατασκεύασαν, το ένα πάνω στο άλλο, τα εργαλεία της παραγωγής: το σύστημα αξιωμάτων και τον modus ponens, τις τέσσερις βασικές τεχνικές και την αντικατάσταση της διπλής άρνησης, τις συμμετρίες των συνδέσμων και τις τεχνικές της κλασικής λογικής. Αυτό το μάθημα δεν προσθέτει κανέναν νέο κανόνα· τους βάζει να δουλέψουν μαζί. Αν αυτό ισχύει, το ενδιαφέρον του δεν βρίσκεται τόσο στις διατυπώσεις, που ίσως είναι γνωστές από άλλους κύκλους μαθημάτων, όσο στον τρόπο με τον οποίο λαμβάνονται: κάθε γραμμή πρέπει να αιτιολογείται με ένα αξίωμα, μια υπόθεση, έναν ορισμό, έναν από τους δύο πρωταρχικούς κανόνες ή ένα αποτέλεσμα που έχει ήδη αποδειχθεί, και καμία δεν μπορεί να στηρίζεται σε ό,τι «φαίνεται προφανές».

Τι χρησιμοποιείται και πώς αλυσιδώνεται

Από το μάθημα για τα τυπικά παραγωγικά συστήματα λαμβάνονται τα αξιώματα A1, A2 και A3 του Λουκασέβιτς, ο modus ponens (MP), και με υποθέσεις, η ανακλαστικότητα (Ανακλ: αν φ∈Γ\varphi \in \Gamma, τότε Γ⊢φ\Gamma \vdash \varphi), η μονοτονία (Μον), η τομή (Τομή: αν Γ⊢φi\Gamma \vdash \varphi_i για κάθε ii και Γ∪{φ1,…,φn}⊢ψ\Gamma \cup \{\varphi_1, \ldots, \varphi_n\} \vdash \psi, τότε Γ⊢ψ\Gamma \vdash \psi), το θεώρημα της απαγωγής (ΘΑ) και η αποδείξιμη ισοδυναμία (φ⊣⊢ψ\varphi \dashv\vdash \psi αν {φ}⊢ψ\{\varphi\} \vdash \psi και {ψ}⊢φ\{\psi\} \vdash \varphi), με τις ιδιότητές της: είναι ανακλαστική, συμμετρική και μεταβατική, και, αν φ⊣⊢ψ\varphi \dashv\vdash \psi, τότε Γ⊢φ\Gamma \vdash \varphi αν και μόνο αν Γ⊢ψ\Gamma \vdash \psi. Από το μάθημα για τις τέσσερις τεχνικές παραγωγής, η διπλή άρνηση (ΔΑ: φ⊣⊢¬¬φ\varphi \dashv\vdash \neg\neg\varphi), η αντιθετοαντιστροφή (ΑΑ), ειδικότερα (φ→ψ)⊣⊢(¬ψ→¬φ)(\varphi \rightarrow \psi) \dashv\vdash (\neg\psi \rightarrow \neg\varphi), και ο δεύτερος πρωταρχικός κανόνας του συστήματος του κύκλου μαθημάτων, η αντικατάσταση της διπλής άρνησης (ΑΔΑ), με την οποία το θεώρημα της απαγωγής εξακολουθεί να ισχύει: αν ο χ′\chi' προκύπτει από τον χ\chi όταν αντικατασταθεί μια εμφάνιση ενός υποτύπου θ\theta με τον ¬¬θ\neg\neg\theta, ή μια εμφάνιση του ¬¬θ\neg\neg\theta με τον θ\theta, από τον χ\chi συνάγεται ο χ′\chi'· η γραμμή που λαμβάνεται έτσι από τη γραμμή ii αιτιολογείται ΑΔΑ(i)(i). Ανάμεσα στις άμεσες συνέπειές της είναι οι (φ↓ψ)⊣⊢(¬¬φ↓ψ)(\varphi \downarrow \psi) \dashv\vdash (\neg\neg\varphi \downarrow \psi), (φ↓ψ)⊣⊢(φ↓¬¬ψ)(\varphi \downarrow \psi) \dashv\vdash (\varphi \downarrow \neg\neg\psi) και, γενικά, χ⊣⊢χ′\chi \dashv\vdash \chi' όταν ο χ′\chi' προκύπτει από τον χ\chi με ΑΔΑ· από αυτό έπεται ότι η ΑΔΑ(i)(i) εφαρμόζεται και σε μια γραμμή της μορφής χ⊣⊢φ\chi \dashv\vdash \varphi, για να αλλάξει μια διπλή άρνηση στον φ\varphi. Από το μάθημα για τις συμμετρίες των συνδέσμων, η αντικατάσταση ισοδυνάμων (Αντ) και οι συμμετρίες (Συμ), ανάμεσά τους οι (φ∨ψ)⊣⊢(ψ∨φ)(\varphi \vee \psi) \dashv\vdash (\psi \vee \varphi) και (φ∧ψ)⊣⊢(ψ∧φ)(\varphi \wedge \psi) \dashv\vdash (\psi \wedge \varphi).

Από το μάθημα για τις τεχνικές της κλασικής λογικής λαμβάνονται, όλοι με ένα σύνολο Γ\Gamma υποθέσεων, οι ακόλουθοι κανόνες. Η εισαγωγή της διάζευξης (∨\veeΕισ): αν Γ⊢φ\Gamma \vdash \varphi, τότε Γ⊢(φ∨ψ)\Gamma \vdash (\varphi \vee \psi) και Γ⊢(ψ∨φ)\Gamma \vdash (\psi \vee \varphi). Η απαλοιφή της διάζευξης (∨\veeΑπ, διαζευκτικός συλλογισμός): αν Γ⊢(φ∨ψ)\Gamma \vdash (\varphi \vee \psi) και Γ⊢¬φ\Gamma \vdash \neg\varphi, τότε Γ⊢ψ\Gamma \vdash \psi. Η εισαγωγή της σύζευξης (∧\wedgeΕισ): αν Γ⊢φ\Gamma \vdash \varphi και Γ⊢ψ\Gamma \vdash \psi, τότε Γ⊢(φ∧ψ)\Gamma \vdash (\varphi \wedge \psi). Η απαλοιφή της σύζευξης (∧\wedgeΑπ): αν Γ⊢(φ∧ψ)\Gamma \vdash (\varphi \wedge \psi), τότε Γ⊢φ\Gamma \vdash \varphi και Γ⊢ψ\Gamma \vdash \psi. Το αποκλειόμενο τρίτο (ΑΤ): ⊢(φ∨¬φ)\vdash (\varphi \vee \neg\varphi). Και η απόδειξη κατά περιπτώσεις (Περ) στις δύο μορφές της: αν Γ∪{φ}⊢χ\Gamma \cup \{\varphi\} \vdash \chi και Γ∪{¬φ}⊢χ\Gamma \cup \{\neg\varphi\} \vdash \chi, τότε Γ⊢χ\Gamma \vdash \chi· και αν Γ∪{φ}⊢χ\Gamma \cup \{\varphi\} \vdash \chi, Γ∪{ψ}⊢χ\Gamma \cup \{\psi\} \vdash \chi και Γ⊢(φ∨ψ)\Gamma \vdash (\varphi \vee \psi), τότε Γ⊢χ\Gamma \vdash \chi. Στις παραγωγές, η πρώτη μορφή αναφέρεται με δύο γραμμές, Περ(i,j)(i, j), και η δεύτερη με τρεις, Περ(i,j,k)(i, j, k), με τη σειρά της διατύπωσης: οι δύο περιπτώσεις και, στο τέλος, η διάζευξη. Το μάθημα εκείνο θυμίζει επιπλέον ότι κάθε κανόνας που έχει ήδη αποδειχθεί ισχύει μέσα σε ένα πλαίσιο Γ\Gamma, και έτσι χρησιμοποιούνται εδώ η διπλή άρνηση και η αντιθετοαντιστροφή.

Ονόματα μιας συμβολοσειράς και ισοδύναμοι τύποι

Ας θυμηθούμε, από το μάθημα για τη γλώσσα της προτασιακής λογικής, ότι οι σύνδεσμοι που διαφέρουν από τον ↓\downarrow είναι συντομογραφίες με επίσημο και μοναδικό ορισμό: ¬φ:=(φ↓φ)\neg\varphi := (\varphi \downarrow \varphi), (φ∨ψ):=¬(φ↓ψ)(\varphi \vee \psi) := \neg(\varphi \downarrow \psi), (φ∧ψ):=¬(¬φ∨¬ψ)(\varphi \wedge \psi) := \neg(\neg\varphi \vee \neg\psi), (φ→ψ):=(¬φ∨ψ)(\varphi \rightarrow \psi) := (\neg\varphi \vee \psi), (φ↔ψ):=((φ→ψ)∧(ψ→φ))(\varphi \leftrightarrow \psi) := ((\varphi \rightarrow \psi) \wedge (\psi \rightarrow \varphi)) και (φ⊻ψ):=¬(φ↔ψ)(\varphi \veebar \psi) := \neg(\varphi \leftrightarrow \psi). Ένας ορισμός δεν βεβαιώνει τίποτε για τους τύπους: δίνει ένα δεύτερο όνομα σε μια συμβολοσειρά που υπήρχε ήδη. Από αυτό έπεται ότι, αν δύο εκφράσεις δηλώνουν την ίδια συμβολοσειρά, η μία μπορεί να τεθεί στη θέση της άλλης οπουδήποτε, και μέσα σε έναν μεγαλύτερο τύπο, επειδή αυτό που γράφεται είναι η ίδια ακολουθία κύκλων και δίσκων. Έτσι, ο ¬(φ∧ψ)\neg(\varphi \wedge \psi) και ο ¬¬(¬φ∨¬ψ)\neg\neg(\neg\varphi \vee \neg\psi) είναι η ίδια συμβολοσειρά: ο δεύτερος προκύπτει αν γραφτεί, μέσα στον πρώτο, η ανάπτυξη της σύζευξης. Στις παραγωγές, αυτή η αλλαγή ονόματος αιτιολογείται με «Ορ», ακολουθούμενο από τον σύνδεσμο που αναπτύσσεται ή συμπτύσσεται.

Όμως, μια αποδείξιμη ισοδυναμία δεν είναι ταυτότητα. Ότι φ⊣⊢¬¬φ\varphi \dashv\vdash \neg\neg\varphi σημαίνει ότι από τον καθένα παράγεται ο άλλος, όχι ότι είναι η ίδια συμβολοσειρά: ο ¬¬φ\neg\neg\varphi είναι πολύ μακρύτερος από τον φ\varphi. Επομένως, το ότι γνωρίζουμε ότι φ⊣⊢φ′\varphi \dashv\vdash \varphi' δεν επιτρέπει, χωρίς άλλο, να γράψουμε τον φ′\varphi' στη θέση του φ\varphi μέσα σε έναν μεγαλύτερο τύπο. Ούτε επιτρέπει να «αρνηθούμε και τις δύο πλευρές»: ότι από το φ⊣⊢φ′\varphi \dashv\vdash \varphi' έπεται το ¬φ⊣⊢¬φ′\neg\varphi \dashv\vdash \neg\varphi' είναι θεώρημα, η αντικατάσταση ισοδυνάμων, του οποίου η απόδειξη χρησιμοποιεί την αντιθετοαντιστροφή, και όχι μια προφανής πράξη. Υπάρχει μία μόνο περίπτωση στην οποία το σύστημα επιτρέπει την αντικατάσταση άμεσα, σε οποιοδήποτε σημείο ενός τύπου: του θ\theta με τον ¬¬θ\neg\neg\theta, ή αντίστροφα, που είναι ο κανόνας ΑΔΑ· και το μάθημα για τα παραγωγικά συστήματα έδειξε, με τη σήμανση, ότι ούτε καν αυτή η περίπτωση παράγεται από τα αξιώματα και τον modus ponens, ώστε χρειάστηκε να τεθεί ως αίτημα. Αυτή η προσοχή δεν είναι σχολαστικισμός· είναι αυτό που διακρίνει μια απόδειξη από έναν χειρισμό συμβόλων που θα μπορούσε, εφαρμοσμένος σε άλλους συνδέσμους ή σε άλλα συστήματα, να οδηγήσει σε ψεύδη.

Δύο αποτελέσματα καθορίζουν με ακρίβεια τι επιτρέπεται. Το πρώτο είναι η πρόταση για τις ιδιότητες της αποδείξιμης ισοδυναμίας από το μάθημα για τα τυπικά παραγωγικά συστήματα: αν Γ⊢φ\Gamma \vdash \varphi και φ⊣⊢φ′\varphi \dashv\vdash \varphi', τότε Γ⊢φ′\Gamma \vdash \varphi', ώστε μια αποδείξιμη ισοδυναμία μπορεί να εφαρμοστεί σε ολόκληρο τον τύπο μιας γραμμής· και η αποδείξιμη ισοδυναμία είναι ανακλαστική, συμμετρική και μεταβατική, ώστε οι ισοδυναμίες αλυσιδώνονται (αν χ⊣⊢φ\chi \dashv\vdash \varphi και φ⊣⊢φ′\varphi \dashv\vdash \varphi', τότε χ⊣⊢φ′\chi \dashv\vdash \varphi') και δύο εκφράσεις που δηλώνουν την ίδια συμβολοσειρά είναι, λόγω ανακλαστικότητας, αποδείξιμα ισοδύναμες. Το δεύτερο, το λήμμα που ακολουθεί, συγκεντρώνει, για να παραπέμπουμε εύκολα σε αυτήν, την επέκταση της αντικατάστασης ισοδυνάμων στη διάζευξη και στη σύζευξη, την οποία το μάθημα για τις συμμετρίες αποδεικνύει για την άρνηση, τη συνεπαγωγή και την κοινή άρνηση και επεκτείνει σε αυτούς τους δύο συνδέσμους σε ένα από τα λυμένα προβλήματά του.

ΛήμμαΑντικατάσταση στη διάζευξη και στη σύζευξη

Αν φ⊣⊢φ′\varphi \dashv\vdash \varphi', τότε, για κάθε τύπο ψ\psi, (φ∨ψ)⊣⊢(φ′∨ψ)(\varphi \vee \psi) \dashv\vdash (\varphi' \vee \psi), (ψ∨φ)⊣⊢(ψ∨φ′)(\psi \vee \varphi) \dashv\vdash (\psi \vee \varphi'), (φ∧ψ)⊣⊢(φ′∧ψ)(\varphi \wedge \psi) \dashv\vdash (\varphi' \wedge \psi) και (ψ∧φ)⊣⊢(ψ∧φ′)(\psi \wedge \varphi) \dashv\vdash (\psi \wedge \varphi').

Απόδειξη

  1. (φ∨ψ)=¬(φ↓ψ)(\varphi \vee \psi) = \neg\resaltar{(\varphi \downarrow \psi)}

    Η διάζευξη είναι, εξ ορισμού, η άρνηση μιας κοινής άρνησης.

  2. (φ↓ψ)⊣⊢(φ′↓ψ)\dato{int}{(\varphi \downarrow \psi) \dashv\vdash (\varphi' \downarrow \psi)}

    Η αντικατάσταση ισοδυνάμων για την κοινή άρνηση δίνει την ισοδυναμία του εσωτερικού στρώματος.

  3. (φ∨ψ)⊣⊢(φ′∨ψ)\dato{disy}{\resaltar{(\varphi \vee \psi)} \dashv\vdash \resaltar{(\varphi' \vee \psi)}}

    Η αντικατάσταση ισοδυνάμων για την άρνηση τη φέρνει στο εξωτερικό στρώμα, ¬(φ↓ψ)⊣⊢¬(φ′↓ψ)\neg(\varphi \downarrow \psi) \dashv\vdash \neg(\varphi' \downarrow \psi), που είναι η διάζευξη. Με τον ίδιο τρόπο, με (ψ↓φ)⊣⊢(ψ↓φ′)(\psi \downarrow \varphi) \dashv\vdash (\psi \downarrow \varphi'), λαμβάνεται η αντικατάσταση στα δεξιά.

  4. (φ∧ψ)=¬(¬φ∨¬ψ),¬φ⊣⊢¬φ′(\varphi \wedge \psi) = \neg(\resaltar{\neg\varphi} \vee \neg\psi), \qquad \neg\varphi \dashv\vdash \neg\varphi'

    Η σύζευξη είναι η άρνηση μιας διάζευξης αρνήσεων. Η αντικατάσταση για την άρνηση δίνει πρώτα ¬φ⊣⊢¬φ′\neg\varphi \dashv\vdash \neg\varphi'.

  5. ¬(¬φ∨¬ψ)⊣⊢¬(¬φ′∨¬ψ),(φ∧ψ)⊣⊢(φ′∧ψ)\neg(\neg\varphi \vee \neg\psi) \dashv\vdash \neg(\neg\varphi' \vee \neg\psi), \qquad \resaltar{(\varphi \wedge \psi)} \dashv\vdash \resaltar{(\varphi' \wedge \psi)}

    Το μέρος που αποδείχθηκε ήδη για τη διάζευξη, εφαρμοσμένο στους ¬φ\neg\varphi και ¬φ′\neg\varphi', δίνει (¬φ∨¬ψ)⊣⊢(¬φ′∨¬ψ)(\neg\varphi \vee \neg\psi) \dashv\vdash (\neg\varphi' \vee \neg\psi), και πάλι η αντικατάσταση για την άρνηση φέρνει την ισοδυναμία στη σύζευξη· στα δεξιά συλλογιζόμαστε με τον ίδιο τρόπο.

Στο εξής, «Αντ» δηλώνει την αντικατάσταση ισοδυνάμων σε οποιαδήποτε από τις μορφές της, και σε εκείνες αυτού του λήμματος, και μπορεί να εφαρμοστεί πολλές φορές διαδοχικά, στρώμα προς στρώμα, για να φτάσει σε έναν υποτύπο που βρίσκεται σε οποιοδήποτε βάθος. Όταν μια γραμμή λαμβάνεται από τη γραμμή ii με την εφαρμογή μιας ισοδυναμίας που έχει ήδη αποδειχθεί, είτε σε ολόκληρο τον τύπο είτε, με Αντ, σε ένα από τα μέρη του, αιτιολογείται με το όνομα αυτής της ισοδυναμίας και τον αριθμό της γραμμής: ΔΑ(i)(i), «Αντ, ΝΜ(i)(i)». Μια αλλαγή ονόματος, που δεν εφαρμόζει καμία ισοδυναμία αλλά ξαναγράφει την ίδια συμβολοσειρά, αιτιολογείται με τον ίδιο τρόπο, με «Ορ», ακολουθούμενο από τον σύνδεσμο που αναπτύσσεται ή συμπτύσσεται: Ορ ∧\wedge (i)(i). Η πρόταση του μαθήματος για τα τυπικά παραγωγικά συστήματα εγγυάται ότι τέτοιες γραμμές είναι αιτιολογημένες, είτε η γραμμή ii βεβαιώνει Γ⊢φ\Gamma \vdash \varphi είτε βεβαιώνει μια ισοδυναμία χ⊣⊢φ\chi \dashv\vdash \varphi που προεκτείνεται βήμα προς βήμα.