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

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

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

Τέλεια διαχωριστική κανονική μορφή (PDNF)

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

Παραδείγματα: y, ¬ y, x 1 ∧ ¬ x 2 ∧ x 3 ∧ x 4

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

Το DNF γράφεται με την ακόλουθη μορφή: F 1 ∨ F 2 ∨ ... ∨ F n , όπου F i είναι ο στοιχειώδης σύνδεσμος

Παραδείγματα: ¬ x 1 ∧ x 2 ∨ x 1 ∧ ¬ x 2 ∨ x 1 ∧ ¬ x 2 ∧ x 3 , ¬ y 1 ∨ y 1 ∧ y 2 ∨ ¬ y 2

Ορισμός. Ένας λογικός τύπος σε k μεταβλητές ονομάζεται τέλεια διαχωριστική κανονική μορφή (PDNF) εάν:
1) ο τύπος είναι ένας DNF, στον οποίο κάθε στοιχειώδης σύνδεσμος είναι ένας σύνδεσμος k μεταβλητών x 1, x 2, ..., x k, και στην i-η θέση αυτού του συνδέσμου υπάρχει είτε μια μεταβλητή x i είτε η άρνησή της ;
2) όλοι οι στοιχειώδεις σύνδεσμοι σε ένα τέτοιο DNF είναι ξεχωριστοί ανά ζεύγη.

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

Τέλεια συνδετική κανονική μορφή (PCNF)

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

Παραδείγματα: ¬ x 3, x 1 ∨ x 2, x 1 ∨ x 2 ∨ ¬ x 3

Ορισμός. Ένας τύπος ονομάζεται συνδετική κανονική μορφή (CNF) εάν είναι σύνδεσμος μη επαναλαμβανόμενων στοιχειωδών διαχωρισμών.

Το CNF γράφεται με την ακόλουθη μορφή: F 1 ∧ F 2 ∧ ... ∧ F n , όπου το F i είναι μια στοιχειώδης διάσταση

Παραδείγματα: (x 1 ∨ ¬ x 2) ∧ x 3, (x 1 ∨ x 2) ∧ (¬ x 1 ∨ x 2 ∨ x 3) ∧ (x 1 ∨ ¬ x 2 ∨ ¬ x 3)

Ορισμός. Ένας λογικός τύπος σε k μεταβλητές ονομάζεται τέλεια συνεκτική κανονική μορφή (CPNF) εάν:
1) ο τύπος είναι CNF, στον οποίο κάθε στοιχειώδης διάζευξη είναι μια διάσταση k μεταβλητών x 1, x 2, ..., x k, και στην i-η θέση αυτής της διάζευξης υπάρχει είτε μια μεταβλητή x i είτε η άρνησή της.
2) όλοι οι στοιχειώδεις διαχωρισμοί σε ένα τέτοιο CNF είναι χωριστές ανά ζεύγη.

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

σημειώσε ότι οποιαδήποτε λογική συνάρτηση που δεν είναι πανομοιότυπη ίση με 0 ή 1 μπορεί να αναπαρασταθεί ως SDNF ή SKNF.

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

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

Αλγόριθμος για την κατασκευή SCNF με χρήση πίνακα αληθείας

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

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

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

Επειδή στις περισσότερες σειρές του πίνακα αλήθειας η τιμή της συνάρτησης είναι 1, τότε θα κατασκευάσουμε το SCNF. Ως αποτέλεσμα, λαμβάνουμε τον ακόλουθο λογικό τύπο:
F = (¬ x ∨ y ∨ z) ∧ (¬ x ∨ y ∨ ¬ z)

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

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

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

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

μια φορά.

Διαζευκτική κανονική μορφή(DNF) είναι ένας τύπος που έχει τη μορφή διαχωρισμού στοιχειωδών συνδέσμων.

Στοιχειώδεις διαχωρισμοί (διασπάται)ονομάζονται διαχωρισμοί μεταβλητών με ή χωρίς αρνήσεις.

