Επίλυση συστημάτων λογικών εξισώσεων με αλλαγή μεταβλητών
Η μέθοδος αντικατάστασης μεταβλητών χρησιμοποιείται εάν ορισμένες μεταβλητές περιλαμβάνονται στις εξισώσεις μόνο με τη μορφή συγκεκριμένης έκφρασης και τίποτα άλλο. Τότε αυτή η έκφραση μπορεί να υποδηλωθεί με μια νέα μεταβλητή.
Παράδειγμα 1.
Πόσα διαφορετικά σύνολα τιμών των λογικών μεταβλητών x1, x2, x3, x4, x5, x6, x7, x8 υπάρχουν που ικανοποιούν όλες τις προϋποθέσεις που αναφέρονται παρακάτω;
(x1 → x2) → (x3→ x4) = 1
(x3 → x4) → (x5 → x6) = 1
(x5 → x6) → (x7 → x8) = 1
Η απάντηση δεν χρειάζεται να απαριθμήσει όλα τα διαφορετικά σύνολα τιμών των μεταβλητών x1, x2, x3, x4, x5, x6, x7, x8, για τις οποίες ικανοποιείται αυτό το σύστημα ισοτήτων. Ως απάντηση, πρέπει να υποδείξετε τον αριθμό τέτοιων συνόλων.
Διάλυμα:
(x1 → x2) = y1; (x3 → x4) = y2; (x5 → x6) = y3; (x7 → x8) = y4.
Τότε μπορούμε να γράψουμε το σύστημα με τη μορφή μιας εξίσωσης:
(y1 → y2) ∧ (y2 → y3) ∧ (y3 → y4) = 1. Ο σύνδεσμος είναι 1 (αληθής) όταν κάθε τελεστής παίρνει την τιμή 1. Δηλαδή καθεμία από τις συνέπειες πρέπει να είναι αληθής, και αυτό ισχύει για όλες τις τιμές εκτός από (1 → 0). Εκείνοι. στον πίνακα τιμών των μεταβλητών y1, y2, y3, y4, το ένα δεν πρέπει να βρίσκεται στα αριστερά του μηδενός:
Εκείνοι. ικανοποιούνται οι προϋποθέσεις για 5 σετ y1-y4.
Επειδή y1 = x1 → x2, τότε η τιμή y1 = 0 επιτυγχάνεται σε ένα μόνο σύνολο x1, x2: (1, 0) και η τιμή y1 = 1 – σε τρία σετ x1, x2: (0,0) , (0 ,1), (1.1). Ομοίως για y2, y3, y4.
Εφόσον κάθε σύνολο (x1,x2) για τη μεταβλητή y1 συνδυάζεται με κάθε σύνολο (x3,x4) για τη μεταβλητή y2 κ.λπ., οι αριθμοί των συνόλων των μεταβλητών x πολλαπλασιάζονται:
|
Αριθμός σετ ανά x1…x8 |
||||
Ας αθροίσουμε τον αριθμό των σετ: 1 + 3 + 9 + 27 + 81 = 121.
Απάντηση: 121
Παράδειγμα 2.
Πόσα διαφορετικά σύνολα τιμών των λογικών μεταβλητών x1, x2, ... x9, y1, y2, ... y9 υπάρχουν που ικανοποιούν όλες τις προϋποθέσεις που αναφέρονται παρακάτω;
(¬ (x1 ≡ y1)) ≡ (x2 ≡ y2)
(¬ (x2 ≡ y2)) ≡ (x3 ≡ y3)
(¬ (x8 ≡ y8)) ≡ (x9 ≡ y9)
Σε απάντηση δεν χρειάζεταιαπαριθμήστε όλα τα διαφορετικά σύνολα τιμών των μεταβλητών x1, x2, ... x9, y1, y2, ... y9 για τις οποίες ικανοποιείται το δεδομένο σύστημα ισοτήτων. Ως απάντηση, πρέπει να υποδείξετε τον αριθμό τέτοιων συνόλων.
Διάλυμα:
Ας κάνουμε μια αλλαγή μεταβλητών:
(x1 ≡ y1) = z1, (x2 ≡ y2) = z2,…. ,(x9 ≡ y9) = z9
Το σύστημα μπορεί να γραφτεί ως μία εξίσωση:
(¬ z1 ≡ z2) ∧ (¬ z2 ≡ z3) ∧ …..∧ (¬ z8 ≡ z9)
Η ισοδυναμία είναι αληθής μόνο αν και οι δύο τελεστές είναι ίσοι. Υπάρχουν δύο σύνολα λύσεων σε αυτήν την εξίσωση:
| z1 | z2 | z3 | z4 | z5 | z6 | z7 | z8 | z9 |
| 0 | 1 | 0 | 1 | 0 | 1 | 0 | 1 | 0 |
| 1 | 0 | 1 | 0 | 1 | 0 | 1 | 0 | 1 |
Επειδή zi = (xi ≡ yi), τότε η τιμή zi = 0 αντιστοιχεί σε δύο σύνολα (xi,yi): (0,1) και (1,0) και η τιμή zi = 1 αντιστοιχεί σε δύο σύνολα (xi,yi ): (0 ,0) και (1,1).
Τότε το πρώτο σύνολο z1, z2,…, z9 αντιστοιχεί σε 2 9 σετ (x1,y1), (x2,y2),…, (x9,y9).
Ο ίδιος αριθμός αντιστοιχεί στο δεύτερο σύνολο z1, z2,…, z9. Τότε υπάρχουν συνολικά 2 9 +2 9 = 1024 σετ.
Απάντηση: 1024
Επίλυση συστημάτων λογικών εξισώσεων με τη μέθοδο του οπτικού προσδιορισμού της αναδρομής.
Αυτή η μέθοδος χρησιμοποιείται εάν το σύστημα των εξισώσεων είναι αρκετά απλό και η σειρά αύξησης του αριθμού των συνόλων κατά την προσθήκη μεταβλητών είναι προφανής.
Παράδειγμα 3.
Πόσες διαφορετικές λύσεις έχει το σύστημα εξισώσεων;
¬x9 ∨ x10 = 1,
όπου x1, x2, … x10 είναι οι λογικές μεταβλητές;
Η απάντηση δεν χρειάζεται να απαριθμήσει όλα τα διαφορετικά σύνολα τιμών x1, x2, ... x10 για τα οποία ικανοποιείται αυτό το σύστημα ισοτήτων. Ως απάντηση, πρέπει να υποδείξετε τον αριθμό τέτοιων συνόλων.
Διάλυμα:
Ας λύσουμε την πρώτη εξίσωση. Μια διάσταση είναι ίση με 1 αν τουλάχιστον ένας από τους τελεστές της είναι ίσος με 1. οι λύσεις είναι τα σετ:
Για x1=0, υπάρχουν δύο τιμές του x2 (0 και 1), και για το x1=1 υπάρχει μόνο μία τιμή του x2 (1), έτσι ώστε το σύνολο (x1,x2) να είναι λύση της εξίσωσης . Υπάρχουν 3 σετ συνολικά.
Ας προσθέσουμε τη μεταβλητή x3 και ας εξετάσουμε τη δεύτερη εξίσωση. Είναι παρόμοιο με το πρώτο, που σημαίνει ότι για x2=0 υπάρχουν δύο τιμές του x3 (0 και 1), και για το x2=1 υπάρχει μόνο μία τιμή x3 (1), έτσι ώστε το σύνολο (x2 ,x3) είναι λύση της εξίσωσης. Υπάρχουν 4 σετ συνολικά.
Είναι εύκολο να δούμε ότι όταν προσθέτουμε μια άλλη μεταβλητή, προστίθεται ένα σύνολο. Εκείνοι. αναδρομικός τύπος για τον αριθμό των συνόλων (i+1) μεταβλητών:
N i +1 = N i + 1. Τότε για δέκα μεταβλητές παίρνουμε 11 σύνολα.
Απάντηση: 11
Επίλυση συστημάτων λογικών εξισώσεων διαφόρων τύπων
Παράδειγμα 4.
Πόσα διαφορετικά σύνολα τιμών των λογικών μεταβλητών x 1, ..., x 4, y 1,..., y 4, z 1,..., z 4 υπάρχουν που ικανοποιούν όλες τις προϋποθέσεις που αναφέρονται παρακάτω ?
(x 1 → x 2) ∧ (x 2 → x 3) ∧ (x 3 → x 4) = 1
(y 1 → y 2) ∧ (y 2 → y 3) ∧ (y 3 → y 4) = 1
(z 1 → z 2) ∧ (z 2 → z 3) ∧ (z 3 → z 4) = 1
x 4 ∧ y 4 ∧ z 4 = 0
Σε απάντηση δεν χρειάζεταιαπαριθμήστε όλα τα διαφορετικά σύνολα τιμών των μεταβλητών x 1, ..., x 4, y 1, ..., y 4, z 1, ..., z 4 για τις οποίες ικανοποιείται το δεδομένο σύστημα ισοτήτων .
Ως απάντηση, πρέπει να υποδείξετε τον αριθμό τέτοιων συνόλων.
Διάλυμα:
Σημειώστε ότι οι τρεις εξισώσεις του συστήματος είναι ίδιες σε διαφορετικά ανεξάρτητα σύνολα μεταβλητών.
Ας δούμε την πρώτη εξίσωση. Ένας σύνδεσμος είναι αληθής (ίσος με 1) μόνο αν όλοι οι τελεστές του είναι αληθείς (ίσοι με 1). Το συμπέρασμα είναι 1 σε όλες τις πλειάδες εκτός από το (1,0). Αυτό σημαίνει ότι η λύση στην πρώτη εξίσωση θα είναι τα ακόλουθα σύνολα x1, x2, x3, x4, στα οποία το 1 δεν βρίσκεται στα αριστερά του 0 (5 σύνολα):
Ομοίως, οι λύσεις στη δεύτερη και τρίτη εξίσωση θα είναι απολύτως τα ίδια σύνολα y1,…,y4 και z1,…, z4.
Ας αναλύσουμε τώρα την τέταρτη εξίσωση του συστήματος: x 4 ∧ y 4 ∧ z 4 = 0. Η λύση θα είναι όλα τα σύνολα x4, y4, z4 στα οποία τουλάχιστον μία από τις μεταβλητές είναι ίση με 0.
Εκείνοι. για x4 = 0, όλα τα πιθανά σύνολα (y4, z4) είναι κατάλληλα και για x4 = 1, τα σύνολα (y4, z4) είναι κατάλληλα, στα οποία υπάρχει τουλάχιστον ένα μηδέν: (0, 0), (0,1 ) , (1, 0).
|
Αριθμός σετ |
||||
Ο συνολικός αριθμός των σετ είναι 25 + 4*9 = 25 + 36 = 61.
Απάντηση: 61
Επίλυση συστημάτων λογικών εξισώσεων με την κατασκευή επαναλαμβανόμενων τύπων
Η μέθοδος κατασκευής επαναλαμβανόμενων τύπων χρησιμοποιείται κατά την επίλυση πολύπλοκων συστημάτων στα οποία η σειρά αύξησης του αριθμού των συνόλων δεν είναι προφανής και η κατασκευή ενός δέντρου είναι αδύνατη λόγω όγκων.
Παράδειγμα 5.
Πόσα διαφορετικά σύνολα τιμών των λογικών μεταβλητών x1, x2, ... x7, y1, y2, ... y7 υπάρχουν που ικανοποιούν όλες τις προϋποθέσεις που αναφέρονται παρακάτω;
(x1 ∨ y1) ∧ ((x2 ∧ y2) → (x1 ∧ y1)) = 1
(x2 ∨ y2) ∧ ((x3 ∧ y3) → (x2 ∧ y2)) = 1
(x6 ∨ y6) ∧ ((x7 ∧ y7) → (x6 ∧ y6)) = 1
Η απάντηση δεν χρειάζεται να απαριθμήσει όλα τα διαφορετικά σύνολα τιμών των μεταβλητών x1, x2, ..., x7, y1, y2, ..., y7 για τις οποίες ικανοποιείται αυτό το σύστημα ισοτήτων. Ως απάντηση, πρέπει να υποδείξετε τον αριθμό τέτοιων συνόλων.
Διάλυμα:
Σημειώστε ότι οι πρώτες έξι εξισώσεις του συστήματος είναι πανομοιότυπες και διαφέρουν μόνο στο σύνολο των μεταβλητών. Ας δούμε την πρώτη εξίσωση. Η λύση του θα είναι τα ακόλουθα σύνολα μεταβλητών:
Ας υποδηλώσουμε:
αριθμός πλειάδων (0,0) στις μεταβλητές (x1,y1) έως A 1,
αριθμός πλειάδων (0,1) στις μεταβλητές (x1,y1) έως B 1,
αριθμός πλειάδων (1,0) στις μεταβλητές (x1,y1) έως C 1,
τον αριθμό των πλειάδων (1,1) στις μεταβλητές (x1,y1) έως D 1 .
αριθμός πλειάδων (0,0) στις μεταβλητές (x2,y2) έως A 2,
αριθμός πλειάδων (0,1) στις μεταβλητές (x2,y2) έως B 2,
αριθμός πλειάδων (1,0) στις μεταβλητές (x2,y2) έως C 2,
τον αριθμό των πλειάδων (1,1) στις μεταβλητές (x2,y2) έως D 2 .
Από το δέντρο αποφάσεων βλέπουμε ότι
A 1 =0, B 1 =1, C 1 =1, D 1 =1.
Σημειώστε ότι το σύνολο (0,0) στις μεταβλητές (x2,y2) προκύπτει από τα σύνολα (0,1), (1,0) και (1,1) στις μεταβλητές (x1,y1). Εκείνοι. A 2 =B 1 +C 1 +D 1.
Το σύνολο (0,1) στις μεταβλητές (x2,y2) προκύπτει από τα σύνολα (0,1), (1,0) και (1,1) στις μεταβλητές (x1,y1). Εκείνοι. Β 2 = Β 1 + Γ 1 + Δ 1.
Με το ίδιο επιχείρημα, σημειώνουμε ότι C 2 =B 1 +C 1 +D 1. D2 = D1.
Έτσι, λαμβάνουμε επαναλαμβανόμενους τύπους:
A i+1 = B i + C i + D i
B i+1 = B i + C i + D i
C i+1 = B i + C i + D i
D i+1 = A i +B i + C i + D i
Ας κάνουμε ένα τραπέζι
| Σκηνικά | Ονομασία. | Τύπος |
Αριθμός σετ |
||||||
| i=1 | i=2 | i=3 | i=4 | i=5 | i=6 | i=7 | |||
| (0,0) | A i | A i+1 =B i +C i +D i | 0 | 3 | 7 | 15 | 31 | 63 | 127 |
| (0,1) | B i | B i+1 =B i +C i +D i | 1 | 3 | 7 | 15 | 31 | 63 | 127 |
| (1,0) | Γ i | C i+1 =B i +C i +D i | 1 | 3 | 7 | 15 | 31 | 63 | 127 |
| (1,1) | D i | D i+1 =D i | 1 | 1 | 1 | 1 | 1 | 1 | 1 |
Η τελευταία εξίσωση (x7 ∨ y7) = 1 ικανοποιείται από όλα τα σύνολα εκτός από αυτά στα οποία x7=0 και y7=0. Στον πίνακα μας ο αριθμός τέτοιων συνόλων είναι Α 7.
Τότε ο συνολικός αριθμός των σετ είναι B 7 + C 7 + D 7 = 127+127+1 = 255
Απάντηση: 255
Πώς να λύσετε ορισμένα προβλήματα στις ενότητες Α και Β της εξέτασης πληροφορικής
Μάθημα #3. Λογικές. Λογικές συναρτήσεις. Επίλυση εξισώσεων
Ένας μεγάλος αριθμός προβλημάτων Ενιαίας Πολιτικής Εξετάσεων είναι αφιερωμένος στην προτασιακή λογική. Για να λυθούν τα περισσότερα από αυτά, αρκεί να γνωρίζουμε τους βασικούς νόμους της προτασιακής λογικής, τη γνώση των πινάκων αλήθειας των λογικών συναρτήσεων μιας και δύο μεταβλητών. Θα δώσω τους βασικούς νόμους της προτασιακής λογικής.
- Αντιμεταθεσιμότητα διαχωρισμού και συνδέσμου:
a ˅ b ≡ b ˅ a
a^b ≡ b^a - Διανεμητικός νόμος σχετικά με τον διαχωρισμό και τον σύνδεσμο:
a ˅ (b^с) ≡ (a ˅ β) ^(a ˅ с)
a ^ (b ˅ c) ≡ (a ^ b) ˅ (a ^ c) - Άρνηση άρνησης:
¬(¬a) ≡ α - Συνοχή:
a ^ ¬а ≡ ψευδής - Αποκλειστικό τρίτο:
a ˅ ¬а ≡ αληθές - Οι νόμοι του De Morgan:
¬(a ˅ β) ≡ ¬a ˄ ¬b
¬(a ˄ β) ≡ ¬a ˅ ¬b - Απλοποίηση:
a ˄ a ≡ a
a ˅ a ≡ a
a ˄ αληθές ≡ α
a ˄ false ≡ false - Απορρόφηση:
a ˄ (a ˅ β) ≡ α
a ˅ (a ˄ β) ≡ α - Αντικατάσταση υπονοούμενων
a → b ≡ ¬a ˅ β - Αντικατάσταση ταυτότητας
a ≡ b ≡(a ˄ b) ˅ (¬a ˄ ¬b)
Αναπαράσταση λογικών συναρτήσεων
Οποιαδήποτε λογική συνάρτηση n μεταβλητών - F(x 1, x 2, ... x n) μπορεί να καθοριστεί από έναν πίνακα αλήθειας. Ένας τέτοιος πίνακας περιέχει 2n σύνολα μεταβλητών, για καθεμία από τις οποίες καθορίζεται η τιμή μιας συνάρτησης σε αυτό το σύνολο. Αυτή η μέθοδος είναι καλή όταν ο αριθμός των μεταβλητών είναι σχετικά μικρός. Ήδη για n > 5 η αναπαράσταση γίνεται ελάχιστα ορατή.
Ένας άλλος τρόπος είναι να ορίσετε τη συνάρτηση με κάποιον τύπο χρησιμοποιώντας γνωστές αρκετά απλές συναρτήσεις. Ένα σύστημα συναρτήσεων (f 1, f 2, ... f k) ονομάζεται πλήρες εάν οποιαδήποτε λογική συνάρτηση μπορεί να εκφραστεί με έναν τύπο που περιέχει μόνο συναρτήσεις f i.
Το σύστημα συναρτήσεων (¬, ˄, ˅) έχει ολοκληρωθεί. Οι νόμοι 9 και 10 είναι παραδείγματα που καταδεικνύουν πώς οι υπονοούμενες και η ταυτότητα εκφράζονται μέσω της άρνησης, του συνδέσμου και του διαχωρισμού.
Στην πραγματικότητα, ένα σύστημα δύο συναρτήσεων – άρνηση και σύνδεσμος ή άρνηση και διαχωρισμός – είναι επίσης πλήρες. Από τους νόμους του De Morgan ακολουθούν ιδέες που επιτρέπουν σε κάποιον να εκφράσει έναν σύνδεσμο μέσω άρνησης και διαχωρισμού και, κατά συνέπεια, να εκφράσει έναν διαχωρισμό μέσω άρνησης και σύνδεσης:
(a ˅ β) ≡ ¬(¬a ˄ ¬b)
(a ˄ b) ≡ ¬(¬a ˅ ¬b)
Παραδόξως, ένα σύστημα που αποτελείται από μία μόνο λειτουργία είναι πλήρες. Υπάρχουν δύο δυαδικές συναρτήσεις - η αντισύνδεση και η αντισύνδεση, που ονομάζονται βέλος Peirce και η διαδρομή Schaeffer, που αντιπροσωπεύουν ένα κοίλο σύστημα.
Οι βασικές λειτουργίες των γλωσσών προγραμματισμού περιλαμβάνουν συνήθως την ταυτότητα, την άρνηση, τη σύνδεση και την αποσύνδεση. ΣΕ Καθήκοντα Ενιαίας Κρατικής ΕξέτασηςΜαζί με αυτές τις λειτουργίες, συχνά εντοπίζονται υπονοούμενα.
Ας δούμε μερικά απλές εργασίεςπου σχετίζονται με λογικές συναρτήσεις.
Πρόβλημα 15:
Δίνεται ένα τμήμα του πίνακα αλήθειας. Ποια από τις τρεις συναρτήσεις που δίνονται αντιστοιχεί σε αυτό το τμήμα;
| Χ 1 | Χ 2 | Χ 3 | Χ 4 | φά |
| 1 | 1 | 0 | 0 | 1 |
| 0 | 1 | 1 | 1 | 1 |
| 1 | 0 | 0 | 1 | 0 |
- (X 1 → X 2) ˄ ¬ X 3 ˅ X 4
- (¬ X 1 ˄ X 2) ˅ (¬ X 3 ˄ X 4)
- ¬ X 1 ˅ X 2 ˅ (X 3 ˄ X 4)
Λειτουργία αριθμός 3.
Για να λύσετε το πρόβλημα, πρέπει να γνωρίζετε τους πίνακες αλήθειας των βασικών συναρτήσεων και να θυμάστε τις προτεραιότητες των πράξεων. Να σας υπενθυμίσω ότι ο σύνδεσμος (λογικός πολλαπλασιασμός) έχει μεγαλύτερη προτεραιότητα και εκτελείται νωρίτερα από τον διαχωρισμό (λογική πρόσθεση). Κατά τους υπολογισμούς, είναι εύκολο να παρατηρήσετε ότι οι συναρτήσεις με αριθμούς 1 και 2 στο τρίτο σύνολο έχουν την τιμή 1 και για αυτό το λόγο δεν αντιστοιχούν στο τμήμα.
Πρόβλημα 16:
Ποιος από τους αριθμούς που δίνονται ικανοποιεί την προϋπόθεση:
(τα ψηφία, ξεκινώντας από το πιο σημαντικό ψηφίο, είναι σε φθίνουσα σειρά) → (αριθμός - ζυγός) ˄ (χαμηλό ψηφίο - ζυγό) ˄ (υψηλό ψηφίο - περιττό)
Εάν υπάρχουν πολλοί τέτοιοι αριθμοί, υποδείξτε τον μεγαλύτερο.
- 13579
- 97531
- 24678
- 15386
Η προϋπόθεση ικανοποιείται από τον αριθμό 4.
Οι δύο πρώτοι αριθμοί δεν ικανοποιούν την προϋπόθεση για τον λόγο ότι το χαμηλότερο ψηφίο είναι περιττό. Ένας συνδυασμός συνθηκών είναι ψευδής εάν ένας από τους όρους του συνδέσμου είναι ψευδής. Για τον τρίτο αριθμό, η προϋπόθεση για το υψηλότερο ψηφίο δεν πληρούται. Για τον τέταρτο αριθμό πληρούνται οι προϋποθέσεις που επιβάλλονται στα χαμηλά και υψηλά ψηφία του αριθμού. Ο πρώτος όρος του συνδέσμου είναι επίσης αληθής, αφού η υπονοούμενη είναι αληθής αν η υπόθεση του είναι ψευδής, πράγμα που συμβαίνει εδώ.
Πρόβλημα 17: Δύο μάρτυρες κατέθεσαν τις ακόλουθες καταθέσεις:
Πρώτος μάρτυρας: Αν ο Α είναι ένοχος, τότε ο Β είναι ακόμα πιο ένοχος και ο Γ είναι αθώος.
Δεύτερος μάρτυρας: Δύο είναι ένοχοι. Και ένας από τους υπόλοιπους είναι σίγουρα ένοχος και ένοχος, αλλά δεν μπορώ να πω ποιος ακριβώς.
Ποια συμπεράσματα για την ενοχή των Α, Β και Γ μπορούν να εξαχθούν από τη μαρτυρία;
Απάντηση: Από τη μαρτυρία προκύπτει ότι ο Α και ο Β είναι ένοχοι και ο Γ είναι αθώος.
Λύση: Φυσικά, η απάντηση μπορεί να δοθεί με βάση την κοινή λογική. Ας δούμε όμως πώς μπορεί να γίνει αυτό αυστηρά και επίσημα.
Το πρώτο πράγμα που πρέπει να κάνετε είναι να επισημοποιήσετε τις δηλώσεις. Ας εισαγάγουμε τρεις λογικές μεταβλητές - A, B και C, καθεμία από τις οποίες έχει την τιμή true (1) εάν ο αντίστοιχος ύποπτος είναι ένοχος. Στη συνέχεια η κατάθεση του πρώτου μάρτυρα δίνεται με τον τύπο:
A → (B ˄ ¬C)
Η κατάθεση του δεύτερου μάρτυρα δίνεται με τον τύπο:
A ˄ ((B ˄ ¬C) ˅ (¬B ˄ C))
Η κατάθεση και των δύο μαρτύρων θεωρείται αληθής και αντιπροσωπεύει το συνδυασμό των αντίστοιχων τύπων.
Ας φτιάξουμε έναν πίνακα αλήθειας για αυτές τις αναγνώσεις:
| ΕΝΑ | σι | ντο | F 1 | F 2 | F 1 ˄ F 2 |
| 0 | 0 | 0 | 1 | 0 | 0 |
| 0 | 0 | 1 | 1 | 0 | 0 |
| 0 | 1 | 0 | 1 | 0 | 0 |
| 0 | 1 | 1 | 1 | 0 | 0 |
| 1 | 0 | 0 | 0 | 0 | 0 |
| 1 | 0 | 1 | 0 | 1 | 0 |
| 1 | 1 | 0 | 1 | 1 | 1 |
| 1 | 1 | 1 | 0 | 0 | 0 |
Τα συνοπτικά στοιχεία είναι αληθή μόνο σε μία περίπτωση, οδηγώντας σε μια ξεκάθαρη απάντηση - ο Α και ο Β είναι ένοχοι και ο Γ είναι αθώος.
Από την ανάλυση αυτού του πίνακα προκύπτει επίσης ότι η κατάθεση του δεύτερου μάρτυρα είναι πιο κατατοπιστική. Μόνο δύο πράγματα προκύπτουν από την αλήθεια της μαρτυρίας του: πιθανές επιλογές- Ο Α και ο Β είναι ένοχοι και ο Γ είναι αθώος, ή ο Α και ο Γ είναι ένοχοι και ο Β είναι αθώος. Η κατάθεση του πρώτου μάρτυρα είναι λιγότερο κατατοπιστική - υπάρχουν 5 διάφορες επιλογές, που αντιστοιχεί στη μαρτυρία του. Μαζί, η κατάθεση και των δύο μαρτύρων δίνει ξεκάθαρη απάντηση για την ενοχή των υπόπτων.
Λογικές εξισώσεις και συστήματα εξισώσεων
Έστω F(x 1, x 2, …x n) μια λογική συνάρτηση n μεταβλητών. Η λογική εξίσωση μοιάζει με:
F(x 1, x 2, …x n) = C,
Η σταθερά C έχει την τιμή 1 ή 0.
Μια λογική εξίσωση μπορεί να έχει από 0 έως 2 n διαφορετικές λύσεις. Αν το C είναι ίσο με 1, τότε οι λύσεις είναι όλα εκείνα τα σύνολα μεταβλητών από τον πίνακα αλήθειας για τα οποία η συνάρτηση F παίρνει την τιμή true (1). Τα υπόλοιπα σύνολα είναι λύσεις της εξίσωσης με το C ίσο με μηδέν. Μπορείτε πάντα να εξετάζετε μόνο εξισώσεις της μορφής:
F(x 1, x 2, …x n) = 1
Πράγματι, ας δοθεί η εξίσωση:
F(x 1, x 2, …x n) = 0
Σε αυτήν την περίπτωση, μπορούμε να πάμε στην ισοδύναμη εξίσωση:
¬F(x 1 , x 2 , …x n) = 1
Θεωρήστε ένα σύστημα k λογικών εξισώσεων:
F 1 (x 1, x 2, …x n) = 1
F 2 (x 1, x 2, …x n) = 1
F k (x 1 , x 2 , …x n) = 1
Η λύση σε ένα σύστημα είναι ένα σύνολο μεταβλητών στις οποίες ικανοποιούνται όλες οι εξισώσεις του συστήματος. Όσον αφορά τις λογικές συναρτήσεις, για να ληφθεί μια λύση σε ένα σύστημα λογικών εξισώσεων, θα πρέπει να βρεθεί ένα σύνολο στο οποίο η λογική συνάρτηση Ф είναι αληθής, αντιπροσωπεύοντας το συνδυασμό των αρχικών συναρτήσεων F:
Ф = F 1 ˄ F 2 ˄ … F k
Εάν ο αριθμός των μεταβλητών είναι μικρός, για παράδειγμα, μικρότερος από 5, τότε δεν είναι δύσκολο να κατασκευάσουμε έναν πίνακα αλήθειας για τη συνάρτηση Ф, ο οποίος μας επιτρέπει να πούμε πόσες λύσεις έχει το σύστημα και ποια είναι τα σύνολα που δίνουν λύσεις.
Σε ορισμένα προβλήματα ΧΡΗΣΗΣ για την εύρεση λύσεων σε ένα σύστημα λογικών εξισώσεων, ο αριθμός των μεταβλητών φτάνει τις 10. Τότε η κατασκευή ενός πίνακα αλήθειας γίνεται σχεδόν αδύνατη. Η επίλυση του προβλήματος απαιτεί διαφορετική προσέγγιση. Για ένα αυθαίρετο σύστημα εξισώσεων δεν υπάρχουν γενική μέθοδος, διαφορετικό από την ωμή βία, που επιτρέπει την επίλυση τέτοιων προβλημάτων.
Στα προβλήματα που προτείνονται στην εξέταση, η λύση βασίζεται συνήθως στο να ληφθούν υπόψη οι ιδιαιτερότητες του συστήματος εξισώσεων. Επαναλαμβάνω, εκτός από τη δοκιμή όλων των επιλογών για ένα σύνολο μεταβλητών, δεν υπάρχει γενικός τρόπος επίλυσης του προβλήματος. Η λύση πρέπει να χτιστεί με βάση τις ιδιαιτερότητες του συστήματος. Συχνά είναι χρήσιμο να πραγματοποιηθεί μια προκαταρκτική απλοποίηση ενός συστήματος εξισώσεων χρησιμοποιώντας γνωστούς νόμους της λογικής. Αλλος χρήσιμο κόλποΗ λύση σε αυτό το πρόβλημα είναι η εξής. Δεν μας ενδιαφέρουν όλα τα σύνολα, αλλά μόνο εκείνα στα οποία η συνάρτηση Φ έχει την τιμή 1. Αντί να κατασκευάσουμε πλήρες τραπέζιαλήθεια, θα φτιάξουμε το ανάλογό του - ένα δυαδικό δέντρο αποφάσεων. Κάθε κλάδος αυτού του δέντρου αντιστοιχεί σε μία λύση και καθορίζει ένα σύνολο στο οποίο η συνάρτηση Ф έχει την τιμή 1. Ο αριθμός των κλάδων στο δέντρο απόφασης συμπίπτει με τον αριθμό των λύσεων στο σύστημα εξισώσεων.
Θα εξηγήσω τι είναι ένα δυαδικό δέντρο αποφάσεων και πώς κατασκευάζεται χρησιμοποιώντας παραδείγματα πολλών προβλημάτων.
Πρόβλημα 18
Πόσα διαφορετικά σύνολα τιμών των λογικών μεταβλητών x1, x2, x3, x4, x5, y1, y2, y3, y4, y5 υπάρχουν που ικανοποιούν το σύστημα δύο εξισώσεων;
Απάντηση: Το σύστημα έχει 36 διαφορετικές λύσεις.
Λύση: Το σύστημα των εξισώσεων περιλαμβάνει δύο εξισώσεις. Ας βρούμε τον αριθμό των λύσεων για την πρώτη εξίσωση, ανάλογα με 5 μεταβλητές - x 1, x 2, ...x 5. Η πρώτη εξίσωση μπορεί με τη σειρά της να θεωρηθεί ως ένα σύστημα 5 εξισώσεων. Όπως έχει αποδειχθεί, το σύστημα των εξισώσεων στην πραγματικότητα αντιπροσωπεύει το συνδυασμό λογικών συναρτήσεων. Το αντίστροφο ισχύει επίσης: ένας συνδυασμός συνθηκών μπορεί να θεωρηθεί ως σύστημα εξισώσεων.
Ας δημιουργήσουμε ένα δέντρο απόφασης για την επίπτωση (x1→ x2) - τον πρώτο όρο του συνδέσμου, που μπορεί να θεωρηθεί ως η πρώτη εξίσωση. Έτσι μοιάζει μια γραφική αναπαράσταση αυτού του δέντρου:
Το δέντρο αποτελείται από δύο επίπεδα ανάλογα με τον αριθμό των μεταβλητών στην εξίσωση. Το πρώτο επίπεδο περιγράφει την πρώτη μεταβλητή X 1 . Δύο κλάδοι αυτού του επιπέδου αντικατοπτρίζουν τις πιθανές τιμές αυτής της μεταβλητής - 1 και 0. Στο δεύτερο επίπεδο, τα κλαδιά του δέντρου αντικατοπτρίζουν μόνο εκείνες τις πιθανές τιμές της μεταβλητής X 2 για τις οποίες ισχύει η εξίσωση. Εφόσον η εξίσωση καθορίζει μια έννοια, ένας κλάδος στον οποίο το X 1 έχει την τιμή 1 απαιτεί ότι σε αυτόν τον κλάδο το X 2 έχει την τιμή 1. Ένας κλάδος στον οποίο το X 1 έχει την τιμή 0 παράγει δύο κλάδους με τις τιμές του X 2 ίσο με 0 και 1 Το κατασκευασμένο δέντρο ορίζει τρεις λύσεις, στις οποίες η συνεπαγωγή X 1 → X 2 παίρνει την τιμή 1. Σε κάθε κλάδο, γράφεται ένα αντίστοιχο σύνολο μεταβλητών τιμών, δίνοντας λύση στην εξίσωση.
Αυτά τα σετ είναι: ((1, 1), (0, 1), (0, 0))
Ας συνεχίσουμε να χτίζουμε το δέντρο αποφάσεων προσθέτοντας την ακόλουθη εξίσωση, την ακόλουθη συνέπεια X 2 → X 3 . Η ιδιαιτερότητα του συστήματος εξισώσεων μας είναι ότι κάθε νέα εξίσωση του συστήματος χρησιμοποιεί μία μεταβλητή από την προηγούμενη εξίσωση, προσθέτοντας μία νέα μεταβλητή. Εφόσον η μεταβλητή X 2 έχει ήδη τιμές στο δέντρο, τότε σε όλους τους κλάδους όπου η μεταβλητή X 2 έχει τιμή 1, η μεταβλητή X 3 θα έχει επίσης τιμή 1. Για τέτοιους κλάδους, η κατασκευή του δέντρου συνεχίζει στο επόμενο επίπεδο, αλλά δεν εμφανίζονται νέοι κλάδοι. Ο απλός κλάδος όπου η μεταβλητή X 2 έχει την τιμή 0 θα διακλαδωθεί σε δύο κλάδους όπου η μεταβλητή X 3 θα λάβει τις τιμές 0 και 1. Έτσι, κάθε προσθήκη μιας νέας εξίσωσης, δεδομένων των ιδιαιτεροτήτων της, προσθέτει μία λύση. Αρχική πρώτη εξίσωση:
(x1→x2) /\ (x2→x3) /\ (x3→x4) /\ (x4→x5) = 1
έχει 6 λύσεις. Έτσι φαίνεται γεμάτο δέντρολύσεις για αυτήν την εξίσωση:
Η δεύτερη εξίσωση του συστήματός μας είναι παρόμοια με την πρώτη:
(y1→y2) /\ (y2→y3) /\ (y3→y4) /\ (y4→y5) = 1
Η μόνη διαφορά είναι ότι η εξίσωση χρησιμοποιεί μεταβλητές Υ Αυτή η εξίσωση έχει επίσης 6 λύσεις. Εφόσον κάθε λύση για τις μεταβλητές X i μπορεί να συνδυαστεί με κάθε λύση για τις μεταβλητές Y j , τότε συνολικός αριθμόςΥπάρχουν 36 λύσεις.
Σημειώστε ότι το κατασκευασμένο δέντρο αποφάσεων δίνει όχι μόνο τον αριθμό των λύσεων (από τον αριθμό των κλάδων), αλλά και τις ίδιες τις λύσεις που είναι γραμμένες σε κάθε κλάδο του δέντρου.
Πρόβλημα 19
Πόσα διαφορετικά σύνολα τιμών των λογικών μεταβλητών x1, x2, x3, x4, x5, y1, y2, y3, y4, y5 υπάρχουν που ικανοποιούν όλες τις προϋποθέσεις που αναφέρονται παρακάτω;
(x1→x2) /\ (x2→x3) /\ (x3→x4) /\ (x4→x5) = 1
(y1→y2) /\ (y2→y3) /\ (y3→y4) /\ (y4→y5) = 1
(x1→ y1) = 1
Αυτή η εργασία είναι μια τροποποίηση της προηγούμενης εργασίας. Η διαφορά είναι ότι προστίθεται μια άλλη εξίσωση που συσχετίζει τις μεταβλητές X και Y.
Από την εξίσωση X 1 → Y 1 προκύπτει ότι όταν το X 1 έχει την τιμή 1 (υπάρχει μια τέτοια λύση), τότε το Y 1 έχει επίσης την τιμή 1. Έτσι, υπάρχει ένα σύνολο στο οποίο τα X 1 και Y 1 έχουν τις τιμές 1 Όταν το X 1 ισούται με 0, το Y 1 μπορεί να έχει οποιαδήποτε τιμή, τόσο 0 όσο και 1. Επομένως, κάθε σύνολο με X 1 ίσο με 0, και υπάρχουν 5 τέτοια σύνολα, αντιστοιχεί και στα 6 σύνολα με μεταβλητές Υ. Επομένως, ο συνολικός αριθμός λύσεων είναι 31 .
Πρόβλημα 20
(¬X 1 ˅ X 2) ˄ (¬X 2 ˅ X 3) ˄ (¬X 3 ˅ X 4) ˄ (¬X 4 ˅ X 5) ˄ (¬X 5 ˅ X 1) = 1
Λύση: Θυμόμαστε τις βασικές ισοδυναμίες, γράφουμε την εξίσωσή μας ως:
(X 1 → X 2) ˄ (X 2 → X 3) ˄ (X 3 → X 4) ˄ (X 4 → X 5) ˄ (X 5 → X 1) = 1
Η κυκλική αλυσίδα των συνεπειών σημαίνει ότι οι μεταβλητές είναι πανομοιότυπες, επομένως η εξίσωσή μας είναι ισοδύναμη με την εξίσωση:
X 1 ≡ X 2 ≡ X 3 ≡ X 4 ≡ X 5 = 1
Αυτή η εξίσωση έχει δύο λύσεις όταν όλα τα X i είναι είτε 1 είτε 0.
Πρόβλημα 21
(X 1 → X 2) ˄ (X 2 → X 3) ˄ (X 3 → X 4) ˄ (X 4 → X 2) ˄ (X 4 → X 5) = 1
Λύση: Ακριβώς όπως στο πρόβλημα 20, μετακινούμαστε από τις κυκλικές επιπτώσεις στις ταυτότητες, ξαναγράφοντας την εξίσωση με τη μορφή:
(X 1 → X 2) ˄ (X 2 ≡ X 3 ≡ X 4) ˄ (X 4 → X 5) = 1
Ας δημιουργήσουμε ένα δέντρο αποφάσεων για αυτήν την εξίσωση: 
Πρόβλημα 22
Πόσες λύσεις έχει το παρακάτω σύστημα εξισώσεων;
((X 1 ≡X 2) ˄ (X 3 ≡X 4)) ˅(¬(X 1 ≡X 2) ˄ ¬(X 3 ≡X 4)) = 0
((X 3 ≡X 4) ˄ (X 5 ≡X 6)) ˅(¬(X 3 ≡X 4) ˄ ¬(X 5 ≡X 6)) = 0
((X 5 ≡X 6) ˄ (X 7 ≡X 8)) ˅(¬(X 5 ≡X 6) ˄ ¬(X 7 ≡X 8)) = 0
((X 7 ≡X 8) ˄ (X 9 ≡X 10)) ˅(¬(X 7 ≡X 8) ˄ ¬(X 9 ≡X 10)) = 0
Απάντηση: 64
Λύση: Ας μετακινηθούμε από 10 μεταβλητές σε 5 μεταβλητές εισάγοντας την ακόλουθη αλλαγή μεταβλητών:
Y 1 = (X 1 ≡ X 2); Y 2 = (X 3 ≡ X 4); Υ 3 = (Χ 5 ≡ Χ 6); Υ 4 = (Χ 7 ≡ Χ 8); Υ 5 = (Χ 9 ≡ Χ 10);
Τότε η πρώτη εξίσωση θα πάρει τη μορφή:
(Y 1 ˄ Y 2) ˅ (¬Y 1 ˄ ¬Y 2) = 0
Η εξίσωση μπορεί να απλοποιηθεί γράφοντάς την ως εξής:
(Y 1 ≡ Y 2) = 0
Προχωρώντας στην παραδοσιακή μορφή, γράφουμε το σύστημα μετά από απλοποιήσεις στη μορφή:
¬(Y 1 ≡ Y 2) = 1
¬(Y 2 ≡ Y 3) = 1
¬(Y 3 ≡ Y 4) = 1
¬(Y 4 ≡ Y 5) = 1
Το δέντρο αποφάσεων για αυτό το σύστημα είναι απλό και αποτελείται από δύο κλάδους με εναλλασσόμενες τιμές μεταβλητών:
Επιστρέφοντας στις αρχικές μεταβλητές X, σημειώστε ότι για κάθε τιμή στη μεταβλητή Y υπάρχουν 2 τιμές στις μεταβλητές X, επομένως κάθε λύση στις μεταβλητές Y δημιουργεί 2 5 λύσεις στις μεταβλητές X 5 λύσεις, άρα ο συνολικός αριθμός λύσεων είναι 64.
Όπως μπορείτε να δείτε, κάθε πρόβλημα επίλυσης ενός συστήματος εξισώσεων απαιτεί τη δική του προσέγγιση. Μια κοινή τεχνική είναι η εκτέλεση ισοδύναμων μετασχηματισμών για την απλοποίηση των εξισώσεων. Μια κοινή τεχνική είναι η κατασκευή δέντρων αποφάσεων. Η προσέγγιση που χρησιμοποιείται θυμίζει εν μέρει την κατασκευή ενός πίνακα αληθείας με την ιδιαιτερότητα ότι δεν κατασκευάζονται όλα τα σύνολα πιθανών τιμών μεταβλητών, αλλά μόνο εκείνα στα οποία η συνάρτηση παίρνει την τιμή 1 (true). Συχνά στα προτεινόμενα προβλήματα δεν χρειάζεται να δημιουργηθεί ένα πλήρες δέντρο αποφάσεων, αφού ήδη αρχικό στάδιοείναι δυνατό να δημιουργηθεί ένα μοτίβο εμφάνισης νέων κλάδων σε κάθε επόμενο επίπεδο, όπως έγινε, για παράδειγμα, στο πρόβλημα 18.
Γενικά, τα προβλήματα που αφορούν την εύρεση λύσεων σε ένα σύστημα λογικών εξισώσεων είναι καλές μαθηματικές ασκήσεις.
Εάν το πρόβλημα είναι δύσκολο να λυθεί χειροκίνητα, τότε μπορείτε να αναθέσετε τη λύση στον υπολογιστή γράφοντας ένα κατάλληλο πρόγραμμα για την επίλυση εξισώσεων και συστημάτων εξισώσεων.
Δεν είναι δύσκολο να γράψεις ένα τέτοιο πρόγραμμα. Ένα τέτοιο πρόγραμμα θα αντιμετωπίσει εύκολα όλες τις εργασίες που προσφέρονται στην Ενιαία Κρατική Εξέταση.
Παραδόξως, το έργο της εύρεσης λύσεων σε συστήματα λογικών εξισώσεων είναι δύσκολο για έναν υπολογιστή και αποδεικνύεται ότι ένας υπολογιστής έχει τα όριά του. Ένας υπολογιστής μπορεί πολύ εύκολα να αντιμετωπίσει εργασίες όπου ο αριθμός των μεταβλητών είναι 20-30, αλλά θα αρχίσει να σκέφτεται προβλήματα για μεγάλο χρονικό διάστημα μεγαλύτερο μέγεθος. Το γεγονός είναι ότι η συνάρτηση 2 n, η οποία καθορίζει τον αριθμό των συνόλων, είναι μια εκθετική που αυξάνεται γρήγορα καθώς το n αυξάνεται. Τόσο γρήγορα που ένας συνηθισμένος προσωπικός υπολογιστής δεν μπορεί να αντεπεξέλθει σε μια εργασία που έχει 40 μεταβλητές την ημέρα.
Πρόγραμμα επίλυσης λογικών εξισώσεων σε γλώσσα C#
Η σύνταξη ενός προγράμματος για την επίλυση λογικών εξισώσεων είναι χρήσιμη για πολλούς λόγους, μόνο και μόνο επειδή μπορείτε να το χρησιμοποιήσετε για να ελέγξετε την ορθότητα της δικής σας λύσης σε προβλήματα δοκιμής Unified State Exam. Ένας άλλος λόγος είναι ότι ένα τέτοιο πρόγραμμα είναι ένα εξαιρετικό παράδειγμα μιας εργασίας προγραμματισμού που πληροί τις απαιτήσεις για εργασίες κατηγορίας Γ στην Εξεταστική Ενιαία Πολιτεία.
Η ιδέα της δημιουργίας ενός προγράμματος είναι απλή - βασίζεται σε μια πλήρη αναζήτηση όλων των πιθανών συνόλων μεταβλητών τιμών. Εφόσον για μια δεδομένη λογική εξίσωση ή σύστημα εξισώσεων ο αριθμός των μεταβλητών n είναι γνωστός, τότε είναι γνωστός και ο αριθμός των συνόλων - 2 n που πρέπει να ταξινομηθούν. Χρησιμοποιώντας βασικές λειτουργίεςΓλώσσα C# - άρνηση, διαχωρισμός, σύνδεσμος και ταυτότητα, δεν είναι δύσκολο να γραφτεί ένα πρόγραμμα που, για ένα δεδομένο σύνολο μεταβλητών, υπολογίζει την τιμή μιας λογικής συνάρτησης που αντιστοιχεί σε μια λογική εξίσωση ή σύστημα εξισώσεων.
Σε ένα τέτοιο πρόγραμμα, πρέπει να δημιουργήσετε έναν βρόχο με βάση τον αριθμό των συνόλων, να σχηματίσετε το ίδιο το σύνολο στο σώμα του βρόχου με βάση τον αριθμό του συνόλου, να υπολογίσετε την τιμή της συνάρτησης σε αυτό το σύνολο και αν αυτή η τιμή είναι 1, τότε το σύνολο δίνει λύση στην εξίσωση.
Η μόνη δυσκολία που προκύπτει κατά την εφαρμογή του προγράμματος σχετίζεται με την εργασία δημιουργίας του ίδιου του συνόλου μεταβλητών τιμών με βάση τον αριθμό συνόλου. Η ομορφιά αυτού του προβλήματος είναι ότι αυτό το φαινομενικά δύσκολο έργο καταλήγει στην πραγματικότητα σε ένα απλό πρόβλημα που έχει ήδη προκύψει πολλές φορές. Πράγματι, αρκεί να κατανοήσουμε ότι το σύνολο των μεταβλητών τιμών που αντιστοιχεί στον αριθμό i, που αποτελείται από μηδενικά και μονάδες, αντιπροσωπεύει τη δυαδική αναπαράσταση του αριθμού i. Ετσι δύσκολο έργοΗ λήψη ενός συνόλου μεταβλητών τιμών ανά αριθμό συνόλου καταλήγει στο γνωστό πρόβλημα της μετατροπής ενός αριθμού στο δυαδικό σύστημα.
Έτσι φαίνεται μια συνάρτηση στην C# που λύνει το πρόβλημά μας:
///
/// Πρόγραμμα μέτρησης του αριθμού των λύσεων
/// λογική εξίσωση (σύστημα εξισώσεων)
///
///
/// λογική συνάρτηση - μέθοδος,
/// του οποίου η υπογραφή καθορίζεται από τον εκπρόσωπο του DF
///
/// αριθμός μεταβλητών
///
static int SolveEquations (διασκέδαση DF, int n)
bool set = νέο bool[n];
int m = (int)Math.Pow(2, n); //αριθμός συνόλων
int p = 0, q = 0, k = 0;
//Ολοκλήρωση αναζήτησης κατά αριθμό συνόλων
για (int i = 0; i< m; i++)
//Σχηματισμός του επόμενου συνόλου - συνόλου,
//καθορίζεται από τη δυαδική αναπαράσταση του αριθμού i
για (int j = 0; j< n; j++)
k = (int)Math.Pow(2, j);
//Υπολογισμός της τιμής της συνάρτησης στο σύνολο
Για την κατανόηση του προγράμματος, ελπίζω οι επεξηγήσεις της ιδέας του προγράμματος και τα σχόλια στο κείμενό του να είναι επαρκείς. Θα επικεντρωθώ μόνο στην εξήγηση του τίτλου της συγκεκριμένης συνάρτησης. Η συνάρτηση SolveEquations έχει δύο παραμέτρους εισόδου. Η παράμετρος fun καθορίζει μια λογική συνάρτηση που αντιστοιχεί στην εξίσωση ή το σύστημα των εξισώσεων που επιλύονται. Η παράμετρος n καθορίζει τον αριθμό μεταβλητές συνάρτησηςδιασκέδαση. Ως αποτέλεσμα, η συνάρτηση SolveEquations επιστρέφει τον αριθμό των λύσεων της λογικής συνάρτησης, δηλαδή τον αριθμό εκείνων των συνόλων στα οποία η συνάρτηση αξιολογείται ως αληθής.
Είναι σύνηθες για τους μαθητές όταν κάποια συνάρτηση F(x) έχει μια παράμετρο εισόδου x που είναι μια μεταβλητή αριθμητικής, συμβολοσειράς ή λογικού τύπου. Στην περίπτωσή μας, χρησιμοποιείται πιο ισχυρό σχέδιο. Η συνάρτηση SolveEquations αναφέρεται σε συναρτήσεις υψηλότερης τάξης - συναρτήσεις τύπου F(f), των οποίων οι παράμετροι μπορεί να είναι όχι μόνο απλές μεταβλητές, αλλά και συναρτήσεις.
Η κλάση των συναρτήσεων που μπορεί να μεταβιβαστεί ως παράμετρος στη συνάρτηση SolveEquations καθορίζεται ως εξής:
ανάθεση bool DF(bool vars);
Αυτή η κλάση κατέχει όλες τις συναρτήσεις που μεταβιβάζονται ως παράμετρος ένα σύνολο τιμών λογικών μεταβλητών που καθορίζονται από τον πίνακα vars. Το αποτέλεσμα είναι μια Boolean τιμή που αντιπροσωπεύει την τιμή της συνάρτησης σε αυτό το σύνολο.
Τέλος, εδώ είναι ένα πρόγραμμα που χρησιμοποιεί τη συνάρτηση SolveEquations για να λύσει πολλά συστήματα λογικών εξισώσεων. Η συνάρτηση SolveEquations είναι μέρος της παρακάτω κατηγορίας ProgramCommon:
class ProgramCommon
ανάθεση bool DF(bool vars);
static void Main (args string)
Console.WriteLine("And Functions - " +
SolveEquations(FunAnd, 2));
Console.WriteLine("Η συνάρτηση έχει 51 λύσεις - " +
SolveEquations(Fun51, 5));
Console.WriteLine("Η συνάρτηση έχει 53 λύσεις - " +
SolveEquations(Fun53, 10));
static bool FunAnd(bool vars)
επιστροφή vars && vars;
static bool Fun51 (bool vars)
f = f && (!vars || vars);
f = f && (!vars || vars);
f = f && (!vars || vars);
f = f && (!vars || vars);
f = f && (!vars || vars);
static bool Fun53 (bool vars)
f = f && ((vars == vars) || (vars == vars));
f = f && ((vars == vars) || (vars == vars));
f = f && ((vars == vars) || (vars == vars));
f = f && ((vars == vars) || (vars == vars));
f = f && ((vars == vars) || (vars == vars));
f = f && ((vars == vars) || (vars == vars));
f = f && (!((vars == vars) || (vars == vars)));
Δείτε πώς φαίνονται τα αποτελέσματα της λύσης για αυτό το πρόγραμμα:
10 εργασίες για ανεξάρτητη εργασία
- Ποιες από τις τρεις συναρτήσεις είναι ισοδύναμες:
- (X → Y) ˅ ¬Y
- ¬(X ˅ ¬Y) ˄ (X → ¬Y)
- ¬X ˄Y
- Δίνεται ένα απόσπασμα του πίνακα αλήθειας:
| Χ 1 | Χ 2 | Χ 3 | Χ 4 | φά |
| 1 | 0 | 0 | 1 | 1 |
| 0 | 1 | 1 | 1 | 1 |
| 1 | 0 | 1 | 0 | 0 |
Σε ποια από τις τρεις συναρτήσεις αντιστοιχεί αυτό το τμήμα:
- (X 1 ˅ ¬X 2) ˄ (X 3 → X 4)
- (X 1 → X 3) ˄ X 2 ˅ X 4
- X 1 ˄ X 2 ˅ (X 3 → (X 1 ˅ X 4))
- Η κριτική επιτροπή αποτελείται από τρία άτομα. Η απόφαση λαμβάνεται εάν την ψηφίσει ο πρόεδρος της κριτικής επιτροπής, υποστηριζόμενος από τουλάχιστον ένα από τα μέλη της κριτικής επιτροπής. Διαφορετικά δεν λαμβάνεται απόφαση. Κατασκευάστε μια λογική συνάρτηση που επισημοποιεί τη διαδικασία λήψης αποφάσεων.
- Το X κερδίζει το Y εάν τέσσερις πετάξεις νομισμάτων οδηγούν σε κεφάλια τρεις φορές. Ορίστε μια λογική συνάρτηση που περιγράφει την απόδοση του X.
- Οι λέξεις σε μια πρόταση αριθμούνται ξεκινώντας από το ένα. Μια πρόταση θεωρείται σωστά κατασκευασμένη εάν πληρούνται οι ακόλουθοι κανόνες:
- Αν μια άρτιη λέξη τελειώνει με φωνήεν, τότε επόμενη λέξη, αν υπάρχει, πρέπει να αρχίζει με φωνήεν.
- Αν μια λέξη με περιττό αριθμό τελειώνει με σύμφωνο, τότε η επόμενη λέξη, αν υπάρχει, πρέπει να αρχίζει με σύμφωνο και να τελειώνει με φωνήεν.
Ποιες από τις παρακάτω προτάσεις έχουν κατασκευαστεί σωστά: - Η μαμά έπλυνε τη Μάσα με σαπούνι.
- Ένας ηγέτης είναι πάντα πρότυπο.
- Η αλήθεια είναι καλή, αλλά η ευτυχία είναι καλύτερη.
- Πόσες λύσεις έχει η εξίσωση:
(a ˄ ¬ β) ˅ (¬a ˄ b) → (c ˄ d) = 1 - Καταγράψτε όλες τις λύσεις της εξίσωσης:
(α → β) → γ = 0 - Πόσες λύσεις έχει το παρακάτω σύστημα εξισώσεων:
X 0 → X 1 ˄ X 1 → X 2 = 1
X 2 → X 3 ˄ X 3 → X 4 = 1
X 5 → X 6 ˄ X 6 → X 7 = 1
X 7 → X 8 ˄ X 8 → X 9 = 1
X 0 → X 5 = 1 - Πόσες λύσεις έχει η εξίσωση:
((((X 0 → X 1) → X 2) → X 3) →X 4) →X 5 = 1
Απαντήσεις σε προβλήματα:
- Οι συναρτήσεις b και c είναι ισοδύναμες.
- Το θραύσμα αντιστοιχεί στη συνάρτηση β.
- Αφήστε τη λογική μεταβλητή P να λάβει την τιμή 1 όταν ο πρόεδρος της κριτικής επιτροπής ψηφίσει «υπέρ» την απόφαση. Οι μεταβλητές M 1 και M 2 αντιπροσωπεύουν τις απόψεις των μελών της κριτικής επιτροπής. Η λογική συνάρτηση που καθορίζει τη λήψη μιας θετικής απόφασης μπορεί να γραφτεί ως εξής:
P ˄ (M 1 ˅ M 2) - Ας πάρει η λογική μεταβλητή P i την τιμή 1 όταν το i-ο νόμισμα προσγειωθεί στα κεφάλια. Η λογική συνάρτηση που καθορίζει την πληρωμή X μπορεί να γραφτεί ως εξής:
¬((¬P 1 ˄ (¬P 2 ˅ ¬P 3 ˅ ¬P 4)) ˅
(¬P 2 ˄ (¬P 3 ˅ ¬P 4)) ˅
(¬P 3 ˄ ¬P 4)) - Πρόταση β.
- Η εξίσωση έχει 3 λύσεις: (a = 1; b = 1; c = 0); (a = 0; b = 0; c = 0); (a = 0; b = 1; c = 0)
Μέθοδοι επίλυσης συστημάτων λογικών εξισώσεων
Μπορείτε να λύσετε ένα σύστημα λογικών εξισώσεων, για παράδειγμα, χρησιμοποιώντας έναν πίνακα αλήθειας (αν ο αριθμός των μεταβλητών δεν είναι πολύ μεγάλος) ή χρησιμοποιώντας ένα δέντρο αποφάσεων, έχοντας πρώτα απλοποιήσει κάθε εξίσωση.
1. Μέθοδος αντικατάστασης μεταβλητής.
Η εισαγωγή νέων μεταβλητών σάς επιτρέπει να απλοποιήσετε το σύστημα εξισώσεων, μειώνοντας τον αριθμό των αγνώστων.Οι νέες μεταβλητές πρέπει να είναι ανεξάρτητες η μία από την άλλη. Αφού λύσουμε το απλοποιημένο σύστημα, πρέπει να επιστρέψουμε στις αρχικές μεταβλητές.
Ας εξετάσουμε την εφαρμογή αυτής της μεθόδου χρησιμοποιώντας ένα συγκεκριμένο παράδειγμα.
Παράδειγμα.
((X1 ≡ X2) ∧ (X3 ≡ X4)) ∨ (¬(X1 ≡ X2) ∧ ¬(X3 ≡ X4)) = 0
((X3 ≡ X4) ∧ (X5 ≡ X6)) ∨ (¬(X3 ≡ X4) ∧ ¬(X5 ≡ X6)) = 0
((X5 ≡ X6) ∧ (X7 ≡ X8)) ∨ (¬(X5 ≡ X6) ∧ ¬(X7 ≡ X8)) = 0
((X7 ≡ X8) ∧ (X9 ≡ X10)) ∨ (¬(X7 ≡ X8) ∧ ¬(X9 ≡ X10)) = 0
Διάλυμα:
Ας εισάγουμε νέες μεταβλητές: A=(X1≡ X2); B=(X3 ≡ X4); С=(X5 ≡ X6); D=(X7 ≡ X8); Ε=(Χ9 ≡ Χ10).
(Προσοχή! Κάθε μία από τις μεταβλητές x1, x2, ..., x10 πρέπει να περιλαμβάνεται μόνο σε μία από τις νέες μεταβλητές Α, Β, Γ, Δ, Ε, δηλ. οι νέες μεταβλητές είναι ανεξάρτητες μεταξύ τους).
Τότε το σύστημα των εξισώσεων θα μοιάζει με αυτό:
(A ∧ B) ∨ (¬A ∧ ¬B)=0
(B ∧ C) ∨ (¬B ∧ ¬C)=0
(C ∧ D) ∨ (¬C ∧ ¬D)=0
(D ∧ E) ∨ (¬D ∧ ¬E)=0
Ας δημιουργήσουμε ένα δέντρο αποφάσεων για το σύστημα που προκύπτει:
Θεωρούμε την εξίσωση A=0, δηλ. (Χ1≡ X2)=0. Έχει 2 ρίζες:
X1 ≡ X2 |
||
Από τον ίδιο πίνακα φαίνεται ότι η εξίσωση Α=1 έχει επίσης 2 ρίζες. Ας τακτοποιήσουμε τον αριθμό των ριζών στο δέντρο αποφάσεων:
Για να βρείτε τον αριθμό των λύσεων ενός κλάδου, πρέπει να πολλαπλασιάσετε τον αριθμό των λύσεων σε κάθε επίπεδο. Ο αριστερός κλάδος έχει 2⋅ 2 ⋅ 2 ⋅ 2 ⋅ 2=32 λύσεις; ο δεξιός κλάδος έχει επίσης 32 λύσεις. Εκείνοι. όλο το σύστημα έχει 32+32=64 λύσεις.
Απάντηση: 64.
2. Μέθοδος συλλογισμού.
Η δυσκολία επίλυσης συστημάτων λογικών εξισώσεων έγκειται στη δυσκινησία ενός πλήρους δέντρου αποφάσεων. Η συλλογιστική μέθοδος σας επιτρέπει να μην χτίσετε ολόκληρο το δέντρο, αλλά να καταλάβετε πόσα κλαδιά θα έχει. Ας δούμε αυτή τη μέθοδο χρησιμοποιώντας συγκεκριμένα παραδείγματα.
Παράδειγμα 1. Πόσα διαφορετικά σύνολα τιμών των λογικών μεταβλητών x1, x2, x3, x4, x5, y1, y2, y3, y4, y5 υπάρχουν που ικανοποιούν όλες τις προϋποθέσεις που αναφέρονται παρακάτω;
(x1→x2) /\ (x2→x3) /\ (x3→x4) /\ (x4→x5) = 1
(y1→y2) /\ (y2→y3) /\ (y3→y4) /\ (y4→y5) = 1
x1\/y1 =1
Η απάντηση δεν χρειάζεται να απαριθμήσει όλα τα διαφορετικά σύνολα τιμών των μεταβλητών x1, x2, x3, x4, x5, y1, y2, y3, y4, y5 για τις οποίες ικανοποιείται αυτό το σύστημα ισοτήτων. Ως απάντηση, πρέπει να υποδείξετε τον αριθμό τέτοιων συνόλων.
Λύση:
Η πρώτη και η δεύτερη εξίσωση περιέχουν ανεξάρτητες μεταβλητές που σχετίζονται με την τρίτη συνθήκη. Ας φτιάξουμε ένα δέντρο λύσεων για την πρώτη και τη δεύτερη εξίσωση.
Για να αναπαραστήσουμε ένα δέντρο λύσης για ένα σύστημα της πρώτης και της δεύτερης εξισώσεων, κάθε κλάδος του πρώτου δέντρου πρέπει να συνεχιστεί με ένα δέντρο για μεταβλητέςστο . Το δέντρο που κατασκευάζεται με αυτόν τον τρόπο θα περιέχει 36 κλαδιά. Ορισμένοι από αυτούς τους κλάδους δεν ικανοποιούν την τρίτη εξίσωση του συστήματος. Ας σημειώσουμε τον αριθμό των κλαδιών του δέντρου στο πρώτο δέντρο"υ" , που ικανοποιούν την τρίτη εξίσωση:
Ας εξηγήσουμε: για να ικανοποιηθεί η τρίτη συνθήκη, όταν x1=0 πρέπει να υπάρχουν y1=1, δηλαδή όλα τα κλαδιά του δέντρου"Χ" , όπου x1=0 μπορεί να συνεχιστεί με ένα μόνο κλαδί από το δέντρο"υ" . Και μόνο για ένα κλαδί του δέντρου"Χ" (δεξιά) όλα τα κλαδιά του δέντρου ταιριάζουν"υ". Έτσι, το πλήρες δέντρο ολόκληρου του συστήματος περιέχει 11 κλάδους. Κάθε κλάδος αντιπροσωπεύει μία λύση στο αρχικό σύστημα εξισώσεων. Αυτό σημαίνει ότι ολόκληρο το σύστημα έχει 11 λύσεις.
Απάντηση: 11.
Παράδειγμα 2. Πόσες διαφορετικές λύσεις έχει το σύστημα εξισώσεων;
(X1 ≡ X2) ∨ (X1 ∧ X10) ∨ (¬X1 ∧ ¬ X10)= 1
(X2 ≡ X3) ∨ (X2 ∧ X10) ∨ (¬X2 ∧ ¬ X10)= 1.
………………
(X9 ≡ X10) ∨ (X9 ∧ X10) ∨ (¬X9 ∧ ¬ X10)= 1
(X1 ≡ X10) = 0
όπου x1, x2, …, x10 είναι οι λογικές μεταβλητές; Η απάντηση δεν χρειάζεται να αναφέρει όλα τα διαφορετικά σύνολα μεταβλητών τιμών για τα οποία ισχύει αυτή η ισότητα. Ως απάντηση, πρέπει να υποδείξετε τον αριθμό τέτοιων συνόλων.
Λύση: Ας απλοποιήσουμε το σύστημα. Ας φτιάξουμε έναν πίνακα αλήθειας για μέρος της πρώτης εξίσωσης:
X1 ∧ X10 | ¬X1 ∧ ¬X10 | (X1 ∧ X10) ∨ (¬X1 ∧ ¬ X10) |
||
Προσοχή στην τελευταία στήλη, ταιριάζει με το αποτέλεσμα της ενέργειας X1 ≡ X10.
X1 ≡ X10 |
Μετά την απλοποίηση παίρνουμε:
(X1 ≡ X2) ∨ (X1 ≡ X10)=1
(X2 ≡ X3) ∨ (X2 ≡ X10)=1
(X3 ≡ X4) ∨ (X3 ≡ X10)=1
……
(X9 ≡ X10) ∨ (X9 ≡ X10)=1
(X1 ≡ X10) = 0
Εξετάστε την τελευταία εξίσωση:(X1 ≡ X10) = 0, δηλ. Το x1 δεν πρέπει να συμπίπτει με το x10. Για να είναι η πρώτη εξίσωση ίση με 1, η ισότητα πρέπει να είναι αληθής(X1 ≡ X2)=1, δηλ. Το x1 πρέπει να ταιριάζει με το x2.
Ας φτιάξουμε ένα δέντρο λύσης για την πρώτη εξίσωση:
Θεωρούμε τη δεύτερη εξίσωση: για x10=1 και για x2=0 την αγκύληπρέπει να είναι ίσο με 1 (δηλαδή το x2 συμπίπτει με το x3). για x10=0 και για x2=1 παρένθεση(X2 ≡ X10)=0, που σημαίνει το στήριγμα (X2 ≡ X3) πρέπει να είναι ίσο με 1 (δηλαδή το x2 συμπίπτει με το x3):
Συλλογιζόμενοι με αυτόν τον τρόπο, χτίζουμε ένα δέντρο λύσεων για όλες τις εξισώσεις:
Έτσι, το σύστημα των εξισώσεων έχει μόνο 2 λύσεις.
Απάντηση: 2.
Παράδειγμα 3.
Πόσα διαφορετικά σύνολα τιμών των λογικών μεταβλητών x1, x2, x3, x4, y1, y2, y3, y4, z1, z2, z3, z4 υπάρχουν που ικανοποιούν όλες τις προϋποθέσεις που αναφέρονται παρακάτω;
(x1→x2) /\ (x2→x3) /\ (x3→x4) = 1
(¬x1 /\ y1 /\ z1) \/ (x1 /\ ¬y1 /\ z1) \/ (x1 /\ y1 /\ ¬z1) = 1
(¬x2 /\ y2 /\ z2) \/ (x2 /\ ¬y2 /\ z2) \/ (x2 /\ y2 /\ ¬z2) = 1
(¬x3 /\ y3 /\ z3) \/ (x3 /\ ¬y3 /\ z3) \/ (x3 /\ y3 /\ ¬z3) = 1
(¬x4 /\ y4 /\ z4) \/ (x4 /\ ¬y4 /\ z4) \/ (x4 /\ y4 /\ ¬z4) = 1
Διάλυμα:
Ας φτιάξουμε ένα δέντρο λύσης για την 1η εξίσωση:
Θεωρήστε τη δεύτερη εξίσωση:
- Όταν x1=0 : η δεύτερη και η τρίτη παρένθεση θα είναι ίσες με 0. για την πρώτη αγκύλη να είναι ίση με 1, y1=1, z1=1 (δηλαδή σε αυτήν την περίπτωση - 1 λύση)
- Όταν x1=1 : η πρώτη αγκύλη θα είναι ίση με 0. δεύτεροςή η τρίτη παρένθεση πρέπει να είναι ίση με 1. η δεύτερη αγκύλη θα είναι ίση με 1 όταν y1=0 και z1=1. η τρίτη αγκύλη θα είναι ίση με 1 όταν y1=1 και z1=0 (δηλαδή σε αυτή την περίπτωση - 2 λύσεις).
Ομοίως για τις υπόλοιπες εξισώσεις. Ας σημειώσουμε τον αριθμό των λύσεων που προκύπτει για κάθε κόμβο δέντρου:
Για να μάθετε τον αριθμό των λύσεων για κάθε κλάδο, πολλαπλασιάστε τους αριθμούς που προκύπτουν χωριστά για κάθε κλάδο (από αριστερά προς τα δεξιά).
1 κλάδος: 1 ⋅ 1 ⋅ 1 ⋅ 1 = 1 διάλυμα
Κλάδος 2: 1 ⋅ 1 ⋅ 1 ⋅ 2 =2 διαλύματα
3ος κλάδος: 1 ⋅ 1 ⋅ 2 ⋅ 2 =4 λύσεις
4ος κλάδος: 1 ⋅ 2 ⋅ 2 ⋅ 2 =8 λύσεις
5ος κλάδος: 2 ⋅ 2 ⋅ 2 ⋅ 2=16 λύσεις
Ας αθροίσουμε τους αριθμούς που προκύπτουν: υπάρχουν 31 λύσεις συνολικά.
Απάντηση: 31.
3. Φυσική αύξηση του αριθμού των ριζών
Σε ορισμένα συστήματα, ο αριθμός των ριζών της επόμενης εξίσωσης εξαρτάται από τον αριθμό των ριζών της προηγούμενης εξίσωσης.
Παράδειγμα 1. Πόσα διαφορετικά σύνολα τιμών των λογικών μεταβλητών x1, x2, x3, x4, x5, x6, x7, x8, x9, x10 υπάρχουν που ικανοποιούν όλες τις προϋποθέσεις που αναφέρονται παρακάτω;
¬(x1 ≡ x2) ∧ ((x1 ∧ ¬x3) ∨ (¬x1 ∧ x3)) = 0
¬(x2 ≡ x3) ∧ ((x2 ∧ ¬x4) ∨ (¬x2 ∧ x4)) = 0
¬(x8 ≡ x9) ∧ ((x8 ∧ ¬x10) ∨ (¬x8 ∧ x10)) = 0
Ας απλοποιήσουμε πρώτη εξίσωση:(x1 ∧ ¬x3) ∨ (¬x1 ∧ x3)=x1 ⊕ x3=¬(x1 ≡ x3). Τότε το σύστημα θα πάρει τη μορφή:
¬(x1 ≡ x2) ∧ ¬(x1 ≡ x3) = 0
¬(x2 ≡ x3) ∧ ¬(x2 ≡ x4)= 0
¬(x8 ≡ x9) ∧ ¬(x8 ≡ x10) = 0
Και τα λοιπά.
Κάθε επόμενη εξίσωση έχει 2 περισσότερες ρίζες από την προηγούμενη.
Η 4 εξίσωση έχει 12 ρίζες.
Η εξίσωση 5 έχει 14 ρίζες
Η εξίσωση 8 έχει 20 ρίζες.
Απάντηση: 20 ρίζες.
Μερικές φορές ο αριθμός των ριζών αυξάνεται σύμφωνα με το νόμο Fibonacci.
Η επίλυση ενός συστήματος λογικών εξισώσεων απαιτεί δημιουργική προσέγγιση.
Έστω μια λογική συνάρτηση n μεταβλητών. Η λογική εξίσωση μοιάζει με:
Η σταθερά C έχει την τιμή 1 ή 0.
Μια λογική εξίσωση μπορεί να έχει από 0 έως διαφορετικές λύσεις. Αν το C είναι ίσο με 1, τότε οι λύσεις είναι όλα εκείνα τα σύνολα μεταβλητών από τον πίνακα αλήθειας για τα οποία η συνάρτηση F παίρνει την τιμή true (1). Τα υπόλοιπα σύνολα είναι λύσεις της εξίσωσης με το C ίσο με μηδέν. Μπορείτε πάντα να εξετάζετε μόνο εξισώσεις της μορφής:
Πράγματι, ας δοθεί η εξίσωση:
Σε αυτήν την περίπτωση, μπορούμε να πάμε στην ισοδύναμη εξίσωση:
Θεωρήστε ένα σύστημα k λογικών εξισώσεων:
Η λύση σε ένα σύστημα είναι ένα σύνολο μεταβλητών στις οποίες ικανοποιούνται όλες οι εξισώσεις του συστήματος. Όσον αφορά τις λογικές συναρτήσεις, για να ληφθεί μια λύση σε ένα σύστημα λογικών εξισώσεων, θα πρέπει να βρεθεί ένα σύνολο στο οποίο η λογική συνάρτηση Ф είναι αληθής, αντιπροσωπεύοντας το συνδυασμό των αρχικών συναρτήσεων:
Εάν ο αριθμός των μεταβλητών είναι μικρός, για παράδειγμα, μικρότερος από 5, τότε δεν είναι δύσκολο να κατασκευάσουμε έναν πίνακα αλήθειας για τη συνάρτηση, ο οποίος μας επιτρέπει να πούμε πόσες λύσεις έχει το σύστημα και ποια είναι τα σύνολα που παρέχουν λύσεις.
Σε ορισμένα προβλήματα ΧΡΗΣΗΣ για την εύρεση λύσεων σε ένα σύστημα λογικών εξισώσεων, ο αριθμός των μεταβλητών φτάνει τις 10. Τότε η κατασκευή ενός πίνακα αλήθειας γίνεται σχεδόν αδύνατη. Η επίλυση του προβλήματος απαιτεί διαφορετική προσέγγιση. Για ένα αυθαίρετο σύστημα εξισώσεων, δεν υπάρχει γενική μέθοδος εκτός από την απαρίθμηση που να επιτρέπει την επίλυση τέτοιων προβλημάτων.
Στα προβλήματα που προτείνονται στην εξέταση, η λύση βασίζεται συνήθως στο να ληφθούν υπόψη οι ιδιαιτερότητες του συστήματος εξισώσεων. Επαναλαμβάνω, εκτός από τη δοκιμή όλων των επιλογών για ένα σύνολο μεταβλητών, δεν υπάρχει γενικός τρόπος επίλυσης του προβλήματος. Η λύση πρέπει να χτιστεί με βάση τις ιδιαιτερότητες του συστήματος. Συχνά είναι χρήσιμο να πραγματοποιηθεί μια προκαταρκτική απλοποίηση ενός συστήματος εξισώσεων χρησιμοποιώντας γνωστούς νόμους της λογικής. Μια άλλη χρήσιμη τεχνική για την επίλυση αυτού του προβλήματος είναι η εξής. Δεν μας ενδιαφέρουν όλα τα σύνολα, αλλά μόνο εκείνα στα οποία η συνάρτηση έχει την τιμή 1. Αντί να δημιουργήσουμε έναν πλήρη πίνακα αλήθειας, θα δημιουργήσουμε το ανάλογό του - ένα δυαδικό δέντρο αποφάσεων. Κάθε κλάδος αυτού του δέντρου αντιστοιχεί σε μία λύση και καθορίζει ένα σύνολο στο οποίο η συνάρτηση έχει την τιμή 1. Ο αριθμός των κλάδων στο δέντρο αποφάσεων συμπίπτει με τον αριθμό των λύσεων στο σύστημα των εξισώσεων.
Θα εξηγήσω τι είναι ένα δυαδικό δέντρο αποφάσεων και πώς κατασκευάζεται χρησιμοποιώντας παραδείγματα πολλών προβλημάτων.
Πρόβλημα 18
Πόσα διαφορετικά σύνολα τιμών των λογικών μεταβλητών x1, x2, x3, x4, x5, y1, y2, y3, y4, y5 υπάρχουν που ικανοποιούν το σύστημα δύο εξισώσεων;
Απάντηση: Το σύστημα έχει 36 διαφορετικές λύσεις.
Λύση: Το σύστημα των εξισώσεων περιλαμβάνει δύο εξισώσεις. Ας βρούμε τον αριθμό των λύσεων για την πρώτη εξίσωση, ανάλογα με 5 μεταβλητές - . Η πρώτη εξίσωση μπορεί με τη σειρά της να θεωρηθεί ως ένα σύστημα 5 εξισώσεων. Όπως έχει αποδειχθεί, το σύστημα των εξισώσεων στην πραγματικότητα αντιπροσωπεύει το συνδυασμό λογικών συναρτήσεων. Η αντίστροφη πρόταση είναι επίσης αληθής - ένας συνδυασμός συνθηκών μπορεί να θεωρηθεί ως σύστημα εξισώσεων.
Ας οικοδομήσουμε ένα δέντρο απόφασης για συνεπαγωγή () - τον πρώτο όρο του συνδέσμου, ο οποίος μπορεί να θεωρηθεί ως η πρώτη εξίσωση. Έτσι μοιάζει μια γραφική αναπαράσταση αυτού του δέντρου
Το δέντρο αποτελείται από δύο επίπεδα ανάλογα με τον αριθμό των μεταβλητών στην εξίσωση. Το πρώτο επίπεδο περιγράφει την πρώτη μεταβλητή. Δύο κλάδοι αυτού του επιπέδου αντικατοπτρίζουν τις πιθανές τιμές αυτής της μεταβλητής - 1 και 0. Στο δεύτερο επίπεδο, τα κλαδιά του δέντρου αντικατοπτρίζουν μόνο εκείνες τις πιθανές τιμές της μεταβλητής για τις οποίες η εξίσωση αξιολογείται ως αληθής. Εφόσον η εξίσωση καθορίζει μια έννοια, ένας κλάδος στον οποίο έχει την τιμή 1 απαιτεί να υπάρχει σε αυτόν τον κλάδο η τιμή 1. Ένας κλάδος στον οποίο έχει την τιμή 0 δημιουργεί δύο κλάδους με τιμές ίσες με 0 και 1. Το κατασκευασμένο Το δέντρο καθορίζει τρεις λύσεις, από τις οποίες η συνεπαγωγή παίρνει την τιμή 1. Σε κάθε κλάδο, γράφεται ένα αντίστοιχο σύνολο μεταβλητών τιμών, δίνοντας μια λύση στην εξίσωση.
Αυτά τα σετ είναι: ((1, 1), (0, 1), (0, 0))
Ας συνεχίσουμε να χτίζουμε το δέντρο αποφάσεων προσθέτοντας την ακόλουθη εξίσωση, την ακόλουθη συνέπεια. Η ιδιαιτερότητα του συστήματος εξισώσεων μας είναι ότι κάθε νέα εξίσωση του συστήματος χρησιμοποιεί μία μεταβλητή από την προηγούμενη εξίσωση, προσθέτοντας μία νέα μεταβλητή. Εφόσον η μεταβλητή έχει ήδη τιμές στο δέντρο, τότε σε όλους τους κλάδους όπου η μεταβλητή έχει τιμή 1, η μεταβλητή θα έχει επίσης τιμή 1. Για τέτοιους κλάδους, η κατασκευή του δέντρου συνεχίζεται στο επόμενο επίπεδο, αλλά δεν εμφανίζονται νέοι κλάδοι. Ένας μεμονωμένος κλάδος όπου μια μεταβλητή έχει τιμή 0 θα διακλαδωθεί σε δύο κλάδους όπου η μεταβλητή θα λάβει τιμές 0 και 1. Έτσι, κάθε προσθήκη μιας νέας εξίσωσης, δεδομένης της ειδικότητάς της, προσθέτει μία λύση. Αρχική πρώτη εξίσωση:
έχει 6 λύσεις. Δείτε πώς φαίνεται το πλήρες δέντρο αποφάσεων για αυτήν την εξίσωση:
Η δεύτερη εξίσωση του συστήματός μας είναι παρόμοια με την πρώτη:
Η μόνη διαφορά είναι ότι η εξίσωση χρησιμοποιεί μεταβλητές Υ Αυτή η εξίσωση έχει επίσης 6 λύσεις. Δεδομένου ότι κάθε λύση μεταβλητής μπορεί να συνδυαστεί με κάθε λύση μεταβλητής, ο συνολικός αριθμός λύσεων είναι 36.
Σημειώστε ότι το κατασκευασμένο δέντρο αποφάσεων δίνει όχι μόνο τον αριθμό των λύσεων (από τον αριθμό των κλάδων), αλλά και τις ίδιες τις λύσεις που είναι γραμμένες σε κάθε κλάδο του δέντρου.
Πρόβλημα 19
Πόσα διαφορετικά σύνολα τιμών των λογικών μεταβλητών x1, x2, x3, x4, x5, y1, y2, y3, y4, y5 υπάρχουν που ικανοποιούν όλες τις προϋποθέσεις που αναφέρονται παρακάτω;
Αυτή η εργασία είναι μια τροποποίηση της προηγούμενης εργασίας. Η διαφορά είναι ότι προστίθεται μια άλλη εξίσωση που συσχετίζει τις μεταβλητές X και Y.
Από την εξίσωση προκύπτει ότι όταν έχει τιμή 1 (υπάρχει μια τέτοια λύση), τότε έχει τιμή 1. Έτσι, υπάρχει ένα σύνολο στο οποίο και έχει τιμές 1. Όταν ισούται με 0, μπορεί έχουν οποιαδήποτε τιμή, τόσο 0 όσο και 1. Επομένως, κάθε σύνολο με , ίσο με 0, και υπάρχουν 5 τέτοια σύνολα, αντιστοιχεί και στα 6 σύνολα με μεταβλητές Y. Επομένως, ο συνολικός αριθμός λύσεων είναι 31.
Πρόβλημα 20
Λύση: Θυμόμαστε τις βασικές ισοδυναμίες, γράφουμε την εξίσωσή μας ως:
Η κυκλική αλυσίδα των συνεπειών σημαίνει ότι οι μεταβλητές είναι πανομοιότυπες, επομένως η εξίσωσή μας είναι ισοδύναμη με την εξίσωση:
Αυτή η εξίσωση έχει δύο λύσεις όταν όλες είναι είτε 1 είτε 0.
Πρόβλημα 21
Πόσες λύσεις έχει η εξίσωση:
Λύση: Ακριβώς όπως στο πρόβλημα 20, μετακινούμαστε από τις κυκλικές επιπτώσεις στις ταυτότητες, ξαναγράφοντας την εξίσωση με τη μορφή:
Ας δημιουργήσουμε ένα δέντρο αποφάσεων για αυτήν την εξίσωση:
Πρόβλημα 22
Πόσες λύσεις έχει το παρακάτω σύστημα εξισώσεων;
Μπορείτε να επιλέξετε διάφορους τρόπουςεπίλυση συστημάτων λογικών εξισώσεων. Αυτό είναι αναγωγή σε μία εξίσωση, κατασκευή πίνακα αλήθειας και αποσύνθεση.
Εργο:Λύστε ένα σύστημα λογικών εξισώσεων:
Ας αναλογιστούμε μέθοδος αναγωγής σε μία εξίσωση . Αυτή η μέθοδος περιλαμβάνει μετασχηματισμό λογικών εξισώσεων έτσι ώστε οι δεξιές πλευρές τους να είναι ίσες με την τιμή αλήθειας (δηλαδή 1). Για να το κάνετε αυτό, χρησιμοποιήστε τη λειτουργία λογικής άρνησης. Στη συνέχεια, εάν οι εξισώσεις περιέχουν σύνθετες λογικές πράξεις, τις αντικαθιστούμε με βασικές: «ΚΑΙ», «Ή», «ΟΧΙ». Το επόμενο βήμα είναι να συνδυάσετε τις εξισώσεις σε μία, ισοδύναμη με το σύστημα, χρησιμοποιώντας τη λογική πράξη «AND». Μετά από αυτό, θα πρέπει να μετατρέψετε την εξίσωση που προκύπτει με βάση τους νόμους της λογικής άλγεβρας και να αποκτήσετε μια συγκεκριμένη λύση στο σύστημα.
Λύση 1:Εφαρμόστε αντιστροφή και στις δύο πλευρές της πρώτης εξίσωσης:
Ας φανταστούμε την επίπτωση μέσω των βασικών πράξεων "OR" και "NOT":
Δεδομένου ότι οι αριστερές πλευρές των εξισώσεων είναι ίσες με 1, μπορούμε να τις συνδυάσουμε χρησιμοποιώντας την πράξη "AND" σε μία εξίσωση που είναι ισοδύναμη με το αρχικό σύστημα:
Ανοίγουμε την πρώτη αγκύλη σύμφωνα με το νόμο του De Morgan και μετατρέπουμε το αποτέλεσμα που προκύπτει:
Η εξίσωση που προκύπτει έχει μία λύση: A =0, B=0 και C=1.
Η επόμενη μέθοδος είναι κατασκευή πινάκων αλήθειας . Δεδομένου ότι τα λογικά μεγέθη έχουν μόνο δύο τιμές, μπορείτε απλά να περάσετε από όλες τις επιλογές και να βρείτε μεταξύ τους εκείνες για τις οποίες ικανοποιείται ένα δεδομένο σύστημα εξισώσεων. Δηλαδή, χτίζουμε έναν κοινό πίνακα αλήθειας για όλες τις εξισώσεις του συστήματος και βρίσκουμε μια γραμμή με τις απαιτούμενες τιμές.
Λύση 2:Ας δημιουργήσουμε έναν πίνακα αλήθειας για το σύστημα:
|
0 |
0 |
1 |
1 |
0 |
1 |
Η γραμμή για την οποία πληρούνται οι συνθήκες εργασίας επισημαίνεται με έντονη γραφή. Άρα Α=0, Β=0 και Γ=1.
Τρόπος αποσύνθεση . Η ιδέα είναι να καθορίσουμε την τιμή μιας από τις μεταβλητές (να την ορίσουμε ίση με 0 ή 1) και έτσι να απλοποιηθούν οι εξισώσεις. Στη συνέχεια, μπορείτε να διορθώσετε την τιμή της δεύτερης μεταβλητής και ούτω καθεξής.
Λύση 3:Έστω A = 0, τότε:
Από την πρώτη εξίσωση παίρνουμε B = 0, και από τη δεύτερη - C = 1. Λύση του συστήματος: Α = 0, Β = 0 και Γ = 1.
Στην Ενιαία Κρατική Εξέταση στην επιστήμη των υπολογιστών, είναι πολύ συχνά απαραίτητο να προσδιοριστεί ο αριθμός των λύσεων σε ένα σύστημα λογικών εξισώσεων, χωρίς να βρεθούν οι ίδιες οι λύσεις, υπάρχουν επίσης ορισμένες μέθοδοι για αυτό. Ο κύριος τρόπος για να βρείτε τον αριθμό των λύσεων σε ένα σύστημα λογικών εξισώσεων είναιαντικατάσταση μεταβλητών. Πρώτα, πρέπει να απλοποιήσετε όσο το δυνατόν περισσότερο καθεμία από τις εξισώσεις με βάση τους νόμους της λογικής άλγεβρας και στη συνέχεια να αντικαταστήσετε τα σύνθετα μέρη των εξισώσεων με νέες μεταβλητές και να καθορίσετε τον αριθμό των λύσεων νέο σύστημα. Στη συνέχεια, επιστρέψτε στην αντικατάσταση και καθορίστε τον αριθμό των λύσεων για αυτό.
Εργο:Πόσες λύσεις έχει η εξίσωση (A →B) + (C →D) = 1; Όπου Α, Β, Γ, Δ είναι λογικές μεταβλητές.
Διάλυμα:Ας εισάγουμε νέες μεταβλητές: X = A →B και Y = C →D. Λαμβάνοντας υπόψη το νέο μεταβλητή εξίσωσηθα γραφεί με τη μορφή: X + Y = 1.
Ο διαχωρισμός είναι αληθής σε τρεις περιπτώσεις: (0;1), (1;0) και (1;1), ενώ τα Χ και Υ είναι συνεπακόλουθα, δηλαδή είναι αληθής σε τρεις περιπτώσεις και ψευδής σε μία. Επομένως, η περίπτωση (0;1) θα αντιστοιχεί σε τρεις πιθανούς συνδυασμούς παραμέτρων. Περίπτωση (1;1) – θα αντιστοιχεί σε εννέα πιθανούς συνδυασμούς παραμέτρων της αρχικής εξίσωσης. Αυτό σημαίνει ότι οι συνολικές πιθανές λύσεις δεδομένη εξίσωση 3+9=15.
Ο επόμενος τρόπος προσδιορισμού του αριθμού των λύσεων σε ένα σύστημα λογικών εξισώσεων είναι δυαδικό δέντρο. Ας δούμε αυτή τη μέθοδο χρησιμοποιώντας ένα παράδειγμα.
Εργο:Πόσες διαφορετικές λύσεις έχει το σύστημα των λογικών εξισώσεων:
Το δεδομένο σύστημα εξισώσεων είναι ισοδύναμο με την εξίσωση:
(x 1 → x 2 )*(x 2 → x 3 )*…*(x m -1 → x m) = 1.
Ας υποθέσουμε ότι x 1 – είναι αλήθεια, τότε από την πρώτη εξίσωση προκύπτει ότι x 2 επίσης αλήθεια, από το δεύτερο - x 3 =1, και ούτω καθεξής μέχρι x m= 1. Αυτό σημαίνει ότι το σύνολο (1; 1; …; 1) των m μονάδων είναι μια λύση στο σύστημα. Αφήστε το τώρα x 1 =0, τότε από την πρώτη εξίσωση έχουμε x 2 =0 ή x 2 =1.
Οταν x 2 true, παίρνουμε ότι οι υπόλοιπες μεταβλητές είναι επίσης αληθείς, δηλαδή το σύνολο (0; 1; ...; 1) είναι μια λύση στο σύστημα. Στο x 2 =0 το καταλαβαίνουμε x 3 =0 ή x 3 =, και ούτω καθεξής. Συνεχίζοντας στην τελευταία μεταβλητή, βρίσκουμε ότι οι λύσεις της εξίσωσης είναι τα ακόλουθα σύνολα μεταβλητών (m +1 λύση, κάθε λύση περιέχει m τιμές των μεταβλητών):
(1; 1; 1; …; 1)
(0; 1; 1; …; 1)
(0; 0; 0; …; 0)
Αυτή η προσέγγιση απεικονίζεται καλά με την κατασκευή ενός δυαδικού δέντρου. Ο αριθμός των πιθανών λύσεων είναι ο αριθμός των διαφορετικών κλάδων του κατασκευασμένου δέντρου. Είναι εύκολο να δούμε ότι είναι ίσο με m +1.
|
Δέντρο |
Αριθμός λύσεων |
|
|
x 1 |
|
|
|
x 2 |
||
|
x 3 |
||
|
… |
Σε περίπτωση δυσκολιών στο συλλογισμό έρευνα και κατασκευήτων λύσεων με τις οποίες μπορείτε να αναζητήσετε μια λύσηχρησιμοποιώντας πίνακες αλήθειας, για μία ή δύο εξισώσεις.
Ας ξαναγράψουμε το σύστημα των εξισώσεων με τη μορφή:
Και ας δημιουργήσουμε έναν πίνακα αλήθειας ξεχωριστά για μία εξίσωση:
|
x 1 |
x 2 |
(x 1 → x 2) |
Ας δημιουργήσουμε έναν πίνακα αλήθειας για δύο εξισώσεις:
|
x 1 |
x 2 |
x 3 |
x 1 → x 2 |
x 2 → x 3 |
(x 1 → x 2) * (x 2 → x 3) |