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

Συναρτησιακή πληρότητα

Περίληψη

Κάθε τύπος καθορίζει έναν πίνακα αληθείας· αυτό το μάθημα αποδεικνύει τον αντίστροφο ισχυρισμό: κάθε πίνακας, δηλαδή κάθε απόδοση τιμών αλήθειας στις γραμμές, είναι ο πίνακας κάποιου τύπου. Ορίζει τις συναρτήσεις αληθείας, μετρά εκείνες με nn ορίσματα (22n2^{2^{n}}) και διευκρινίζει πότε ένας τύπος παριστάνει μία από αυτές. Αποδεικνύει έπειτα το θεώρημα της συναρτησιακής πληρότητας μέσω του τύπου του πίνακα, μιας διάζευξης συζεύξεων λεκτικών που κατασκευάζεται γραμμή προς γραμμή και που το μάθημα για τις κανονικές μορφές θα χρησιμοποιήσει ως πρώτη απόδειξη της ύπαρξης της διαζευκτικής κανονικής μορφής. Επειδή κάθε τύπος του κύκλου μαθημάτων είναι μια συμβολοσειρά κύκλων και δίσκων, έπεται χωρίς περαιτέρω εργασία ότι η κοινή άρνηση αρκεί μόνη της, και δείχνεται πώς γράφεται μαζί της οποιαδήποτε συνάρτηση. Τέλος, μελετά ποια σύνολα συνδέσμων αρκούν για να παραστήσουν όλες τις συναρτήσεις: αποδεικνύει ένα γενικό κριτήριο, το εφαρμόζει στα {¬,∧}\{\neg, \wedge\}, {¬,∨}\{\neg, \vee\}, {¬,→}\{\neg, \rightarrow\}, {↓}\{\downarrow\} και στην εναλλακτική άρνηση, και αποδεικνύει ότι το {∧,∨,→,↔}\{\wedge, \vee, \rightarrow, \leftrightarrow\} δεν αρκεί, επειδή όλοι οι τύποι του διατηρούν την τιμή 11.

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

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

Συναρτήσεις αληθείας

Το μάθημα για τη σημασιολογία της προτασιακής λογικής απέδωσε σε κάθε τύπο, σε κάθε αποτίμηση, μια τιμή αλήθειας, και έδειξε ότι η τιμή αυτή εξαρτάται μόνο από τις τιμές των μεταβλητών που εμφανίζονται σε αυτόν· επομένως κάθε τύπος με nn μεταβλητές έχει πίνακα αληθείας με 2n2^{n} γραμμές. Το ερώτημα αυτού του μαθήματος είναι το αντίστροφο. Δοσμένου ενός οποιουδήποτε πίνακα, δηλαδή μιας στήλης από άσσους και μηδενικά γραμμένης αυθαίρετα δίπλα στις 2n2^{n} γραμμές, υπάρχει κάποιος τύπος που να τον έχει ως πίνακα; Αν αυτό ισχύει για κάθε πίνακα, η γλώσσα δεν έχει εκφραστικά κενά: ό,τι μπορεί να ειπωθεί για την τιμή αλήθειας nn αποφάνσεων, συναρτήσει των τιμών τους, λέγεται με έναν τύπο. Και επειδή σε αυτόν τον κύκλο μαθημάτων κάθε σύνθετος τύπος είναι μια κοινή άρνηση, η απάντηση θα πει επίσης αν ένας μόνο σύνδεσμος αρκεί για να ειπωθούν όλα.

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

Μια αποτίμηση είναι μια συνάρτηση vv από το σύνολο των μεταβλητών {v1,v2,…}\{v_1, v_2, \ldots\} στο {0,1}\{0, 1\}, όπου το 11 είναι το αληθές και το 00 το ψευδές· η επέκτασή της σε όλους τους τύπους, που γράφεται επίσης vv, ορίζεται με αναδρομή: v((φ↓ψ))=1v((\varphi \downarrow \psi)) = 1 αν και μόνο αν v(φ)=0v(\varphi) = 0 και v(ψ)=0v(\psi) = 0. Από τις επίσημες συντομογραφίες, το ίδιο μάθημα υπολόγισε, στο θεώρημα των τιμών των παράγωγων συνδέσμων, την τιμή κάθε συνδέσμου· γραμμένες με αθροίσματα και γινόμενα, οι τιμές αυτές είναι οι εξής, για κάθε αποτίμηση vv και για όλους τους τύπους φ\varphi και ψ\psi:

