Μια συνάρτηση f που λαμβάνεται από τις συναρτήσεις f 1 , f 2 ,…f n χρησιμοποιώντας τις πράξεις αντικατάστασης και μετονομασίας ορισμάτων ονομάζεται προσθήκη λειτουργίες.

Κάθε τύπος που εκφράζει μια συνάρτηση f ως υπέρθεση άλλων συναρτήσεων καθορίζει μια μέθοδο για τον υπολογισμό της, δηλαδή, ο τύπος μπορεί να υπολογιστεί εάν υπολογιστούν οι τιμές όλων των υποτύπων του. Η τιμή ενός υποτύπου μπορεί να υπολογιστεί από ένα γνωστό σύνολο τιμών δυαδικών μεταβλητών.

Χρησιμοποιώντας κάθε τύπο, μπορείτε να επαναφέρετε τον πίνακα μιας λογικής συνάρτησης, αλλά όχι το αντίστροφο, γιατί Κάθε λογική συνάρτηση μπορεί να αναπαρασταθεί από πολλούς τύπους σε διαφορετικές βάσεις

Καλούνται οι τύποι F i και F j που αντιπροσωπεύουν την ίδια λογική συνάρτηση f i ισοδύναμος . Έτσι, οι ισοδύναμοι τύποι είναι:

1. f 2 (x 1 ; x 2)=(x 1 ×`x 2)=ù(`x 1 Úx 2)= ù(x 1 ®x 2);

2. f 6 (x 1 ; x 2)=(`x 1 ×x 2 Úx 1 ×`x 2)= ù(x 1 “x 2)=(x 1 Åx 2);

3. f 8 (x 1 ; x 2)=(`x 1 ×`x 2)= ù(x 1 Úx 2)=(x 1 ¯x 2);

4. f 14 (x 1 ;x 2)=(`x 1 Ú`x 2)= ù(x 1 ×x 2)=x 1 ½x 2 ;

5. f 9 (x 1 ;x 2)=((`x 1 ×`x 2)Ú(x 1 ×x 2))=(x 1 "x 2) ;

6. f 13 (x 1 ;x 2)= (`x 1 Úx 2)=(x 1 ®x 2).

Εάν οποιοσδήποτε τύπος F περιέχει έναν υποτύπο F i , τότε η αντικατάσταση του F i με ένα ισοδύναμο F j δεν αλλάζει την τιμή του τύπου F για οποιοδήποτε σύνολο Boolean διανυσμάτων, αλλά αλλάζει τη μορφή της περιγραφής του. Ο νέος τύπος F' είναι ισοδύναμος με τον τύπο F.

Για την απλοποίηση σύνθετων αλγεβρικών παραστάσεων, εκτελούνται συναρτήσεις Boolean ισοδύναμους μετασχηματισμούς χρησιμοποιώντας τους νόμους της άλγεβρας Boole και κανόνες αντικατάστασης Και υποκατάσταση ,

Όταν γράφετε τύπους άλγεβρας Boole, να θυμάστε:

· ο αριθμός των αριστερών παρενθέσεων είναι ίσος με τον αριθμό των δεξιών παρενθέσεων,

· Δεν υπάρχουν δύο γειτονικές λογικές συνδέσεις, δηλαδή πρέπει να υπάρχει ένας τύπος μεταξύ τους,

· Δεν υπάρχουν δύο παρακείμενοι τύποι, δηλαδή πρέπει να υπάρχει μια λογική σύνδεση μεταξύ τους,

· το λογικό συνδετικό "×" είναι ισχυρότερο από το λογικό συνδετικό "Ú",

· εάν το "ù" αναφέρεται στον τύπο (F 1 ×F 2) ή (F 1 Ú F 2), τότε πρώτα απ 'όλα αυτοί οι μετασχηματισμοί θα πρέπει να πραγματοποιηθούν σύμφωνα με το νόμο του De Morgan: ù(F 1 ×F 2) = ` F 1 Ú` F 2 ή ù(F 1 ÚF 2)=`F 1 ×`F 2 ;

· λειτουργία " × Το " είναι ισχυρότερο από το "Ú", το οποίο σας επιτρέπει να παραλείψετε τις παρενθέσεις.

Παράδειγμα: εκτελέστε ισοδύναμους μετασχηματισμούς του τύπου F=x 1 ×x 2 ×x 3 ×`x 4 Ú`x 1 ×x 3 Ú`x 2 ×x 3 Úx 3 ×x 4 .

· σύμφωνα με το νόμο της ανταλλαγής:

F=x 3 ×x 1 ×x 2 ×`x 4 Úx 3 ×`x 1 Úx 3 ×`x 2 Úx 3 ×x 4 ;

· σύμφωνα με το νόμο της κατανομής:

F=x 3 ×x 1 ×x 2 ×`x 4 Úx 3 ×`x 1 Úx 3 ×(`x 2 Úx 4);

· σύμφωνα με το νόμο της κατανομής:

F=x 3 ×x 1 ×x 2 ×`x 4 Úx 3 ×(`x 1 Ú`x 2 Úx 4);

· σύμφωνα με το νόμο της κατανομής:

F=x 3 ×((x 1 ×x 2 ×`x 4)Ú(`x 1 Ú`x 2 Úx 4));

· σύμφωνα με το νόμο του De Morgan:

F=x 3 ×((x 1 ×x 2 ×`x 4)Úù(x 1 ×x 2 ×`x 4));

· σύμφωνα με το νόμο της αντίφασης:

Έτσι x 1 ×x 2 ×x 3 ×`x 4 Ú`x 1 ×x 3 Ú`x 2 ×x 3 Úx 3 ×x 4 =x 3 .

Παράδειγμα:εκτελέστε μετασχηματισμούς τύπου

F=(x 1 ×`x 2 Ú`x 1 ×x 2)×ù(x 1 ×x 2)Ú(x 1 ×x 2)×ù(x 1 ×`x 2 Ú`x 1 ×x 2 )

· σύμφωνα με το νόμο του De Morgan

F=(x 1 ×`x 2 Ú`x 1 ×x 2)×(`x 1 Ú`x 2)Ú(x 1 ×x 2)×(`x 1 Úx 2)×(x 1 Ú`x 2);

· σύμφωνα με το νόμο της κατανομής:

F=x 1 ×`x 2 Ú`x 1 ×x 2 Úx 1 ×x 2 ;

· σύμφωνα με τους νόμους της ανταλλαξιμότητας και της κατανομής:

F= `x 1 ×x 2 Úx 1 ×(`x 2 Úx 2);

· σύμφωνα με το νόμο της αντίφασης:

F= `x 1 ×x 2 Úx 1 ;

· σύμφωνα με το νόμο του Poretsky

Έτσι (x 1 ×`x 2 Ú`x 1 ×x 2)×ù(x 1 ×x 2)Ú(x 1 ×x 2)×ù(x 1 ×`x 2 Ú`x 1 ×x 2 ) = (x 2 Úx 1).

Παράδειγμα:μετατρέψτε τον τύπο F=ù(`x 1 Úx 2)Ú((`x 1 Úx 3)×x 2).

· σύμφωνα με το νόμο του De Morgan:

F= ù(`x 1 Úx 2)×ù((`x 1 Úx 3)×x 2);

· σύμφωνα με το νόμο του De Morgan:

F=x 1 ×`x 2 ×(ù(`x 1 Úx 3)Ú`x 2);

· σύμφωνα με το νόμο του De Morgan:

F=x 1 ×`x 2 ×(x 1 ×`x 3 Ú`x 2);

· σύμφωνα με το νόμο της κατανομής:

F=x 1 ×`x 2 ×`x 3 Úx 1 ×`x 2 ;

· σύμφωνα με το νόμο της απορρόφησης:

Έτσι ù(`x 1 Úx 2)×((`x 1 Úx 3)×x 2)= x 1 ×`x 2 .

Παράδειγμα: Μετατρέψτε τον τύπο:

F=ù(x 1 ®x 2)×(`x 3 Ú`x 4)Ú(x 1 ¯x 2)×ù(x 3 ×x 4).

1) μετατρέψτε τον τύπο σε βάση της άλγεβρας Boole:

F=ù(`x 1 Úx 2)×(`x 3 Ú`x 4)Úù(x 1 Úx 2)× ù(x 3 ×x 4);

2) παραλείψτε το σύμβολο "`" πριν από τις δυαδικές μεταβλητές:

F=(x 1 ×`x 2)×(`x 3 Ú`x 4)Ú(`x 1 ×`x 2)×(`x 3 Ú`x 4);

3) μετατρέψτε τον τύπο σύμφωνα με τον διανεμητικό νόμο:

F=x 1 ×`x 2 ×`x 3 Úx 1 ×`x 2 ×`x 4 Ú`x 1 ×`x 2 ×`x 3 Ú`x 1 ×`x 2 ×`x 4 ;

4) Βάλτε `x 2 εκτός παρενθέσεων σύμφωνα με τον διανεμητικό νόμο:

F=`x 2 ×(x 1 ×`x 3 Úx 1 ×`x 4 Ú`x 1 ×`x 3 Ú`x 1 ×`x 4);

5) μετασχηματισμός σύμφωνα με το νόμο της κατανομής:

F=`x 2 ×(`x 3 ×(x 1 Ú`x 1)Ú`x 4 ×(x 1 Ú`x 1));

6) χρησιμοποιήστε το νόμο της αντίφασης:

