Υπάρχουν δύο κατευθύνσεις για ελαχιστοποίηση:

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

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

2. Μέθοδος Quine.

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

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

Για αυτό:

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

Αλγόριθμος μεθόδου Quine (βήματα):

• 1. Εύρεση των πρωταρχικών εμφυτευμάτων (οι αρχικοί όροι από το DNF είναι γραμμένοι σε μια στήλη και κολλημένοι από πάνω προς τα κάτω, τα μη επισημασμένα εμφυτεύματα μεταβαίνουν σε συναρτήσεις σε αυτό το βήμα).
• 2. Τακτοποίηση ετικετών πλεονασμού (συντάσσεται ένας πίνακας στον οποίο οι σειρές είναι οι κύριες εμπλοκές, οι στήλες είναι οι αρχικοί όροι, εάν κάποιος ελάχιστος όρος περιέχει μια κύρια εμπλοκή, τότε βάζουμε μια ετικέτα στη διασταύρωση της γραμμής και της στήλης) .
• 3. Εύρεση βασικών εμφυτευμάτων (αν υπάρχει μόνο μία ετικέτα σε οποιαδήποτε στήλη, τότε η κύρια εμπλοκή της αντίστοιχης σειράς είναι απαραίτητη).
• 4. Η σειρά που περιέχει το βασικό εμφύτευμα και οι αντίστοιχες στήλες διαγράφονται (εάν, ως αποτέλεσμα της διαγραφής των στηλών, εμφανίζονται σειρές από πρωτεύοντα εμφυτεύματα που δεν περιέχουν ετικέτες ή περιέχουν πανομοιότυπες ετικέτες στις σειρές, τότε αυτές οι κύριες εμπλοκές διαγράφονται έξω και στην τελευταία περίπτωση μένει ένας κατώτερος).
• 5. Επιλογή της ελάχιστης κάλυψης (από τον πίνακα που λήφθηκε στο βήμα 3, επιλέξτε ένα σύνολο πρωτογενών εμφυτευμάτων που περιλαμβάνει ετικέτες σε όλες τις στήλες με τουλάχιστον μία ετικέτα σε καθεμία· με πολλές πιθανές επιλογές, προτιμάται η κάλυψη με την ελάχιστη συνολικός αριθμός στοιχείων στα εμφυτεύματα που σχηματίζουν επίστρωση).
• 6. Το αποτέλεσμα γράφεται ως συνάρτηση.

Ας δοθεί η συνάρτηση:

Για ευκολία παρουσίασης, ας σημειώσουμε κάθε στοιχείο της μονάδας από τη συνάρτηση SDNF F με κάποιο δεκαδικό αριθμό (αυθαίρετα). Κάνουμε κόλληση. Το συστατικό 1 είναι κολλημένο μόνο με το συστατικό 2 (από τη μεταβλητή x3) και με το συστατικό 3 (από τη μεταβλητή x2) του συστατικού 2 με το συστατικό 4 κ.λπ. Ως αποτέλεσμα, παίρνουμε:

Σημειώστε ότι το αποτέλεσμα της κόλλησης είναι πάντα ένα στοιχειώδες προϊόν, το οποίο είναι το κοινό μέρος των συστατικών που κολλώνται.

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

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

Ο εμφυτευόμενος πίνακας έχει τη μορφή βλέπε πίνακα. 1.1

Πίνακας 1.1 Εμπλοκή μήτρα

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

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

Επομένως η συνάρτηση μοιάζει με:

3. Μέθοδος Quine-McCluskey.

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

• 1. Όλα τα στοιχεία μονάδας από το SDNF της Boolean συνάρτησης F γράφονται με τους δυαδικούς αριθμούς τους.
• 2. Όλοι οι αριθμοί χωρίζονται σε μη επικαλυπτόμενες ομάδες. Πρόσημο σχηματισμού της i-ης ομάδας: οι μονάδες i σε κάθε δυαδικό αριθμό αποτελούν συστατικά του ενός.
• 3. Η κόλληση πραγματοποιείται μόνο μεταξύ των αριθμών των γειτονικών ομάδων. Οι αριθμοί που είναι κολλημένοι μεταξύ τους επισημαίνονται με κάποιου είδους πρόσημο (διαγραφή, αστερίσκος κ.λπ.).
• 4. Γίνονται όλα τα είδη κολλήσεων, όπως στη μέθοδο Quine. Οι αριθμοί που δεν σημειώνονται μετά την κόλληση είναι απλοί εμβολιακοί.

Σχηματίζουμε ομάδες δυαδικών αριθμών. Σημάδι του σχηματισμού της i-ης ομάδας είναι οι μονάδες i στο δυαδικό αριθμό της συστατικής μονάδας (Πίνακας 1.2).

Πίνακας 1.2 Ομάδες δυαδικών αριθμών

Ας κολλήσουμε αριθμούς από γειτονικές ομάδες του πίνακα. 1.3 Μόνο αριθμοί που έχουν παύλες στις ίδιες θέσεις μπορούν να συγχωνευθούν. Ας σημειώσουμε τους αριθμούς που είναι κολλημένοι μεταξύ τους. Τα αποτελέσματα της κόλλησης θα τα εισάγουμε στον πίνακα. 1.4.

Πίνακας 1.4 Αποτελέσματα συγκόλλησης 2

Σύμφωνα με τον πίνακα 5. Καθορίζουμε το σύνολο των απλών εμφυτευμάτων - 0--1 και 111-, που αντιστοιχεί στο ελάχιστο DNF. Για να επαναφέρετε την κυριολεκτική μορφή ενός απλού εννοούμενου, αρκεί να γράψετε τα γινόμενα εκείνων των μεταβλητών που αντιστοιχούν στα υπόλοιπα δυαδικά ψηφία:

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

4. Μέθοδος διαγράμματος Veitch.

Η μέθοδος σας επιτρέπει να αποκτήσετε γρήγορα ελάχιστα DNF μιας Boolean συνάρτησης f ενός μικρού αριθμού μεταβλητών. Η μέθοδος βασίζεται στον καθορισμό συναρτήσεων Boole με διαγράμματα κάποιου ειδικού τύπου, που ονομάζονται διαγράμματα Veitch. Για μια Boolean συνάρτηση δύο μεταβλητών, το διάγραμμα Veitch μοιάζει με (Εικόνα 1).

Εικ.1.

Κάθε κελί στο διάγραμμα αντιστοιχεί σε ένα σύνολο μεταβλητών συνάρτησης Boole στον πίνακα αληθείας του. Στο (Εικ. 1) αυτή η αντιστοιχία εμφανίζεται ένα κελί στο διάγραμμα Veitch σημειώνεται με ένα εάν η συνάρτηση Boolean παίρνει μία τιμή στο αντίστοιχο σύνολο. Οι μηδενικές τιμές της συνάρτησης Boolean δεν ορίζονται στο διάγραμμα Veitch. Για μια Boolean συνάρτηση τριών μεταβλητών, το διάγραμμα Veitch μοιάζει με αυτό (Εικόνα 2).

Εικ.2.

Η προσθήκη του ίδιου πίνακα σε αυτόν δίνει ένα διάγραμμα για μια συνάρτηση 4 μεταβλητών (Εικ. 3).

Εικ.3.

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

5. Χάρτες Carnot.

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

Ας φτιάξουμε έναν πίνακα για τη μέθοδο του χάρτη Karnaugh (Πίνακας 1.6).

Πίνακας 1.6 Χάρτες Carnot

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

