Έστω μια λογική συνάρτηση n μεταβλητών. Η λογική εξίσωση είναι:

Η σταθερά C έχει την τιμή 1 ή 0.

Η λογική εξίσωση μπορεί να έχει από 0 έως διάφορες λύσεις. Αν το C είναι ίσο με 1, τότε οι λύσεις είναι όλα εκείνα τα σύνολα μεταβλητών από τον πίνακα αλήθειας στα οποία η συνάρτηση F παίρνει την τιμή true (1). Τα υπόλοιπα σύνολα είναι λύσεις της εξίσωσης για το C, μηδέν. Μπορούμε πάντα να θεωρούμε μόνο εξισώσεις της μορφής:

Πράγματι, ας δοθεί η εξίσωση:

Σε αυτήν την περίπτωση, μπορείτε να μεταβείτε στην ισοδύναμη εξίσωση:

Θεωρήστε ένα σύστημα k λογικών εξισώσεων:

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

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

Σε ορισμένες ΧΡΗΣΗ Εργασιώνβρίσκοντας λύσεις στο σύστημα των λογικών εξισώσεων, ο αριθμός των μεταβλητών φτάνει την τιμή του 10. Τότε η κατασκευή ενός πίνακα αλήθειας γίνεται σχεδόν άλυτη εργασία. Η επίλυση του προβλήματος απαιτεί διαφορετική προσέγγιση. Για ένα αυθαίρετο σύστημα εξισώσεων, δεν υπάρχει γενικό τρόπο, που διαφέρει από την απαρίθμηση, η οποία επιτρέπει την επίλυση τέτοιων προβλημάτων.

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

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

Πρόβλημα 18

Πόσα διαφορετικά σύνολα τιμών Boolean μεταβλητών x1, x2, x3, x4, x5, y1, y2, y3, y4, y5 υπάρχουν που ικανοποιούν ένα σύστημα δύο εξισώσεων;

Απάντηση: Το σύστημα έχει 36 διαφορετικές λύσεις.

Λύση: Το σύστημα των εξισώσεων περιλαμβάνει δύο εξισώσεις. Ας βρούμε τον αριθμό των λύσεων για την πρώτη εξίσωση ανάλογα με 5 μεταβλητές - . Η πρώτη εξίσωση μπορεί με τη σειρά της να θεωρηθεί ως ένα σύστημα 5 εξισώσεων. Όπως έχει αποδειχθεί, το σύστημα των εξισώσεων στην πραγματικότητα αντιπροσωπεύει έναν συνδυασμό λογικών συναρτήσεων. Η αντίστροφη πρόταση είναι επίσης αληθής - ο συνδυασμός συνθηκών μπορεί να θεωρηθεί ως σύστημα εξισώσεων.

Ας δημιουργήσουμε ένα δέντρο απόφασης για την επίπτωση () - τον πρώτο όρο του συνδέσμου, ο οποίος μπορεί να θεωρηθεί ως η πρώτη εξίσωση. Δείτε πώς φαίνεται η γραφική εικόνα αυτού του δέντρου

Το δέντρο έχει δύο επίπεδα μεταβλητές εξίσωσης. Το πρώτο επίπεδο περιγράφει την πρώτη μεταβλητή. Οι δύο κλάδοι αυτού του επιπέδου αντανακλούν πιθανές τιμέςαυτή η μεταβλητή - 1 και 0. Στο δεύτερο επίπεδο, τα κλαδιά του δέντρου αντικατοπτρίζουν μόνο εκείνες τις πιθανές τιμές της μεταβλητής για τις οποίες η εξίσωση παίρνει την τιμή true. Εφόσον η εξίσωση ορίζει μια έννοια, ο κλάδος στον οποίο έχει τιμή 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 σύνολα με μεταβλητές Υ. Επομένως, ο συνολικός αριθμός λύσεων είναι 31.

Πρόβλημα 20

Λύση: Θυμόμαστε τη βασική ισοδυναμία, γράφουμε την εξίσωσή μας ως:

Η κυκλική αλυσίδα των συνεπειών σημαίνει ότι οι μεταβλητές είναι πανομοιότυπες, επομένως η εξίσωσή μας είναι ισοδύναμη με:

Αυτή η εξίσωση έχει δύο λύσεις όταν όλες είναι είτε 1 είτε 0.

Πρόβλημα 21

Πόσες λύσεις έχει η εξίσωση:

Λύση: Ακριβώς όπως στο Πρόβλημα 20, περνάμε από τις κυκλικές συνέπειες στις ταυτότητες ξαναγράφοντας την εξίσωση με τη μορφή:

Ας δημιουργήσουμε ένα δέντρο αποφάσεων για αυτήν την εξίσωση:

Πρόβλημα 22

Πόσες λύσεις έχει το παρακάτω σύστημα εξισώσεων;

142. Βρείτε τη μεγαλύτερη δυαδική λύση ενός byte της εξίσωσης
.

143. Βρε Χ, Αν .

144. Η σειρά των δηλώσεων ορίζεται από την ακόλουθη σχέση επανάληψης: . Οι δηλώσεις δίνονται, και οι δύο είναι αληθείς, ψευδείς. Είναι η δήλωση αληθής ή ψευδής; Πώς εκφράζεται μέσω;

145. Πόσες διαφορετικές λύσεις έχει μια λογική εξίσωση
?

146. Πόσες διαφορετικές λύσεις έχει μια λογική εξίσωση
?

147. Πόσες διαφορετικές λύσεις έχει μια λογική εξίσωση:
.

148. Πόσες διαφορετικές λύσεις έχει μια λογική εξίσωση:.

149. Πόσες διαφορετικές λύσεις έχει μια λογική εξίσωση:.

150. Πόσες διαφορετικές λύσεις έχει μια λογική εξίσωση:.

151. Πόσες διαφορετικές λύσεις έχει μια λογική εξίσωση:
.

152. Λύστε την εξίσωση:

153. Να βρείτε όλες τις διαφορετικές λύσεις της εξίσωσης: .

Βρείτε τις ρίζες μιας λογικής εξίσωσης:

Βρείτε τις ρίζες συστημάτων λογικών εξισώσεων:

Βρείτε τον αριθμό των λύσεων στα ακόλουθα συστήματα λογικών εξισώσεων:

Χ 3

μεγάλο 2

μεγάλο 3

κ

Μ

Ν

Ηλεκτρικό κύκλωμα μεταξύ σημείων ΜΚαι Νκαταρτίζεται σύμφωνα με το σχήμα που φαίνεται στο σχήμα. Εξετάστε τις ακόλουθες τέσσερις δηλώσεις:
ΕΝΑ= (Στοιχείο αλυσίδας κεκτός λειτουργίας),
B i= (Στοιχείο αλυσίδας l iεκτός λειτουργίας). Είναι το κύκλωμα κλειστό εάν:
α) η δήλωση είναι αληθής
β) είναι αληθής η δήλωση;
Είναι η μία από αυτές τις δηλώσεις άρνηση της άλλης;

183. (Οικονομική εργασία) Κατασκευάστε ένα διάγραμμα ηλεκτρικού κυκλώματος για την είσοδο τριώροφου κτιρίου έτσι ώστε ένας διακόπτης σε οποιοδήποτε όροφο να μπορεί να ανάβει και να σβήνει το φως σε όλη την είσοδο.

184. (Μηχάνημα έκτακτης ανάγκης) Υπάρχουν τρία μηχανήματα στο χώρο του συνεργείου - δύο εργάτες, το τρίτο είναι έκτακτης ανάγκης. Απαιτείται η σύνδεση των μηχανών με μια αυτόματη γραμμή έτσι ώστε το τρίτο μηχάνημα να ανάβει εάν και μόνο εάν σταματήσει τουλάχιστον ένα από τα δύο πρώτα μηχανήματα.

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