F=`x 2 ×(`x 3 Ú`x 4)

Σκηνικά θέατρου Boolean συναρτήσεις

Συχνά τίθεται το ερώτημα: είναι κάθε συνάρτηση Boolean αναπαραστάσιμη με μια υπέρθεση των τύπων f 0, f 1,..f 15; Προκειμένου να προσδιοριστεί η πιθανότητα σχηματισμού οποιασδήποτε συνάρτησης Boole χρησιμοποιώντας μια υπέρθεση αυτών των τύπων, είναι απαραίτητο να προσδιοριστούν οι ιδιότητές τους και οι συνθήκες χρήσης ενός λειτουργικά πλήρους συστήματος.

Αυτοδιπλές συναρτήσεις Boolean

αυτοδιττός , εάν f(x 1 ;x 2 ;…x n)=`f(`x 1 ;`x 2 ;…`x n).

Για παράδειγμα, οι συναρτήσεις f 3 (x 1 ;x 2)=x 1 , f 5 (x 1 ;x 2)=x 2 , f 10 (x 1 ;x 2)=`x 2 και f 12 (x 1 ;x 2)=`x 1 είναι αυτοδιπλό, γιατί όταν αλλάζει η τιμή του ορίσματος, αλλάζουν την τιμή τους.

Οποιαδήποτε συνάρτηση λαμβάνεται με πράξεις υπέρθεσης από αυτοδιπλές συναρτήσεις Boolean είναι η ίδια αυτοδιπλή. Επομένως, το σύνολο των αυτοδιπλών συναρτήσεων Boole δεν επιτρέπει το σχηματισμό μη αυτοδιπλών συναρτήσεων.

Μονοτονικές Boolean συναρτήσεις

Καλείται η συνάρτηση f(x 1 ; x 2 ;…x n). μονότονος , εάν για κάθε s 1i £s 2i Boolean διανύσματα (s 11 ; s 12 ;……;s 1n) και (s 21 ;s 22 ;……;s 2n) ικανοποιείται η ακόλουθη συνθήκη: f(s 11 ;s 12 ;… ;s 1i ;…;s 1n)£f(s 21 ;s 22 ;…;s 2i ;…;s 2n).

Για παράδειγμα, για τις συναρτήσεις f(x 1 ; x 2) οι μονοτονικές συναρτήσεις είναι:

αν (0; 0) £ (0; 1), τότε f(0; 0) £ f (0; 1),

αν (0; 0)£(1; 0), τότε f(0; 0)£f(1; 0),

αν (0; 1) £ (1; 1), τότε f(0; 1) £ f (1; 1),

αν (1; 0) £ (1; 1), τότε f(1; 0) £ f(1; 1).

Οι ακόλουθες λειτουργίες πληρούν αυτές τις προϋποθέσεις:

f 0 (x 1 ; x 2) = 0; f 1 (x 1 ; x 2) = (x 1 × x 2); f 3 (x 1 ; x 2) = x 1 ; f 5 (x 1 ; x 2) = x 2 ; f 7 (x 1 ;x 2)=(x 1 Úx 2); f 15 (x 1 ; x 2) = 1.

Οποιαδήποτε συνάρτηση λαμβάνεται χρησιμοποιώντας την πράξη υπέρθεσης από μονοτονικές συναρτήσεις Boolean είναι η ίδια μονότονη. Επομένως, το σύνολο των μονοτονικών συναρτήσεων δεν επιτρέπει το σχηματισμό μη μονοτονικών συναρτήσεων.

Γραμμικές συναρτήσεις Boolean

Η άλγεβρα Zhegalkin, που βασίζεται στη βάση F 4 =(×; Å; 1), επιτρέπει σε οποιαδήποτε λογική συνάρτηση να αναπαρασταθεί από ένα πολυώνυμο, κάθε όρος του οποίου είναι ένας συνδυασμός μεταβλητών I Boolean ενός διανύσματος Boole εντός 0£i£ n:

P(x 1 ; x 2 ;…x n)=b 0 ×1 Å b i ×x i Å 1 £ j ¹ k £ n b j ×x j ×x k Å……Å b 2n-1 ×x 1 ×x 2 ×... ×x n.

Για παράδειγμα, για λογικές συναρτήσεις f 8 (x 1 ; x 2)

Το πολυώνυμο Zhegalkin έχει τη μορφή: P(x 1; x 2)=1Å x 1 Å x 2 Å x 1 ×x 2.

Τα πλεονεκτήματα της άλγεβρας Zhegalkin είναι η «αριθμητοποίηση» των λογικών τύπων, ενώ τα μειονεκτήματα είναι η πολυπλοκότητα, ειδικά με μεγάλο αριθμό δυαδικών μεταβλητών.

Πολυώνυμα Zhegalkin που δεν περιέχουν συνδέσμους δυαδικών μεταβλητών, π.χ. P(x 1 ; x 2 ;…;x n)=b 0 ×1Åb 1 ×x 1 Å…Åb n ×x n ονομάζεται γραμμικός .

Για παράδειγμα, f 9 (x 1 ; x 2) = 1Åx 1 Åx 2, ή f 12 (x 1 ; x 2) = 1Åx 1 .

Οι κύριες ιδιότητες του συντελεστή λειτουργίας πρόσθεσης 2 δίνονται στον Πίνακα 1.18.

Εάν μια λογική συνάρτηση καθορίζεται από έναν πίνακα ή τύπο σε οποιαδήποτε βάση, π.χ. Εάν γνωρίζετε τις τιμές μιας συνάρτησης Boolean για διάφορα σύνολα Boolean μεταβλητών, τότε μπορείτε να υπολογίσετε όλες

συντελεστές b i του πολυωνύμου Zhegalkin, συντάσσοντας ένα σύστημα εξισώσεων για όλα τα γνωστά σύνολα δυαδικών μεταβλητών.

Παράδειγμα: δίνεται μια Boolean συνάρτηση f(x 1 ;x 2)=x 1 Úx 2. Οι τιμές αυτής της συνάρτησης είναι γνωστές για όλα τα σύνολα Boolean μεταβλητών.

F(0;0)=0=b 0 ×1Å b 1 ×0 Å b 2 ×0 Å b 3 ×0×0;

f(1;0)=1=b 0 ×1Å b 1 ×1Å b 2 ×0Å b 3 ×1×0;

f(1;1)=1=b 0 ×1Å b 1 ×1Å b 2 ×1Å b 3 ×1×1;

Πού βρίσκουμε b 0 =0; b 1 =1; b 2 =1; b 3 =1.

Επομένως, (x 1 Úx 2)=x 1 Åx 2 Åx 1 ×x 2, δηλαδή ο διαχωρισμός είναι μια μη γραμμική συνάρτηση Boole.

Παράδειγμα: δίνεται μια Boolean συνάρτηση f(x 1 ;x 2)=(x 1 ®x 2). Οι τιμές αυτής της συνάρτησης είναι επίσης γνωστές για όλα τα σύνολα δυαδικών μεταβλητών.

F(0;0)=1=b 0 ×1Å b 1 ×0 Å b 2 ×0 Å b 3 ×0×0;

f(0;1)=1=b 0 ×1Å b 1 ×0 Å b 2 ×1Å b 3 ×0×1;

f(1;0)=0=b 0 ×1Åb 1 ×1Åb 2 ×0Åb 3 ×1×0;

f(1;1)=1=b 0 ×1Åb 1 ×1Åb 2 ×1Åb 3 ×1×1;

Πού βρίσκουμε b 0 =1; b 1 =1; b 2 =0; b 3 =1.

Επομένως, (x 1 ®x 2)=1Å x 2 Å x 1 ×x 2.

Ο Πίνακας 1.19 δείχνει τα πολυώνυμα Zhegalkin για τους κύριους αντιπροσώπους των Boolean συναρτήσεων από τον Πίνακα 1.15.

Εάν δίνεται μια αναλυτική έκφραση για μια λογική συνάρτηση και οι τιμές της είναι άγνωστες για διάφορα σύνολα δυαδικών μεταβλητών, τότε είναι δυνατό να κατασκευαστεί ένα πολυώνυμο Zhegalkin με βάση τη συνδετική βάση της άλγεβρας Boole F 2 =(` ; ×) :

Έστω f(x 1 ; x 2)=(x 1 Úx 2).

Τότε (x 1 Úx 2)=ù(`x 1 ×`x 2)=((x 1 Å 1)×(x 2 Å 1))Å 1=x 1 ×x 2 Å x 1 ×1Å x 2 × 1Å 1×1Å1=

(x 1 Åx 2 Åx 1 × x 2).

Έστω f(x 1 ;x 2)=(x 1 ®x 2).

Τότε (x 1 ®x 2)=(`x 1 Úx 2)=ù(x 1 ×`x 2)=x 1 ×(x 2 Å 1)Å 1=x 1 ×x 2 Å x 1 ×1Å 1 = =(1Åx 1 Åx 1 ×x 2).

Έστω f(x 1 ;x 2)=(x 1 “x 2).

Τότε (x 1 “x 2)=(`x 1 ×`x 2 Úx 1 ×x 2)=ù(ù(`x 1 ×`x 2)×ù(x 1 ×x 2))=((( x 1 Å1)×(x 2 Å1))Å1)× ×(x 1 ×x 2 Å)Å1=(x 1 ×x 2 Åx 1 Åx 2 Å1Å1)×(x 1 ×x 2 Å1)Å1=x 1 ×x 2 Åx 1 ×x 2 Åx 1 ×x 2 Åx 1 Å

x 1 × x 2 Åx 2 Å1=(1Åx 1 Åx 2).

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

1.5.6.4. Λειτουργίες που αποθηκεύουν το "0"

Η συνάρτηση f(x 1 ; x 2 ;...x n) ονομάζεται διατήρηση του "0" εάν για σύνολα τιμών δυαδικών μεταβλητών (0; 0;...0) η συνάρτηση παίρνει την τιμή f(0; 0;…0)=0.

Για παράδειγμα, f 0 (0; 0)=0, f 3 (0; 0)=0, f 7 (0; 0)=0, κ.λπ.

Οποιαδήποτε συνάρτηση που λαμβάνεται με χρήση της λειτουργίας υπέρθεσης από συναρτήσεις που διατηρούν το "0" είναι η ίδια μια συνάρτηση που διατηρεί το "0", επομένως, το σύνολο των συναρτήσεων που διατηρεί το "0" δεν επιτρέπει το σχηματισμό συναρτήσεων που δεν διατηρούν το "0".

1.5.6.5. Λειτουργίες που αποθηκεύουν το "1"

Η συνάρτηση f(x 1 ; x 2 ;…x n) ονομάζεται διατήρηση του «1» εάν για σύνολα τιμών δυαδικών μεταβλητών (1; 1;…1) η συνάρτηση παίρνει την τιμή f(1;1;…1 )=1.