Συνδετική κανονική μορφή(CNF) είναι ένας τύπος που έχει τη μορφή ενός συνδέσμου στοιχειωδών διαχωρισμών.

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

Αλγόριθμος για την κατασκευή DNF:

1. Μεταβείτε στις πράξεις Boolean χρησιμοποιώντας ισοδύναμους τύπους μετασχηματισμού.

2. Μεταβείτε σε τύπους με κοντινές αρνήσεις, δηλαδή σε έναν τύπο στον οποίο οι αρνήσεις δεν βρίσκονται πάνω από τις μεταβλητές - εφαρμόστε τους νόμους του De Morgan.

3. Ανοίξτε τις αγκύλες - εφαρμόστε τους νόμους της κατανομής.

4. Πάρτε επαναλαμβανόμενους όρους μία φορά τη φορά - ο νόμος της αδυναμίας.

5. Εφαρμόστε τους νόμους της απορρόφησης και της μισής απορρόφησης.

Παράδειγμα 6.Βρείτε τύπους DNF: .

Στην άλγεβρα Boole είναι αλήθεια αρχή της δυαδικότητας. Είναι ως εξής.

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

Παράδειγμα 7.Βρείτε τη συνάρτηση dual to .

Από τις στοιχειώδεις συναρτήσεις της άλγεβρας της λογικής, το 1 είναι διπλό προς το 0 και αντίστροφα, το x είναι διπλό προς το x, το διπλό προς το , το διπλό και το αντίστροφο.

Αν στον τύπο F 1 που αντιπροσωπεύει τη συνάρτηση αντικαθιστούμε όλους τους συνδέσμους

σε διάζευξη, διάζευξη σε σύνδεσμο, 1 σε 0, 0 σε 1, τότε λαμβάνουμε τον τύπο F *, που αντιπροσωπεύει τη συνάρτηση * διπλή σε .

Η συνδετική κανονική μορφή (CNF) είναι μια διπλή έννοια για το DNF, επομένως μπορεί να κατασκευαστεί εύκολα σύμφωνα με το ακόλουθο σχήμα:

Παράδειγμα 8.Βρείτε τον τύπο CNF: .

Χρησιμοποιώντας το αποτέλεσμα του Παραδείγματος 6, έχουμε

Τέλειες διαζευκτικές και τέλειοι συνδετικοί κανονικοί τύποι.Σε καθέναν από τους τύπους κανονικών μορφών (διαζευκτική και συνεκτική), μπορεί κανείς να διακρίνει μια κατηγορία τέλειων μορφών SDNF και SCNF.

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

Οποιοδήποτε DNF μπορεί να αναχθεί σε SDNF διαχωρίζοντας συνδέσμους που δεν περιέχουν όλες τις μεταβλητές, π.χ. προσθέτοντας για τη μεταβλητή που λείπει το x i πολλαπλασιάζεται χρησιμοποιώντας τον κατανεμητικό νόμο

Παράδειγμα 9.Βρείτε το SDNF για το DNF του Παραδείγματος 6

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

Οποιοδήποτε CNF μπορεί να αναχθεί σε SCNF προσθέτοντας έναν όρο σύνδεσης που δεν περιέχει καμία μεταβλητή X i από τον σύνδεσμο και εφαρμόζοντας τον νόμο διανομής

Παράδειγμα 10.Φέρτε το KNF στο SKNF:

Για την κατασκευή του SCNF, μπορείτε να χρησιμοποιήσετε το διάγραμμα

Παράδειγμα 11.Βρείτε το SCNF για τον τύπο του παραδείγματος 6.

Κάθε λειτουργία έχει ένα SDNF και, επιπλέον, ένα μοναδικό. Κάθε συνάρτηση έχει ένα SCNF και, επιπλέον, ένα μοναδικό.

Επειδή Τα SDNF και SKNF ορίζονται μοναδικά από τύπους και μπορούν να κατασκευαστούν χρησιμοποιώντας τον πίνακα αλήθειας του τύπου.