186. Τρεις δάσκαλοι επιλέγουν εργασίες για την Ολυμπιάδα. Υπάρχουν πολλές εργασίες για να διαλέξετε. Για κάθε μια από τις εργασίες, ο καθένας από τους εκπαιδευτικούς εκφράζει τη γνώμη του: μια εύκολη εργασία (0) ή μια δύσκολη εργασία (1). Μια εργασία περιλαμβάνεται στην εργασία της Ολυμπιάδας εάν τουλάχιστον δύο δάσκαλοι τη σημείωσαν ως δύσκολη, αλλά εάν και οι τρεις δάσκαλοι τη θεωρούν δύσκολη, τότε μια τέτοια εργασία δεν περιλαμβάνεται στην εργασία της Ολυμπιάδας ως πολύ δύσκολη. Κάντε ένα λειτουργικό διάγραμμα μιας συσκευής που θα βγάζει 1 εάν η εργασία περιλαμβάνεται στην εργασία της Ολυμπιάδας και 0 εάν δεν περιλαμβάνεται.

187. Καταγράψτε δομικός τύποςγια το ακόλουθο λογικό διάγραμμα:

&

ένα

σι

ντο

φά

191. Υπάρχουν μόνο δύο σύνδεσμοι και ένας μετατροπέας. Μπορούν αυτά τα τρία λογικά στοιχεία (πύλες) να χρησιμοποιηθούν για την κατασκευή λογικό διάγραμμα, ισοδύναμο κυκλώματοςεκφράσεις. Ποια είναι η μορφή αυτού του σχήματος;

192. Υπάρχουν μόνο 1 σύνδεσμος, 1 διαχωριστής και 1 μετατροπέας. Μπορούν αυτά τα στοιχεία να συνδυαστούν σε ένα λογικό κύκλωμα που είναι ισοδύναμο με το κύκλωμα μιας λογικής έκφρασης; Πρέπει να χρησιμοποιηθούν και οι τρεις βαλβίδες. Ποια είναι η μορφή αυτού του σχήματος;

Αυτό το υλικό περιέχει μια παρουσίαση που παρουσιάζει μεθόδους επίλυσης λογικών εξισώσεων και συστημάτων λογικών εξισώσεων στην εργασία Β15 (Αρ. 23, 2015) της Ενιαίας Κρατικής Εξέτασης στην Πληροφορική. Είναι γνωστό ότι αυτό το έργο είναι ένα από τα πιο δύσκολα μεταξύ των εργασιών της εξέτασης. Η παρουσίαση μπορεί να είναι χρήσιμη κατά τη διεξαγωγή μαθημάτων με θέμα "Λογική" σε εξειδικευμένες τάξεις, καθώς και κατά την προετοιμασία για επιτυχία στις εξετάσεις.

Κατεβάστε:

Προεπισκόπηση:

Για να χρησιμοποιήσετε την προεπισκόπηση των παρουσιάσεων, δημιουργήστε έναν λογαριασμό Google (λογαριασμό) και συνδεθείτε: https://accounts.google.com

Λεζάντες διαφανειών:

Λύση της εργασίας Β15 (σύστημα λογικών εξισώσεων) Vishnevskaya M.P., MAOU "Gymnasium No. 3" 18 Νοεμβρίου 2013, Saratov

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

Τι δεν πρέπει να κάνετε χωρίς!

Τι δεν πρέπει να κάνετε χωρίς!

Σύνδεσμος συμβάσεων: 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 XOR: 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. Ανάλυση του συστήματος .Προς. 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 λύσεις, ο αριθμός των t είναι 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  0, σε όλες τις άλλες περιπτώσεις (0  0, 0  1, 1  1) η πράξη επιστρέφει 1. Ας το γράψουμε αυτό με τη μορφή πίνακα:

Βήμα 1. Διαδοχική λύση εξισώσεων Т.о. Λαμβάνονται 6 σετ λύσεων για х1,х2,х3,х4,х5: (00000), (00001), (00011), (00111), (01111), (11111). Υποστηρίζοντας παρόμοια, συμπεραίνουμε ότι για τα y1, y2, y3, y4, y5 υπάρχει το ίδιο σύνολο λύσεων. Επειδή αυτές οι εξισώσεις είναι ανεξάρτητες, δηλ. δεν υπάρχουν κοινές μεταβλητές σε αυτά, τότε η λύση σε αυτό το σύστημα εξισώσεων (χωρίς να λαμβάνεται υπόψη η τρίτη εξίσωση) θα είναι 6 * 6 = 36 ζεύγη "Xs" και "Ys". Θεωρήστε την τρίτη εξίσωση: 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