Για παράδειγμα, f 1 (1; 1)=1, f3(1; 1)=1, f 5 (1; 1)=1, κ.λπ.

Οποιαδήποτε συνάρτηση λαμβάνεται χρησιμοποιώντας την πράξη υπέρθεσης από συναρτήσεις που διατηρούν το "1" διατηρεί η ίδια το "1". Επομένως, το σύνολο των συναρτήσεων που διατηρούν το "1" δεν επιτρέπει το σχηματισμό συναρτήσεων που δεν διατηρούν το "1".

- (Ύστερα λατ. superpositio, - επικάλυψη, από το λατ. superpositus - τοποθετείται από πάνω) (σύνθεση) - λογική-μαθηματική πράξη. λογισμός, ο οποίος συνίσταται στη λήψη από κ.λ. δίνονται οι συναρτήσεις f και g δεδομένου λογισμού μιας νέας συνάρτησης g (f) (έκφραση g... ... Φιλοσοφική Εγκυκλοπαίδεια

Ο όρος υπέρθεση (υπέρθεση) μπορεί να αναφέρεται στις ακόλουθες έννοιες: Σύνθεση υπέρθεσης συναρτήσεων (σύνθετη συνάρτηση) Η αρχή της υπέρθεσης είναι μια αρχή στη φυσική και στα μαθηματικά που περιγράφει την υπέρθεση διεργασιών (για παράδειγμα, κύματα) και, ως συνέπεια, ... ... Βικιπαίδεια

Σύνθεση συναρτήσεων, σύνθεση δύο συναρτήσεων σύνθετη λειτουργία … Μαθηματική Εγκυκλοπαίδεια

Αυτός ο όρος έχει άλλες έννοιες, βλέπε Υπέρθεση. Κβαντομηχανική ... Wikipedia

Αυτό το άρθρο ή ενότητα περιέχει μια λίστα πηγών ή εξωτερικούς συνδέσμους, αλλά οι πηγές των επιμέρους δηλώσεων παραμένουν ασαφείς λόγω έλλειψης υποσημειώσεων... Wikipedia

Στη θεωρία των διακριτών συναρτησιακών συστημάτων, μια Boolean συνάρτηση είναι μια συνάρτηση τύπου, όπου είναι ένα Boolean σύνολο και το n είναι ένας μη αρνητικός ακέραιος, ο οποίος ονομάζεται αριότητα ή εντοπιότητα της συνάρτησης. Τα στοιχεία 1 (ένα) και 0 (μηδέν) ερμηνεύονται τυπικά ... ... Wikipedia

Ένα από τα πιο σημαντικά για τα θεμέλια των μαθηματικών και των μαθηματικών. λογικές κατηγορίες εννοιών που χρησιμεύουν ως διευκρινίσεις περιέχουν. οι έννοιες μιας αποτελεσματικά υπολογίσιμης αριθμητικής συνάρτησης και ενός αποτελεσματικά αποφασίσιμου αριθμητικού κατηγορήματος, και τελικά, και... ... Φιλοσοφική Εγκυκλοπαίδεια

Συνάρτηση, ο υπολογισμός των τιμών ενός σμήνους μπορεί να πραγματοποιηθεί χρησιμοποιώντας μια προκαθορισμένη αποτελεσματική διαδικασία ή αλγόριθμο. Ένα χαρακτηριστικό γνώρισμα των υπολογιστικών διαδικασιών είναι ο υπολογισμός των απαιτούμενων ποσοτήτων προβλημάτων που προκύπτουν διαδοχικά από τα αρχικά δεδομένα... ... Μαθηματική Εγκυκλοπαίδεια

Είναι απαραίτητο να μεταφέρετε τα περιεχόμενα αυτού του άρθρου στο άρθρο "Διαφοροποίηση μιγαδικής συνάρτησης". Μπορείτε να βοηθήσετε το έργο συνδυάζοντας άρθρα. Εάν είναι απαραίτητο να συζητήσουμε τη σκοπιμότητα της συγχώνευσης, αντικαταστήστε αυτό το πρότυπο με το πρότυπο ((για συγχώνευση)) ... Wikipedia

- (λατ. compositio σύνθεση, σύνδεση, προσθήκη, σύνδεση): Το Βικιλεξικό έχει άρθρο «σύνθεση» Η σύνθεση τέχνης (καλή τέχνη) είναι ένα οργανωτικό συστατικό μιας καλλιτεχνικής μορφής που δίνει υπέρ... Wikipedia

Βιβλία

• Διακριτά μαθηματικά. Βασικές θεωρητικές κατασκευές συνόλων. Μέρος VI, A.I Shirokov. Το εγχειρίδιο αποτελεί μέρος VI της ενότητας «Βασικές θεωρητικές κατασκευές συνόλων διακριτών μαθηματικών». Στο κεφ. XI θεωρεί τις ακόλουθες έννοιες: συνθέσεις συναρτήσεων (§1); λειτουργίες,...

Έστω μια συνάρτηση f(x 1 , x 2 , ... , x n) και συναρτήσεις

τότε θα καλέσουμε τη συνάρτηση υπέρθεση μιας συνάρτησης f(x 1 , x 2 , ... , x n) και λειτουργίες .

Με άλλα λόγια: έστω F = ( f j ) - ένα σύνολο συναρτήσεων λογικής άλγεβρας, όχι απαραίτητα πεπερασμένες. Μια συνάρτηση f λέγεται υπέρθεση συναρτήσεων από το σύνολο F ή συνάρτηση πάνω από F εάν λαμβάνεται από μια συνάρτηση αντικαθιστώντας μία ή περισσότερες από τις μεταβλητές της με συναρτήσεις από το σύνολο F.

Παράδειγμα.

Ας δοθεί ένα σύνολο συναρτήσεων

F = (f 1 (x 1), f 2 (x 1 , x 2 , x 3), f 3 (x 1 , x 2)).

Τότε οι υπέρθεση συναρτήσεων από το F θα είναι, για παράδειγμα, οι συναρτήσεις:

j 1 (x 2 , x 3) = f 3 (f 1 (x 2), f 1 (x 3));

j 2 (x 1 , x 2) = f 2 (x 1 , f 1 (x 1), f 3 (x 1 , x 2)).

Τέλειο DNF - υπέρθεση συναρτήσεων από ένα σύνολο

. ð

Ορισμός.

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

Έχουμε ήδη κάποιο σετ ολοκληρωμένα συστήματα:

;

Επειδή ;

Επειδή ;

(x+y, xy, 1). ð

Πώς μπορούμε να προσδιορίσουμε τις συνθήκες κάτω από τις οποίες είναι πλήρες το σύστημα; Στενά συνδεδεμένη με την έννοια της πληρότητας είναι η έννοια της κλειστής τάξης.

Κλειστά τμήματα.

Το σύνολο (κλάση) Κ των συναρτήσεων της άλγεβρας της λογικής ονομάζεται κλειστή τάξη, εάν περιέχει όλες τις συναρτήσεις που λαμβάνονται από το K με πράξεις υπέρθεσης και αλλαγής μεταβλητών και δεν περιέχει άλλες συναρτήσεις.

Έστω K κάποιο υποσύνολο συναρτήσεων από το P 2 . Το κλείσιμο του K είναι το σύνολο όλων των Boolean συναρτήσεων που μπορούν να αναπαρασταθούν χρησιμοποιώντας τις πράξεις υπέρθεσης και αλλαγής μεταβλητών συναρτήσεων από το σύνολο K. Το κλείσιμο ενός συνόλου K συμβολίζεται με [K].

Όσον αφορά το κλείσιμο, μπορούμε να δώσουμε άλλους ορισμούς του κλεισίματος και της πληρότητας (αντίστοιχοι με τους αρχικούς):

Το K είναι μια κλειστή κλάση αν K = [K];

Το K είναι ένα πλήρες σύστημα εάν [K] = P 2 .

Παραδείγματα.

* (0), (1) - κλειστά τμήματα.

* Ένα σύνολο συναρτήσεων μιας μεταβλητής είναι μια κλειστή κλάση.

* - κλειστή τάξη.

* Η κλάση (1, x+y) δεν είναι κλειστή τάξη.

Ας δούμε μερικές από τις πιο σημαντικές κλειστές τάξεις.

1. Τ 0- κατηγορία συναρτήσεων που διατηρούν το 0.

Ας συμβολίσουμε με T 0 την κλάση όλων των συναρτήσεων της άλγεβρας της λογικής f(x 1 , x 2 , ... , x n) διατηρώντας τη σταθερά 0, δηλαδή συναρτήσεις για τις οποίες f(0, ... , 0 ) = 0.

Είναι εύκολο να δούμε ότι υπάρχουν συναρτήσεις που ανήκουν στο T 0 και συναρτήσεις που δεν ανήκουν σε αυτήν την κατηγορία:

0, x, xy, xÚy, x+y О T 0 ;

Από το γεγονός ότι Ï T 0 προκύπτει, για παράδειγμα, ότι δεν μπορεί να εκφραστεί μέσω διαχωρισμού και συνδέσμου.

Δεδομένου ότι ο πίνακας για τη συνάρτηση f από την κλάση T 0 περιέχει την τιμή 0 στην πρώτη γραμμή, τότε για συναρτήσεις από T 0 μπορείτε να ορίσετε αυθαίρετες τιμές μόνο σε 2 n - 1 σύνολο μεταβλητών τιμών, δηλαδή

,

όπου είναι το σύνολο των συναρτήσεων που διατηρούν το 0 και εξαρτώνται από n μεταβλητές.

Ας δείξουμε ότι το T 0 είναι μια κλειστή τάξη. Εφόσον xΟT 0 , τότε για να δικαιολογηθεί η κλειστότητα αρκεί να δείξουμε την κλειστότητα ως προς την πράξη της υπέρθεσης, αφού η πράξη των μεταβαλλόμενων μεταβλητών είναι ειδική περίπτωσηυπέρθεση με συνάρτηση x.

Αφήστε . Τότε αρκεί να το δείξουμε . Το τελευταίο προκύπτει από την αλυσίδα των ισοτήτων

2. Τ 1- κλάση συναρτήσεων με διατήρηση 1.

Ας συμβολίσουμε με T 1 την κλάση όλων των συναρτήσεων της άλγεβρας της λογικής f(x 1, x 2, ... , x n) διατηρώντας τη σταθερά 1, δηλαδή συναρτήσεις για τις οποίες f(1, ... , 1 ) = 1.

Είναι εύκολο να δούμε ότι υπάρχουν συναρτήσεις που ανήκουν στην T 1 και συναρτήσεις που δεν ανήκουν σε αυτήν την κατηγορία:

1, x, xy, xÚy, xºy О T 1 ;

0, , x+y Ï T 1 .

Από το γεγονός ότι x + y Ï T 0 προκύπτει, για παράδειγμα, ότι το x + y δεν μπορεί να εκφραστεί με όρους διαχωρισμού και συνδέσμου.

Τα αποτελέσματα σχετικά με την κλάση T 0 μεταφέρονται επιπόλαια στην κατηγορία T 1 . Έτσι έχουμε:

T 1 - κλειστή τάξη.

.

3. Λ- κατηγορία γραμμικών συναρτήσεων.

Ας συμβολίσουμε με L την κλάση όλων των συναρτήσεων της άλγεβρας της λογικής f(x 1 , x 2 , ... , x n) που είναι γραμμικές:

Είναι εύκολο να δούμε ότι υπάρχουν συναρτήσεις που ανήκουν στο L και συναρτήσεις που δεν ανήκουν σε αυτήν την κατηγορία:

0, 1, x, x+y, x 1 º x 2 = x 1 + x 2 + 1, = x+1 О L;

Ας αποδείξουμε, για παράδειγμα, ότι xÚy Ï L .

Ας υποθέσουμε το αντίθετο. Θα αναζητήσουμε μια έκφραση για το xÚy με τη μορφή γραμμικής συνάρτησης με απροσδιόριστους συντελεστές:

Για x = y = 0 έχουμε a=0,

για x = 1, y = 0 έχουμε b = 1,

για x = 0, y = 1 έχουμε g = 1,

αλλά τότε για x = 1, y = 1 έχουμε 1v 1 ¹ 1 + 1, που αποδεικνύει τη μη γραμμικότητα της συνάρτησης xy.

Η απόδειξη της κλειστότητας της κλάσης των γραμμικών συναρτήσεων είναι αρκετά προφανής.

Εφόσον μια γραμμική συνάρτηση καθορίζεται μοναδικά καθορίζοντας τις τιμές n+1 του συντελεστή a 0 , ... , a n , ο αριθμός των γραμμικών συναρτήσεων στην κατηγορία L (n) των συναρτήσεων ανάλογα με n μεταβλητές είναι ίσος με 2 n+1 .

.

4. Σ- κατηγορία αυτοδιπλών λειτουργιών.

Ο ορισμός της κατηγορίας αυτοδιπλών συναρτήσεων βασίζεται στη χρήση της λεγόμενης αρχής της δυαδικότητας και των διπλών συναρτήσεων.

Η συνάρτηση που ορίζεται από την ισότητα καλείται διπλή στη λειτουργία .

Προφανώς, ο πίνακας για τη διπλή συνάρτηση (με την τυπική σειρά των συνόλων μεταβλητών τιμών) λαμβάνεται από τον πίνακα για την αρχική συνάρτηση αντιστρέφοντας (δηλαδή αντικαθιστώντας το 0 με το 1 και το 1 με το 0) τη στήλη των τιμών συνάρτησης και αναποδογυρίζοντας το.

Είναι εύκολο να το δεις αυτό

(x 1 Ú x 2)* = x 1 Ù x 2,

(x 1 Ù x 2)* = x 1 Ú x 2 .

Από τον ορισμό προκύπτει ότι (f*)* = f, δηλαδή η συνάρτηση f είναι διπλή προς f*.

Αφήστε μια συνάρτηση να εκφραστεί χρησιμοποιώντας υπέρθεση μέσω άλλων συναρτήσεων. Το ερώτημα είναι πώς να κατασκευάσετε έναν τύπο που να υλοποιεί ; Ας συμβολίσουμε με = (x 1, ..., x n) όλα τα διαφορετικά σύμβολα μεταβλητών που βρίσκονται στα σύνολα.

Θεώρημα 2.6.Αν η συνάρτηση j προκύπτει ως υπέρθεση των συναρτήσεων f, f 1, f 2, ..., f m, δηλαδή

μια συνάρτηση διπλή σε μια υπέρθεση είναι μια υπέρθεση διπλών συναρτήσεων.

Απόδειξη.

j*(x 1 ,...,x n) = ` f(`x 1 ,...,`x n) =

Το θεώρημα είναι αποδεδειγμένο. ð

Η αρχή της δυαδικότητας προκύπτει από το θεώρημα: εάν ένας τύπος A πραγματοποιεί τη συνάρτηση f(x 1 , ... , x n), τότε ο τύπος που προκύπτει από το A αντικαθιστώντας τις συναρτήσεις που περιλαμβάνονται σε αυτόν με τις διπλές τους πραγματοποιεί τη διπλή συνάρτηση f *(x 1 , ... , xn).

Ας υποδηλώσουμε με S την κλάση όλων των αυτοδιπλών συναρτήσεων από το P 2:

S = (f | f* = f )

Είναι εύκολο να δούμε ότι υπάρχουν συναρτήσεις που ανήκουν στο S και συναρτήσεις που δεν ανήκουν σε αυτήν την κατηγορία:

0, 1, xy, xÚy Ï S .

Ένα λιγότερο ασήμαντο παράδειγμα αυτοδιπλής συνάρτησης είναι η συνάρτηση

h(x, y, z) = xy Ú xz Ú ​​yz;

Χρησιμοποιώντας το θεώρημα της συνάρτησης διπλής υπέρθεσης, έχουμε

h*(x, y, z)= (x Ú y)Ù(x Ú z) Ù (y Ù z) = x y Ú x z Ú y z; h = h* ; h О S.

Για μια αυτοδιπλή λειτουργία, η ταυτότητα ισχύει

έτσι στα σετ και , που θα ονομάσουμε αντίθετο, η αυτοδιπλή συνάρτηση παίρνει αντίθετες τιμές. Από αυτό προκύπτει ότι η αυτοδιπλή συνάρτηση καθορίζεται πλήρως από τις τιμές της στο πρώτο μισό των σειρών του τυπικού πίνακα. Επομένως, ο αριθμός των αυτοδιπλών συναρτήσεων στην κλάση S (n) των συναρτήσεων ανάλογα με n μεταβλητές είναι ίσος με:

.

Ας αποδείξουμε τώρα ότι η κλάση S είναι κλειστή. Εφόσον xÎS , τότε για να δικαιολογηθεί η κλειστότητα αρκεί να δείξουμε την κλειστότητα ως προς τη λειτουργία της υπέρθεσης, αφού η πράξη αλλαγής μεταβλητών είναι ειδική περίπτωση υπέρθεσης με τη συνάρτηση x. Αφήστε . Τότε αρκεί να το δείξουμε . Το τελευταίο εγκαθίσταται απευθείας:

5. Μ- κατηγορία μονοτονικών συναρτήσεων.

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

Λένε ότι το σετ έρχεται πριν από το σετ (ή "όχι περισσότερο από", ή "λιγότερο από ή ίσο με"), και χρησιμοποιήστε τον συμβολισμό εάν a i £ b i για όλα τα i = 1, ... , n. Αν και , τότε θα πούμε ότι το σύνολο προηγείται αυστηρά του συνόλου (ή «αυστηρά λιγότερο», ή «λιγότερο από» του συνόλου) και θα χρησιμοποιήσουμε τον συμβολισμό . Τα σύνολα και ονομάζονται συγκρίσιμα αν , ή , στην περίπτωση που καμία από αυτές τις σχέσεις δεν ισχύει, τα σύνολα και ονομάζονται ασύγκριτα. Για παράδειγμα, (0, 1, 0, 1) £ (1, 1, 0, 1), αλλά τα σύνολα (0, 1, 1, 0) και (1, 0, 1, 0) είναι ασύγκριτα. Έτσι, η σχέση £ (συχνά αποκαλούμενη σχέση προτεραιότητας) είναι μια μερική σειρά στο σύνολο B n. Παρακάτω υπάρχουν διαγράμματα των μερικώς διατεταγμένων σετ Β 2, Β 3 και Β 4.

Η εισαγόμενη σχέση μερικής παραγγελίας είναι μια εξαιρετικά σημαντική έννοια που υπερβαίνει κατά πολύ το εύρος της πορείας μας.

Τώρα έχουμε την ευκαιρία να ορίσουμε την έννοια της μονοτονικής συνάρτησης.

Καλείται η συνάρτηση λογικής άλγεβρας μονότονος, εάν για οποιαδήποτε δύο σύνολα και , έτσι ώστε να ισχύει η ανισότητα . Το σύνολο όλων των μονότονων συναρτήσεων της άλγεβρας της λογικής συμβολίζεται με M και το σύνολο όλων των μονότονων συναρτήσεων που εξαρτώνται από n μεταβλητές συμβολίζεται με M(n).

Είναι εύκολο να δούμε ότι υπάρχουν συναρτήσεις που ανήκουν στο M και συναρτήσεις που δεν ανήκουν σε αυτήν την κλάση:

0, 1, x, xy, xÚy О M;

x+y, x®y, xºy Ï M .

Ας δείξουμε ότι η κλάση μονότονων συναρτήσεων M είναι μια κλειστή κλάση. Αφού xОМ, τότε για να δικαιολογήσουμε το κλειστό αρκεί να δείξουμε το κλειστό σε σχέση με τη λειτουργία της υπέρθεσης, αφού η πράξη αλλαγής μεταβλητών είναι ειδική περίπτωση υπέρθεσης με τη συνάρτηση x.

Αφήστε . Τότε αρκεί να το δείξουμε .

Έστω σύνολα μεταβλητών, αντίστοιχα, συναρτήσεις j, f 1 , ... , f m , και το σύνολο των μεταβλητών της συνάρτησης j αποτελείται από εκείνες και μόνο αυτές τις μεταβλητές που εμφανίζονται στις συναρτήσεις f 1 , ... , f m . Έστω και είναι δύο σύνολα τιμών της μεταβλητής, και . Αυτά τα σύνολα ορίζουν τα σύνολα μεταβλητές τιμές , τέτοιο που . Λόγω της μονοτονίας των συναρτήσεων f 1 , ... , f m

και λόγω της μονοτονίας της συνάρτησης f

Από εδώ παίρνουμε

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

όπου - είναι το ακέραιο μέρος του n/2.

Επίσης απλώς αποδεικνύεται ότι η παραπάνω εκτίμηση είναι πολύ υψηλή:

Η βελτίωση αυτών των εκτιμήσεων είναι ένα σημαντικό και ενδιαφέρον έργο της σύγχρονης έρευνας.

Κριτήριο πληρότητας

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

Λήμμα 2.7.Λήμμα σχετικά με τη μη αυτοδιπλή λειτουργία.

Αν f(x 1 , ... , x n)Ï S , τότε μια σταθερά μπορεί να ληφθεί από αυτήν αντικαθιστώντας τις συναρτήσεις x και `x.

Απόδειξη. Από το fÏS, τότε υπάρχει ένα σύνολο τιμών των μεταβλητών
=(a 1 ,...,a n) τέτοια ώστε

f(`a 1 ,...,`a n) = f(a 1 ,...,a n)

Ας αντικαταστήσουμε τα ορίσματα στη συνάρτηση f:

Το x i αντικαθίσταται από ,

δηλαδή ας βάλουμε και ας θεωρήσουμε τη συνάρτηση

Έτσι, έχουμε λάβει μια σταθερά (αν και δεν είναι γνωστό ποια σταθερά είναι: 0 ή 1). ð

Λήμμα 2.8.Λήμμα για τη μη μονοτονική λειτουργία.

Εάν η συνάρτηση f(x 1 ,...,x n) είναι μη μονότονη, f(x 1 ,...,x n) Ï M, τότε μια άρνηση μπορεί να ληφθεί από αυτήν αλλάζοντας μεταβλητές και αντικαθιστώντας τις σταθερές 0 και 1.

Απόδειξη. Εφόσον f(x 1 ,...,x n) Ï M, τότε υπάρχουν σύνολα τιμών των μεταβλητών του, , , έτσι ώστε , και για τουλάχιστον μία τιμή i, a i< b i . Выполним следующую замену переменных функции f:

x i θα αντικατασταθεί από

Μετά από μια τέτοια αντικατάσταση παίρνουμε μια συνάρτηση μιας μεταβλητής j(x), για την οποία έχουμε:

Αυτό σημαίνει ότι j(x)=`x. Το λήμμα είναι αποδεδειγμένο. ð

Λήμμα 2.9.Λήμμα για τη μη γραμμική συνάρτηση.

Αν f(x 1 ,...,x n) Ï L , τότε από αυτό αντικαθιστώντας τις σταθερές 0, 1 και χρησιμοποιώντας τη συνάρτηση `x μπορούμε να λάβουμε τη συνάρτηση x 1 &x 2 .

Απόδειξη. Ας αναπαραστήσουμε τη f ως DNF (για παράδειγμα, τέλειο DNF) και χρησιμοποιούμε τις σχέσεις:

Παράδειγμα. Ας δώσουμε δύο παραδείγματα εφαρμογής αυτών των μετασχηματισμών.

Έτσι, μια συνάρτηση γραμμένη σε διαζευκτική κανονική μορφή, μετά την εφαρμογή των υποδεικνυόμενων σχέσεων, ανοίγοντας παρενθέσεις και απλούς αλγεβρικούς μετασχηματισμούς, γίνεται πολυώνυμο mod 2 (πολυώνυμο Zhegalkin):

όπου A 0 είναι μια σταθερά, και A i είναι ένας σύνδεσμος ορισμένων μεταβλητών από τον αριθμό x 1,..., x n, i = 1, 2, ..., r.

Αν κάθε σύνδεσμος A i αποτελείται από μία μόνο μεταβλητή, τότε η f είναι μια γραμμική συνάρτηση, η οποία έρχεται σε αντίθεση με την συνθήκη του λήμματος.

Κατά συνέπεια, στο πολυώνυμο Zhegalkin για τη συνάρτηση f υπάρχει ένας όρος που περιέχει τουλάχιστον δύο παράγοντες. Χωρίς απώλεια γενικότητας, μπορούμε να υποθέσουμε ότι μεταξύ αυτών των παραγόντων υπάρχουν οι μεταβλητές x 1 και x 2. Τότε το πολυώνυμο μπορεί να μετασχηματιστεί ως εξής:

f = x 1 x 2 f 1 (x 3 ,..., x n) + x 1 f 2 (x 3 ,..., x n) + x 2 f 3 (x 3 ,..., x n) + f 4 (x 3 ,..., x n),

όπου f 1 (x 3 ,..., x n) 1 0 (διαφορετικά το πολυώνυμο δεν περιλαμβάνει σύνδεσμο που περιέχει τον σύνδεσμο x 1 x 2).

Έστω (a 3 ,...,a n) έτσι ώστε f 1 (a 3 ,...,a n) = 1. Τότε

j(x 1 ,x 2) = f(x 1 ,x 2 , a 3 ,...,a n) = x 1 x 2 +ax 1 +bx 2 +g ,

όπου a, b, g είναι σταθερές ίσες με 0 ή 1.

Ας χρησιμοποιήσουμε την πράξη άρνησης που έχουμε και ας θεωρήσουμε τη συνάρτηση y(x 1 ,x 2) που προκύπτει από το j(x 1 ,x 2) ως εξής:

y(x 1 ,x 2) = j(x 1 +b, x 2 +a)+ab+g.

Είναι προφανές ότι

y(x 1 ,x 2) =(x 1 +b)(x 2 +a)+a(x 1 +b)+b(x 2 +a)+g+ab+g = x 1 x 2.

Οθεν,

y(x 1 ,x 2) = x 1 x 2 .

Το λήμμα είναι απόλυτα αποδεδειγμένο. ð

Λήμμα 2.10.Το κύριο λήμμα του κριτηρίου πληρότητας.

Εάν η κλάση F=( f ) των συναρτήσεων λογικής άλγεβρας περιέχει συναρτήσεις που δεν διατηρούν την ενότητα, δεν διατηρούν το 0, είναι μη-αυτοδιττές και μη μονότονες:

τότε από τις συναρτήσεις αυτού του συστήματος, με πράξεις υπέρθεσης και αντικατάστασης μεταβλητών, μπορεί κανείς να πάρει τις σταθερές 0, 1 και τη συνάρτηση.

Απόδειξη. Ας εξετάσουμε τη συνάρτηση. Τότε

.

Υπάρχουν δύο πιθανές περιπτώσεις μεταγενέστερων εκτιμήσεων, που προσδιορίζονται στην ακόλουθη παρουσίαση ως 1) και 2).

