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

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, ελαχιστοποιήστε τις λογικές εκφράσεις που καθορίζονται από τα εργασιακά και απαγορευμένα σύνολα

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

Όλες οι λογικές συναρτήσεις καθορίζονται είτε ως τύπος είτε ως πίνακας τιμών. Μερικές φορές είναι απαραίτητο να προσδιοριστεί απλούστερη μορφήγράφοντας αυτή τη συνάρτηση με έναν ελάχιστο αριθμό στοιχειωδών λογικές συναρτήσειςΚΑΙ, Ή, ΟΧΙ για ευκολία στη χρήση. Για αυτό, χρησιμοποιούνται όλες οι εξεταζόμενες λειτουργίες ξεκινώντας από το Νο. 4 και τις μεθόδους Quine και Veitch.

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

Μέθοδος Veitch (χάρτες Karnaugh)

Σε αυτή τη μέθοδο, για να απεικονιστεί μια συνάρτηση n μεταβλητών, σχεδιάζεται ένας ειδικός πίνακας που περιέχει 2n κελιά. Κάθε κελί αντιστοιχεί σε ένα από τα σύνολα n μεταβλητών. Το κελί καταγράφει την τιμή που δέχεται η συνάρτηση για αυτό το σύνολο ορισμάτων. Όλα τα κελιά που αντιστοιχούν σε σύνολα που περιέχουν κάποια μεταβλητή χωρίς το σύμβολο αντιστροφής σχηματίζουν μια περιοχή 2 n -1 κελιών. Αυτή η περιοχή ονομάζεται περιοχή μιας δεδομένης μεταβλητής(για παράδειγμα, το εύρος της μεταβλητής x). Τα υπόλοιπα κύτταρα σχηματίζουν την περιοχή αυτής της αντίστροφης μεταβλητής. Πιθανά σύνολα ορισμάτων κατανέμονται μεταξύ των κελιών με τέτοιο τρόπο ώστε τα όρια των περιοχών όλων των μεταβλητών και οι αντιστροφές τους να είναι ξεκάθαρα και να αναγνωρίζεται εύκολα οπτικά η συμμετοχή οποιουδήποτε κελιού σε μια συγκεκριμένη περιοχή.

1) Συνάρτηση μιας μεταβλητής:

2) Συνάρτηση δύο μεταβλητών:

3) Διάγραμμα για διαχωρισμό:

4) Διάγραμμα για σύνδεση:

5) Για τρία επιχειρήματα:

6) Για τέσσερα επιχειρήματα:

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

σι)

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

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

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

Περιεχόμενο

Εισαγωγή

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

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

Επιπλέον, η διαδικασία απλοποίησης 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.

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

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

;

.

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

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

Πριν προχωρήσουμε στα 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

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

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

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

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

ρύζι. 1

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

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

δίνεται από τον πίνακαΗ αλήθεια (Εικ. 2 α) μπορεί επίσης να ελαχιστοποιηθεί χρησιμοποιώντας χάρτες Karnaugh. Ο χάρτης 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 Και Χ 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. Ψηφιακές συσκευέςκαι συστήματα μικροεπεξεργαστών: Εγχειρίδιο για τις τεχνικές σχολές επικοινωνίας. - Μ.: Γραμμή επικοινωνίας– Telecom, 2000. – 336 p.

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. Εργαστήριο Γνώσης, 2004. – 394 σελ.

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

Rabkin E. L., Farforovskaya Yu B. Διακριτά μαθηματικά: Boolean συναρτήσεις και στοιχεία της θεωρίας γραφημάτων: Κατευθυντήριες γραμμέςΚαι εργασίες ελέγχου[Ηλεκτρονικός πόρος]. – Λειτουργία πρόσβασης: 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 σελ.

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

Οι μέθοδοι ελαχιστοποίησης βασίζονται στη λειτουργία κόλλησης (αλγόριθμος για το συνδυασμό γειτονικών δυαδικών αριθμών):

όπου το Α είναι στοιχειώδης σύνδεσμος.

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

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

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

Ελαχιστοποίηση μιγαδικών παραστάσεων Boole χρησιμοποιώντας τον πίνακα Carnot

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