Μέθοδος που χρησιμοποιεί απλοποιήσεις Boolean εκφράσειςΠόσες διαφορετικές λύσεις έχει η εξίσωση ((J → K) → (M  N  L))  ((M  N  L) → (¬ J  K))  (M → J) = 1 όπου J , K, L, M, N - Μεταβλητές Boolean; Η απάντηση δεν χρειάζεται να αναφέρει όλα τα διαφορετικά σύνολα τιμών 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 για τις ίδιες αξίεςΑ και Β 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. Ουσένκοφ. В15: νέες εργασίες και νέα λύση // Πληροφορική, αρ. 6, 2012, σελ. 35 – 39. K.Yu. Πολιάκοφ. Λογικές Εξισώσεις // Πληροφορική, Αρ. 14, 2011, σελ. 30-35. http://ege-go.ru/zadania/grb/b15/ , [ Ηλεκτρονικός πόρος] . http://kpolyakov.narod.ru/school/ege.htm, [Ηλεκτρονικός πόρος].

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

Λύση. Ας γράψουμε τις παραδοχές από την κατάσταση του προβλήματος με τη μορφή λογικών δηλώσεων: «Η λήψη κέρδους από τη διαίρεση Β δεν είναι απαραίτητη προϋπόθεσηγια να πάρεις

κέρδος ανά διαίρεση A ": F 1 (A, B, C) \u003d A → B

"Η λήψη κέρδους από τουλάχιστον ένα τμήμα Β και Γ δεν αρκεί για να πραγματοποιήσει κέρδος το τμήμα Α": F 2 (A , B , C ) = (B + C ) → A

"Τα τμήματα Α και Β δεν θα ωφεληθούν ταυτόχρονα": F 3 (A , B , C ) = A B

Είναι γνωστό από την προϋπόθεση ότι μόνο μία από τις τρεις υποθέσεις είναι αληθής. Αυτό σημαίνει ότι πρέπει να βρούμε ποια από τις ακόλουθες τρεις λογικές εκφράσεις δεν είναι ταυτόσημη εσφαλμένη:

1) F 1 F 2 F 3

2) F 1 F 2 F 3

3) F 1 F 2 F 3

1) (A → B) ((B + C) → A) (A ↔ B) = A B (B C + A) (A B + A B) = 0

2) (A → B) ((B + C) → A) (A ↔ B) = (A + B) (A B + A C) (A B + A B) = A B C

3) (A → B) ((B + C) → A) (A B) = (A + B) (B C + A) (A B + A B) = 0

Κατά συνέπεια, στο τέλος του έτους, η δεύτερη υπόθεση αποδείχθηκε αληθής και η πρώτη και η τρίτη ήταν ψευδείς.

									Α=0
	F1 F2 F3 = A B C = 1
									αν και μόνο αν B = 0 .
									C=1

Επομένως, το τμήμα Γ θα έχει κέρδος, ενώ τα τμήματα Α και Β δεν θα έχουν κέρδος.

Επίλυση λογικών εξισώσεων

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

Να βρείτε τη ρίζα της λογικής εξίσωσης: (A + B )(X AB ) = B + X → A .

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

F1 (A, B, X ) = (A + B) (X AB)

					Α+Β	(A+B)(X AB)	F 1 (A , B , X )

F2 (A, B, X ) = B + X → A

			Χ→Α							F 2 (A , B , X )
					Χ→Α			Χ→Α

Ας συγκρίνουμε τους ληφθέντες πίνακες αλήθειας και ας επιλέξουμε εκείνες τις σειρές στις οποίες ταιριάζουν οι τιμές F 1 (A , B , X ) και F 2 (A , B , X ).

			F 1 (A , B , X )	F 2 (A , B , X )

Ας ξαναγράψουμε μόνο τις επιλεγμένες σειρές, αφήνοντας μόνο τις στήλες ορισμάτων. Ας δούμε τη μεταβλητή X ως συνάρτηση των A και B .