1). Η συνάρτηση στο σύνολο μονάδων παίρνει την τιμή 0:

.

Θα τα αντικαταστήσουμε όλα μεταβλητές συναρτήσειςμεταβλητή x. Στη συνέχεια η συνάρτηση

υπάρχει γιατί

Και .

Ας πάρουμε μια μη αυτοδιπλή συνάρτηση. Εφόσον έχουμε ήδη αποκτήσει τη συνάρτηση, τότε από το λήμμα σε μια μη αυτοδιπλή συνάρτηση (λήμμα 2.7. ) μπορείτε να πάρετε μια σταθερά από. Η δεύτερη σταθερά μπορεί να ληφθεί από την πρώτη χρησιμοποιώντας τη συνάρτηση. Έτσι, στην πρώτη περίπτωση που εξετάστηκε, λαμβάνονται οι σταθερές και η άρνηση. . Η δεύτερη περίπτωση, και μαζί της το κύριο λήμμα του κριτηρίου της πληρότητας, αποδεικνύονται πλήρως. ð

Θεώρημα 2.11.Κριτήριο για την πληρότητα συστημάτων συναρτήσεων στην άλγεβρα της λογικής (θεώρημα Post).

Προκειμένου το σύστημα των συναρτήσεων F = (f i) να είναι πλήρες, είναι απαραίτητο και αρκετό να μην περιέχεται πλήρως σε καμία από τις πέντε κλειστές κλάσεις T 0, T 1, L, S, M, δηλαδή για καθεμία από τις κλάσεις T 0 , T 1 , L , S, M στο F υπάρχει τουλάχιστον μία συνάρτηση που δεν ανήκει σε αυτήν την κλάση.