για το πρώτο - X 3 X 4;

για το δεύτερο - X 1 X 3;

για το τρίτο - X 2 X 3;

για το τέταρτο - X 1 X 2 X 4;

για το πέμπτο - X 1 X 2 X 4;

Ένα ελάχιστο DNF θα μοιάζει με αυτό:

6. Μέθοδος απροσδιόριστων συντελεστών.

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

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

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

Ας εξισώσουμε όλους τους συντελεστές με 0 σε εκείνες τις σειρές που αντιστοιχούν στο 0 στη στήλη του διανύσματος. Στη συνέχεια εξισώνουμε τους αντίστοιχους συντελεστές σε άλλες σειρές με 0. Μετά από αυτούς τους μετασχηματισμούς, το σύστημα θα πάρει την ακόλουθη μορφή (Εικ. 4):

Εικ.4.

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

Ας γράψουμε τώρα τους συνδέσμους που αντιστοιχούν σε συντελεστές ίσους με μονάδα. Θα λάβουμε το ελάχιστο DNF.

Άλγεβρες της λογικής

3.3.1. Ελαχιστοποίηση του FAL χρησιμοποιώντας τον πίνακα Carnot

Ο πίνακας Carnot είναι ένα είδος πίνακα αλήθειας FAL, ο οποίος χωρίζεται σε κελιά. Ο αριθμός των κελιών μήτρας είναι 2 n, Οπου n– αριθμός ορισμάτων FAL. Οι στήλες και οι σειρές ενός πίνακα ορίζονται από σύνολα ορισμάτων. Κάθε κελί του πίνακα αντιστοιχεί σε ένα συστατικό της μονάδας FAL (δυαδικός αριθμός). Ο δυαδικός αριθμός ενός κελιού αποτελείται από ένα σύνολο ορισμάτων σειρών και στηλών. Ο πίνακας Carnot για το FAL, ανάλογα με δύο ορίσματα, παρουσιάζεται με τη μορφή του πίνακα 3.3., από τρία ορίσματα στον πίνακα 3.4. και από τέσσερα ορίσματα πίνακα 3.5.

Πίνακας 3.3.

Πίνακας 3.5.

Χ 3 Χ 4 Χ 1 Χ 2
	0 0 0 0	0 0 0 1	0 0 1 1	0 0 1 0
	0 1 0 0	0 1 0 1	0 1 1 1	0 1 1 0
	1 1 0 0	1 1 0 1	1 1 1 1	1 1 1 0
	1 0 0 0	1 0 0 1	1 0 1 1	1 0 1 0

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

Η διαδικασία ελαχιστοποίησης του FAL χρησιμοποιώντας τον πίνακα Carnot βασίζεται στον νόμο της κόλλησης γειτονικών δυαδικών αριθμών. Μπορείτε να κολλήσετε δυαδικούς αριθμούς γειτονικών κελιών, αλλά συνιστάται να κολλήσετε σύνολα ορισμάτων που υποδεικνύουν τις σειρές και τις στήλες των πινάκων. Ας εξετάσουμε το ενδεχόμενο να κολλήσουμε τους δυαδικούς αριθμούς των κελιών της πρώτης στήλης του πίνακα (Πίνακας 3.5.).

Κελιά 0 και 4, δυαδικοί αριθμοί 0000 και 0100, αντίστοιχα, το αποτέλεσμα της κόλλησης είναι 0-00.

Κελιά 8 και 12, δυαδικοί αριθμοί 1000 και 1100, αποτέλεσμα 1-00. Τα εμφυτεύματα που προκύπτουν είναι κολλημένα μεταξύ τους, επειδή Η παύλα βρίσκεται στην ίδια θέση και οι εμπλεκόμενοι δυαδικοί αριθμοί είναι δίπλα, το τελικό αποτέλεσμα είναι - 00.

Κελιά 8 και 12

Έτσι, εάν όλοι οι δυαδικοί αριθμοί μιας στήλης είναι κολλημένοι μεταξύ τους, τότε αυτά τα bit που υποδεικνύουν τις σειρές εξαφανίζονται. Ομοίως, εάν όλοι οι δυαδικοί αριθμοί μιας σειράς είναι κολλημένοι μεταξύ τους, για παράδειγμα 4, 5, 7, 6, τότε όλα τα ψηφία που υποδεικνύουν τις στήλες εξαφανίζονται, δηλ. το αποτέλεσμα θα είναι το εξής 01- -.

Εάν οι δυαδικοί αριθμοί μόνο δύο κελιών είναι κολλημένοι μεταξύ τους, τότε τοποθετείται μια παύλα αντί αυτού του ψηφίου των δυαδικών αριθμών μιας γραμμής ή στήλης που θα αλλάξει όταν τα κελιά μετακινούνται από τη μια γραμμή στην άλλη (ή από τη μια στήλη στην άλλη). . Για παράδειγμα, οι αριθμοί των κελιών 5 και 13 είναι κολλημένοι μεταξύ τους, παίρνουμε το αποτέλεσμα -101 ή κελιά 7 και 6 το αποτέλεσμα είναι 011-.

Όταν κολλάτε δυαδικούς αριθμούς οκτώ γειτονικών κελιών, τρεις μεταβλητές εξαφανίζονται, για παράδειγμα, για τα κελιά 3, 7, 15, 11, 2, 6, 14, 10, οι μεταβλητές εξαφανίζονται Χ 1 , Χ 2 , Χ 3. Μεταβλητές Χ 1 , Χ 2 εξαφανίζονται επειδή όλα τα κελιά των στηλών είναι κολλημένα μεταξύ τους και Χ 3 γιατί οι δύο τελευταίες στήλες είναι κολλημένες μεταξύ τους.

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

Είναι γνωστό ότι για κάθε FAL υπάρχουν 2 σετ ορισμάτων n, Οπου n– ο αριθμός των ορισμάτων από τα οποία εξαρτάται μια συνάρτηση ή μια λογική έκφραση.

Τα σύνολα επιχειρημάτων χωρίζονται σε τρεις τύπους

1. Τα σύνολα ορισμάτων στα οποία η συνάρτηση είναι ίση με ένα λέγονται λειτουργικά.

2. Τα σύνολα ορισμάτων στα οποία η συνάρτηση είναι ίση με μηδέν ονομάζονται απαγορευμένα.

3. Τα σύνολα ορισμάτων για τα οποία μια συνάρτηση μπορεί να είναι ίση είτε με ένα είτε με μηδέν ονομάζονται αδιάφορα.

Εάν ένα δεδομένο FAL δεν έχει αδιάφορα σύνολα, τότε μπορεί να αναπαρασταθεί σε κυριολεκτική έκφραση με τη μορφή SDNF. Εάν υπάρχουν αδιάφορα σύνολα σε ένα δεδομένο FAL, η αναπαράστασή του μπορεί να έχει την ακόλουθη μορφή.

όπου είναι τα δεκαδικά ισοδύναμα των συνόλων εργασίας,

– δεκαδικά ισοδύναμα απαγορευμένων συνόλων.

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

Παράδειγμα 3.3. Ελαχιστοποιήστε το δεδομένο FAL με τη μορφή SDNF χρησιμοποιώντας τον πίνακα Carnot.

Επομένως, η συνάρτηση καθορίζεται μόνο από σύνολα εργασίας. Τα υπόλοιπα θα απαγορευθούν. Η συνάρτηση εξαρτάται μόνο από τρία ορίσματα. Κατασκευάζουμε έναν πίνακα Carnot και βάζουμε στα κελιά του εκείνα που αντιστοιχούν στα σύνολα εργασίας και βάζουμε μηδενικά στα υπόλοιπα κελιά.