Είναι προφανές ότι X = B → A .

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

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

F1 = (A + B) (X AB) = A + B + (X ↔ AB) = A B + X A B + X A + X B

F1 = (A + B) (X AB) = (A + B) (X A + X B + X A B) = X A B + X A B + X A B

F2 = B + X → A = B (X → A) = B (X + A) = X B + A B F2 = B + X → A = B + X + A = B + X A

Ας αντικαταστήσουμε το σύμβολο ίσου στη λογική μας εξίσωση με ένα σύμβολο ισοδυναμίας:

F1 ↔ F2 = F1 F2 + F1 F2 = (A B + X A B + X A + X B) (X B + A B) +

+ (Χ Α Β + Χ Α Β + Χ Α Β) (Β + Χ Α) =

= (X A B + X B + X A B) + (X A B + X A B) =

Ας ανασυγκροτήσουμε τους λογικούς όρους αυτής της έκφρασης, βγάζοντας τους παράγοντες Χ και Χ .

X(A B) + X(B+AB) = X(A B) + X(B + A) =

Σημειώστε T = A B, τότε

X T + X T = X ↔ T .

Επομένως, για να έχει λύση μια λογική εξίσωση: X = A B = B + A = B → A .

Λογικά στοιχεία του υπολογιστή. Κατασκευή λειτουργικών διαγραμμάτων

Η μαθηματική λογική με την ανάπτυξη του BT αποδείχθηκε ότι ήταν μέσα ΣΤΕΝΗ ΣΧΕΣΗμε θέματα σχεδιασμού και προγραμματισμού τεχνολογίας υπολογιστών. Η άλγεβρα της λογικής βρήκε ευρεία εφαρμογή αρχικά στην ανάπτυξη του ρελέ-επαφήσυστήματα. Πρώτα βασική έρευνα, ο οποίος επέστησε την προσοχή των μηχανικών που ασχολούνται με το σχεδιασμό των υπολογιστών στη δυνατότητα ανάλυσης ηλεκτρικών κυκλωμάτων χρησιμοποιώντας άλγεβρα Boole, ένα άρθρο του Αμερικανού Claude Shannon "Συμβολική ανάλυση των κυκλωμάτων ρελέ-επαφής" δημοσιεύθηκε τον Δεκέμβριο του 1938. Μετά από αυτό το άρθρο, ο σχεδιασμός των υπολογιστών δεν ολοκληρώθηκε χωρίς τη χρήση της άλγεβρας Boole.

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

Σειριακή σύνδεση επαφών

Παράλληλη σύνδεση επαφών

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

		Κατάσταση κυκλώματος με	Κατάσταση κυκλώματος με παράλληλο
		σειριακή σύνδεση	σύνδεση

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

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

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

Εξετάστε τα λογικά στοιχεία που υλοποιούν τις βασικές λογικές πράξεις:

Inverter - υλοποιεί τη λειτουργία άρνησης ή αντιστροφής. Στο

ο μετατροπέας έχει μία είσοδο και μία έξοδο. Εμφανίζεται το σήμα εξόδου

όταν δεν υπάρχει στην είσοδο και αντίστροφα.

Σύνδεσμος -

Χ1Χ2...Χν

υλοποιεί τη λειτουργία σύνδεσης.

Στο σύνδεσμο

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

η έξοδος εμφανίζεται εάν και μόνο εάν

όλες οι είσοδοι σηματοδοτούνται.

X 2 + ... X n

Disjunctor - υλοποιεί τη λειτουργία διαχωρισμού. Στο

διαχωριστή μία έξοδο και τουλάχιστον δύο

Το σήμα εξόδου δεν εμφανίζεται εάν και μόνο εάν

όταν δεν σηματοδοτούνται όλες οι είσοδοι.

	Χτίζω	λειτουργικός
F(X, Y, Z) = X (Y + Z)
			Χ+Ζ

διάγραμμα που αντιστοιχεί στη συνάρτηση:

& F(X , Y , Z )

Επίλυση προβλημάτων με τη χρήση του συνδέσμου-κανονικού