Ανάγκη. Έστω F ένα πλήρες σύστημα. Ας υποθέσουμε ότι η F περιέχεται σε μια από τις υποδεικνυόμενες κλάσεις, ας τη συμβολίσουμε με K, δηλ. F Í K. Η τελευταία συμπερίληψη είναι αδύνατη, αφού το K είναι μια κλειστή τάξη που δεν είναι πλήρες σύστημα.

Επάρκεια. Έστω ότι ολόκληρο το σύστημα συναρτήσεων F = (f i ) δεν περιέχεται σε καμία από τις πέντε κλειστές κλάσεις T 0 , T 1 , L , S , M .

Στη συνέχεια, με βάση το κύριο λήμμα (λήμμα 2.10 ) από μια συνάρτηση που δεν διατηρεί το 0, μια συνάρτηση που δεν διατηρεί το 1, τις μη αυτοδιπλές και μη μονότονες συναρτήσεις, μπορούμε να λάβουμε τις σταθερές 0, 1 και τη συνάρτηση άρνησης:

.

Με βάση το λήμμα των μη γραμμικών συναρτήσεων (λήμμα 2.9 ) από σταθερές, άρνηση και μη γραμμική συνάρτηση μπορούμε να πάρουμε τον σύνδεσμο:

.

Σύστημα λειτουργίας - ένα πλήρες σύστημα σύμφωνα με το θεώρημα σχετικά με τη δυνατότητα αναπαράστασης οποιασδήποτε συνάρτησης της άλγεβρας της λογικής με τη μορφή μιας τέλειας διαζευκτικής κανονικής μορφής (σημειώστε ότι η διάζευξη μπορεί να εκφραστεί μέσω σύνδεσης και άρνησης στη μορφή ).