Για να δημιουργήσετε ένα SDNF, είναι απαραίτητο να επιλέξετε τις σειρές στις οποίες το F παίρνει την τιμή 1 και να γράψετε τέλειους στοιχειώδεις συνδέσμους για αυτές. Εάν η τιμή μιας μεταβλητής στην επιθυμητή γραμμή του πίνακα αληθείας είναι ίση με ένα, τότε σε τέλειο συνδυασμό λαμβάνεται χωρίς άρνηση, αν μηδέν, τότε με άρνηση. Στη συνέχεια, οι τέλειοι σύνδεσμοι (ο αριθμός τους είναι ίσος με τον αριθμό των μονάδων του πίνακα) συνδέονται με σημεία διαχωρισμού.

Για να κατασκευάσετε ένα SCNF χρησιμοποιώντας έναν πίνακα αλήθειας, είναι απαραίτητο να επιλέξετε τις σειρές σε αυτό όπου F = 0, και να σημειώσετε τέλειους στοιχειώδεις διαχωρισμούς και, στη συνέχεια, να τις συνδέσετε με σημεία σύνδεσης. Αν στην απαιτούμενη σειρά του πίνακα αληθείας (F=0) η τιμή της μεταβλητής αντιστοιχεί στο μηδέν, τότε στην τέλεια πρόταση λαμβάνεται χωρίς άρνηση, αν είναι ένα, τότε με άρνηση.

Παράδειγμα 12.Βρείτε τα SDNF και SCNF χρησιμοποιώντας τον πίνακα αλήθειας για τον τύπο του παραδείγματος 6.

Ο Πίνακας 14 δείχνει μόνο την τελική τιμή F=10101101. Θα πρέπει να επαληθεύσετε μόνοι σας την εγκυρότητα αυτής της δήλωσης κατασκευάζοντας έναν λεπτομερή πίνακα αλήθειας.

Πίνακας 14

Κανονικές μορφές λογικών συναρτήσεων Η αναπαράσταση μιας Boolean συνάρτησης με τη μορφή διαχωρισμού συνδετικών όρων των συστατικών της μονάδας Ki 2.7 ονομάζεται διαζευκτική κανονική μορφή του DNF αυτής της συνάρτησης. περιέχει ακριβώς μία από όλες τις λογικές μεταβλητές που λαμβάνονται με ή χωρίς αρνήσεις, τότε αυτή η μορφή αναπαράστασης μιας συνάρτησης ονομάζεται τέλεια διαχωριστική κανονική μορφή SDNF αυτής της συνάρτησης. Όπως μπορείτε να δείτε, όταν συνθέτετε μια συνάρτηση SDNF, πρέπει να δημιουργήσετε έναν διαχωρισμό όλων των λεπτομέτρων για τους οποίους η συνάρτηση παίρνει την τιμή 1.

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

Διάλεξη 1.χχ

Κανονικές μορφές λογικών συναρτήσεων

Αναπαράσταση μιας Boolean συνάρτησης με τη μορφή διαχωρισμού συνδετικών όρων (συστατικό μονάδας) K i

, (2.7)

που ονομάζεται διαζευκτική κανονική μορφή(DNF) αυτής της συνάρτησης.

Αν όλοι οι συνδετικοί όροι στο DNF είναι minterms , δηλαδή περιέχει ακριβώς μία από όλες τις λογικές μεταβλητές, που λαμβάνονται με ή χωρίς αρνήσεις, τότε αυτή η μορφή αναπαράστασης συνάρτησης ονομάζεταιτέλεια διαχωριστική κανονική μορφή(SDNF ) αυτή τη λειτουργία. Ονομάζεται SDNFτέλειος , επειδή κάθε όρος στον διαχωρισμό περιλαμβάνει όλες τις μεταβλητές.διαζευκτικός , επειδή η κύρια πράξη στον τύπο είναι η διάζευξη. Εννοια "κανονικό σχήμα” σημαίνει έναν ξεκάθαρο τρόπο για να γράψετε έναν τύπο που υλοποιεί μια δεδομένη συνάρτηση.

Λαμβάνοντας υπόψη τα παραπάνω, από το Θεώρημα 2.1 προκύπτει το ακόλουθο θεώρημα.