Πίνακας 3.5.

Χ 2 Χ 3 Χ 1
	0

Για ελαχιστοποίηση, τα κελιά μήτρας που περιέχουν αυτά συνδυάζονται σε περιγράμματα. Το κύκλωμα μπορεί να περιλαμβάνει δύο κελιά, τέσσερα ή και τα οκτώ. Σε αυτό το παράδειγμα, το περίγραμμα περιλαμβάνει τέσσερα γειτονικά κελιά της ίδιας σειράς. Η εμπλοκή του δεδομένου περιγράμματος θα είναι 1 - -. Το αποτέλεσμα της ελαχιστοποίησης είναι το εξής, δηλ. υπήρξε μείωση της δεδομένης λειτουργίας στο SDNF κατά 11 γράμματα.

Παράδειγμα 3.4. Ελαχιστοποιήστε την έκφραση Boolean που δίνεται από τα λειτουργικά και απαγορευμένα σύνολα χρησιμοποιώντας τον πίνακα Carnot.

Κατασκευάζουμε έναν πίνακα Carnot για τέσσερις μεταβλητές και γεμίζουμε τα κελιά με μονάδες και μηδενικά, αντίστοιχα, για εργασιακά και απαγορευμένα σύνολα.

Πίνακας 3.6.

Χ 3 Χ 4 Χ 1 Χ 2	00
			(1)
	(1)		(1)

Όταν συνδυάζονται κελιά με μονάδες σε περιγράμματα, είναι επιθυμητό κάθε περίγραμμα να περιλαμβάνει τον μεγαλύτερο δυνατό αριθμό κελιών. Για να γίνει αυτό, χρησιμοποιούμε τα κελιά ορισμένων αδιάφορων συνόλων ως κελιά των συνόλων εργασίας, αντικαθιστώντας αυτά που βρίσκονται σε παρένθεση σε αυτά. Ως αποτέλεσμα, έχουμε τρία περιγράμματα που περιέχουν 4 κελιά το καθένα. Στον κώδικα γενικευμένου κυκλώματος, που περιλαμβάνει όλα τα κελιά μιας γραμμής, οι μεταβλητές εξαφανίζονται Χ 2 Χ 3 (10 - -). Στον κώδικα γενικευμένου κυκλώματος, που περιλαμβάνει όλα τα κελιά μιας στήλης, οι μεταβλητές εξαφανίζονται Χ 1 Χ 2 (- - 11) και για ένα περίγραμμα που περιέχει δύο κελιά δύο γραμμών, οι μεταβλητές εξαφανίζονται Χ 2 (όταν μετακινείστε από τη μια γραμμή στην άλλη σε περίγραμμα) και Χ 3 (όταν μετακινείστε από τη μια στήλη στην άλλη). Ως αποτέλεσμα, λαμβάνουμε το ελάχιστο DNF στην ακόλουθη μορφή

Πιθανές επιλογές για το συνδυασμό κελιών μήτρας Carnot σε περιγράμματα φαίνονται στην Εικόνα 3.4.

Χ 3 Χ 4 Χ 1 Χ 2

A = 0 - 0 -

Z = - 0 - 0

Ν

B = 1 - 1 -

Κ = - - - 1

Β = - - 0 0

L = - 1 - -

Г = 1 0 - -

Μ = - - - 0

D = - 0 0 1

H = - 0 - -

E = - 0 1 -

F = - 1 - 1

Ρύζι. 3.1. Πιθανές επιλογές για το συνδυασμό κελιών μήτρας Carnot σε περιγράμματα

3.3.2. Ελαχιστοποίηση συναρτήσεων λογικής άλγεβρας χρησιμοποιώντας έναν πίνακα πέντε μεταβλητών

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

Σε έναν πίνακα πέντε μεταβλητών (Πίνακας 3.7.), οι σειρές αντιστοιχούν σε σύνολα μεταβλητών Χ 1 Χ 2 Χ 3, και οι στήλες είναι σύνολα μεταβλητών Χ 4 Χ 5 . Κάθε κελί του πίνακα αντιστοιχεί σε έναν δυαδικό αριθμό πέντε bit. Τα κελιά του πίνακα (Πίνακας 3.7.) περιέχουν τα δεκαδικά ισοδύναμα των αντίστοιχων δυαδικών αριθμών.

Πίνακας 3.7.

Χ 4 Χ 5 Χ 1 Χ 2 Χ 3

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

Η ιδιαιτερότητα εδώ είναι ότι στις στήλες μιας μήτρας πέντε μεταβλητών, μπορείτε να συνδυάσετε τέσσερα κελιά μόνο σε περιγράμματα ή τέσσερα κελιά στην κορυφή ή τέσσερα κελιά στο κάτω μέρος ή τέσσερα κελιά στη μέση. Για παράδειγμα, για την τελευταία στήλη του πίνακα, τα περιγράμματα μπορεί να αποτελούνται από κελιά 2, 6, 14, 10 ή 26, 30, 22, 18 ή 14, 10, 26, 30.

Παράδειγμα 3.6. Χρησιμοποιήστε έναν πίνακα πέντε μεταβλητών για να ελαχιστοποιήσετε την ακόλουθη λογική έκφραση

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

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

Πίνακας 3.8.

Χ 4 Χ 5 Χ 1 Χ 2 Χ 3
	(1)	(1)	(1)
	(1)
	(1)	(1)
		(1)	(1)
	(1)		(1)
			(1)
	(1)		(1)

Παίρνουμε το ελάχιστο DNF

Ερωτήσεις ελέγχου

1. Ορίστε το συντομευμένο DNF.

2. Τι είναι ένα αδιέξοδο DNF;

3. Πώς επιλέγεται το ελάχιστο DNF από αδιέξοδα DNF;

4. Σε τι χρησιμεύει ο εμφυτευόμενος πίνακας και πώς κατασκευάζεται;

5. Εξηγήστε την αναλυτική μέθοδο για την ελαχιστοποίηση του Quine-McClassky FAL.

6. Πώς κατασκευάζεται ο πίνακας Carnot για τρεις και τέσσερις μεταβλητές;

7. Ελαχιστοποιήστε αναλυτικά τις ακόλουθες λογικές εκφράσεις που δίνονται μόνο από σύνολα εργασίας

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

Σχετική πληροφορία.

Εργαστείτε πάνω στο θέμα

ΜΕΘΟΔΟΙ ΕΛΑΧΙΣΤΟΠΟΙΗΣΗΣ
ΛΟΓΙΚΕΣ ΛΕΙΤΟΥΡΓΙΕΣ

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

Περιεχόμενο

Εισαγωγή

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

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

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

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

Από αυτή την άποψη, η ελαχιστοποίηση των λογικών συναρτήσεων είναι ιδιαίτερα σημαντική.

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

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

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

Καθήκονταέρευνα:

μελέτη των βασικών στοιχείων της μαθηματικής λογικής.

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

επιλέξτε εργασίες για ανεξάρτητη εργασία.

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

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

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

Η πρώτη ενότητα συζητά τα λογικά θεμέλια της λειτουργίας ενός υπολογιστή.

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

Συμπερασματικά, συνοψίζονται τα γενικά αποτελέσματα της μελέτης.

Λογική βάση λειτουργίας υπολογιστή