Συνιστάται να χρησιμοποιείτε πίνακες Carnot για να ελαχιστοποιήσετε το FAL σε σύνολα 2,3,4,5 και 6 μεταβλητών. Οι αριθμοί στηλών στους πίνακες Carnot σχηματίζουν τα λιγότερο σημαντικά ψηφία και οι αριθμοί σειρών τα πιο σημαντικά ψηφία των συνόλων. Οι αριθμοί κελιών αποτελούνται από αριθμούς σειρών και στηλών και αντιστοιχούν σε σύνολα μεταβλητών.

Ας εξετάσουμε τον πίνακα Carnot για μια συνάρτηση λογικής άλγεβρας σε σύνολα 4 μεταβλητών (Πίνακας 1).

Πίνακας 1. Πίνακας Carnot

Οι στήλες και οι σειρές σε αυτόν τον πίνακα ορίζονται με δυαδικούς γειτονικούς αριθμούς: 00-0I-II-I0. Επομένως, οι αριθμοί των οριζόντια και κατακόρυφα παρακείμενων κελιών, καθώς και τα πιο εξωτερικά κελιά σε σειρές και στήλες, είναι γειτονικοί αριθμοί, για παράδειγμα:

κελιά με αριθμούς και?

κελιά με αριθμούς.

κελιά με αριθμούς.

κελιά με αριθμούς.

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

Οι «υποκύβοι» συνδυάζουν:

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

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

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

Ο πίνακας Carnot, συμπληρωμένος σύμφωνα με αυτόν τον τύπο, μπορεί να παρουσιαστεί με τη μορφή του Πίνακα 2:

Πίνακας 2. Πίνακας Carnot

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

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

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

Στο πρώτο στάδιο, γίνεται μια μετάβαση από μια συνάρτηση που καθορίζεται σε μορφή DNF σε μια μειωμένη DNF. Η ουσία της μεθόδου είναι διαδοχική εκτέλεσηόλες οι πιθανές συμφύσεις και μετά όλες οι απορροφήσεις, με αποτέλεσμα ένα συντομευμένο DNF. Η μέθοδος είναι εφαρμόσιμη σε τέλειο DNF. Από τη σχέση απορρόφησης προκύπτει ότι ένα αυθαίρετο στοιχειώδες προϊόν απορροφάται από οποιοδήποτε μέρος του. Για να το αποδείξουμε, αρκεί να δείξουμε ότι ένας αυθαίρετος πρώτος εμπεριστατωμένος p = x i1Χ i2... Χ σεμπορεί να ληφθεί. Πράγματι, εφαρμόζοντας τη λειτουργία επέκτασης ( αντίστροφη λειτουργίακόλληση):

για όλες τις μεταβλητές που λείπουν x ik , ..., x imτην αρχική συνάρτηση f, λαμβάνουμε το σύνολο S των συστατικών της ενότητας. Συγκολλώντας μεταξύ τους όλα τα συστατικά από το S λαμβάνουμε την εμπλοκή p. Το τελευταίο είναι προφανές, αφού η λειτουργία κόλλησης είναι το αντίστροφο της λειτουργίας ξεδίπλωσης. Το σύνολο S των συστατικών είναι αναγκαστικά παρόν σε μια τέλεια συνάρτηση DNF f αφού το p είναι το συνεπαγόμενο της.

Ως αποτέλεσμα της κόλλησης, προκύπτει ένας σύνδεσμος n-1 κατάταξης και οι σύνδεσμοι παραμένουν στην αρχική έκφραση και συμμετέχουν σε σύγκριση με άλλα μέλη του SDNF. Έτσι, είναι δυνατή η μείωση της κατάταξης των όρων.

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

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

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

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

f SDNF = V (1,2,5,6,7)=x 1 Χ 2 Χ 3 +x 1 Χ 2 Χ 3 +x 1 Χ 2 Χ 3 +x 1 Χ 2 Χ 3 +x 1 Χ 2 Χ 3

1 2 3 4 5

Ας εκτελέσουμε τη λειτουργία κόλλησης:

• 1 - 3 (χ 1 )Χ 2 Χ 3 1
• 2 - 4 (Χ 1 )Χ 2 Χ 3 2
• 3 - 5 (χ 2 )Χ 1 Χ 3 3
• 4 - 5 (χ 3 )Χ 1 Χ 2 4

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

f abbr SDNF =x 2 Χ 3 +x 2 Χ 3 +x 1 Χ 3 +x 1 Χ 2

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

