Συστήματα λογικών εξισώσεων. Λογικές. Λογικές συναρτήσεις. Επίλυση εξισώσεων
Πίνακας αλήθειας – ένας πίνακας που περιέχει όλους τους πιθανούς συνδυασμούς μεταβλητών εισόδου και τις αντίστοιχες τιμές εξόδου τους.
Ο πίνακας αλήθειας περιέχει 2n σειρές, όπου n είναι ο αριθμός των μεταβλητών εισόδου και n+m είναι στήλες, όπου m είναι μεταβλητές εξόδου.
Οδηγίες. Κατά την είσοδο από το πληκτρολόγιο, χρησιμοποιήστε τις ακόλουθες συμβάσεις:
Για παράδειγμα, η λογική έκφραση abc+ab~c+a~bc πρέπει να εισαχθεί ως εξής: a*b*c+a*b=c+a=b*cΓια να εισαγάγετε δεδομένα με τη μορφή λογικού διαγράμματος, χρησιμοποιήστε αυτήν την υπηρεσία.
Κανόνες εισαγωγής λογικής συνάρτησης
- Αντί για το σύμβολο v (διάσπαση, OR), χρησιμοποιήστε το σύμβολο +.
- Δεν χρειάζεται να προσδιορίσετε έναν προσδιορισμό συνάρτησης πριν από μια λογική συνάρτηση. Για παράδειγμα, αντί για F(x,y)=(x|y)=(x^y) πρέπει απλώς να εισαγάγετε (x|y)=(x^y) .
- Μέγιστο ποσόμεταβλητές είναι ίσες με 10.
Ο σχεδιασμός και η ανάλυση των λογικών κυκλωμάτων υπολογιστών πραγματοποιείται χρησιμοποιώντας έναν ειδικό κλάδο των μαθηματικών - λογική άλγεβρα. Στην άλγεβρα της λογικής διακρίνονται τρεις κύριες λογικές συναρτήσεις: «ΟΧΙ» (άρνηση), «ΚΑΙ» (σύνδεση), «OR» (διάσπαση).
Για τη δημιουργία οποιασδήποτε λογικής συσκευής, είναι απαραίτητο να προσδιοριστεί η εξάρτηση καθεμιάς από τις μεταβλητές εξόδου από τις υπάρχουσες μεταβλητές εισόδου· αυτή η εξάρτηση ονομάζεται συνάρτηση μεταγωγής ή συνάρτηση λογικής άλγεβρας.
Μια συνάρτηση λογικής άλγεβρας ονομάζεται πλήρως καθορισμένη εάν δίνονται και τα 2n από τις τιμές της, όπου n είναι ο αριθμός των μεταβλητών εξόδου.
Εάν δεν έχουν καθοριστεί όλες οι τιμές, η συνάρτηση ονομάζεται μερικώς καθορισμένη.
Μια συσκευή ονομάζεται λογική εάν η κατάστασή της περιγράφεται χρησιμοποιώντας μια συνάρτηση λογικής άλγεβρας.
Οι ακόλουθες μέθοδοι χρησιμοποιούνται για την αναπαράσταση μιας συνάρτησης λογικής άλγεβρας:
Σε αλγεβρική μορφή, μπορείτε να δημιουργήσετε ένα κύκλωμα μιας λογικής συσκευής χρησιμοποιώντας λογικά στοιχεία. 
Εικόνα 1 - Διάγραμμα λογικής συσκευής
Όλες οι πράξεις της άλγεβρας της λογικής ορίζονται πίνακες αλήθειαςαξίες. Ο πίνακας αλήθειας καθορίζει το αποτέλεσμα μιας πράξης για όλοι είναι δυνατοί x λογικές τιμές των αρχικών δηλώσεων. Ο αριθμός των επιλογών που αντικατοπτρίζουν το αποτέλεσμα της εφαρμογής πράξεων θα εξαρτηθεί από τον αριθμό των δηλώσεων στη λογική έκφραση. Εάν ο αριθμός των δηλώσεων σε μια λογική παράσταση είναι N, τότε ο πίνακας αλήθειας θα περιέχει 2 N σειρές, αφού υπάρχουν 2 N διαφορετικοί συνδυασμοί πιθανών τιμών ορίσματος.
Λειτουργία NOT - λογική άρνηση (αναστροφή)
Μια λογική πράξη ΔΕΝ εφαρμόζεται σε ένα μεμονωμένο όρισμα, το οποίο μπορεί να είναι μια απλή ή σύνθετη λογική έκφραση. Το αποτέλεσμα της επέμβασης ΔΕΝ είναι το εξής:- Εάν η αρχική έκφραση είναι αληθής, τότε το αποτέλεσμα της άρνησής της θα είναι ψευδές.
- αν η αρχική έκφραση είναι ψευδής, τότε το αποτέλεσμα της άρνησής της θα είναι αληθές.
όχι A, Ā, όχι A, ¬A, !A
Το αποτέλεσμα της πράξης άρνησης ΔΕΝ προσδιορίζεται από τον ακόλουθο πίνακα αληθείας:
| ΕΝΑ | δεν είναι |
| 0 | 1 |
| 1 | 0 |
Το αποτέλεσμα της πράξης άρνησης είναι αληθές όταν η αρχική πρόταση είναι ψευδής και το αντίστροφο.
Λειτουργία Ή - λογική προσθήκη (διάσπαση, ένωση)
Η λειτουργία λογικής OR εκτελεί τη λειτουργία του συνδυασμού δύο δηλώσεων, οι οποίες μπορεί να είναι είτε απλή είτε σύνθετη λογική έκφραση. Οι δηλώσεις που είναι τα σημεία εκκίνησης για μια λογική πράξη ονομάζονται ορίσματα. Το αποτέλεσμα της λειτουργίας OR είναι μια έκφραση που θα είναι αληθής εάν και μόνο εάν τουλάχιστον μία από τις αρχικές εκφράσεις είναι αληθής.Χρησιμοποιούνται ονομασίες: A ή B, A V B, A ή B, A||B.
Το αποτέλεσμα της πράξης OR προσδιορίζεται από τον ακόλουθο πίνακα αληθείας:
Το αποτέλεσμα της πράξης OR είναι αληθές όταν το Α είναι αληθές, ή το Β είναι αληθές, ή και το Α και το Β είναι αληθές και ψευδές όταν τα ορίσματα Α και Β είναι ψευδή.
Πράξη ΚΑΙ - λογικός πολλαπλασιασμός (σύνδεση)
Η λογική πράξη ΚΑΙ εκτελεί τη συνάρτηση τομής δύο προτάσεων (επιχειρήματα), που μπορεί να είναι είτε απλή είτε σύνθετη λογική έκφραση. Το αποτέλεσμα της λειτουργίας AND είναι μια έκφραση που θα είναι αληθής εάν και μόνο εάν και οι δύο αρχικές εκφράσεις είναι αληθείς.Χρησιμοποιούνται ονομασίες: Α και Β, Α Λ Β, Α & Β, Α και Β.
Το αποτέλεσμα της πράξης AND καθορίζεται από τον ακόλουθο πίνακα αληθείας:
| ΕΝΑ | σι | Α και Β |
| 0 | 0 | 0 |
| 0 | 1 | 0 |
| 1 | 0 | 0 |
| 1 | 1 | 1 |
Το αποτέλεσμα της πράξης AND είναι αληθές αν και μόνο αν οι προτάσεις Α και Β είναι και αληθείς και ψευδείς σε όλες τις άλλες περιπτώσεις.
Λειτουργία «ΑΝ-ΤΟΤΕ» - λογική συνέπεια (υπόνοια)
Αυτή η λειτουργία συνδέει δύο απλές λογικές εκφράσεις, εκ των οποίων η πρώτη είναι συνθήκη και η δεύτερη είναι συνέπεια αυτής της συνθήκης.Ονομασίες που χρησιμοποιούνται:
αν Α, τότε Β. Το Α συνεπάγεται το Β. αν Α τότε Β; Α→Β.
Πίνακας αλήθειας:
| ΕΝΑ | σι | Α → Β |
| 0 | 0 | 1 |
| 0 | 1 | 1 |
| 1 | 0 | 0 |
| 1 | 1 | 1 |
Το αποτέλεσμα της πράξης υπαινιγμού είναι ψευδές μόνο εάν η υπόθεση Α είναι αληθής και το συμπέρασμα Β (συνέπεια) είναι ψευδές.
Λειτουργία «Α εάν και μόνο εάν Β» (ισοδυναμία, ισοδυναμία)
Ονομασία που χρησιμοποιείται: A ↔ B, A ~ B.Πίνακας αλήθειας:
| ΕΝΑ | σι | Α↔Β |
| 0 | 0 | 1 |
| 0 | 1 | 0 |
| 1 | 0 | 0 |
| 1 | 1 | 1 |
Λειτουργία "Addition modulo 2" (XOR, αποκλειστική ή αυστηρή διάσπαση)
Χρησιμοποιημένος συμβολισμός: A XOR B, A ⊕ B.Πίνακας αλήθειας:
| ΕΝΑ | σι | A⊕B |
| 0 | 0 | 0 |
| 0 | 1 | 1 |
| 1 | 0 | 1 |
| 1 | 1 | 0 |
Το αποτέλεσμα της πράξης ισοδυναμίας είναι αληθές μόνο εάν το Α και το Β είναι ταυτόχρονα αληθές ή ψευδές.
Προτεραιότητα λογικών πράξεων
- Ενέργειες σε παρένθεση
- Αναστροφή
- Σύνδεσμος (&)
- Disjunction (V), Exclusive OR (XOR), sum modulo 2
- Υπονοούμενα (→)
- Ισοδυναμία (↔)
Τέλεια διαχωριστική κανονική μορφή
Τέλεια διαχωριστική κανονική μορφή φόρμουλαςΤο (SDNF) είναι ένας ισοδύναμος τύπος, ο οποίος είναι ένας διαχωρισμός στοιχειωδών συνδέσμων και έχει τις ακόλουθες ιδιότητες:- Κάθε λογικός όρος του τύπου περιέχει όλες τις μεταβλητές που περιλαμβάνονται στη συνάρτηση F(x 1,x 2,...x n).
- Όλοι οι λογικοί όροι του τύπου είναι διαφορετικοί.
- Κανένας λογικός όρος δεν περιέχει μια μεταβλητή και την άρνησή της.
- Κανένας λογικός όρος σε έναν τύπο δεν περιέχει την ίδια μεταβλητή δύο φορές.
Για κάθε συνάρτηση, τα SDNF και SCNF ορίζονται μοναδικά μέχρι τη μετάθεση.
Τέλεια συνδετική κανονική μορφή
Τέλεια συνδετική κανονική μορφή τύπου (SCNF)Αυτός είναι ένας τύπος ισοδύναμος με αυτόν, ο οποίος είναι ένας συνδυασμός στοιχειωδών διαχωρισμών και ικανοποιεί τις ιδιότητες:- Όλοι οι στοιχειώδεις διαχωρισμοί περιέχουν όλες τις μεταβλητές που περιλαμβάνονται στη συνάρτηση F(x 1 ,x 2 ,...x n).
- Όλοι οι στοιχειώδεις διαχωρισμοί είναι διαφορετικοί.
- Κάθε στοιχειώδης διαχωρισμός περιέχει μια μεταβλητή μία φορά.
- Κανένας στοιχειώδης διαχωρισμός δεν περιέχει μια μεταβλητή και την άρνησή της.
Πώς να λύσετε ορισμένα προβλήματα στις ενότητες Α και Β της εξέτασης πληροφορικής
Μάθημα #3. Λογικές. Λογικές συναρτήσεις. Επίλυση εξισώσεων
Ένας μεγάλος αριθμός προβλημάτων Ενιαίας Πολιτικής Εξετάσεων είναι αφιερωμένος στην προτασιακή λογική. Για να λυθούν τα περισσότερα από αυτά, αρκεί να γνωρίζουμε τους βασικούς νόμους της προτασιακής λογικής, τη γνώση των πινάκων αλήθειας των λογικών συναρτήσεων μιας και δύο μεταβλητών. Θα δώσω τους βασικούς νόμους της προτασιακής λογικής.
- Αντιμεταθεσιμότητα διαχωρισμού και συνδέσμου:
a ˅ b ≡ b ˅ a
a^b ≡ b^a - Διανεμητικός νόμος σχετικά με τον διαχωρισμό και τον σύνδεσμο:
a ˅ (b^с) ≡ (a ˅ β) ^(a ˅ с)
a ^ (b ˅ c) ≡ (a ^ b) ˅ (a ^ c) - Άρνηση άρνησης:
¬(¬a) ≡ α - Συνοχή:
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 ˄ β) ≡ ¬(¬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))
Η κατάθεση και των δύο μαρτύρων θεωρείται αληθής και αντιπροσωπεύει το συνδυασμό των αντίστοιχων τύπων.
Ας φτιάξουμε έναν πίνακα αλήθειας για αυτές τις αναγνώσεις:
| ΕΝΑ | σι | ντο | F1 | F2 | 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. Οι δύο κλάδοι δημιουργούν 2 * 2 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 όταν στο ι-η ρίψηκέρματα ανεβαίνουν κεφάλια. Η λογική συνάρτηση που καθορίζει την πληρωμή 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)
Αυτό το υλικό περιέχει μια παρουσίαση που παρουσιάζει μεθόδους επίλυσης λογικών εξισώσεων και συστημάτων λογικών εξισώσεων στην εργασία Β15 (Αρ. 23, 2015) της Ενιαίας Κρατικής Εξέτασης στην επιστήμη των υπολογιστών. Είναι γνωστό ότι αυτό το έργο είναι ένα από τα πιο δύσκολα μεταξύ των εργασιών της Ενιαίας Κρατικής Εξέτασης. Η παρουσίαση μπορεί να είναι χρήσιμη κατά τη διδασκαλία μαθημάτων σχετικά με το θέμα «Λογική» σε εξειδικευμένες τάξεις, καθώς και κατά την προετοιμασία για την Ενιαία Κρατική Εξέταση.
Κατεβάστε:
Προεπισκόπηση:
Για να χρησιμοποιήσετε προεπισκοπήσεις παρουσίασης, δημιουργήστε έναν λογαριασμό Google και συνδεθείτε σε αυτόν: https://accounts.google.com
Λεζάντες διαφάνειας:
Λύση της εργασίας Β15 (συστήματα λογικών εξισώσεων) Vishnevskaya M.P., MAOU “Gymnasium No. 3” 18 Νοεμβρίου 2013, Saratov
Η εργασία Β15 είναι από τις πιο δύσκολες στην Ενιαία Κρατική Εξέταση στην επιστήμη των υπολογιστών!!! Δοκιμάζονται οι ακόλουθες δεξιότητες: μετατροπή εκφράσεων που περιέχουν λογικές μεταβλητές. περιγράψτε σε φυσική γλώσσα το σύνολο των τιμών των λογικών μεταβλητών για τις οποίες ισχύει ένα δεδομένο σύνολο λογικών μεταβλητών· μετρήστε τον αριθμό των δυαδικών συνόλων που ικανοποιούν δεδομένες συνθήκες. Το πιο δύσκολο είναι γιατί... δεν υπάρχουν επίσημοι κανόνες για το πώς να το κάνετε αυτό, απαιτεί εικασίες.
Αυτό που δεν μπορείτε να κάνετε χωρίς!
Αυτό που δεν μπορείτε να κάνετε χωρίς!
Σύνδεσμος συμβόλων: A /\ B , A B , AB , A &B, A και B διαχωρισμός: A \ / B , A + B , A | B , A ή B άρνηση: A , A, όχι A ισοδυναμία: A B, A B, A B αποκλειστικό «ή»: A B , A xor B
Μέθοδος αντικατάστασης μεταβλητής Πόσα διαφορετικά σύνολα τιμών λογικών μεταβλητών x1, x2, ..., x9, x10 υπάρχουν που ικανοποιούν όλες τις προϋποθέσεις που αναφέρονται παρακάτω: ((x1 ≡ x2) \/ (x3 ≡ x4)) /\ (¬(x1 ≡ x2) \/ ¬(x3 ≡ x4)) = 1 ((x3 ≡ x4) \/ (x5 ≡ x6)) /\ · (¬(x3 ≡ x4) \/ ¬(x5 ≡ x6)) = 1 ((x5 ≡ x6 ) \/ (x7 ≡ x8)) /\ · (¬(x5 ≡ x7) \/ ¬(x7 ≡ x8)) = 1 ((x7 ≡ x8) \/ (x9 ≡ x10)) /\ · (¬(x7 ≡ x8) \/ ¬(x9 ≡ x10)) = 1 Η απάντηση δεν χρειάζεται να αναφέρει όλα τα διαφορετικά σύνολα x1, x2, …, x9, x10 για τα οποία ισχύει αυτό το σύστημα ισοτήτων. Ως απάντηση, πρέπει να υποδείξετε τον αριθμό τέτοιων συνόλων (έκδοση επίδειξης 2012)
Λύση Βήμα 1. Απλοποιήστε αλλάζοντας τις μεταβλητές t1 = x1 x2 t2 = x3 x4 t3 = x5 x6 t4 = x7 x8 t5 = x9 x10 Μετά την απλοποίηση: (t1 \/ t2) /\ (¬t1 \/ ¬ t2) =1 (t2 \/ t3) /\ (¬t2 \/ ¬ t3) =1 (t3 \/ t4) /\ (¬t3 \/ ¬ t4) =1 (t4 \/ t5) /\ ( ¬ t4 \/ ¬ t5) =1 Θεωρήστε μια από τις εξισώσεις: (t1 \/ t2) /\ (¬t1 \/ ¬ t2) =1 Προφανώς, είναι =1 μόνο εάν μία από τις μεταβλητές είναι 0 και η άλλη είναι 1 Ας χρησιμοποιήσουμε τον τύπο για να εκφράσουμε την πράξη XOR μέσω σύνδεσης και διαχωρισμού: (t1 \/ t2) /\ (¬t1 \/ ¬ t2) = t1 t2 = ¬(t1 ≡ t2) =1 ¬(t1 ≡ t2) =1 ¬( t2 ≡ t3) =1 ¬(t3 ≡ t4) =1 ¬(t4 ≡ t5) =1
Βήμα 2. Ανάλυση συστήματος ¬(t1 ≡ t2) =1 ¬(t2 ≡ t3) =1 ¬(t3 ≡ t4) =1 ¬(t4 ≡ t5) =1 t1 t2 t3 t4 t5 0 1 0 1 0 1 0 1 0 1 Т .Προς την. tk = x2k-1 ≡ x2k (t1 = x1 x2 ,….), τότε κάθε τιμή tk αντιστοιχεί σε δύο ζεύγη τιμών x2k-1 και x2k, για παράδειγμα: tk =0 αντιστοιχεί σε δύο ζεύγη - (0 ,1) και (1, 0) , και tk =1 – ζεύγη (0,0) και (1,1).
Βήμα 3. Μετρώντας τον αριθμό των λύσεων. Κάθε t έχει 2 λύσεις, ο αριθμός των ts είναι 5. Έτσι. για τις μεταβλητές t υπάρχουν 2 5 = 32 λύσεις. Αλλά για κάθε t αντιστοιχεί ένα ζεύγος λύσεων x, δηλ. το αρχικό σύστημα έχει 2*32 = 64 λύσεις. Απάντηση: 64
Μέθοδος εξάλειψης μέρους των λύσεων Πόσα διαφορετικά σύνολα τιμών λογικών μεταβλητών x1, x2, ..., x5, y1,y2,..., y5 υπάρχουν που ικανοποιούν όλες τις προϋποθέσεις που αναφέρονται παρακάτω: (x1→ x2 )∧(x2→ x3)∧(x3→ x4 )∧(x4→ x5) =1; (y1→ y2)∧(y2→ y3)∧(y3→ y4) ∧(y4→ y5) =1; y5→ x5 =1. Η απάντηση δεν χρειάζεται να απαριθμήσει όλα τα διαφορετικά σύνολα x1, x2, ..., x5, y 1 , y2, ... , y5 για τα οποία ισχύει αυτό το σύστημα ισοτήτων. Η απάντηση πρέπει να αναφέρει τον αριθμό τέτοιων συνόλων.
Λύση. Βήμα 1. Διαδοχική λύσηεξισώσεις x1 1 0 x2 1 0 1 x3 1 0 1 1 x4 1 0 1 1 1 x5 1 0 1 1 1 1 Η πρώτη εξίσωση είναι ο συνδυασμός πολλών πράξεων υπονοούμενων, ίση με 1, δηλ. καθεμία από τις συνέπειες είναι αληθινή. Η συνεπαγωγή είναι ψευδής μόνο σε μία περίπτωση, όταν 1 0, σε όλες τις άλλες περιπτώσεις (0 0, 0 1, 1 1) η πράξη επιστρέφει 1. Ας το γράψουμε αυτό σε μορφή πίνακα:
Βήμα 1. Διαδοχική λύση εξισώσεων Τ.ο. Λήφθηκαν 6 σετ διαλυμάτων για x1, x2, x3, x4, x5: (00000), (00001), (00011), (00111), (01111), (11111). Συλλογίζοντας παρόμοια, καταλήγουμε στο συμπέρασμα ότι για τα y1, y2, y3, y4, y5 υπάρχει το ίδιο σύνολο λύσεων. Επειδή αυτές οι εξισώσεις είναι ανεξάρτητες, δηλ. δεν έχουν κοινές μεταβλητές, τότε η λύση σε αυτό το σύστημα εξισώσεων (χωρίς να λαμβάνεται υπόψη η τρίτη εξίσωση) θα είναι 6 * 6 = 36 ζεύγη "X" και "Y". Θεωρήστε την τρίτη εξίσωση: y5→ x5 =1 Η λύση είναι τα ζεύγη: 0 0 0 1 1 1 Το ζεύγος δεν είναι λύση: 1 0
Ας συγκρίνουμε τις λύσεις που προέκυψαν όπου το y5 =1, το x5=0 δεν είναι κατάλληλο. υπάρχουν 5 τέτοια ζεύγη Αριθμός λύσεων στο σύστημα: 36-5= 31. Απάντηση: Χρειάζονταν 31 Συνδυαστικοί!!!
Μέθοδος δυναμικού προγραμματισμού Πόσες διαφορετικές λύσεις έχει η λογική εξίσωση x 1 → x 2 → x 3 → x 4 → x 5 → x 6 = 1, όπου x 1, x 2, …, x 6 είναι λογικές μεταβλητές; Η απάντηση δεν χρειάζεται να αναφέρει όλα τα διαφορετικά σύνολα μεταβλητών τιμών για τα οποία ισχύει αυτή η ισότητα. Ως απάντηση, πρέπει να υποδείξετε τις ποσότητες τέτοιων συνόλων.
Λύση Βήμα 1. Ανάλυση της συνθήκης Αριστερά στην εξίσωση οι πράξεις του υπονοούμενου γράφονται διαδοχικά, η προτεραιότητα είναι η ίδια. Ας ξαναγράψουμε: ((((X 1 → X 2) → X 3) → X 4) → X 5) → X 6 = 1 NB! Κάθε επόμενη μεταβλητή δεν εξαρτάται από την προηγούμενη, αλλά από το αποτέλεσμα της προηγούμενης συνεπαγωγής!
Βήμα 2. Αποκάλυψη ενός μοτίβου Ας εξετάσουμε την πρώτη συνέπεια, X 1 → X 2. Πίνακας αλήθειας: X 1 X 2 X 1 → X 2 0 0 1 0 1 1 1 0 0 1 1 1 Από ένα 0 πήραμε 2 μονάδες, και από 1 πήραμε ένα 0 και ένα 1. Υπάρχει μόνο ένα 0 και τρία 1, αυτό είναι το αποτέλεσμα της πρώτης πράξης.
Βήμα 2. Αποκάλυψη ενός σχεδίου Συνδέοντας το x 3 στο αποτέλεσμα της πρώτης πράξης, παίρνουμε: F(x 1 ,x 2) x 3 F(x 1 ,x 2) x 3 0 0 1 0 1 1 1 0 0 1 1 1 1 0 0 1 1 1 1 0 0 1 1 1 Από δύο 0 – δύο 1, από κάθε 1 (υπάρχουν 3) ένα 0 και ένα 1 (3+3)
Βήμα 3. Παραγωγή του τύπου Τ.ο. μπορείτε να δημιουργήσετε τύπους για τον υπολογισμό του αριθμού των μηδενικών N i και του αριθμού των μονάδων E i για μια εξίσωση με μεταβλητές i:
Βήμα 4. Συμπλήρωση του πίνακα Ας συμπληρώσουμε τον πίνακα από αριστερά προς τα δεξιά για i = 6, υπολογίζοντας τον αριθμό των μηδενικών και των μονάδων χρησιμοποιώντας τους παραπάνω τύπους. ο πίνακας δείχνει πώς χτίζεται η επόμενη στήλη από την προηγούμενη: αριθμός μεταβλητών 1 2 3 4 5 6 Αριθμός μηδενικών N i 1 1 3 5 11 21 Αριθμός μονάδων E i 1 2*1+1= 3 2*1 +3= 5 11 21 43 Απάντηση: 43
Μέθοδος που χρησιμοποιεί απλοποιήσεις λογικών παραστάσεων Πόσες διαφορετικές λύσεις έχει η εξίσωση ((J → K) → (M N L)) ((M N L) → (¬ J K)) (M → J) = 1 όπου J, K, L, M, N είναι λογικές μεταβλητές; Η απάντηση δεν χρειάζεται να απαριθμήσει όλα τα διαφορετικά σύνολα τιμών των J, K, L, M και N για τα οποία ισχύει αυτή η ισότητα. Ως απάντηση, πρέπει να υποδείξετε τον αριθμό τέτοιων συνόλων.
Λύση Σημειώστε ότι J → K = ¬ J K Ας εισάγουμε μια αλλαγή μεταβλητών: J → K=A, M N L =B Ας ξαναγράψουμε την εξίσωση λαμβάνοντας υπόψη την αλλαγή: (A → B) (B → A) (M → J)=1 4. (A B) (M → J)= 1 5. Προφανώς, A B για τις ίδιες τιμές των A και B 6. Θεωρήστε την τελευταία συνέπεια M → J =1 Αυτό είναι δυνατό εάν: M= J=0 M=0, J=1 M=J=1
Λύση Διότι A B, τότε όταν M=J=0 παίρνουμε 1 + K=0. Δεν υπάρχουν λύσεις. Όταν M=0, J=1 παίρνουμε 0 + K=0, K=0, και N και L είναι οποιαδήποτε, 4 λύσεις: ¬ J K = M N L K N L 0 0 0 0 0 1 0 1 0 0 1 1
Λύση 10. Όταν M=J=1 παίρνουμε 0+K=1 *N * L, ή K=N*L, 4 λύσεις: 11. Το σύνολο έχει 4+4=8 λύσεις Απάντηση: 8 K N L 0 0 0 0 0 1 0 1 0 1 1 1
Πηγές πληροφοριών: Ο.Β. Bogomolova, D.Yu. Ουσένκοφ. B15: νέες εργασίες και νέες λύσεις // Πληροφορική, Αρ. 6, 2012, σελ. 35 – 39. K.Yu. Πολιάκοφ. Λογικές εξισώσεις // Πληροφορική, Αρ. 14, 2011, σελ. 30-35. http://ege-go.ru/zadania/grb/b15/, [Ηλεκτρονικός πόρος]. http://kpolyakov.narod.ru/school/ege.htm, [Ηλεκτρονικός πόρος].
Έστω μια λογική συνάρτηση 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
Πόσες λύσεις έχει το παρακάτω σύστημα εξισώσεων;
Θέμα μαθήματος: Επίλυση Λογικών Εξισώσεων
Εκπαιδευτικός - μελέτη μεθόδων για την επίλυση λογικών εξισώσεων, ανάπτυξη δεξιοτήτων επίλυσης λογικών εξισώσεων και κατασκευή λογικής έκφρασης χρησιμοποιώντας έναν πίνακα αλήθειας.Αναπτυξιακή - δημιουργία συνθηκών για την ανάπτυξη του γνωστικού ενδιαφέροντος των μαθητών, προώθηση της ανάπτυξης της μνήμης, της προσοχής, λογική σκέψη;
Εκπαιδευτικός : προωθήστε την ικανότητα να ακούτε τις απόψεις των άλλων,καλλιεργώντας τη θέληση και την επιμονή για την επίτευξη τελικών αποτελεσμάτων.
Τύπος μαθήματος: συνδυασμένο μάθημα
Εξοπλισμός: υπολογιστής, προβολέας πολυμέσων, παρουσίαση 6.
Κατά τη διάρκεια των μαθημάτων
Επανάληψη και ενημέρωση βασικών γνώσεων. Εξέταση εργασία για το σπίτι(10 λεπτά)
Σε προηγούμενα μαθήματα, εξοικειωθήκαμε με τους βασικούς νόμους της λογικής άλγεβρας και μάθαμε να χρησιμοποιούμε αυτούς τους νόμους για να απλοποιήσουμε τις λογικές εκφράσεις.
Ας ελέγξουμε την εργασία μας για την απλοποίηση λογικών εκφράσεων:
1. Ποια από τις παρακάτω λέξεις ικανοποιεί τη λογική συνθήκη:
(σύμφωνο πρώτου γράμματος→ σύμφωνο δεύτερου γράμματος)٨ (φωνήεν τελευταίου γράμματος → φωνήεν προτελευταίο γράμμα); Εάν υπάρχουν πολλές τέτοιες λέξεις, υποδείξτε τη μικρότερη από αυτές.
1) ΑΝΝΑ 2) ΜΑΡΙΑ 3) ΟΛΕΓ 4) ΣΤΕΠΑΝ
Ας εισάγουμε τον ακόλουθο συμβολισμό:
Α – σύμφωνο πρώτου γράμματος
Β – σύμφωνο δεύτερου γράμματος
S – τελευταίο γράμμα φωνήεν
Δ – προτελευταίο φωνήεν
Ας κάνουμε μια έκφραση:
Ας κάνουμε έναν πίνακα:
2. Υποδείξτε ποια λογική έκφραση είναι ισοδύναμη με την παράσταση
Ας απλοποιήσουμε την εγγραφή της αρχικής έκφρασης και τις προτεινόμενες επιλογές:
3. Δίνεται ένα τμήμα του πίνακα αλήθειας της έκφρασης F:
Ποια έκφραση ταιριάζει με το F;
Ας προσδιορίσουμε τις τιμές αυτών των παραστάσεων για τις καθορισμένες τιμές των ορισμάτων:
Εισαγωγή στο θέμα του μαθήματος, παρουσίαση νέου υλικού (30 λεπτά)
Συνεχίζουμε να μελετάμε τα βασικά της λογικής και το θέμα του σημερινού μας μαθήματος είναι «Επίλυση Λογικών Εξισώσεων». Αφού μελετήσετε αυτό το θέμα, θα μάθετε τους βασικούς τρόπους επίλυσης λογικών εξισώσεων, θα αποκτήσετε τις δεξιότητες επίλυσης αυτών των εξισώσεων χρησιμοποιώντας τη γλώσσα της λογικής άλγεβρας και την ικανότητα να συνθέσετε μια λογική έκφραση χρησιμοποιώντας έναν πίνακα αλήθειας.
1. Λύστε μια λογική εξίσωση
(¬Κ M) → (¬L Μ Ν) =0
Γράψτε την απάντησή σας ως μια συμβολοσειρά τεσσάρων χαρακτήρων: τις τιμές των μεταβλητών K, L, M και N (με αυτή τη σειρά). Έτσι, για παράδειγμα, η γραμμή 1101 αντιστοιχεί στο γεγονός ότι K=1, L=1, M=0, N=1.
Λύση:
Ας μεταμορφώσουμε την έκφραση(¬Κ M) → (¬L Μ Ν)
Μια έκφραση είναι ψευδής όταν και οι δύο όροι είναι ψευδείς. Ο δεύτερος όρος είναι ίσος με 0 εάν M =0, N =0, L =1. Στον πρώτο όρο K = 0, αφού M = 0, και 
.
Απάντηση: 0100
2. Πόσες λύσεις έχει η εξίσωση (αναφέρετε μόνο τον αριθμό στην απάντησή σας);
Λύση: μετασχηματίστε την έκφραση
(A +B)*(C +D)=1
A +B =1 και C +D =1
Μέθοδος 2: κατάρτιση πίνακα αληθείας
3 τρόπος: κατασκευή ενός SDNF - μια τέλεια διαζευκτική κανονική μορφή για μια συνάρτηση - μια διάσπαση πλήρων τακτικών στοιχειωδών συνδέσμων.Ας μετατρέψουμε την αρχική έκφραση, ανοίξτε τις αγκύλες για να λάβετε τον διαχωρισμό των συνδέσμων:
(A+B)*(C+D)=A*C+B*C+A*D+B*D=
Ας συμπληρώσουμε τους συνδέσμους σε πλήρεις συνδέσμους (το γινόμενο όλων των ορισμάτων), ανοίξτε τις αγκύλες:
Ας λάβουμε υπόψη τους ίδιους συνδέσμους:
Ως αποτέλεσμα, λαμβάνουμε ένα SDNF που περιέχει 9 συνδέσμους. Επομένως, ο πίνακας αλήθειας για αυτήν τη συνάρτηση έχει την τιμή 1 σε 9 σειρές των 2 4 = 16 συνόλων τιμών μεταβλητών.
3. Πόσες λύσεις έχει η εξίσωση (αναφέρετε μόνο τον αριθμό στην απάντησή σας);
Ας απλοποιήσουμε την έκφραση:
,
3 τρόπος: κατασκευή SDNF
Ας λάβουμε υπόψη τους ίδιους συνδέσμους:
Ως αποτέλεσμα, λαμβάνουμε ένα SDNF που περιέχει 5 συνδέσμους. Επομένως, ο πίνακας αλήθειας για αυτήν τη συνάρτηση έχει την τιμή 1 σε 5 σειρές των 2 4 = 16 συνόλων τιμών μεταβλητών.
Κατασκευάζοντας μια λογική έκφραση χρησιμοποιώντας έναν πίνακα αλήθειας:
Για κάθε γραμμή του πίνακα αληθείας που περιέχει 1, συνθέτουμε ένα γινόμενο ορισμάτων και μεταβλητές ίσες με 0 περιλαμβάνονται στο γινόμενο με άρνηση και μεταβλητές ίσες με 1 περιλαμβάνονται χωρίς άρνηση. Η επιθυμητή έκφραση F θα αποτελείται από το άθροισμα των προϊόντων που προκύπτουν. Στη συνέχεια, εάν είναι δυνατόν, αυτή η έκφραση θα πρέπει να απλοποιηθεί.
Παράδειγμα: δίνεται ένας πίνακας αλήθειας μιας έκφρασης. Κατασκευάστε μια λογική έκφραση.
Λύση:3. Εργασία για το σπίτι (5 λεπτά)
Λύστε την εξίσωση:
Πόσες λύσεις έχει η εξίσωση (αναφέρετε μόνο τον αριθμό στην απάντησή σας);
Χρησιμοποιώντας έναν δεδομένο πίνακα αληθείας, κατασκευάστε μια λογική έκφραση και
απλοποιήστε το.