Στοιχεία μαθηματικής λογικής

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

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

Η λογική (από το αρχαίο ελληνικό logos, που σημαίνει «λέξη, σκέψη, έννοια, συλλογισμός, νόμος») είναι μια αρχαία επιστήμη που μελετά την ορθότητα των κρίσεων, των συλλογισμών και των στοιχείων.

Η μαθηματική λογική είναι μια μαθηματική επιστήμη που μελετά την τεχνική της απόδειξης.

Ο ιδρυτής της μαθηματικής λογικής είναι ο μεγάλος Γερμανός μαθηματικός Gottfried Wilhelm Leibniz (1646 – 1716). Έθεσε την ιδέα της χρήσης μαθηματικών συμβολισμών και της κατασκευής λογικών λογισμών στη λογική, έθεσε το πρόβλημα της λογικής αιτιολόγησης των μαθηματικών και έπαιξε σημαντικό ρόλο στην ιστορία της δημιουργίας ηλεκτρονικών υπολογιστών: πρότεινε τη χρήση του δυαδικού αριθμού σύστημα για τους σκοπούς των υπολογιστικών μαθηματικών. Στα θεμέλια που έθεσε ο Leibniz, ο Ιρλανδός μαθηματικός George Boole έχτισε το κτίριο μιας νέας επιστήμης - της μαθηματικής λογικής - η οποία, σε αντίθεση με τη συνηθισμένη άλγεβρα, δεν λειτουργεί με αριθμούς, αλλά με δηλώσεις. Προς τιμήν του D. Boole, οι λογικές μεταβλητές στη γλώσσα προγραμματισμού Pascal ονομάστηκαν στη συνέχεια Boolean.

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

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

Διάφορες λογικές εκφράσεις (δηλώσεις) μπορούν να λάβουν μόνο δύο έννοιες: «αληθές» ή «λάθος». Κάθε λογιστική μεταβλητή μπορεί να πάρει μόνο μία τιμή. Υπάρχουν διάφορες επιλογές για τον προσδιορισμό της αλήθειας και του ψεύδους:

Αληθής

ΚΑΙ

Αληθής

Τ

1

Ψέμα

μεγάλο

Ψευδής

φά

0

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

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

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

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

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

1

0

0

1

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

1

1

1

1

0

0

0

1

0

0

0

0

Ο ορισμός του συνδέσμου δύο δηλώσεων επεκτείνεται φυσικά σε οποιονδήποτε πεπερασμένο αριθμό συστατικών: σύνδεσμος ΕΝΑ 1 &ΕΝΑ 2 &ΕΝΑ 3 &...& ΕΝΑ Ναληθές αν και μόνο αν όλες οι προτάσεις είναι αληθείς ΕΝΑ 1 , ΕΝΑ 2 , ΕΝΑ 3 , ...ΕΝΑ Ν(και, επομένως, ψευδής όταν τουλάχιστον μία από αυτές τις δηλώσεις είναι ψευδής).

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

1

1

1

1

0

1

0

1

1

0

0

0

Ο ορισμός του διαχωρισμού δύο δηλώσεων επεκτείνεται φυσικά σε οποιονδήποτε πεπερασμένο αριθμό συνιστωσών: διαχωρισμόςΕΝΑ 1 ΕΝΑ 2 ΕΝΑ 3 ... ΕΝΑ Ν αληθές εάν και μόνο εάν τουλάχιστον μία από τις προτάσεις είναι αληθήςΕΝΑ 1 , ΕΝΑ 2 , ΕΝΑ 3 , ..., ΕΝΑ Ν (και επομένως ψευδές όταν όλες αυτές οι δηλώσεις είναι ψευδείς).

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

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

Ας γράψουμε αυτόν τον ορισμό με τη μορφή πίνακα αλήθειας:

1

1

1

1

0

0

0

1

1

0

0

1

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

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

1

1

1

1

0

0

0

1

0

0

0

1

Λογικές συναρτήσεις και ο μετασχηματισμός τους

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

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

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

;

.

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

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

Πριν προχωρήσουμε στα SDNF και SKNF, ας εισαγάγουμε μερικές έννοιες.

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

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

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

Για παράδειγμα, η έκφρασηείναι DNF.

Οποιοσδήποτε σύνδεσμος στοιχειωδών διαχωρισμών ονομάζεται συνδετικός κανονικός τύπος, δηλαδή CNF.

Για παράδειγμα, η έκφρασηείναι KNF.

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

Για παράδειγμα, η έκφραση είναι DNF, αλλά όχι SDNF. έκφρασηείναι SDNF.

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

Για παράδειγμα, η έκφραση .

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

μετάβαση από την αυθαίρετη εκχώρηση συνάρτησης στο DNF

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

Για παράδειγμα:

μετάβαση από το DNF στο KNF

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

Ο δεύτερος τρόπος για να μετακινηθείτε από το DNF στο CNF είναι να χρησιμοποιήσετε τον νόμο διανομής:

μετάβαση από το KNF στο DNF

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

μετάβαση από το KNF στο SKNF

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

μετάβαση από DNF σε SDNF

Εάν σε κάποιο απλό σύνδεσμο λείπει μια μεταβλητή, για παράδειγμα,z , τότε πολλαπλασιάζουμε τον ημιτελή σύνδεσμο με μια έκφραση της φόρμας , μετά ανοίγουμε τις αγκύλες (δεν γράφουμε επαναλαμβανόμενους ασύνδεσμους όρους). Για παράδειγμα:

Για να αποκτήσετε SDNF και SCNF από πίνακες αλήθειας, πρέπει να εκτελέσετε τα ακόλουθα 4 σημεία του αλγορίθμου:

SDNF

SKNF

Η κατασκευή του SDNF και του SKNF ξεκινά με έναν πίνακα αλήθειας.

Ας σημειώσουμε εκείνες τις γραμμές του πίνακα των οποίων οι έξοδοι είναι ίσες

1

0

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

σύνδεσμος (&)

διαχωρισμός (V)

Τακτοποιούμε τα σημάδια της λειτουργίας άρνησης ως εξής:

Εάν μια μεταβλητή είναι ίση με 1, τότε γράφουμε αυτή τη μεταβλητή, αν είναι ίση με 0, τότε σημειώνουμε την άρνησή της.

Εάν μια μεταβλητή είναι ίση με 0, τότε γράφουμε αυτή τη μεταβλητή, αν είναι ίση με 1, τότε γράφουμε την άρνησή της.

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

διασπάσεις

συνδέσμους

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

αντιστροφέας

σύνδεσμος

διαχωριστής

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

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

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

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

Υπάρχουν δύο κατευθύνσεις για ελαχιστοποίηση:

Η συντομότερη μορφή σημειογραφίας (αυτό παράγει τις συντομότερες μορφές KDNF, KKNF, KPNF).

Λήψη της ελάχιστης φόρμας εγγραφής (λήψη του ελάχιστου αριθμού χαρακτήρων για την εγγραφή ολόκληρης της συνάρτησης ταυτόχρονα).

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

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

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

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

Μέθοδος Quine-McCluskey;

Μέθοδος Blake-Poretsky;

Η μέθοδος του Petrik και άλλοι.

Ας σταθούμε λεπτομερέστερα στις δύο πρώτες μεθόδους.

Μέθοδος άμεσων μετασχηματισμών λογικών συναρτήσεων

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

Όταν χρησιμοποιείτε αυτήν τη μέθοδο:

Οι λογικές συναρτήσεις SDNF είναι γραμμένες,