Το θεώρημα είναι πλήρως αποδεδειγμένο. ð

Παραδείγματα.

1. Ας δείξουμε ότι η συνάρτηση f(x,y) = x|y σχηματίζει ένα πλήρες σύστημα. Ας δημιουργήσουμε έναν πίνακα τιμών της συνάρτησης x½y:

x	y	x|y

f(0,0) = 1, επομένως x | yÏT 0.

f(1,1) = 0, επομένως x | yÏT 1.

f(0,0) = 1, f(1,1) = 0, επομένως x | yÏM.

f(0,1) = f(1,0) = 1, - σε αντίθετα σύνολα x | Το y παίρνει τις ίδιες τιμές, επομένως το x | ναι .

Τελικά, τι σημαίνει η μη γραμμικότητα της συνάρτησης;
x | y.

Με βάση το κριτήριο της πληρότητας, μπορούμε να δηλώσουμε ότι f(x,y) = x | y σχηματίζει ένα πλήρες σύστημα. ð

2. Ας δείξουμε ότι το σύστημα συναρτήσεων σχηματίζει ένα πλήρες σύστημα.

Αλήθεια, .

Έτσι, μεταξύ των συναρτήσεων του συστήματός μας βρήκαμε: μια συνάρτηση που δεν διατηρεί το 0, μια συνάρτηση που δεν διατηρεί το 1, μη αυτοδιπλές, μη μονοτονικές και μη γραμμικές συναρτήσεις. Με βάση το κριτήριο της πληρότητας, μπορεί να υποστηριχθεί ότι το σύστημα συναρτήσεων σχηματίζει ένα πλήρες σύστημα. ð

Έτσι, είμαστε πεπεισμένοι ότι το κριτήριο πληρότητας δίνει μια εποικοδομητική και αποτελεσματικό τρόποαποσαφήνιση της πληρότητας συστημάτων συναρτήσεων της άλγεβρας της λογικής.

Ας διατυπώσουμε τώρα τρία συμπεράσματα από το κριτήριο της πληρότητας.

Συμπέρασμα 1. Οποιαδήποτε κλειστή κλάση K συναρτήσεων της άλγεβρας της λογικής που δεν συμπίπτει με ολόκληρο το σύνολο των συναρτήσεων της άλγεβρας της λογικής (K1P 2) περιέχεται σε τουλάχιστον μία από τις κατασκευασμένες κλειστές κλάσεις.

Ορισμός.Η κλειστή κλάση Κ ονομάζεται προ-γεμάτη, αν το K είναι ατελές και για οποιαδήποτε συνάρτηση fÏ K η κλάση K È (f) είναι πλήρης.

Από τον ορισμό προκύπτει ότι η προ-ολοκληρωμένη κλάση είναι κλειστή.

Συμπέρασμα 2.Στην άλγεβρα της λογικής υπάρχουν μόνο πέντε προολοκληρωμένες τάξεις, δηλαδή: T 0, T 1, L, M, S.

Για να αποδείξετε το συμπέρασμα, χρειάζεται μόνο να ελέγξετε ότι καμία από αυτές τις κλάσεις δεν περιέχεται στην άλλη, κάτι που επιβεβαιώνεται, για παράδειγμα, από τον ακόλουθο πίνακα συναρτήσεων που ανήκουν σε διαφορετικές κλάσεις:

	T0	Τ 1	μεγάλο	μικρό	Μ
	+	-	+	-	+
	-	+	+	-	+
	-	-	+	+	-

Συμπέρασμα 3.Από οποιοδήποτε πλήρες σύστημα συναρτήσεων είναι δυνατό να διακριθεί ένα πλήρες υποσύστημα που δεν περιέχει περισσότερες από τέσσερις συναρτήσεις.

Από την απόδειξη του κριτηρίου της πληρότητας προκύπτει ότι δεν μπορούν να διακριθούν περισσότερες από πέντε συναρτήσεις. Από την απόδειξη του κύριου λήμματος (Λήμμα 2.10 ) προκύπτει ότι είναι είτε μη-αυτοδιττός είτε δεν διατηρεί την ενότητα και δεν είναι μονοτονικός. Επομένως, δεν χρειάζονται περισσότερες από τέσσερις λειτουργίες.

Οι διακριτές λογικές συσκευές ενός κύκλου (δεν περιέχουν στοιχεία μνήμης) εφαρμόζουν στην έξοδο ένα συγκεκριμένο σύνολο συναρτήσεων λογικής άλγεβρας `F m =(φά 1 ,ΦΑ 2 ,…,F m), τα οποία σε κάθε χρονική στιγμή εξαρτώνται μόνο από την κατάσταση των εισόδων της συσκευής `x n =(x 1 ,χ 2 ,…,x n): `F m = `F m(`x n). Στην πράξη, τέτοιες συσκευές σχεδιάζονται και κατασκευάζονται από ξεχωριστά αδιαίρετα στοιχεία που υλοποιούν ένα συγκεκριμένο σύνολο (σύστημα) ( φά) στοιχειώδεις συναρτήσεις της άλγεβρας συνδέοντας τις εξόδους ορισμένων στοιχείων με τις εισόδους άλλων.

Κατά το σχεδιασμό λογικών συσκευών, οι ακόλουθες ερωτήσεις είναι σχετικές.

1. Δίνεται ένα σύστημα στοιχειωδών συναρτήσεων ( φά). Ποιες είναι οι συναρτήσεις εξόδου; F iμπορεί να ληφθεί χρησιμοποιώντας συναρτήσεις από ( φά}?

2. Ένα σύνολο συναρτήσεων Boolean εξόδου ( φά) (συγκεκριμένα, ίσο με ολόκληρο το σύνολο των συναρτήσεων της άλγεβρας της λογικής R 2). Ποιο θα πρέπει να είναι το αρχικό σύστημα στοιχειωδών συναρτήσεων ( φά), παρέχοντας τη δυνατότητα λήψης στην έξοδο οποιασδήποτε από τις λειτουργίες του συνόλου ( φά}?

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

Ορισμός.Ας εξετάσουμε ένα σύνολο λογικών συνδέσεων ( φά), που αντιστοιχεί σε κάποιο σύστημα συναρτήσεων ( φά} . Τελείωσε η υπέρθεση{φά) είναι οποιαδήποτε συνάρτηση j που μπορεί να πραγματοποιηθεί με έναν τύπο πάνω από ( φά}.

Στην πράξη, η υπέρθεση μπορεί να αναπαρασταθεί ως αποτέλεσμα αντικατάστασης συναρτήσεων από ( φά) ως ορίσματα σε μια συνάρτηση από το ίδιο σύνολο.

Παράδειγμα 1. Εξετάστε ένα σύστημα συναρτήσεων ( φά} = {φά 1 (Χ) =`x, f 2 (x,y)= Χ&y, f 3 (x,y)=ΧÚ y). Αντικατάσταση στη συνάρτηση φά 3 (x,y) αντί για το πρώτο όρισμα Χλειτουργία φά 1 (Χ), αντί για το δεύτερο - φά 2 (x,y), παίρνουμε την υπέρθεση η(x,y)=φά 3 (φά 1 (Χ), στ 2 (x,y))=`xÚ Χ& στο. Η φυσική υλοποίηση της αντικατάστασης δίνεται στο Σχ. 1.18.

Ορισμός.Αφήνω Μ-ορισμένο σύνολο συναρτήσεων λογικής άλγεβρας( Π 2). Το σύνολο όλων των υπερθέσεων έχει τελειώσει Μκάλεσε βραχυκύκλωμασκηνικά Μκαι συμβολίζεται με [ Μ]. Λήψη [ Μ]από το αρχικό σετ Μκάλεσε λειτουργία κλεισίματος. Πολοί Μκάλεσε λειτουργικά κλειστή τάξη, Αν [ Μ] = Μ. Υποσύνολο mÍ Μκάλεσε λειτουργικά πλήρες σύστημα στο Μ, Αν [ m] = Μ.

Κλείσιμο [ Μ] αντιπροσωπεύει ολόκληρο το σύνολο των συναρτήσεων που μπορούν να ληφθούν από Μεφαρμόζοντας την πράξη υπέρθεσης, δηλ. όλες τις πιθανές αντικαταστάσεις.

Σημειώσεις. 1.Προφανώς, οποιοδήποτε σύστημα λειτουργιών ( φά) είναι λειτουργικά πλήρης από μόνη της.

2 . Χωρίς απώλεια γενικότητας, μπορούμε να υποθέσουμε ότι η ταυτότητα λειτουργεί φά(Χ)=x, το οποίο δεν αλλάζει τις τιμές αλήθειας των μεταβλητών, είναι αρχικά μέρος οποιουδήποτε συστήματος συναρτήσεων.

Παράδειγμα 2. Για τα συστήματα λειτουργιών που συζητούνται παρακάτω ( φά) κάντε τα εξής:

1) βρείτε το κλείσιμο [ φά],

2) μάθετε εάν το σύστημα ( φά) κλειστή τάξη,

3) βρείτε λειτουργικά πλήρη συστήματα στο ( φά}.

Διάλυμα.

Ι. ( φά}={0} . Κατά την αντικατάσταση της συνάρτησης ( στº 0) το λαμβάνουμε στον εαυτό μας, δηλ. δεν δημιουργούνται νέες λειτουργίες. Ακολουθεί: [ φά] = {φά). Το εξεταζόμενο σύστημα είναι μια λειτουργικά κλειστή κατηγορία. Το λειτουργικά πλήρες σύστημα σε αυτό είναι ένα και ίσο με το σύνολο ( φά}.

II. ( φά} = {0,Ø } . Αλλαγή Ø (Ø Χ) δίνει μια πανομοιότυπη λειτουργία που δεν επεκτείνει επίσημα το αρχικό σύστημα. Ωστόσο, όταν αντικαθιστούμε το Ø (0) παίρνουμε την ίδια μονάδα - νέο χαρακτηριστικό, που δεν ήταν στο αρχικό σύστημα: Ø (0)=1 . Η εφαρμογή όλων των άλλων αντικαταστάσεων δεν οδηγεί στην εμφάνιση νέων συναρτήσεων, για παράδειγμα: ØØ 0 = 0, 0 (Ø Χ)=0.

Έτσι, η χρήση της λειτουργίας υπέρθεσης κατέστησε δυνατή την απόκτηση ενός ευρύτερου συνόλου συναρτήσεων από το αρχικό [ φά]=(0,Ø ,1). Αυτό συνεπάγεται αυστηρή καταχώριση: ( φά} Ì [ φά]. Σύστημα πηγής ( φά) δεν είναι λειτουργικά κλειστή τάξη. Εκτός από το ίδιο το σύστημα ( φά) δεν υπάρχουν άλλα λειτουργικά ολοκληρωμένα συστήματα σε αυτό, αφού σε περίπτωση στένωσης από μία συνάρτηση f=Το 0 δεν μπορεί να αναιρεθεί με αντικατάσταση και το ίδιο μηδέν δεν μπορεί να ληφθεί μόνο από τη συνάρτηση άρνησης.

III. ( φά) = (& ,Ú ,Ø ).Το κλείσιμο αυτού του συστήματος είναι ολόκληρο το σύνολο των συναρτήσεων της άλγεβρας της λογικής Π 2, αφού ο τύπος οποιουδήποτε από αυτούς μπορεί να αναπαρασταθεί ως DNF ή CNF, που χρησιμοποιεί στοιχειώδεις συναρτήσεις ( φά) = (& ,Ú ,Ø). Αυτό το γεγονός είναι μια εποικοδομητική απόδειξη της πληρότητας του εξεταζόμενου συστήματος λειτουργιών στο Π 2: [φά]=Π 2 .

Από μέσα ΠΤο 2 περιέχει έναν άπειρο αριθμό άλλων συναρτήσεων εκτός από ( φά) = (& ,Ú ,Ø ), τότε αυτό συνεπάγεται ένα αυστηρό συμβάν: ( φά}Ì[ φά]. Το εξεταζόμενο σύστημα δεν είναι λειτουργικά κλειστή κατηγορία.

Εκτός από το ίδιο το σύστημα, τα υποσυστήματα θα είναι λειτουργικά πλήρη ( φά) 1 = (& ,Ø ) και ( φά) 2 = (Ú ,Ø ). Αυτό προκύπτει από το γεγονός ότι, χρησιμοποιώντας τους κανόνες του De Morgan, η συνάρτηση λογικής πρόσθεσης Ú μπορεί να εκφραστεί μέσω (& , Ø) και η συνάρτηση λογικού πολλαπλασιασμού & μέσω (Ú, Ø):

(Χ & στο) = Ø (` ΧÚ` στο), (Χ Ú στο) = Ø ( Χ &`στο).