Και διαζευκτικός-κανονικόςμορφές

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

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

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

ορίσματα και τιμή 0 για όλα τα άλλα. Παράδειγμα: x 1 x 2 x 3 x 4 .

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

Παράδειγμα: x 1 + x 2 + x 3 .

Λειτουργία σε διαζευκτική κανονική μορφή(DNF) είναι το λογικό άθροισμα των minterms.

Παράδειγμα: x 1 x 2 + x 1 x 2 + x 1 x 2 x 3 .

Συνδετική κανονική μορφήΤο (CNF) είναι ένα λογικό προϊόν στοιχειωδών διαχωρισμών (maxterms).

Παράδειγμα: (x 1 + x 2 + x 3 ) (x 1 + x 2 ) .

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

Παράδειγμα: x 1 x 2 x 3 + x 1 x 2 x 3 + x 1 x 2 x 3

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

Παράδειγμα: (x 1 + x 2 + x 3 ) (x 1 + x 2 + x 3 )

Καταγραφή λογικής συνάρτησης σε πίνακα

Οποιαδήποτε λογική συνάρτηση μπορεί να εκφραστεί ως SDNF ή SKNF. Για παράδειγμα, θεωρήστε τη συνάρτηση f που παρουσιάζεται στον πίνακα.

			f(x1, x2, x3)

Οι συναρτήσεις G0, G1, G4, G5, G7 είναι minterms (δείτε τον ορισμό). Κάθε μία από αυτές τις συναρτήσεις είναι το γινόμενο τριών μεταβλητών ή των αντιστρόφων τους και παίρνει την τιμή 1 μόνο σε μία περίπτωση. Μπορεί να φανεί ότι για να ληφθεί 1 στην τιμή της συνάρτησης f, χρειάζεται ένα minterm. Επομένως, ο αριθμός των λεπτομέτρων που συνθέτουν το SDNF αυτής της συνάρτησης είναι ίσος με τον αριθμό των όρων στην τιμή της συνάρτησης: f= G0+G1+G4+G5+G7. Έτσι, το SDNF έχει τη μορφή:

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

Ομοίως, μπορεί κανείς να κατασκευάσει ένα SKNF. Ο αριθμός των παραγόντων είναι ίσος με τον αριθμό των μηδενικών στις τιμές της συνάρτησης:

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

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

Αλγόριθμος για την κατασκευή SDNF σύμφωνα με τον πίνακα αλήθειας

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

1. Επιλέξτε όλες τις σειρές στον πίνακα όπου η συνάρτηση παίρνει την τιμή 1.

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

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

Αλγόριθμος για την κατασκευή του SKNF σύμφωνα με τον πίνακα αλήθειας

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

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

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

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

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

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

			F(A, B, C)

Επιλέγουμε εκείνες τις γραμμές στον πίνακα αληθείας που η τιμή της συνάρτησης είναι ίση με 0.

F(A, B, C) = (A + B + C) (A + B + C)

Ας ελέγξουμε την παράγωγη συνάρτηση συντάσσοντας έναν πίνακα αλήθειας.

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

Επίλυση προβλήματος

1. Τρεις δάσκαλοι επιλέγουν εργασίες για την Ολυμπιάδα. Υπάρχουν πολλές εργασίες για να διαλέξετε. Για κάθε εργασία, ο καθένας από τους εκπαιδευτικούς εκφράζει τη γνώμη του: εύκολη (0) ή δύσκολη (1) εργασία. Μια εργασία περιλαμβάνεται στην εργασία της Ολυμπιάδας εάν τουλάχιστον δύο δάσκαλοι τη σημείωσαν ως δύσκολη, αλλά εάν και οι τρεις δάσκαλοι τη θεωρούν δύσκολη, τότε μια τέτοια εργασία δεν περιλαμβάνεται στην εργασία της Ολυμπιάδας ως πολύ δύσκολη. Δημιουργήστε ένα λογικό διάγραμμα μιας συσκευής που θα βγάζει 1 εάν το πρόβλημα περιλαμβάνεται στην εργασία της Ολυμπιάδας και 0 εάν δεν περιλαμβάνεται.

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