Η φόρμα μετασχηματίζεται και απλοποιείται χρησιμοποιώντας τα αξιώματα της άλγεβρας της λογικής και, ειδικότερα, προσδιορίζονται γειτονικοί όροι (μέλη) στο αρχικό SDNF, στους οποίους υπάρχει μια μη συμπίπτουσα μεταβλητή.

Ο νόμος της κόλλησης ισχύει για γειτονικούς όρους.

Οι όροι που σχηματίζονται με την κόλληση ονομάζονται εμφυτεύματα.

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

Η συνάρτηση που προκύπτει ως αποτέλεσμα της ελαχιστοποίησης ονομάζεται αδιέξοδη συνάρτηση.

Αφήστε τη συνάρτηση να δοθεί

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

Έχουμε την ελάχιστη συνάρτηση

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

Μέθοδος ελαχιστοποίησης λογικών συναρτήσεων με χρήση χαρτών Karnaugh

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

Οι χάρτες Karnaugh είναι χρήσιμοι όταν υπάρχει μικρός αριθμός μεταβλητών.

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

Στο Σχ. Το 1 δείχνει χάρτες Veitch για δύο, τρεις και τέσσερις μεταβλητές, αντίστοιχα.

ρύζι. 1

Τοποθεσία μεταβλητών ομάδων Χ δεν έχει σημασία, είναι απαραίτητο μόνο κάθε κελί να διαφέρει από οποιοδήποτε γειτονικό κελί μόνο κατά μία μεταβλητή. Σύμφωνα με την αποδεκτή μορφή κατασκευής χαρτών, τα κελιά της πρώτης και της τελευταίας σειράς και τα κελιά της πρώτης και της τελευταίας στήλης θεωρούνται επίσης γειτονικά. Ο αριθμός των κελιών χάρτη είναι ίσος με τον αριθμό των πιθανών συνδυασμών τιμών μεταβλητών (όροι) και η τιμή μιας λογικής συνάρτησης που αντιστοιχεί σε ένα δεδομένο σύνολο μεταβλητών γράφεται σε κάθε κελί. Εάν οποιοσδήποτε από τους πιθανούς συνδυασμούς υπάρχει στην τέλεια διαχωριστική κανονική μορφή (PDNF) της εγγραφής της συνάρτησης, τότε το "1" τοποθετείται στο αντίστοιχο κελί του χάρτη Carnot. Εάν δεν υπάρχει όρος στη συνάρτηση που προκύπτει, τότε το "0" τοποθετείται στο αντίστοιχο κελί του χάρτη Carnaugh.

Για παράδειγμα, η συνάρτηση που εξετάστηκε στο προηγούμενο παράδειγμα

που καθορίζεται από τον πίνακα αληθείας (Εικ. 2 α) μπορεί επίσης να ελαχιστοποιηθεί χρησιμοποιώντας χάρτες Carnaugh. Ο χάρτης Karnaugh για αυτό θα έχει τη μορφή που φαίνεται στο Σχ. 2 β.

ρύζι. 2

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

Έτσι στην πρώτη γραμμή του χάρτη Karnaugh (βλ. Εικ. 2 β) η μεταβλητή Χ , εμφανίζεται σε συνδυασμό με Χ 1 Και Χ 2 , που αλληλοσυμπληρώνονται:

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

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

Οι προκύπτουσες απλοποιημένες εκφράσεις συνδυάζονται χρησιμοποιώντας τη λειτουργία OR.

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

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

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

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

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

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

Έτσι, ο χάρτης Veitch για τη λογική συνάρτηση

φαίνεται στο σχήμα 3.

ρύζι. 3

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

Μια απλοποιημένη έκφραση για μια λογική συνάρτηση είναι

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

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

Ο χάρτης Karnaugh για αυτήν τη συνάρτηση φαίνεται στο Σχήμα 4:

ρύζι. 4

Τα κύτταρα που πρόκειται να ομαδοποιηθούν περιβάλλονται από δύο περιγράμματα. Το κάτω περίγραμμα καθιστά δυνατή την εξάλειψη μιας μεταβλητήςΧ 3 και μετά από αυτό ένα μέλος παραμένει σε αυτό.

Στον επάνω βρόχο, δύο μεταβλητές μπορούν να εξαλειφθούν (Χ 2 Και Χ 4 ) και μετά από αυτό το μέλος παραμένει σε αυτό. Μια απλοποιημένη έκφραση Boole για μια λογική συνάρτηση είναι

Ας εξετάσουμε την ελαχιστοποίηση μιας λογικής συνάρτησης, ο χάρτης Veitch της οποίας φαίνεται στο Σχ. 5.

ρύζι. 5

Η έκφραση Boole για αυτή τη συνάρτηση είναι

Τα τέσσερα γωνιακά κελιά μπορούν να συνδυαστούν σε μία ομάδα. Αυτή η ένωση εξαλείφει δύο μεταβλητές (Χ 1 Και Χ 2 ) και γίνετε μέλος.

Τα δύο 1 από την πρώτη σειρά μπορούν να συνδυαστούν με τα δύο 1 από την κάτω σειρά για να δημιουργήσουν μια ομάδα τεσσάρων κελιών που επιτρέπει την εξάλειψη των δύο μεταβλητών (Χ 1 Και Χ 3 ) και γίνετε μέλος.

Τέλος, το μόνο 1 που απομένει (από τη δεύτερη σειρά και την τελευταία στήλη) μπορεί να συνδυαστεί με το κελί πάνω από αυτό, εξαλείφοντας μία μεταβλητή (Χ 4 ) και γίνετε μέλος.

Έτσι παίρνουμε την ελαχιστοποιημένη λογική συνάρτηση

Η μέθοδος των χαρτών Karnaugh (διαγράμματα Veitch), ουσιαστικά, απλοποιεί την εύρεση κολλημένων συνδέσμων στο SDNF της αρχικής λογικής συνάρτησης.

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

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

Απλοποιήστε τη χρήση των χαρτών Carnaugh για μια συνάρτηση 2 μεταβλητών:

Ο χάρτης Karnaugh (διάγραμμα Vaitch) για αυτήν τη συνάρτηση θα μοιάζει με:

Στην πρώτη γραμμή μπορείτε να εξαιρέσετε τη μεταβλητή Χ 2 και αποκτήστε μια απλοποιημένη έκφραση Χ 1 .

Στη δεύτερη στήλη μπορείτε να εξαιρέσετε τη μεταβλητήΧ 1

Έτσι, θα μοιάζει μια απλοποιημένη έκφραση της λογικής συνάρτησης

Στην πρώτη στήλη μπορείτε να εξαιρέσετε τη μεταβλητή Χ 1 και αποκτήστε μια απλοποιημένη έκφραση Χ 2 .

Στη δεύτερη γραμμή, μπορείτε να εξαλείψετε τη μεταβλητή και να πάρετε μια απλοποιημένη έκφραση.

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

Έτσι, θα μοιάζει μια απλοποιημένη έκφραση της λογικής συνάρτησης

Απλοποιήστε τη χρήση χαρτών Carnaugh για μια συνάρτηση 3 μεταβλητών:

Το διάγραμμα Veitch για αυτή τη συνάρτηση θα μοιάζει με αυτό:

Χ 3 και αποκτήστε μια απλοποιημένη έκφραση.

Χ 3 και αποκτήστε μια απλοποιημένη έκφραση.