Θεώρημα 2. Οποιαδήποτε συνάρτηση Boolean(όχι πανομοιότυπα 0) μπορεί να παρουσιαστεί σε SDNF, .

Παράδειγμα 3. Ας έχουμε μια συνάρτηση που δίνεται στον πίνακα f (x 1, x 2, x 3) (Πίνακας 10).

Πίνακας 10

Με βάση τον τύπο (2.6) παίρνουμε:

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

Αναπαράσταση μιας Boolean συνάρτησης με τη μορφή ενός συνδέσμου διαζευκτικών όρων (μηδενικό συστατικό) D i

, (2.8)

που ονομάζεται συνδετική κανονική μορφή(CNF) αυτής της συνάρτησης.

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

Θεώρημα 3. Οποιαδήποτε συνάρτηση Boolean(δεν είναι πανομοιότυπο με 1) μπορεί να υποβληθεί στην SKNF, και μια τέτοια αναπαράσταση είναι η μοναδική.

Η απόδειξη του θεωρήματος μπορεί να πραγματοποιηθεί παρόμοια με την απόδειξη του Θεωρήματος 2.1 με βάση το ακόλουθο λήμμα Shannon για τη συνεκτική αποσύνθεση.

Το Λήμμα του Σάνον . Οποιαδήποτε συνάρτηση Boolean f (x 1, x 2, …, x m) από m οι μεταβλητές μπορούν να αναπαρασταθούν έτσι:

. (2.9)

Πρέπει να σημειωθεί ότι και οι δύο μορφές αναπαράστασης μιας λογικής συνάρτησης (DNF και CNF) είναι θεωρητικά ίσες ως προς τις δυνατότητές τους: οποιοσδήποτε λογικός τύπος μπορεί να αναπαρασταθεί τόσο σε DNF (εκτός από το ίδιο μηδέν) όσο και σε CNF (εκτός από τον ίδιο ). Ανάλογα με την κατάσταση, η αναπαράσταση μιας συνάρτησης με τη μία ή την άλλη μορφή μπορεί να είναι μικρότερη.

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

Παράδειγμα 4. Για τη συνάρτηση f (x 1 , x 2 , x 3 ), δίνεται από τον πίνακα. 10, γράψτε το στο SKNF.

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

Θα πρέπει να σημειωθεί ότι είναι αδύνατη η απευθείας μετάβαση από το SDNF μιας συνάρτησης στο SCNF της ή το αντίστροφο. Όταν επιχειρείτε τέτοιους μετασχηματισμούς, τα αποτελέσματα είναι συναρτήσεις που είναι αντίθετες από τις επιθυμητές. Οι εκφράσεις για τις συναρτήσεις SDNF και SCNF μπορούν να ληφθούν απευθείας μόνο από τον πίνακα αληθείας.

Παράδειγμα 5. Για τη συνάρτηση f (x 1 , x 2 , x 3 ), δίνεται από τον πίνακα. 10, προσπαθήστε να αλλάξετε από SDNF σε SKNF.

Χρησιμοποιώντας το αποτέλεσμα του παραδείγματος 2.3 παίρνουμε:

Όπως μπορείτε να δείτε, κάτω από τη γενική αντιστροφή λάβαμε το SCNF μιας λογικής συνάρτησης, που είναι το αντίστροφο της συνάρτησης που ελήφθη στο παράδειγμα 2.4:

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

1. Χρησιμοποιώντας τις ιδιότητες των πράξεων (βλ. Πίνακα 9) ταυτότητα (), άθροισμα modulo 2 (), συνεπαγωγή (), προχωράμε στις πράξεις ΚΑΙ, Ή, ΟΧΙ (στη βάση Boolean).

2. Χρησιμοποιώντας τις ιδιότητες της άρνησης και τους νόμους του De Morgan (βλ. Πίνακας 9), διασφαλίζουμε ότι οι πράξεις άρνησης εφαρμόζονται μόνο σε μεμονωμένες μεταβλητές και όχι σε ολόκληρες εκφράσεις.