Αναλύοντας την κατάσταση του προβλήματος, λαμβάνουμε τον ακόλουθο πίνακα αληθείας:

Κατασκευάζουμε SDNF. F(A, B, C) = ABC + ABC + ABC

Τώρα κατασκευάζουμε το λογικό κύκλωμα αυτής της συνάρτησης.

B & 1 F(A,B,C)

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

Έτσι, έχουμε τρεις διακόπτες με τους οποίους πρέπει να ανάβουμε και να σβήνουμε το φως. Κάθε διακόπτης έχει δύο καταστάσεις: υψηλή (0) και χαμηλή (1). Ας υποθέσουμε ότι εάν και οι τρεις διακόπτες βρίσκονται στη θέση 0, το φως στην είσοδο είναι σβηστό. Στη συνέχεια, όταν μετακινείτε οποιονδήποτε από τους τρεις διακόπτες στη θέση 1, το φως στην είσοδο πρέπει να ανάβει. Προφανώς, όταν μετακινήσετε οποιονδήποτε άλλο διακόπτη στη θέση 1, το φως στην είσοδο θα σβήσει. Εάν ο τρίτος διακόπτης μετακινηθεί στη θέση 1, το φως στην είσοδο θα ανάψει. Χτίζουμε έναν πίνακα αλήθειας.

Τότε, F(A, B, C) = ABC + ABC + ABC + ABC .

	3. Αλλαγή συνθήκης			τιμές λογικής συνάρτησης			F(A, B, C) = C →		Α+Β
	Η ταυτόχρονη αλλαγή των ορισμάτων Β και Γ ισούται με:
		A→(B C)						(Β Γ) → Α
					A(B C)
	4) (Β Γ) → Α				A→(B C)

Σημείωση. Για την επιτυχή επίλυση αυτού του προβλήματος, υπενθυμίζουμε τους ακόλουθους λογικούς τύπους:

x → y = x + y x y = x y + x y

x ↔ y = x y + x y

Μας δίνεται μια λογική συνάρτηση τριών μεταβλητών F 1 (A , B , C ) = C → A + B = C + A B .

Ας αλλάξουμε τις μεταβλητές B και C ταυτόχρονα: F 2 (A , B , C ) = F 1 (A , B , C ) = C + A B . Ας δημιουργήσουμε τους πίνακες αλήθειας αυτών των δύο συναρτήσεων:

Ας αναλύσουμε τον πίνακα που προκύπτει. Από τις οκτώ σειρές του πίνακα, μόνο στις δύο (2η και 3η) η συνάρτηση δεν αλλάζει την τιμή της. Σημειώστε ότι σε αυτές τις γραμμές η μεταβλητή Α δεν αντιστρέφει την τιμή της, ενώ οι μεταβλητές Β και Γ κάνουν.

Κατασκευάζουμε συναρτήσεις SKNF σύμφωνα με αυτές τις γραμμές:

F3 (A, B, C) = (A + B + C) (A + B C) = A + AB + AC + AB + BC + AC + B C = .

A + (B ↔ C) = A + B C = (B C) → A

Επομένως, η απαιτούμενη απάντηση είναι 4.

4. Συνθήκη για την αλλαγή της τιμής μιας λογικής συνάρτησης F (A , B , C ) = C + AB ενώ η αλλαγή των ορισμάτων A και B είναι ίση με:

1) C + (A B)

C + (A B)

ΤΑΞΙ)

4) Γ(Α Β)

C → (A B)

F 1 (A, B, C) =

C+AB

F 2 (A, B, C) = F 1 (

Γ)=Α

Χτίζουμε έναν πίνακα αλήθειας.

Ας αναλύσουμε τον πίνακα που προκύπτει. Από τις οκτώ σειρές του πίνακα, μόνο σε δύο (1η και 7η) η συνάρτηση αλλάζει την τιμή της. Σημειώστε ότι σε αυτές τις γραμμές, η μεταβλητή C δεν αλλάζει την τιμή της, ενώ οι μεταβλητές A και B αλλάζουν.