Στην τελευταία στήλη μπορείτε να εξαιρέσετε τη μεταβλητήΧ 1 και αποκτήστε μια απλοποιημένη έκφραση.

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

Έτσι, θα μοιάζει μια απλοποιημένη έκφραση της λογικής συνάρτησης

Το διάγραμμα Veitch για αυτή τη συνάρτηση θα μοιάζει με αυτό:

Στην πρώτη γραμμή μπορείτε να εξαιρέσετε τη μεταβλητήΧ 3 και πάρτε μια απλοποιημένη έκφραση και μια μεταβλητήΧ 2 και αποκτήστε μια απλοποιημένη έκφραση.

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

Έτσι, θα μοιάζει μια απλοποιημένη έκφραση της λογικής συνάρτησης

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

Τότε το διάγραμμα Veitch για αυτή τη συνάρτηση θα μοιάζει με αυτό:

Στην πρώτη γραμμή μπορείτε να εξαιρέσετε τη μεταβλητήΧ 3 και αποκτήστε μια απλοποιημένη έκφραση.

Η πρώτη γραμμή περιέχει την έκφραση .

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

Έτσι, θα μοιάζει μια απλοποιημένη έκφραση της λογικής συνάρτησης

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

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

Το διάγραμμα Veitch για αυτή τη συνάρτηση θα μοιάζει με αυτό:

η πρώτη γραμμή μπορεί να αποκλείσει τη μεταβλητή Χ 3 και αποκτήστε μια απλοποιημένη έκφραση.

0 1 0 0

Σχετικά με τη δεύτερη στήλη μπορείτε να εξαιρέσετε τη μεταβλητή Χ 1 .

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

Έτσι, θα μοιάζει μια απλοποιημένη έκφραση της λογικής συνάρτησης

Το διάγραμμα Veitch για αυτή τη συνάρτηση θα μοιάζει με αυτό:

Στην πρώτη γραμμή μπορείτε να εξαιρέσετε τη μεταβλητήΧ 3 και αποκτήστε μια απλοποιημένη έκφραση.

Στη δεύτερη γραμμή μπορείτε να εξαιρέσετε τη μεταβλητήΧ 3 και αποκτήστε μια απλοποιημένη έκφραση.

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

Έτσι, θα μοιάζει μια απλοποιημένη έκφραση της λογικής συνάρτησης

Το διάγραμμα Veitch για αυτή τη συνάρτηση θα μοιάζει με αυτό:

Μπορείτε να εξαιρέσετε μεταβλητές στην πρώτη και την τελευταία στήληΧ 1 Και Χ 2 και αποκτήστε μια απλοποιημένη έκφραση.

Στη δεύτερη γραμμή μπορείτε να εξαιρέσετε τη μεταβλητήΧ 2 και αποκτήστε μια απλοποιημένη έκφραση. ΣΧΕΤΙΚΑ ΜΕ .

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

Έτσι, θα μοιάζει μια απλοποιημένη έκφραση της λογικής συνάρτησης

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

συμπέρασμα

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

1. τα βασικά στοιχεία της μαθηματικής λογικής έχουν μελετηθεί.

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

   επιλεγμένες εργασίες για ανεξάρτητη εργασία.

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

Εξέτασα λεπτομερώς 2 μεθόδους ελαχιστοποίησης λογικών συναρτήσεων:

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

μέθοδος ελαχιστοποίησης χρησιμοποιώντας διαγράμματα Veitch (χάρτες Karnaugh).

Η πρώτη μέθοδος έχει γίνει ευρέως διαδεδομένη ακόμη και στα σχολικά εγχειρίδια πληροφορικής (για παράδειγμα, εγχειρίδια για τις τάξεις 10-11 από τους N. Ugrinovich, L. Shchautsukova), καθώς είναι μια από τις απλές μεθόδους απλοποίησης των συναρτήσεων λογικής άλγεβρας. Τα καθήκοντα που παρουσιάζονται στα εγχειρίδια αυτών των συγγραφέων είναι αρκετά διαφορετικά:

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

να κατασκευάσει ένα λογικό κύκλωμα με βάση μια δεδομένη συνάρτηση.

απλοποίηση του κυκλώματος μεταγωγής.

να αποδείξετε μια λογική έκφραση χρησιμοποιώντας έναν πίνακα αλήθειας.

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

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

Αυτό το θέμα είναι πρακτικής σημασίας στη μικροηλεκτρονική. Επιπλέον, το Unified State Examination στην επιστήμη των υπολογιστών και στις ΤΠΕ περιέχει μια σειρά από εργασίες που σχετίζονται με τη λογική άλγεβρα, τις οποίες έχουμε χωρίσει σε 4 ομάδες.

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

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

Η τρίτη ομάδα περιλαμβάνει εργασίες για την εύρεση της αλήθειας των δηλώσεων για οποιεσδήποτε τιμές μεταβλητών Χ Και στο .

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

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

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

Βιβλιογραφία

Gavryukova G. A. Λογική στην επιστήμη των υπολογιστών [Ηλεκτρονικός πόρος]. – Λειτουργία πρόσβασης: Οκτ. 2010).

Ivin A. A. Logic: Σχολικό βιβλίο. – 2η έκδ. – Μ.: Γνώση, 1998. – 233 σελ.

Igoshin V.I. Μαθηματική λογική και θεωρία αλγορίθμων: Εγχειρίδιο για μαθητές. πιο ψηλά εγχειρίδιο εγκαταστάσεις. – 2η έκδ., σβησμένο. – Μ.: Ακαδημία, 2008. – 448 σελ.

Πληροφορική και ΤΠΕ. Προετοιμασία για την Ενιαία Κρατική Εξέταση 2009. Εισαγωγικές εξετάσεις. / Εκδ. F. F. Lysenko. – Rostov n/d: Legion-M, 2009. – 208 p.

Computer Science: Textbook / B.V. Sobol [κ.λπ.]. – 3η έκδ., πρόσθ. και επεξεργάζεται – Rostov n/d: Phoenix, 2007. – 446 p.

Computer Science: Textbook / A. V. Mogilev, N. I. Pak, E. K. Henner. – 3η έκδ. – Μ.: Ακαδημία, 2004. – 848 σελ.

Kalabekov B. A. Ψηφιακές συσκευές και συστήματα μικροεπεξεργαστή: Εγχειρίδιο για τις τεχνικές σχολές επικοινωνίας. – M.: Hotline – Telecom, 2000. – 336 σελ.

Kaimin V. A. Computer Science: Textbook. – 2η έκδ., αναθεωρημένη. και επιπλέον – Μ.: INFRA-M, 2001. – 272 σελ.

Kovalenko A. A, Petropavlovsky M. D. Fundamentals of microelectronics: Textbook. – Μ.: Ακαδημία, 2006. – 240 σελ.

Lvovsky M. B. Μεθοδολογικό εγχειρίδιο για την επιστήμη των υπολογιστών για μαθητές των τάξεων 9-11 που σπουδάζουν IBM PC [Ηλεκτρονικός πόρος]. – Λειτουργία πρόσβασης: Σεπτ. 2010).

Μαθηματικά θεμέλια της επιστήμης των υπολογιστών. Μάθημα επιλογής: Σχολικό βιβλίο / E. V. Andreeva, L. L. Bosova, I. N. Falina. – Μ.: BINOM. Εργαστήριο Γνώσης, 2005. – 328 σελ.

Ελαχιστοποίηση λογικών συναρτήσεων [Ηλεκτρονικός πόρος]. – Λειτουργία πρόσβασης: Αύγ. 2010).