Πίνακας 3. Πίνακας εμπλοκής

	x 1 x 2 x3	X 1 x 2 x3	x 1 x 2 x3	x 1 x 2 x3	x 1 x 2 x3

Τα πρωταρχικά εμφυτεύματα είναι υποχρεωτικά αφού μόνο αυτά καλύπτουν τα συστατικά και περιλαμβάνονται στην ελάχιστη κάλυψη. Παραμένει ένα ακάλυπτο συστατικό x 1 Χ 2 Χ 3 που μπορεί να καλυφθεί από ένα από τα δύο εναπομείναντα πρωταρχικά εμφυτεύματα. Αυτό έχει ως αποτέλεσμα δύο αδιέξοδες μορφές.

Μέθοδος Blake-Poretsky

Η μέθοδος επιτρέπει σε κάποιον να αποκτήσει ένα μειωμένο DNF μιας Boolean συνάρτησης f από το αυθαίρετο DNF της. Με βάση την εφαρμογή της γενικευμένης φόρμουλας κόλλησης:

η εγκυρότητα των οποίων είναι εύκολο να αποδειχθεί. Πραγματικά,

Ως εκ τούτου,

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

Ας δούμε ένα παράδειγμα. Έστω η Boolean συνάρτηση f δίνεται από ένα αυθαίρετο DNF.

Είναι απαραίτητο να ληφθεί ένα συντομευμένο DNF της συνάρτησης f χρησιμοποιώντας τη μέθοδο Blake-Poretsky. Πραγματοποιούμε γενική κόλληση. Είναι εύκολο να δούμε ότι το πρώτο και το δεύτερο στοιχείο του αρχικού DNF επιδέχονται γενικευμένη κόλληση σε σχέση με τη μεταβλητή x 1 . Ως αποτέλεσμα της κόλλησης παίρνουμε:

Το πρώτο και το τρίτο στοιχείο του αρχικού DNF επιδέχονται γενικευμένη κόλληση σε σχέση με τη μεταβλητή x 1 και x 2 . Αφού κολλήσετε κατά μήκος του x 1 έχουμε:

Αφού κολλήσουμε κατά μήκος x 2 έχουμε:

Το δεύτερο και το τρίτο στοιχείο του DNF επιδέχονται γενικευμένη κόλληση σε σχέση με τη μεταβλητή x 2 . Μετά την κόλληση παίρνουμε:

Έχοντας εκτελέσει την τελευταία γενικευμένη κόλληση, φτάνουμε στο DNF:

Αφού ολοκληρώσουμε τις απορροφήσεις παίρνουμε:

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

Ελαχιστοποίηση ατελώς καθορισμένων FAL

Εάν, κατά τη σύνθεση ενός λογικού κυκλώματος που εφαρμόζει μερικά FAL από n μεταβλητές, αποδειχθεί ότι ορισμένα σύνολα του συνολικού αριθμού 2 nδεν μπορεί ποτέ να εμφανιστεί στις εισόδους του κυκλώματος, τότε αυτή η λογική συνάρτηση δεν ορίζεται σε αυτά τα σύνολα. Μετά 2 nσύνολα μεταβλητών μπορούν να χωριστούν σε τρεις ομάδες: σύνολα στα οποία η συνάρτηση παίρνει μια μοναδιαία τιμή L, μια μηδενική τιμή D και μια ομάδα συνόλων στα οποία η συνάρτηση δεν ορίζεται N (ακαθορισμένα σύνολα). Ένα FAL που περιέχει απροσδιόριστα σύνολα ονομάζεται ατελώς ή μερικώς καθορισμένο. Απροσδιόριστα σύνολα μπορούν να χρησιμοποιηθούν για τη βελτίωση της ποιότητας της ελαχιστοποίησης. Σε αυτήν την περίπτωση, αβέβαια σύνολα (όταν ελαχιστοποιούνται, για παράδειγμα, από τους χάρτες Veitch, Carnaugh) μπορούν να συμμετέχουν στο σχηματισμό περιγραμμάτων τόσο με μοναδιαία όσο και με μηδενικά σύνολα. Αυτό έχει ως αποτέλεσμα τον σχηματισμό μιας απλούστερης ελαχιστοποιημένης λογικής συνάρτησης.

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