3. Χρησιμοποιώντας τις ιδιότητες των λογικών πράξεων AND και OR (βλ. Πίνακα 9), παίρνουμε την κανονική μορφή (DNF ή CNF).

4. Αν χρειαστεί, προχωρήστε σε τέλειες φόρμες (SDNF ή SKNF). Για παράδειγμα, για να αποκτήσετε SCNF πρέπει συχνά να χρησιμοποιήσετε την ιδιότητα: .

Παράδειγμα 6. Μετατρέψτε μια λογική συνάρτηση σε SKNF

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

Χρησιμοποιώντας την ιδιότητα απορρόφησης, παίρνουμε:

Έτσι, λάβαμε τη συνάρτηση CNF f (x 1 , x 2 , x 3 ). Για να αποκτήσετε το SCNF του, πρέπει να επαναλάβετε κάθε διαχωρισμό στην οποία λείπει οποιαδήποτε μεταβλητή, δύο φορές με αυτήν τη μεταβλητή και με την άρνησή της:

2.2.6. Ελαχιστοποίηση Λογικών Συναρτήσεων

Εφόσον η ίδια λογική συνάρτηση μπορεί να αναπαρασταθεί ωςη προσωπικές φόρμουλες και στη συνέχεια βρίσκοντας την απλούστερη μορφή R Το mule που ορίζει μια Boolean συνάρτηση, απλοποιεί το λογικό κύκλωμα που υλοποιεί τη Boolean συνάρτησηστο tion. Ελάχιστη μορφή lΟ λογική λειτουργίασε κάποια βάση μπορούμε να θεωρήσουμε ένα που περιέχει τον ελάχιστο αριθμό υπερθέσεων διασκέδασηςΠρος την θέσεις της βάσης, επιτρέποντας παρενθέσεις. Ωστόσο, είναι δύσκολο να οικοδομήσουμε ένα αποτελεσματικόμεγάλο αλγόριθμος για μια τέτοια ελαχιστοποίηση για να ληφθεί η ελάχιστη παρένθεση r εμείς.

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

Η μέθοδος του Κουάιν

Η συνάρτηση που πρόκειται να ελαχιστοποιηθεί αναπαρίσταται στο SDNF και όλες οι πιθανές ατελείς λειτουργίες κόλλησης εφαρμόζονται σε αυτό

, (2.10)

και μετά απορρόφηση

, (2.11)

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

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

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

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

Μέθοδος χάρτη Karnaugh

Η μέθοδος των χαρτών Carnot (πίνακες) είναι ένας πιο οπτικός, λιγότερο απαιτητικός και αξιόπιστος τρόπος για την ελαχιστοποίηση των λογικών συναρτήσεων, αλλά η χρήση της περιορίζεται πρακτικά σε συναρτήσεις 3-4 μεταβλητών, το πολύ 5-6 μεταβλητών.

Χάρτης Carnot Αυτή είναι μια δισδιάστατη μορφή πίνακα αναπαράστασης του πίνακα αλήθειας μιας συνάρτησης Boole, η οποία σας επιτρέπει να βρείτε εύκολα τα ελάχιστα DNF λογικών συναρτήσεων σε μια γραφική οπτική μορφή. Κάθε κελί του πίνακα συσχετίζεται με το ελάχιστο όριο SDNF της συνάρτησης που ελαχιστοποιείται και με τέτοιο τρόπο ώστε οποιοιδήποτε άξονες συμμετρίας του πίνακα να αντιστοιχούν σε ζώνες που είναι αμοιβαία αντίστροφες σε σχέση με κάποια μεταβλητή. Αυτή η διάταξη των κελιών στον πίνακα καθιστά εύκολο τον προσδιορισμό των όρων προσκόλλησης του SDNF (που διαφέρουν στο πρόσημο αντιστροφής μιας μόνο μεταβλητής): βρίσκονται συμμετρικά στον πίνακα.