Δημιουργούμε συναρτήσεις SDNF σύμφωνα με αυτές τις γραμμές:

F3 (A, B, C) = A B C + A B C = C(A B + A B) = C(A ↔ B) = C + (A B)

Επομένως, η απαιτούμενη απάντηση είναι 2.

βιβλιογραφικές αναφορές

1. Shapiro S.I. Επίλυση προβλημάτων λογικής και παιχνιδιού(λογικές και ψυχολογικές μελέτες). - Μ.: Ραδιόφωνο και επικοινωνία, 1984. - 152 σελ.

2. Sholomov L.A. Βασικές αρχές της θεωρίας της διακριτής λογικής και των υπολογιστικών συσκευών. – Μ.: Επιστήμη. Ch. εκδ. φυσικός - χαλάκι. λιτ., 1980. - 400 σελ.

3. Pukhalsky G.I., Novoseltseva T.Ya. Σχεδιασμός διακριτών συσκευών σε ολοκληρωμένα κυκλώματα.: Εγχειρίδιο. - M .: Ραδιόφωνο και επικοινωνία, 1990.

Η χρήση των εξισώσεων είναι ευρέως διαδεδομένη στη ζωή μας. Χρησιμοποιούνται σε πολλούς υπολογισμούς, κατασκευές κατασκευών ακόμα και σε αθλήματα. Οι εξισώσεις χρησιμοποιήθηκαν από τον άνθρωπο από την αρχαιότητα και από τότε η χρήση τους έχει αυξηθεί. Στα μαθηματικά, υπάρχουν ορισμένες εργασίες που είναι αφιερωμένες στη λογική των προτάσεων. Για να λύσετε αυτό το είδος εξίσωσης, πρέπει να έχετε μια ορισμένη ποσότητα γνώσης: γνώση των νόμων της προτασιακής λογικής, γνώση των πινάκων αλήθειας λογικών συναρτήσεων 1 ή 2 μεταβλητών, μέθοδοι μετατροπής λογικών εκφράσεων. Επιπλέον, πρέπει να γνωρίζετε τις ακόλουθες ιδιότητες των λογικών πράξεων: συνδέσμους, διαχωρισμούς, αντιστροφές, συνέπειες και ισοδυναμίες.

Οποιαδήποτε λογική συνάρτηση από \ μεταβλητές - \ μπορεί να καθοριστεί από έναν πίνακα αλήθειας.

Ας λύσουμε μερικές λογικές εξισώσεις:

\[\rightharpoondown X1\vee X2=1 \]

\[\rightharpoondown X2\vee X3=1\]

\[\rightharpoondown X3\vee X4=1 \]

\[\rightharpoondown X9\vee X10=1\]

Ας ξεκινήσουμε τη λύση με το \[X1\] και ας προσδιορίσουμε ποιες τιμές μπορεί να πάρει αυτή η μεταβλητή: 0 και 1. Στη συνέχεια, εξετάστε καθεμία από τις παραπάνω τιμές και δείτε τι \[X2.\] μπορεί σε αυτή την περίπτωση

Όπως φαίνεται από τον πίνακα, η λογική μας εξίσωση έχει 11 λύσεις.

Πού μπορώ να λύσω μια λογική εξίσωση στο διαδίκτυο;

Μπορείτε να λύσετε την εξίσωση στον ιστότοπο https:// site μας. Ο δωρεάν διαδικτυακός λύτης θα λύσει την εξίσωση online οποιαδήποτεπολυπλοκότητα σε δευτερόλεπτα. Το μόνο που έχετε να κάνετε είναι απλώς να εισαγάγετε τα δεδομένα σας στο πρόγραμμα επίλυσης. Μπορείτε επίσης να παρακολουθήσετε τις οδηγίες βίντεο και να μάθετε πώς να λύσετε την εξίσωση στον ιστότοπό μας. Και αν έχετε οποιεσδήποτε ερωτήσεις, μπορείτε να τις ρωτήσετε στην ομάδα Vkontakte http://vk.com/pocketteacher. Γίνετε μέλος της ομάδας μας, είμαστε πάντα στην ευχάριστη θέση να σας βοηθήσουμε.