Άλλα λειτουργικά πλήρη υποσυστήματα σε ( φά) Όχι.

Έλεγχος της πληρότητας του υποσυστήματος συνάρτησης ( φά) 1 Μ ( φά) σε ολόκληρο το σύστημα ( φά)μπορεί να παραχθεί με ανάμειξη ( φά) 1 σε άλλο, προφανώς πλήρης σε ( φά)σύστημα.

Ημιτελή του υποσυστήματος ( φά) 1 σε ( φά)μπορεί να επαληθευτεί αποδεικνύοντας την αυστηρή εμφάνιση [ φά 1 ] М [ φά].

Ορισμός.Υποσύνολο mÍ Μκάλεσε λειτουργική βάση(βάση)συστήματα Μ, Αν [ m] = Μ, και αφού εξαιρέσουμε οποιαδήποτε συνάρτηση από αυτήν, το σύνολο των υπόλοιπων δεν είναι πλήρες Μ .

Σχόλιο. Βάσεις του συστήματος συναρτήσεων (φά)είναι όλα τα λειτουργικά πλήρη υποσυστήματα του (φά) 1, το οποίο δεν μπορεί να μειωθεί χωρίς απώλεια πληρότητας (φά).

Παράδειγμα 3. Για όλα τα συστήματα που εξετάζονται στο Παράδειγμα 2, βρείτε βάσεις.

Διάλυμα.Στις περιπτώσεις 1 και 2 μόνο τα ίδια τα συστήματα είναι λειτουργικά πλήρη και είναι αδύνατο να περιοριστούν. Κατά συνέπεια, είναι και βάσεις.

Στην περίπτωση 3 υπάρχουν δύο λειτουργικά πλήρεις σε ( φά) υποσυστήματα ( φά) 1 = (&,Ø ) και ( φά) 2 =(Ú,Ø ), το οποίο δεν μπορεί να μειωθεί χωρίς απώλεια πληρότητας. Θα είναι οι βάσεις του συστήματος ( φά} = {&,Ú,Ø}.

Ορισμός.Αφήστε το σύστημα ( φά) είναι μια κλειστή τάξη. Το υποσύνολο του ( φά) 1 Μ ( φά) καλούνται junior class in{φά), αν ( φά) Το 1 δεν είναι πλήρες σε ( φά} ([φά 1 ] М [ φά]), και για οποιαδήποτε συνάρτηση j από το σύστημα( φά), δεν περιλαμβάνεται στο ( φά) 1 (jΟ( φά} \ {φά) 1) αληθές: [ ιÈ { φά} 1 ] = [φά], δηλ. προσθέτοντας jκ ( φά) 1 το ολοκληρώνει σε ( φά} .

Καθήκοντα

1. Ελέγξτε την κλειστότητα των συνόλων συναρτήσεων:

α) (Ø); β) (1, Ø ); γ) ((0111)· (10))·δ) ((11101110); (0110))·δ) ((0001); (00000001)· (00000000000000001); …).

2. Ελέγξτε την πληρότητα των συστημάτων λειτουργιών Π 2:

α) (0,Ø); β) ((0101) , (1010) ); V ); δ) ((0001) , (1010) ).

3. Βρείτε το κλείσιμο του συστήματος συναρτήσεων και τη βάση του:

α) (0, 1, Ø); β) ((1000) , (1010), (0101)); γ) ((0001), (1110), (10)); δ) ((1010) , (0001), (0111) ).

1.10.2 Συναρτήσεις που αποθηκεύουν σταθερές. Τάξεις Τ 0 και Τ 1

Ορισμός.Λειτουργία φά(`x n) σώζει 0 αν φά(0,..., 0) = 0. Λειτουργία φά(`x n) σώζει 1 αν φά(1, ... , 1) = 1.

Πολλά χαρακτηριστικά nΟι μεταβλητές που αποθηκεύουν το 0 και το 1 συμβολίζονται, αντίστοιχα, Τ 0 nΚαι Τ 1 n. Όλα τα σύνολα συναρτήσεων λογικής άλγεβρας που διατηρούν το 0 και το 1 , δείχνω Τ 0 Και Τ 1. Κάθε ένα από τα σετ Τ 0 και Τ 1 είναι μια κλειστή προολοκληρωμένη τάξη στο R 2 .

Από τις στοιχειώδεις λειτουργίες έως Τ 0 και Τ 1 περιλαμβάνονται ταυτόχρονα, για παράδειγμα, & και Ú. Ανήκει οποιαδήποτε λειτουργία σε κλάσεις Τ 0 , ΤΤο 1 μπορεί να ελεγχθεί από την πρώτη και την τελευταία τιμή του διανύσματος τιμών του στον πίνακα αληθείας ή αντικαθιστώντας απευθείας τα μηδενικά και τα μονά στον τύπο κατά τον αναλυτικό προσδιορισμό της συνάρτησης.

Ορισμός.Αντίγραφοείναι μια αντικατάσταση στην οποία η ίδια μεταβλητή αντικαθίσταται σε μια συνάρτηση αντί για πολλές ανεξάρτητες μεταβλητές. Σε αυτήν την περίπτωση, οι τιμές των μεταβλητών σε σύνολα που προηγουμένως έπαιρναν τιμές ανεξάρτητα το ένα από το άλλο θα είναι πάντα οι ίδιες.

ΚΑΘΗΚΟΝΤΑ

1. Ελέγξτε τη συμμετοχή στην τάξη Τ 0 Και Τ 1λειτουργίες:

α) γενικευμένη πρόσθεση, β) γενικευμένος πολλαπλασιασμός, γ) σταθερές, δ) xyÚ yz, δ) Χ® στο® xy, ε) ΧÅ στο, και)( Χ 1 Å … Å Χ n) ® ( y 1 Å … Å yιγ) στο n,mÎ Ν.

2. Να αποδείξετε την κλειστότητα κάθε τάξης Τ 0 Και Τ 1 .

3. Να αποδείξετε ότι αν φά(`x n) Ï Τ 0, τότε από αυτό, αντιγράφοντας την αντικατάσταση, μπορείτε να πάρετε τη σταθερά 1 ή την άρνηση.

4. Να αποδείξετε ότι αν φά(`x n) Ï Τ 1 , τότε από αυτό, αντιγράφοντας την αντικατάσταση, μπορείτε να πάρετε τη σταθερά 0 ή άρνηση.

5. Να αποδείξετε την προ-πληρότητα καθεμιάς από τις τάξεις Τ 0 Και Τ 1 (για παράδειγμα, μειώνοντας το επαυξημένο σύστημα σε ( φά} = {& ,Ú ,Ø }).

6. Βρείτε την πληθώρα των τάξεων Τ 0 nΚαι Τ 1 n.

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

Ορισμός 9. Εάν, σε ένα ορισμένο διάστημα X, ορίζεται μια συνάρτηση z-φ(lz) με ένα σύνολο τιμών Z και μια συνάρτηση y =/(z) ορίζεται στο σύνολο Z, τότε η συνάρτηση y είναι μια μιγαδική συνάρτηση του x (ή μια υπέρθεση της συνάρτησης), και η μεταβλητή z - μια ενδιάμεση μεταβλητή μιας μιγαδικής συνάρτησης.  