v(¬φ)=1−v(φ),v((φ∧ψ))=v(φ) v(ψ),v((φ∨ψ))=v(φ)+v(ψ)−v(φ) v(ψ)v(\neg\varphi) = 1 - v(\varphi), \qquad v((\varphi \wedge \psi)) = v(\varphi)\,v(\psi), \qquad v((\varphi \vee \psi)) = v(\varphi) + v(\psi) - v(\varphi)\,v(\psi)
v((φ→ψ))=1−v(φ)+v(φ) v(ψ),v((φ↓ψ))=(1−v(φ)) (1−v(ψ))v((\varphi \rightarrow \psi)) = 1 - v(\varphi) + v(\varphi)\,v(\psi), \qquad v((\varphi \downarrow \psi)) = (1 - v(\varphi))\,(1 - v(\psi))

Επιπλέον, v((φ↔ψ))=v(φ) v(ψ)+(1−v(φ)) (1−v(ψ))v((\varphi \leftrightarrow \psi)) = v(\varphi)\,v(\psi) + (1 - v(\varphi))\,(1 - v(\psi)), που ισούται με 11 αν και μόνο αν v(φ)=v(ψ)v(\varphi) = v(\psi), και v((φ⊻ψ))=v(φ)+v(ψ)−2 v(φ) v(ψ)v((\varphi \veebar \psi)) = v(\varphi) + v(\psi) - 2\,v(\varphi)\,v(\psi), που ισούται με 11 αν και μόνο αν v(φ)≠v(ψ)v(\varphi) \neq v(\psi). Επειδή οι τιμές είναι 00 ή 11, το τετράγωνο μιας τιμής είναι η ίδια η τιμή, v(φ) v(φ)=v(φ)v(\varphi)\,v(\varphi) = v(\varphi), και ένα γινόμενο τιμών ισούται με 11 αν και μόνο αν κάθε παράγοντας ισούται με 11· και οι δύο παρατηρήσεις θα χρησιμοποιούνται χωρίς να επαναλαμβάνονται. Χρησιμοποιείται επίσης το λήμμα σύμπτωσης: αν δύο αποτιμήσεις συμπίπτουν στις μεταβλητές του φ\varphi, δηλαδή στις μεταβλητές που είναι υποτύποι του φ\varphi, δίνουν στον φ\varphi την ίδια τιμή. Από το μάθημα για τη σημασιολογική συνέπεια και ισοδυναμία λαμβάνεται η σημασιολογική ισοδυναμία: φ≡ψ\varphi \eqsem \psi όταν v(φ)=v(ψ)v(\varphi) = v(\psi) για κάθε αποτίμηση vv. Τέλος, ισχύει η σύμβαση των γραμμάτων από το μάθημα για την τυποποίηση: τα pp, qq και rr δηλώνουν τις μεταβλητές v1v_1, v2v_2 και v3v_3.

Οι συναρτήσεις αληθείας και το πλήθος τους

Έστω nn ένας φυσικός αριθμός. Μια γραμμή nn τιμών είναι μια ακολουθία a=(a1,…,an)a = (a_1, \ldots, a_n) στην οποία κάθε aia_i είναι 00 ή 11· το σύνολο όλων αυτών συμβολίζεται {0,1}n\{0, 1\}^{n}. Μια συνάρτηση αληθείας nn ορισμάτων είναι μια συνάρτηση

f ⁣:{0,1}n→{0,1}f\colon \{0, 1\}^{n} \to \{0, 1\}

που αποδίδει σε κάθε γραμμή μια τιμή αλήθειας. Παρουσιάζεται ως πίνακας: οι γραμμές γράφονται με τη σειρά του πίνακα, αρχίζοντας από εκείνη όπου όλες οι τιμές είναι 11 (για δύο ορίσματα, 1 11\,1, 1 01\,0, 0 10\,1, 0 00\,0), και δίπλα σε κάθε γραμμή γράφεται η τιμή της. Μια συνάρτηση αληθείας είναι επομένως ένας πίνακας αληθείας χωρίς τύπο: η δεξιά στήλη, χωρίς τίποτα γραμμένο στην κεφαλίδα της.