Πίνακες αλήθειας και χάρτες Carnaugh για τις συναρτήσεις AND και OR δύο λωρίδωνμι Οι μεταβλητές παρουσιάζονται στο Σχ. 8. Σε κάθε κελί του χάρτη γράφεται μια τιμήΕΝΑ Η τιμή μιας συνάρτησης στο σύνολο τιμών ορισμάτων που αντιστοιχούν σε αυτό το κελίΝ σύντροφε

Α) ΚΑΙ β) Ή

Ρύζι. 8. Παράδειγμα χαρτών Karnaugh για συναρτήσεις δύο μεταβλητών

Στον χάρτη Karnaugh υπάρχει μόνο ένα 1 για τη συνάρτηση And, επομένως δεν μπορεί να κολληθεί σε τίποτα. Η έκφραση για την ελάχιστη συνάρτηση θα περιέχει μόνο τον όρο που αντιστοιχεί σε αυτό το 1:

f = xy.

Στον χάρτη Carnot για τη συνάρτηση OR υπάρχουν ήδη τρία 1 και μπορείτε να φτιάξετε δύο ζεύγη κόλλησης, με το 1 να αντιστοιχεί στον όρο xy , χρησιμοποιείται δύο φορές. Στην έκφραση για την ελάχιστη συνάρτηση, πρέπει να γράψετε τους όρους για τα ζεύγη που είναι κολλημένα μεταξύ τους, αφήνοντας σε αυτά όλες τις μεταβλητές που δεν αλλάζουν για αυτό το ζεύγος και αφαιρώντας τις μεταβλητές που αλλάζουν την τιμή τους. Για οριζόντια κόλληση παίρνουμεΧ , και για κάθετη y , ως αποτέλεσμα παίρνουμε την έκφραση

f = x + y.

Στο Σχ. Το 9 δείχνει τους πίνακες αλήθειας δύο συναρτήσεων τριών μεταβλητών (ΕΝΑ ) και τους χάρτες Carnot τους (β και γ). Συνάρτηση f 2 διαφέρει από το πρώτο στο ότι δεν ορίζεται σε τρία σύνολα μεταβλητών (στον πίνακα αυτό υποδεικνύεται με μια παύλα).

Κατά τον καθορισμό της ελάχιστης συνάρτησης DNF, χρησιμοποιούνται οι ακόλουθοι κανόνες. Όλα τα κελιά που περιέχουν 1 συνδυάζονται σε κλειστές ορθογώνιες περιοχές που ονομάζονται k-κύβοι, όπου k = log 2 K, K ποσότητα 1 σε ορθογώνιο εμβαδόν. Σε αυτήν την περίπτωση, κάθε περιοχή πρέπει να είναι ένα ορθογώνιο με τον αριθμό των κελιών 2 k, όπου k = 0, 1, 2, 3, …. Για k = Καλείται 1 ορθογώνιοΤο ένα είναι κύβος και περιέχει 2 1 = 2 μονάδες. για k = 2 ορθογώνιο περιέχει 2 2 = 4 μονάδες και καλείταιδύο κύβους? για k = 3 περιοχή του 2 3 = 8 μονάδες καλούνταιτρικύβου ; κλπ. Μπορούν να ονομαστούν μονάδες που δεν μπορούν να συνδυαστούν σε ορθογώνιαμηδενικοί κύβοι , που περιέχουν μόνο μία μονάδα (2 0 = 1). Όπως φαίνεται, για ακόμηκ οι περιοχές μπορεί να έχουν τετράγωνο σχήμα (αλλά όχι απαραίτητα), και αν είναι περιττέςκ μόνο ορθογώνια.

Ρύζι. 9. Παράδειγμα χαρτών Karnaugh για συναρτήσεις τριών μεταβλητών

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

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

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

Για τη συνάρτηση σύμφωνα με τον χάρτη Karnaugh στο Σχ. 9,β βρίσκουμε

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