Βασικές αρχές της μικροηλεκτρονικής: Εγχειρίδιο για πανεπιστήμια / N. A. Avaev, Yu E. Naumov, V. T. Frolkin. – Μ.: Ραδιόφωνο και Επικοινωνίες, 1991. – 288 σελ.: εικ.

Εργαστήριο για την επιστήμη των υπολογιστών και τις τεχνολογίες της πληροφορίας / N. D. Ugrinovich, L. L. Bosova, N. I. Mikhailova. – 2η έκδ., αναθ. – Μ.: BINOM. Laboratory of Knowledge, 2004. – 394 p.

Εφαρμοσμένα μαθηματικά: Εγχειρίδιο / I. N. Revchuk, V. K. Pchelnik. – Grodno: Grodno State University με το όνομά του. Ya. Kupala, 2007. – 128 σελ.

Rabkin E. L., Farforovskaya Yu B. Διακριτά μαθηματικά: Boolean functions and elements of graph theory: Guidelines and test tasks [Ηλεκτρονική πηγή]. – Λειτουργία πρόσβασης: 7 Αυγούστου 2010).

Savelyev A. Ya. – Μ.: MSTU im. N. E. Bauman, 2001. – 328 pp., ill.

Stepanenko I.P. Βασικές αρχές της μικροηλεκτρονικής: Εγχειρίδιο για τα πανεπιστήμια. – 2η έκδ., αναθεωρημένη. και επιπλέον – Μ.: Εργαστήριο Βασικής Γνώσης, 2001. – 488 σελ.

Θεωρία και μεθοδολογία διδασκαλίας της πληροφορικής: Σχολικό βιβλίο / [Μ. P. Lapchik, I. G. Semakin, E. K. Henner, M. I. Ragulina, κ.λπ.]; εκδ. M. P. Lapchik. – Μ.: Ακαδημία, 2008. – 592 σελ.

Ugrinovich N.V. Πληροφορική και ΤΠΕ. Βαθμός 10. Επίπεδο προφίλ. – 3η έκδ., αναθ. – Μ.: Binom. Εργαστήριο Γνώσης, 2008. – 387 σελ.

Ugrinovich N.V. Επιστήμη υπολογιστών και τεχνολογία πληροφοριών: Εγχειρίδιο για τις τάξεις 10-11. - Μ.: ΔΙΩΝΥΜΙΚΟΣ. Εργαστήριο Γνώσης, 2003. – 512 σελ.

Shautsukova L.Z. Πληροφορική 10 – 11. – Μ.: Εκπαίδευση, 2004. – 420 σελ.

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

Ας το αναπαραστήσουμε ως DNF με απροσδιόριστο συντελεστή:

(**)

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

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

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

Παράδειγμα

Συνθέτουμε το σύστημα χρησιμοποιώντας την έκφραση (**).

Αφού εξαλείψουμε τους μηδενικούς όρους παίρνουμε

Υποθέτουμε ότι οι υπόλοιποι συντελεστές θεωρούνται μηδέν. Παίρνουμε MDNF:

2.2. Μέθοδος Quine-Mack-Clasky

Η εξεταζόμενη μέθοδος των αόριστων συντελεστών είναι αποτελεσματική εάν ο αριθμός των ορισμάτων συνάρτησης δεν είναι μεγαλύτερος από 5 - 6. Αυτό οφείλεται στο γεγονός ότι ο αριθμός των εξισώσεων είναι 2n. Είναι πιο αποτελεσματικό να μην γράφουμε όλους τους πιθανούς συνδέσμους για μια συνάρτηση, αλλά μόνο αυτούς που μπορεί να υπάρχουν στο DNF μιας δεδομένης συνάρτησης. Σε αυτό βασίζεται η μέθοδος του Quine. Υποτίθεται ότι η συνάρτηση καθορίζεται με τη μορφή SDNF. Σε αυτή τη μέθοδο, οι στοιχειώδεις σύνδεσμοι του βαθμού n που περιλαμβάνονται στο DNF ονομάζονται ελάχιστα όροι του βαθμού n. Η μέθοδος του Quine αποτελείται από τη διαδοχική εκτέλεση των παρακάτω βημάτων.

1. Εύρεση πρωτογενών εμπλοκών

Εξετάζουμε κάθε ελάχιστη συνάρτηση διαδοχικά και τη συγχωνεύουμε με όλα τα ελάχιστα με τα οποία αυτό είναι δυνατό. Ως αποτέλεσμα της συγκόλλησης ελαχίστων n-rank, λαμβάνουμε (n-1)-rank miniterms. Σημειώνουμε τα n-rank miniterms που συμμετείχαν στην εργασία κόλλησης. Έπειτα θεωρούμε ελάχιστα της (n-1) κατάταξης και εφαρμόζουμε σε αυτά την λειτουργία κόλλησης. Σημειώνουμε τα ελάχιστα κολλητικά της κατάταξης (n-1) και σημειώνουμε τα ελάχιστα που προκύπτουν της κατάταξης (n-2) κ.λπ. Το στάδιο τελειώνει εάν τα ελάχιστα που αποκτήθηκαν πρόσφατα μεγάλο-η κατάταξη δεν κολλάει πλέον. Όλα τα μη επισημασμένα ελάχιστα ονομάζονται πρωταρχικά εμπεριστατωμένα. Ο διαχωρισμός τους είναι Abbr. Λειτουργίες DNF.

Κολλάμε μινιτερμ της 4ης βαθμίδας και σημειώνουμε με αστερίσκους τα κολλητά μίνι

Σχηματίζουμε μινιτερμ της 2ης κατάταξης:

Οι πρωτογενείς (απλές) εμπλοκές είναι:

2. Τοποθέτηση σημάτων

Για αυτή τη λειτουργία Abbr. Το DNF έχει τη μορφή:

Για την κατασκευή αδιέξοδων DNF και Abbr. Το DNF πρέπει να πετάξει τα επιπλέον διαστήματα. Δημιουργούμε έναν πίνακα του οποίου οι σειρές αντιστοιχούν στα πρωτεύοντα εμφυτεύματα και οι στήλες αντιστοιχούν στα ελάχιστα SDNF. Εάν ένα από τα ελάχιστα λόγια περιλαμβάνει ένα από τα εμπλεκόμενα, τότε ένα σημάδι τοποθετείται στη διασταύρωση της αντίστοιχης γραμμής και στήλης, για παράδειγμα, 1.

Συνέχεια του παραδείγματος

3. Εύρεση βασικών υπονοούμενων

Εάν οποιαδήποτε στήλη περιέχει μόνο ένα 1, τότε η κύρια εμπλοκή που ορίζει αυτή τη σειρά ονομάζεται ουσιαστική. Για παράδειγμα, το ουσιαστικό υπονοούμενο είναι . Το ουσιαστικό υπονοούμενο δεν μπορεί να αφαιρεθεί από το Abbr. DNF, αφού μόνο αυτό είναι ικανό να καλύψει μερικά ελάχιστα γράμματα του SDNF. Επομένως, εξαιρούμε από τον πίνακα τις σειρές που αντιστοιχούν σε αυτά τα εμφυτεύματα και τις στήλες που έχουν αυτές σε αυτές τις γραμμές.

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

Ως αποτέλεσμα παίρνουμε τον πίνακα

4. Διασχίζοντας επιπλέον στήλες και σειρές

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

5. Επιλογή ελάχιστης κάλυψης με μέγιστα διαστήματα

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