ΠρότασηΥπάρχουν 22n2^{2^{n}} συναρτήσεις αληθείας nn ορισμάτων

Για κάθε φυσικό nn, υπάρχουν ακριβώς 2n2^{n} γραμμές nn τιμών και 22n2^{2^{n}} συναρτήσεις αληθείας nn ορισμάτων.

Απόδειξη

  1. 1 0 1    ⟼    ∙∘∙\dato{filas}{1\,0\,1 \;\; \longmapsto \;\; \sigI\sigO\sigI}

    Μια γραμμή είναι μια ακολουθία nn συμβόλων, καθένα από τα οποία είναι 11 ή 00. Αν γραφτεί ο δίσκος στη θέση του 11 και ο κύκλος στη θέση του 00, οι γραμμές αντιστοιχούν, μία προς μία, στις συμβολοσειρές μήκους nn πάνω στο αλφάβητο των δύο συμβόλων, που είναι 2n2^{n} σύμφωνα με το πρώτο λυμένο πρόβλημα του μαθήματος για την επαγωγή, όπου αποδείχθηκε με επαγωγή στο nn.

  2. f    ⟼    f(1,…,1)    …    f(0,…,0)f \;\; \longmapsto \;\; f(1, \ldots, 1) \;\; \ldots \;\; f(0, \ldots, 0)

    Μια συνάρτηση αληθείας καθορίζεται από τις τιμές της στις γραμμές, και κάθε επιλογή αυτών των τιμών δίνει μια συνάρτηση. Αν οι τιμές γραφτούν με τη σειρά του πίνακα, οι συναρτήσεις αντιστοιχούν, μία προς μία, στις ακολουθίες 2n2^{n} συμβόλων, καθένα 11 ή 00.

  3. 22n2^{\resaltar{2^{n}}}

    Με την ίδια μέτρηση, εφαρμοσμένη τώρα σε ακολουθίες μήκους 2n2^{n}, το πλήθος των συναρτήσεων είναι 22 υψωμένο στη 2n2^{n}.

  4. 22=4,24=16,28=256,216=65 5362^{2} = 4, \quad 2^{4} = 16, \quad 2^{8} = 256, \quad 2^{16} = 65\,536

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

ΠαράδειγμαΟι συναρτήσεις ενός και δύο ορισμάτων

Οι τέσσερις συναρτήσεις ενός ορίσματος είναι η σταθερή 11, η ταυτοτική, εκείνη που αλλάζει την τιμή και η σταθερή 00· οι τύποι ⊤\top, pp, ¬p\neg p και ⊥\bot, όπου οι ⊤:=(p→p)\top := (p \rightarrow p) και ⊥:=¬⊤\bot := \neg\top είναι εκείνοι που ορίστηκαν στο μάθημα για τη σημασιολογία, έχουν, αντιστοίχως, αυτούς τους πίνακες. Ανάμεσα στις δεκαέξι συναρτήσεις δύο ορισμάτων βρίσκονται οι συναρτήσεις των έξι συνδέσμων του κύκλου μαθημάτων: η κοινή άρνηση, η διάζευξη, η σύζευξη, η συνεπαγωγή, η διπλή συνεπαγωγή και η αποκλειστική διάζευξη. Μένουν άλλες δέκα, ανάμεσά τους οι δύο σταθερές, εκείνες που λαμβάνουν υπόψη μόνο το ένα από τα ορίσματα και η εναλλακτική άρνηση, που ισούται με 00 μόνο όταν και τα δύο ορίσματα ισούνται με 11· το λυμένο πρόβλημα 1 τις ταξινομεί όλες.

Τύποι που παριστάνουν συναρτήσεις

Ένας τύπος και μια συνάρτηση αληθείας συνδέονται ως εξής. Αν ο φ\varphi είναι ένας τύπος του οποίου οι μεταβλητές βρίσκονται ανάμεσα στις v1,…,vnv_1, \ldots, v_n, λέμε ότι ο φ\varphi παριστάνει τη συνάρτηση αληθείας ff nn ορισμάτων όταν, για κάθε αποτίμηση vv,

v(φ)=f(v(v1),…,v(vn))v(\varphi) = f(v(v_1), \ldots, v(v_n))