Μη καθορισμένες τιμές στον χάρτη στο Σχ. 9, V μπορεί να οριστεί περαιτέρω αντικαθιστώντας το με μηδέν ή ένα. Για αυτή τη συνάρτηση, είναι σαφές ότι είναι πιο κερδοφόρο να αντικατασταθούν και οι δύο απροσδιόριστες τιμές με 1. Σε αυτήν την περίπτωση, σχηματίζονται δύο περιοχές, οι οποίες είναι διαφορετικοί τύποι 2-κύβων. Τότε η έκφραση για την ελάχιστη συνάρτηση DNF θα είναι η εξής:

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

Οι χάρτες Carnaugh μπορούν να σχεδιαστούν με διαφορετικούς τρόπους (Εικ. 10).

α β

Ρύζι. 10. Διαφορετικοί τρόποι απεικόνισης χαρτών Carnaugh
για μια συνάρτηση 3 μεταβλητών

Αλλά οι πιο βολικές επιλογές για χάρτες Karnaugh για συναρτήσεις 2-4 μεταβλητών είναι αυτές που φαίνονται στο Σχ. 11 πίνακες, γιατί εμφανίζονται για κάθε κελίΕΝΑ Έχουμε όλες τις μεταβλητές σε άμεση ή αντίστροφη μορφή.

α β

Ρύζι. έντεκα. Η πιο βολική εικόνα των χαρτών Carnaugh
για τις λειτουργίες 3 (α) και 4 (β) μεταβλητές

Για συναρτήσεις των 5 και 6 μεταβλητών, η μέθοδος που φαίνεται στο Σχ. 10, V .

Ρύζι. 12. Εικόνα χάρτη Karnaugh για συνάρτηση 5 μεταβλητών

Ρύζι. 13. Εικόνα χάρτη Karnaugh για συνάρτηση 6 μεταβλητών

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

Η κανονική μορφή έρχεται σε δύο μορφές:

Συνδετική κανονική μορφή (CNF)-- συνδυασμός πολλών διαχωρισμών, για παράδειγμα, $\left(A\vee \overline(B)\vee C\right)\wedge \left(A\vee C\right)$;

διαζευκτική κανονική μορφή (DNF)-- διαχωρισμός πολλών συνδέσμων, για παράδειγμα, $\left(A\wedge \overline(B)\wedge C\right)\vee \left(B\wedge C\right)$.

SKNF

Τέλεια συνδετική κανονική μορφή (PCNF) είναι ένα CNF που πληροί τρεις προϋποθέσεις:

δεν περιέχει ταυτόσημους στοιχειώδεις διαχωρισμούς.

κανένας από τους διαχωρισμούς δεν περιέχει τις ίδιες μεταβλητές.

κάθε στοιχειώδης διαχωρισμός περιέχει κάθε μεταβλητή που περιλαμβάνεται σε ένα δεδομένο CNF.

Οποιοσδήποτε τύπος Boolean που δεν είναι πανομοιότυπος αληθής μπορεί να αναπαρασταθεί στο SKNF.

Κανόνες για την κατασκευή του SKNF χρησιμοποιώντας έναν πίνακα αλήθειας

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

SDNF

Τέλεια διαχωριστική κανονική μορφή (PDNF) είναι ένα DNF που πληροί τρεις προϋποθέσεις:

δεν περιέχει πανομοιότυπους στοιχειώδεις συνδέσμους.

Κανένας από τους συνδέσμους δεν περιέχει τις ίδιες μεταβλητές.

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

Οποιοσδήποτε τύπος Boolean που δεν είναι πανομοιότυπος ψευδής μπορεί να αναπαρασταθεί στο SDNF και με μοναδικό τρόπο.

Κανόνες για την κατασκευή του SDNF χρησιμοποιώντας έναν πίνακα αλήθειας

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

Παραδείγματα εύρεσης SCNF και SDNF

Παράδειγμα 1

Γράψτε μια λογική συνάρτηση χρησιμοποιώντας τον πίνακα αληθείας της:

Εικόνα 1.

Λύση:

Ας χρησιμοποιήσουμε τον κανόνα για την κατασκευή SDNF:

Σχήμα 2.

Λαμβάνουμε SDNF:

Ας χρησιμοποιήσουμε τον κανόνα για την κατασκευή του SCNF.