Συνέχεια του παραδείγματος

Η ελάχιστη κάλυψη του πίνακα σχηματίζεται από τις σειρές που αντιστοιχούν στα εμφυτεύματα. Τότε το MDNF έχει τη μορφή:

Η μέθοδος του Quine έχει μια σημαντική ταλαιπωρία που σχετίζεται με την ανάγκη για μια πλήρη κατά ζεύγη σύγκριση ελαχίστων στο στάδιο της κατασκευής Abbr. DNF. Το 1956, ο McCluskey πρότεινε έναν εκσυγχρονισμό του πρώτου σταδίου της μεθόδου του Quine, δίνοντας μια σημαντική μείωση στον αριθμό των συγκρίσεων των ελαχίστων όρων.

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

Παράδειγμα

Ας βρούμε το MDNF για τη συνάρτηση:

Miniterms 4ης κατάταξης ανά ομάδες

Miniterms της 3ης βαθμίδας

Miniterms 2η κατάταξη

Μίνι όροι χωρίς επισήμανση ή πρωταρχικά υπονοούμενα

Δημιουργία πίνακα ετικετών

Και τα δύο κύρια εμφυτεύματα είναι απαραίτητα και καθορίζουν την ελάχιστη κάλυψη, δηλαδή το MDNF έχει τη μορφή.

Διαδικασία ελαχιστοποίησης

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

Υπολογισμός δύναμης

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

Το τρίτο βήμα είναι η βελτιστοποίηση του αλγορίθμου για την αναζήτηση ατόμων που βρίσκονται πιο κοντά σε ένα δεδομένο άτομο. Το γεγονός είναι ότι μια απλή αναζήτηση όλων των ατόμων, ο υπολογισμός των αποστάσεων από αυτά και η απόρριψη των ατόμων των οποίων η απόσταση υπερβαίνει την ακτίνα αποκοπής απαιτεί έναν αριθμό πράξεων ανάλογο με το πού είναι ο αριθμός των ατόμων στο σύστημα. Κατά συνέπεια, με την ανάπτυξη, ο αριθμός των απαιτούμενων πράξεων αυξάνεται γρήγορα, και ως εκ τούτου η εκτέλεση των υπολογισμών επιβραδύνεται πολύ και, για μεγάλες, καθίσταται σχεδόν αδύνατη. Έτσι, για να αποφύγουμε αυτή την επιβράδυνση, χρειαζόμαστε έναν αλγόριθμο για τον οποίο ο αριθμός των απαιτούμενων πράξεων αυξάνεται γραμμικά και όχι τετραγωνικά. Κατ 'αρχήν, ένας τέτοιος αλγόριθμος είναι απλός - δεν χρειάζεται να ταξινομήσετε όλα τα άτομα, αλλά μόνο αυτά που είναι αρκετά κοντά. Μια τέτοια δήλωση είναι ταυτολογία έως ότου προσδιοριστεί η έννοια των ατόμων σε κοντινή απόσταση. Για να γίνει αυτό, χωρίζουμε το κελί προσομοίωσης σε μικρότερα υποκελιά. Στη συνέχεια, αυτά που βρίσκονται κοντά σε ένα δεδομένο άτομο θα είναι άτομα που βρίσκονται σε υποκύτταρα δίπλα στο υποκύτταρο που περιέχει αυτό το άτομο ή σε υποκύτταρα δίπλα σε γειτονικά.

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

Έτσι, ο αλγόριθμος για την αναζήτηση ατόμων που βρίσκονται σε απόσταση από ένα δεδομένο άτομο σε απόσταση όχι μεγαλύτερη από την ακτίνα αποκοπής φαίνεται ως εξής. Χρησιμοποιώντας τον αριθμό του ατόμου, βρίσκουμε τις συντεταγμένες του ατόμου και από αυτές το υποκελί στο οποίο βρίσκεται το άτομο. Τότε βρίσκουμε υποκελιά που δεν απέχουν περισσότερο από μια απόσταση από αυτό. Τα άτομα που βρίσκονται σε αυτά τα υποκελιά θα είναι αυτά που αναζητούμε (βλ. Εικ. 1). Για να βρείτε τον αριθμό ενός ατόμου που είναι αποθηκευμένο σε ένα δεδομένο υποκελί, είναι βολικό να εισάγετε έναν πίνακα, κάθε στοιχείο του οποίου αντιστοιχεί σε ένα συγκεκριμένο υποκελί. Αυτό το στοιχείο πίνακα θα αποθηκεύσει τον αριθμό του ατόμου που βρίσκεται σε αυτό το υποκελί ή μηδέν εάν το υποκελί είναι κενό. Τα στοιχεία αυτού του πίνακα ενημερώνονται σε κάθε χρονικό βήμα MD. Είναι σαφές ότι ο περιγραφόμενος αλγόριθμος εξασφαλίζει μια γραμμική αύξηση του αριθμού των λειτουργιών καθώς αυξάνεται ο αριθμός των ατόμων στο σύστημα. Παραλλαγές αυτού του αλγορίθμου χρησιμοποιούνται σε προγράμματα MD "Gromex", "MOLDY", "DL_POLY", κ.λπ.

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

Εικ.1 Σχέδιο αναζήτησης πλησιέστερων ατόμων.

Εάν υπάρχει ένα άτομο σε ένα υποκύτταρο, τότε υπολογίζουμε τη δύναμη που ασκεί σε αυτό από τα πλησιέστερα άτομα που βρίσκονται σε κοντινά υποκελιά. Εάν το υποκελί είναι κενό, προχωρήστε στο επόμενο. Ας σημειώσουμε ότι, για παράδειγμα, για ένα άτομο που βρίσκεται στο υποκελί 6 (βλ. Εικ. 1), είναι απαραίτητο να υπολογιστεί η δύναμη που ασκεί το μέρος των ατόμων που βρίσκεται στα υποκελιά 1, 2, 3, 7. Οι δυνάμεις που δρουν στα μέρος των ατόμων που βρίσκονται στα υποκελιά 5, 9, 10, 11, δυνάμει του τρίτου νόμου του Νεύτωνα, είναι ήδη γνωστά μέχρι το πρόσημο. Υπολογίστηκαν με τον υπολογισμό των δυνάμεων που ασκούνται στα άτομα που βρίσκονται σε αυτά τα υποκύτταρα. Έτσι, σε μια δεδομένη υπολογιστική οργάνωση, είναι απαραίτητο να ληφθούν υπόψη μόνο τα μισά από τα κοντινά υποκελιά. Περαιτέρω, όταν μετακινούμαστε σε παρακείμενο υποκελί 7, δεν υπάρχει ανάγκη να εξεταστούν όλα τα κοντινά υποκελιά για να αναζητήσετε άτομα που βρίσκονται κοντά σε αυτά. Είναι απαραίτητο μόνο να εξερευνήσετε τα κελιά 4 και 8. Και στα άτομα που βρίσκονται σε αυτά, προσθέστε τα άτομα που βρέθηκαν για το κελί 6, με εξαίρεση τα άτομα που βρίσκονται στα υποκελιά 1 και 6. Έτσι, πληροφορίες σχετικά με τα πλησιέστερα άτομα για ένα δεδομένο υποκελί δεν χάνεται, αλλά χρησιμοποιείται στην αναζήτηση πλησιέστερων ατόμων για ένα παρακείμενο υποκελί. Αυτό φυσικά οδηγεί σε ταχύτερους υπολογισμούς.