Ο έλεγχος μπορεί να αναπαρασταθεί ως μια υπέρθεση τριών κλασικών λειτουργιών διαχείρισης - λογιστική, έλεγχος και ανάλυση (αναδρομική). Ο έλεγχος ως λειτουργία ολοκληρωμένης διαχείρισης καθιστά δυνατή όχι μόνο την προετοιμασία μιας απόφασης, αλλά και τη διασφάλιση του ελέγχου επί της εφαρμογής της χρησιμοποιώντας κατάλληλα εργαλεία διαχείρισης.  

Όπως είναι γνωστό /50/, οποιαδήποτε συνάρτηση χρόνου μπορεί να αναπαρασταθεί ως υπέρθεση (σύνολο) απλών αρμονικών συναρτήσεων με διαφορετικές περιόδους, πλάτη και φάσεις. Γενικά, P(t) = f(t),  

Μεταβατικό ή παρορμητική απόκρισηπροσδιορίζεται πειραματικά. Όταν χρησιμοποιούνται χρησιμοποιώντας τη μέθοδο υπέρθεσης, το επιλεγμένο μοντέλο δράσης εισόδου αρχικά αποσυντίθεται σε στοιχειώδεις "συναρτήσεις χρόνου, και στη συνέχεια συνοψίζονται οι αποκρίσεις σε αυτές. Η τελευταία πράξη μερικές φορές ονομάζεται συνέλιξη και τα ολοκληρώματα σε εκφράσεις (24) ... (29) είναι ολοκληρώματα συνέλιξης Από Επιλέγουν εκείνο του οποίου το ολοκλήρωμα είναι απλούστερο.  

Αυτό το θεώρημα μειώνει το υπό όρους ακραίο πρόβλημα σε μια υπέρθεση ακραίων προβλημάτων χωρίς όρους. Πράγματι, ας ορίσουμε τη συνάρτηση R (g)  

Η υπέρθεση ((>(f(x)), όπου το y(y) είναι μια μη φθίνουσα κυρτή συνάρτηση μιας μεταβλητής, το /(x) είναι μια κυρτή συνάρτηση, είναι μια κυρτή συνάρτηση.  

Παράδειγμα 3.28. Ας επιστρέψουμε στο Παράδειγμα 3.27. Στο Σχ. Το σχήμα 3.24 δείχνει με τη μορφή διακεκομμένης καμπύλης το αποτέλεσμα της υπέρθεσης δύο συναρτήσεων μέλους που αντιστοιχούν στους ποσοτικούς δείκτες που υπάρχουν σε αυτό το παράδειγμα. Χρησιμοποιώντας ένα επίπεδο αποκοπής 0,7, λαμβάνονται ασαφή διαστήματα στον άξονα x. Τώρα μπορούμε να πούμε ότι ο αποστολέας θα πρέπει να περιμένει μια αλλαγή στο σχέδιο  

Ένας άλλος τρόπος ορισμού της συνάρτησης F, διαφορετικός από τη μέθοδο της υπέρθεσης, είναι ότι όταν εφαρμόζεται οποιοσδήποτε ποσοτικός σε έναν άλλο ποσοτικοποιητή, εμφανίζεται ένας ορισμένος μονοτονικός μετασχηματισμός της αρχικής συνάρτησης μέλους, ο οποίος καταλήγει στο τέντωμα και τη μετατόπιση του μέγιστου της συνάρτησης σε ένα κατεύθυνση ή άλλη.  

Παράδειγμα 3.29. Στο Σχ. Το Σχήμα 3.25 δείχνει δύο αποτελέσματα που προέκυψαν με χρήση υπέρθεσης και μετατόπισης τάνυσης για την περίπτωση όπου τα ΧΑ και Χ αντιστοιχούν συχνά στον ποσοτικό δείκτη. Η διαφορά φαίνεται να είναι ότι η υπέρθεση απομονώνει στη συνάρτηση μέλους εκείνες τις τιμές που εμφανίζονται συχνά. Στην περίπτωση της μετατόπισης και της έκτασης, μπορούμε να ερμηνεύσουμε το αποτέλεσμα ως την εμφάνιση ενός νέου ποσοτικού δείκτη με την τιμή συχνά-συχνά, η οποία μπορεί, εάν επιθυμείται, να προσεγγιστεί, για παράδειγμα, με την τιμή πολύ συχνά.  

Δείξτε ότι η υπέρθεση μιας αυστηρά αυξανόμενης συνάρτησης και μιας συνάρτησης χρησιμότητας που αντιπροσωπεύει κάποια σχέση προτίμησης > είναι επίσης μια συνάρτηση χρησιμότητας που αντιπροσωπεύει αυτή τη σχέση προτίμησης. Ποια από τις παρακάτω συναρτήσεις μπορεί να λειτουργήσει ως τέτοιος μετασχηματισμός;  

Η πρώτη από τις σχέσεις (2) δεν είναι τίποτα περισσότερο από μια καταγραφή του κανόνα σύμφωνα με τον οποίο κάθε συνάρτηση F(x) που ανήκει στην οικογένεια των μονότονα μη φθίνουσας απολύτως συνεχούς συνάρτησης συνδέεται με μία και μόνο συνεχή συνάρτηση w(j). Αυτός ο κανόνας είναι γραμμικός, δηλ. η αρχή της υπέρθεσης ισχύει για αυτόν  

Απόδειξη. Εάν η αντιστοίχιση F είναι συνεχής, η συνάρτηση M0 είναι συνεχής ως υπέρθεση συνεχών συναρτήσεων. Για να αποδείξετε το δεύτερο μέρος της πρότασης, εξετάστε τη συνάρτηση  

Σύνθετες συναρτήσεις (υπερθέσεις)  

Η μέθοδος των λειτουργικών μετασχηματισμών περιλαμβάνει επίσης τη χρήση μιας ευρετικής προσέγγισης. Για παράδειγμα, η χρήση λογαριθμικών μετασχηματισμών ως τελεστών Β και Γ οδηγεί σε κριτήρια πληροφόρησης για την κατασκευή αναγνωρίσιμων μοντέλων και στη χρήση ενός ισχυρού εργαλείου θεωρίας πληροφοριών. Έστω ο τελεστής Β αντιπροσωπεύει μια υπέρθεση των τελεστών πολλαπλασιασμού με τη συνάρτηση,(.) και μετατόπιση από τη συνάρτηση K0(), ο τελεστής C είναι ο τελεστής  

Εδώ θα περιγράψουμε τα αποτελέσματα της επίλυσης ενός αριθμού προβλημάτων μεταβλητής (1)-(3). Επιλύθηκαν με τη μέθοδο της διαδοχικής γραμμικοποίησης (19-21) το 1962-1963, όταν η τεχνολογία της μεθόδου μόλις άρχιζε να διαμορφώνεται και δοκιμαζόταν. Ως εκ τούτου, θα εστιάσουμε μόνο σε ορισμένες λεπτομέρειες. Πρώτα απ 'όλα, σημειώνουμε ότι οι συναρτήσεις C και C2 καθορίστηκαν από μάλλον σύνθετες εκφράσεις, οι οποίες είναι μια υπέρθεση βοηθητικών συναρτήσεων, συμπεριλαμβανομένων αυτών που καθορίζονται σε πίνακες. Επομένως, κατά την επίλυση του συζυγούς συστήματος φ = -fx χρησιμοποιώντας συναρτήσεις που καθορίζονται σε έναν πίνακα. Συνήθως, τέτοιοι πίνακες περιέχουν μικρό αριθμό τιμών για ένα σύνολο κόμβων στην περιοχή αλλαγής του ανεξάρτητου ορίσματος και μεταξύ τους η συνάρτηση παρεμβάλλεται γραμμικά, καθώς η χρήση πιο ακριβών μεθόδων παρεμβολής δεν δικαιολογείται λόγω στην ανακρίβεια του τιμές πίνακα(κατά κανόνα, οι λειτουργικές εξαρτήσεις πειραματικής φύσης καθορίζονται σε πίνακες). Ωστόσο, για τους σκοπούς μας χρειαζόμαστε διαφοροποιήσιμες συναρτήσεις /(x, u), επομένως θα πρέπει να προτιμούμε ομαλές μεθόδους ολοκλήρωσης μιας συνάρτησης που καθορίζεται στον πίνακα (για παράδειγμα, χρησιμοποιώντας splines).  

Έστω τώρα (DA και (q) αυθαίρετες συναρτήσεις που αντιστοιχούν σε ορισμένες τιμές των ποσοτικών δεικτών συχνότητας. Το σχήμα 3.23 δείχνει δύο καμπύλες μονής καμπής που αντιστοιχούν σε αυτές τις συναρτήσεις. Το αποτέλεσμα της υπέρθεσης τους είναι μια καμπύλη δύο καμπύλων, που φαίνεται από μια διακεκομμένη γραμμή Ποια είναι η σημασία της Αν, για παράδειγμα, (ΝΑΙ υπάρχει σπάνια, και (δ - συχνά,  

Το πλεονέκτημα αυτής της μεθόδου προσδιορισμού του F είναι ότι κατά τους μονοτονικούς μετασχηματισμούς η μορφή της συνάρτησης μέλους δεν αλλάζει δραματικά. Η μονοτροπικότητα ή η μονοτονία του διατηρείται και η μετάβαση από έναν νέο τύπο συνάρτησης (2.16) έχει τραπεζοειδές σχήμα, τότε η γραμμική υπέρθεση (2.15) είναι ένας τραπεζοειδής ασαφής αριθμός (που αποδεικνύεται εύκολα όταν χρησιμοποιείται ο κανόνας υπολογισμού τμήματος). Και μπορούμε να μειώσουμε τις πράξεις με συναρτήσεις μέλους σε πράξεις με τις κορυφές τους. Αν συμβολίσουμε τον τραπεζοειδή αριθμό (2.16) ως (ab a2, az, a4), όπου a αντιστοιχεί στην τετμημένη των κορυφών του τραπεζοειδούς, τότε  

WiFi