δηλαδή όταν ο πίνακας του φ\varphi, γραμμένος με τις μεταβλητές v1,…,vnv_1, \ldots, v_n, είναι ο πίνακας της ff. Η συνθήκη για τις μεταβλητές δεν είναι λεπτομέρεια: ο τύπος (p∧q)(p \wedge q) δεν παριστάνει καμία συνάρτηση ενός ορίσματος, επειδή η τιμή του δεν εξαρτάται μόνο από εκείνη της pp.

ΠρότασηΗ συνάρτηση ενός τύπου

Έστω φ\varphi ένας τύπος του οποίου οι μεταβλητές βρίσκονται ανάμεσα στις v1,…,vnv_1, \ldots, v_n. Τότε ο φ\varphi παριστάνει ακριβώς μία συνάρτηση αληθείας nn ορισμάτων, που συμβολίζεται fφf_\varphi. Αν ο ψ\psi είναι ένας άλλος τύπος του οποίου οι μεταβλητές βρίσκονται ανάμεσα στις v1,…,vnv_1, \ldots, v_n, τότε φ≡ψ\varphi \eqsem \psi αν και μόνο αν fφ=fψf_\varphi = f_\psi.

Απόδειξη

  1. va(vi)=ai(i≤n),va(vk)=0(k>n)\dato{va}{v_a(v_i) = a_i \quad (i \leq n), \qquad v_a(v_k) = 0 \quad (k > n)}

    Για κάθε γραμμή aa υπάρχει μια αποτίμηση που δίνει σε κάθε viv_i την τιμή aia_i: αρκεί να δοθεί στις υπόλοιπες μεταβλητές η τιμή 00.

  2. v(vi)=v′(vi)=ai(i≤n)    ⇒    v(φ)=v′(φ)=fφ(a)v(v_i) = v'(v_i) = a_i \quad (i \leq n) \;\; \Rightarrow \;\; v(\varphi) = v'(\varphi) = \resaltar{f_\varphi(a)}

    Αν δύο αποτιμήσεις δίνουν στις v1,…,vnv_1, \ldots, v_n τις τιμές της γραμμής aa, συμπίπτουν στις μεταβλητές του φ\varphi, και από το λήμμα σύμπτωσης δίνουν στον φ\varphi την ίδια τιμή. Αυτή η κοινή τιμή λαμβάνεται ως fφ(a)f_\varphi(a)· εκ κατασκευής, ο φ\varphi παριστάνει την fφf_\varphi.

  3. g(a)=va(φ)=fφ(a)g(a) = v_a(\varphi) = f_\varphi(a)

    Αν ο φ\varphi παριστάνει επίσης μια συνάρτηση gg, σε κάθε γραμμή aa ισχύει g(a)=va(φ)=fφ(a)g(a) = v_a(\varphi) = f_\varphi(a): η συνάρτηση που παριστάνεται είναι μοναδική.

  4. v(φ)=fφ(v(v1),…,v(vn))=fψ(v(v1),…,v(vn))=v(ψ)v(\varphi) = f_\varphi(v(v_1), \ldots, v(v_n)) = f_\psi(v(v_1), \ldots, v(v_n)) = v(\psi)

    Αν fφ=fψf_\varphi = f_\psi, για κάθε αποτίμηση vv οι τιμές του φ\varphi και του ψ\psi είναι η τιμή της ίδιας συνάρτησης στην ίδια γραμμή· επομένως φ≡ψ\varphi \eqsem \psi.

  5. fφ(a)=va(φ)=va(ψ)=fψ(a)f_\varphi(a) = v_a(\varphi) = v_a(\psi) = f_\psi(a)

    Αντιστρόφως, αν φ≡ψ\varphi \eqsem \psi, σε κάθε γραμμή aa η αποτίμηση vav_a δίνει την ίδια τιμή και στους δύο τύπους, και επομένως fφ(a)=fψ(a)f_\varphi(a) = f_\psi(a).

Υπάρχουν άπειροι τύποι με μεταβλητές ανάμεσα στις v1,…,vnv_1, \ldots, v_n και μόνο 22n2^{2^{n}} συναρτήσεις· επομένως πολλοί τύποι παριστάνουν την ίδια συνάρτηση, και η πρόταση λέει ότι είναι ακριβώς οι ισοδύναμοι μεταξύ τους. Μένει να μάθουμε αν κάθε συνάρτηση παριστάνεται από κάποιον τύπο ή αν κάποιοι πίνακες μένουν χωρίς τύπο που να τους έχει.