Οι νόμοι της απορρόφησης και της κόλλησης του αποκλεισμού. Νόμοι της άλγεβρας απορρόφησης της λογικής
Οι σύγχρονοι υπολογιστές που βασίζονται σε «αρχαίους» ηλεκτρονικούς υπολογιστές βασίζονται σε ορισμένα αξιώματα ως βασικές αρχές λειτουργίας. Ονομάζονται νόμοι της άλγεβρας της λογικής. Για πρώτη φορά, μια τέτοια πειθαρχία περιγράφηκε (φυσικά όχι τόσο λεπτομερώς όσο στη σύγχρονη μορφή της) από τον αρχαίο Έλληνα επιστήμονα Αριστοτέλη.
Αντιπροσωπεύοντας έναν ξεχωριστό κλάδο των μαθηματικών, εντός του οποίου μελετάται ο προτασιακός λογισμός, η άλγεβρα της λογικής έχει μια σειρά από καλά καθορισμένα συμπεράσματα και συμπεράσματα.
Για να κατανοήσουμε καλύτερα το θέμα, θα αναλύσουμε τις έννοιες που θα βοηθήσουν στο μέλλον να μάθουμε τους νόμους της άλγεβρας της λογικής.
Ίσως ο κύριος όρος στον υπό μελέτη κλάδο είναι μια δήλωση. Αυτή είναι μια δήλωση που δεν μπορεί να είναι και ψευδής και αληθινή ταυτόχρονα. Έχει πάντα μόνο ένα από αυτά τα χαρακτηριστικά. Ταυτόχρονα, είναι συμβατικά αποδεκτό να δίνουμε την τιμή 1 στην αλήθεια, 0 στην ψευδή και να ονομάζουμε την ίδια την πρόταση κάποιου είδους A, B, C. Με άλλα λόγια, ο τύπος A=1 σημαίνει ότι η πρόταση A είναι αληθής. Οι εκφράσεις μπορούν να αντιμετωπιστούν με διάφορους τρόπους. Ας εξετάσουμε εν συντομία τις ενέργειες που μπορούν να γίνουν με αυτά. Σημειώστε επίσης ότι οι νόμοι της άλγεβρας της λογικής δεν μπορούν να κατακτηθούν χωρίς να γνωρίζετε αυτούς τους κανόνες.
1. Διάσπασηδύο δηλώσεις - το αποτέλεσμα της πράξης "ή". Μπορεί να είναι είτε ψευδής είτε αληθινός. Χρησιμοποιείται ο χαρακτήρας "v".
2. Σύνδεσμος.Το αποτέλεσμα μιας τέτοιας ενέργειας, που εκτελείται με δύο προτάσεις, θα είναι μια νέα μόνο εάν και οι δύο αρχικές προτάσεις είναι αληθείς. Χρησιμοποιείται η λειτουργία "και", το σύμβολο "^".
3. Υπονοούμενα.Λειτουργία "Αν Α, τότε Β". Το αποτέλεσμα είναι μια πρόταση που είναι ψευδής μόνο εάν το Α είναι αληθές και το Β είναι λάθος. Χρησιμοποιείται το σύμβολο "->".
4. Ισοδυναμία.Λειτουργία "Α εάν και μόνο εάν Β όταν". Αυτή η δήλωση είναι αληθής εάν και οι δύο μεταβλητές έχουν την ίδια τιμή. Το σύμβολο "<->».
Υπάρχει επίσης ένας αριθμός πράξεων κοντά σε υπονοούμενα, αλλά δεν θα ληφθούν υπόψη σε αυτό το άρθρο.
Τώρα ας ρίξουμε μια πιο προσεκτική ματιά στους βασικούς νόμους της άλγεβρας της λογικής:
1. Η αντικατάσταση ή η αντικατάσταση δηλώνει ότι η αλλαγή των θέσεων των λογικών όρων στις πράξεις σύνδεσης ή διαχωρισμού δεν επηρεάζει το αποτέλεσμα.
2. Συνειρμικός ή συνειρμικός. Σύμφωνα με αυτόν τον νόμο, οι μεταβλητές στις πράξεις σύνδεσης ή διαχωρισμού μπορούν να συνδυαστούν σε ομάδες.
3. Διανομή ή διανομή. Η ουσία του νόμου είναι ότι οι ίδιες μεταβλητές στις εξισώσεις μπορούν να αφαιρεθούν από αγκύλες χωρίς να αλλάξει η λογική.
4. Νόμος του De Morgan (αντιστροφή ή άρνηση). Η άρνηση της πράξης του συνδέσμου ισοδυναμεί με τον διαχωρισμό της άρνησης των αρχικών μεταβλητών. Η άρνηση της διάστασης, με τη σειρά της, είναι ίση με τη σύνδεση της άρνησης των ίδιων μεταβλητών.
5. Διπλή άρνηση. Η άρνηση μιας ορισμένης πρότασης δύο φορές έχει ως αποτέλεσμα την αρχική πρόταση, τρεις φορές - την άρνησή της.
6. Ο νόμος της αδυναμίας μοιάζει με αυτό για τη λογική πρόσθεση: x v x v x v x = x; για πολλαπλασιασμό: x^x^x^=x.
7. Ο νόμος της μη αντίφασης λέει: δύο προτάσεις, αν είναι αντιφατικές, δεν μπορούν να είναι αληθείς ταυτόχρονα.
8. Ο νόμος του αποκλεισμού του τρίτου. Μεταξύ δύο αντιφατικών δηλώσεων, η μία είναι πάντα αληθινή, η άλλη είναι ψευδής, η τρίτη δεν δίνεται.
9. Ο νόμος της απορρόφησης μπορεί να γραφτεί με αυτόν τον τρόπο για τη λογική πρόσθεση: x v (x ^ y) = x, για τον πολλαπλασιασμό: x ^ (x v y) = x.
10. Ο νόμος της κόλλησης. Δύο γειτονικοί σύνδεσμοι μπορούν να κολλήσουν μεταξύ τους για να σχηματίσουν έναν σύνδεσμο χαμηλότερης κατάταξης. Σε αυτήν την περίπτωση, η μεταβλητή με την οποία κολλήθηκαν οι αρχικοί σύνδεσμοι εξαφανίζεται. Παράδειγμα λογικής προσθήκης:
(x^y) v (-x^y)=y.
Εξετάσαμε μόνο τους πιο χρησιμοποιούμενους νόμους της άλγεβρας της λογικής, οι οποίοι στην πραγματικότητα μπορεί να είναι πολλοί περισσότεροι, καθώς συχνά οι λογικές εξισώσεις παίρνουν μια μακρά και περίτεχνη μορφή, η οποία μπορεί να μειωθεί με την εφαρμογή αρκετών παρόμοιων νόμων.
Κατά κανόνα, χρησιμοποιούνται ειδικοί πίνακες για τη διευκόλυνση της καταμέτρησης και του προσδιορισμού των αποτελεσμάτων. Όλοι οι υπάρχοντες νόμοι της άλγεβρας της λογικής, του οποίου ο πίνακας έχει τη γενική δομή ενός ορθογωνίου πλέγματος, είναι ζωγραφισμένοι, κατανέμοντας κάθε μεταβλητή σε ξεχωριστό κελί. Όσο μεγαλύτερη είναι η εξίσωση, τόσο πιο εύκολο είναι να αντιμετωπιστεί η χρήση πινάκων.
Διακριτά Μαθηματικά: Μαθηματική Λογική
Διάλεξη 8
Ελαχιστοποίηση δυαδικών συναρτήσεων. Μέθοδος Quine-McCluskey
Νόμοι της Άλγεβρας Boole
Στη μαθηματική λογική ορίζεται μια ειδική άλγεβρα, η άλγεβρα Boole, που περιέχει τις πράξεις του λογικού πολλαπλασιασμού, της λογικής πρόσθεσης και της άρνησης ( ,+, - ), που επιτρέπουν ταυτόσημους μετασχηματισμούς λογικών παραστάσεων. Αυτοί οι νόμοι περιλαμβάνουνΝόμος της ανικανότητας (ομοιότητας)
Νόμος της ανταλλαξιμότητας
a b = b α
Δίκαιο συνεταιρισμού
α + (β + γ) = (α + β) + γ
α (β γ) = (α β) γ
Νόμοι για τη διανομή
Κατανομή του συνδέσμου σε σχέση με τον διαχωρισμό
A (b + c) = a b + a c
Κατανομή του διαχωρισμού σε σχέση με τον σύνδεσμο
A + b c = (a + b) (a + c)
Διπλός Αρνητικός Νόμος
Οι νόμοι του De Morgan
Νόμοι απορρόφησης
a + a b = a
a (a + b) = a
Νόμοι που ορίζουν ενέργειες με λογικές σταθερές 0 και 1
| a + 0 = a a 0 = 0 | a + 1 = 1 a 1 = α |
| 1 = 0 |
|
Η νομιμότητα όλων των νόμων που συζητήθηκαν παραπάνω μπορεί εύκολα να αποδειχθεί, για παράδειγμα, χρησιμοποιώντας πίνακες αλήθειας.
Πρόσθετοι νόμοι
Οι πρόσθετοι νόμοι της άλγεβρας Boole είναι συμπεράσματα των βασικών νόμων και είναι πολύ χρήσιμοι στην απλοποίηση της γραφής των λογικών συναρτήσεων.
Ο νόμος του δεσμού
Η απόδειξη αυτής της ταυτότητας πραγματοποιείται χρησιμοποιώντας τον πρώτο νόμο της κατανομής:
Η απόδειξη αυτής της ταυτότητας πραγματοποιείται χρησιμοποιώντας τον δεύτερο διανεμητικό νόμο:
Ο νόμος Blake-Poretsky
Εφαρμόζοντας τους νόμους της δράσης με λογικές σταθερές, αδυναμία και κόλληση, αυτή η ταυτότητα μπορεί να αποδειχθεί ως εξής:
Ο νόμος της συνέλιξης μιας λογικής έκφρασης
Αυτή η ταυτότητα μπορεί να αποδειχθεί χρησιμοποιώντας διαδοχικά τους νόμους της εργασίας με λογικές σταθερές, της κατανομής, της ανικανότητας και της κόλλησης:
Απλοποίηση Λογικών Συναρτήσεων
Για κανονικές μορφές αναπαράστασης συναρτήσεων, η έννοια της πολυπλοκότητας μιας συνάρτησης ορίζεται ως ο αριθμός των πρωταρχικών όρων σε μια τέτοια αναπαράσταση. Ονομάζονται μετασχηματισμοί κανονικής μορφής για τη μείωση της πολυπλοκότητας μιας συνάρτησης απλοποίηση . Για την απλοποίηση των λογικών συναρτήσεων, χρησιμοποιούνται όλοι οι νόμοι της άλγεβρας της λογικής.Καθήκοντα.
Απλοποιήστε το SDNF με τις ακόλουθες λειτουργίες:
1. (ένα σι) ντο
2. (ένα σι) ντο
Αντιπροσωπεύουμε τη συνάρτηση σε μια τέλεια διαζευκτική μορφή και την απλοποιούμε χρησιμοποιώντας τους νόμους της άλγεβρας της λογικής:
3.
Αντιπροσωπεύουμε τη συνάρτηση σε μια τέλεια διαζευκτική μορφή και την απλοποιούμε χρησιμοποιώντας τους νόμους της άλγεβρας της λογικής:
SDNF = 
Δεν είναι δυνατή η περαιτέρω απλοποίηση.
4. 
Αντιπροσωπεύουμε τη συνάρτηση σε μια τέλεια διαζευκτική μορφή και την απλοποιούμε χρησιμοποιώντας τους νόμους της άλγεβρας της λογικής:
SDNF =
5. 
Αντιπροσωπεύουμε τη συνάρτηση σε μια τέλεια διαζευκτική μορφή και την απλοποιούμε χρησιμοποιώντας τους νόμους της άλγεβρας της λογικής:
Μέθοδος Quine-McCluskey
Η ελαχιστοποίηση των λογικών συναρτήσεων μπορεί να πραγματοποιηθεί χρησιμοποιώντας τη μέθοδο Quine-McClussky, η οποία αποτελείται από τέσσερα βήματα:
Ας αναπαραστήσουμε τα σύνολα (συστατικά) στα οποία η συνάρτηση είναι αληθής με τη μορφή δυαδικών ισοδυνάμων.
Τακτοποιούμε τα δυαδικά ισοδύναμα ανά βαθμίδες (ανάλογα με τον αριθμό των μονάδων δυαδικών ισοδυνάμων) και κολλάμε (εφαρμόζουμε τον κανόνα κόλλησης στα αντίστοιχα συστατικά) σε γειτονικές βαθμίδες, λαμβάνοντας τα μέγιστα διαστήματα όσο το δυνατόν μεγαλύτερα. σημειώνουμε κάθε σετ που συμμετείχε στο κόλλημα. Μόνο αυτά τα σύνολα ή τα διαστήματα είναι κολλημένα μεταξύ τους, η διαφορά στα οποία έγκειται μόνο στην τιμή ενός ψηφίου: 001 και 000, 001- και 101-, κ.λπ.
Ας δημιουργήσουμε έναν πίνακα Quine, οι στήλες του οποίου αντιστοιχούν στα δυαδικά σύνολα αλήθειας της συνάρτησης και οι σειρές αντιστοιχούν στα μέγιστα διαστήματα. Αν το i-ο σύνολο καλύπτεται από το j-ο διάστημα, τότε ορίστε το 1 στη διασταύρωση της αντίστοιχης γραμμής και στήλης, διαφορετικά ορίστε 0 ή τίποτα.
Βρίσκουμε το ελάχιστο εξώφυλλο του πίνακα Quine, που αποτελείται από τον ελάχιστο αριθμό μέγιστων διαστημάτων που περιλαμβάνουν (καλύπτουν) όλα τα σύνολα στα οποία η συνάρτηση είναι αληθής.
Τα δυαδικά ισοδύναμα των αληθών συνόλων είναι τα εξής:
| 1 | 0001 |
| 3 | 0011 |
| 5 | 0101 |
| 7 | 0111 |
| 11 | 1011 |
| 13 | 1101 |
| 15 | 1111 |
Ας τακτοποιήσουμε τα δυαδικά σετ ανά βαθμίδες και ας κάνουμε κόλληση, όσο είναι δυνατόν
| 0001 | 00-1 | 0-1 |
| 0011 | 0-01 | --11 |
| 0101 | -011 | -1-1 |
| 0111 | 0-11 | |
| 1101 | -101 | |
| 1011 | 01-1 | |
| 1111 | 11-1 | |
| -111 | ||
| 1-11 |
Στη συνέχεια χτίζουμε έναν πίνακα Quine:
| 0001 | 0011 | 0101 | 0111 | 1011 | 1101 | 1111 |
|
| 0--1 | 1 | 1 | 1 | 1 | |||
| --11 | 1 | 1 | 1 | 1 | 1 |
||
| -1-1 | 1 | 1 | 1 | 1 |
Στον πίνακα μας, τα σύνολα 0001 και 1011 καλύπτονται με τον μόνο δυνατό τρόπο, επομένως, τα ελάχιστα διαστήματα που τα καλύπτουν ονομάζονται υποχρεωτικόςκαι μορφή πυρήνας επίστρωσης, επειδή πρέπει να περιλαμβάνεται σε οποιαδήποτε κάλυψη. Στον πίνακα, οι αντίστοιχες μονάδες είναι υπογραμμισμένες, τα διαστήματα (0- -1, -11) αποτελούν όχι μόνο τον πυρήνα της κάλυψης, αλλά καλύπτουν και ολόκληρο τον πίνακα Quine.
Έτσι, λάβαμε την ελάχιστη μορφή της διερευνούμενης συνάρτησης με τη μορφή:
MDNF = (0 - - 1, - - 1 1) = 
Ας δούμε μερικά παραδείγματα.
Καθήκοντα.
1. Βρείτε τις λειτουργίες MDNFφά1 =
στ1
| x1 x2 x3 x4 | |
| 0 0 0 0 | 0 |
| 0 0 0 1 | 1 |
| 0 0 1 0 | 1 |
| 0 0 1 1 | 1 |
| 0 1 0 0 | 1 |
| 0 1 0 1 | 0 |
| 0 1 1 0 | 0 |
| 0 1 1 1 | 1 |
| 1 0 0 0 | 0 |
| 1 0 0 1 | 1 |
| 1 0 1 0 | 1 |
| 1 0 1 1 | 1 |
| 1 1 0 0 | 0 |
| 1 1 0 1 | 1 |
| 1 1 1 0 | 0 |
| 1 1 1 1 | 1 |
Το τέλειο DNF της υπό μελέτη συνάρτησης έχει τη μορφή:
| 0001 | 00-1 | -0-1 |
| 0010 | -001 | -01- |
| 0100 | 001- | --11 |
| 0011 | -010 | 1-1 |
| 1010 | 0-11 | |
| 1001 | -011 | |
| 0111 | 101- | |
| 1011 | 10-1 | |
| 1101 | 1-01 | |
| 1111 | -111 | |
| 1-11 | ||
| 11-1 |
Η πρώτη στήλη περιέχει ένα σύνολο που δεν συμμετείχε σε καμία κόλληση - είναι το ίδιο το μέγιστο διάστημα 0100. Στην τρίτη στήλη, προστίθενται άλλα τέσσερα μέγιστα διαστήματα: (-0-1, -01-, -11, 1--1).
Κατασκευάζουμε ένα τραπέζι Quine:
| 0001 | 0010 | 0100 | 0011 | 1010 | 1001 | 0111 | 1011 | 1101 | 1111 |
|
| 0100 | 1 | |||||||||
| -0-1 | 1 | 1 | 1 | 1 | ||||||
| -01- | 1 | 1 | 1 | 1 | ||||||
| --11 | 1 | 1 | 1 | 1 |
||||||
| 1--1 | 1 | 1 | 1 | 1 |
Ας ορίσουμε τον πυρήνα της κάλυψης, ο οποίος θα περιλαμβάνει τα υποχρεωτικά διαστήματα:
(0100, -0-1, -01-, --11). Σε αυτήν την περίπτωση, ο πυρήνας κάλυψης καλύπτει ολόκληρο τον πίνακα ως σύνολο.
Η ελάχιστη διαζευκτική κανονική μορφή f1 έχει τη μορφή:
2. Βρείτε τις λειτουργίες MDNF φά 2( Χ 1, Χ 2, Χ 3), το οποίο παίρνει μεμονωμένες τιμές στα σύνολα 0,2,3,6 και 7.
Ας φτιάξουμε έναν πίνακα αλήθειας για φά2
| x1 x2 x3 | F2 |
| 0 0 0 | 1 |
| 0 0 1 | 0 |
| 0 1 0 | 1 |
| 0 1 1 | 1 |
| 1 0 0 | 0 |
| 1 0 1 | 0 |
| 1 1 0 | 1 |
| 1 1 1 | 1 |
SDNF =
Ας τακτοποιήσουμε τα δυαδικά σετ ανά βαθμίδες και ας πραγματοποιήσουμε την κόλληση:
| 000 | 0-0 | --0 |
| 010 | -00 | |
| 100 | -10 | |
| 110 | 1-0 | |
| 111 | 11- |
Ως αποτέλεσμα της κόλλησης, πήραμε μόνο δύο μέγιστα διαστήματα: (11-, --0). Χωρίς να κατασκευάσουμε τραπέζι Quine, είναι προφανές ότι σχηματίζουν ελάχιστη κάλυψη, αφού η διαγραφή οποιουδήποτε από αυτά τα διαστήματα θα οδηγήσει στην απώλεια συνόλων στα οποία η συνάρτηση f2(x1, x2, x3 ) αληθής. MDNF = x1 x2 +x3.
ΛΟΓΟΤΕΧΝΙΑ
Guseva A.I. Μαθαίνοντας την επιστήμη των υπολογιστών: εργασίες και μέθοδοι επίλυσής τους - M.: DIALOGUE-MEPhI, 2003.
Gorbatov V.A. Βασικές αρχές διακριτών μαθηματικών. - Μ.: Επιστήμη. Fizmatlit, 1999.-544s
Υπάρχουν πέντε νόμοι της άλγεβρας της λογικής:
1. Ο νόμος των μεμονωμένων στοιχείων
1*Χ=Χ
0*X=0
1+Χ=1
0 + Χ = Χ
Αυτός ο νόμος της άλγεβρας της λογικής προκύπτει άμεσα από τις παραπάνω εκφράσεις των αξιωμάτων της άλγεβρας της λογικής.
Οι δύο ανώτερες εκφράσεις μπορεί να είναι χρήσιμες κατά τη δημιουργία διακοπτών, επειδή εφαρμόζοντας ένα λογικό μηδέν ή ένα σε μία από τις εισόδους του στοιχείου "2I", μπορείτε είτε να περάσετε το σήμα στην έξοδο είτε να σχηματίσετε ένα μηδενικό δυναμικό στην έξοδο.
Η δεύτερη παραλλαγή χρήσης αυτών των εκφράσεων είναι η δυνατότητα επιλεκτικού μηδενισμού ορισμένων ψηφίων ενός πολυψήφιου αριθμού. Με την κατά bit εφαρμογή της λειτουργίας "AND", μπορείτε είτε να αφήσετε την προηγούμενη τιμή του ψηφίου είτε να την επαναφέρετε εφαρμόζοντας μια μονάδα ή μηδενικό δυναμικό στα αντίστοιχα ψηφία. Για παράδειγμα, απαιτείται επαναφορά των ψηφίων 6, 3 και 1. Τότε:
Στο παραπάνω παράδειγμα χρήσης των νόμων της άλγεβρας της λογικής, φαίνεται ξεκάθαρα ότι για να μηδενιστούν τα απαραίτητα ψηφία στη μάσκα (κατώτερος αριθμός), στη θέση των αντίστοιχων ψηφίων γράφονται μηδενικά και στα υπόλοιπα γράφονται ένα ψηφία. Στον αρχικό αριθμό (ανώτερος αριθμός), υπάρχουν μονάδες στη θέση των 6 και 1 ψηφίων. Μετά την εκτέλεση της λειτουργίας "AND", εμφανίζονται μηδενικά σε αυτά τα σημεία. Στη θέση του τρίτου ψηφίου στον αρχικό αριθμό είναι το μηδέν. Στον αριθμό που προκύπτει, το μηδέν υπάρχει επίσης σε αυτό το μέρος. Τα υπόλοιπα ψηφία, όπως απαιτείται από την κατάσταση του προβλήματος, δεν αλλάζουν.
Με τον ίδιο τρόπο, με τη βοήθεια του νόμου των μεμονωμένων στοιχείων, ενός από τους βασικούς νόμους της άλγεβρας της λογικής, μπορούμε να γράψουμε μονάδες στα ψηφία που χρειαζόμαστε. Σε αυτήν την περίπτωση, είναι απαραίτητο να χρησιμοποιηθούν οι δύο χαμηλότερες εκφράσεις του νόμου των μεμονωμένων στοιχείων. Με την κατά bit εφαρμογή της λειτουργίας "OR", μπορείτε είτε να αφήσετε την προηγούμενη τιμή του ψηφίου είτε να την επαναφέρετε εφαρμόζοντας μηδέν ή δυναμικό μονάδας στα αντίστοιχα ψηφία. Έστω ότι απαιτείται η εγγραφή μονάδων σε 7 και 6 bit ενός αριθμού. Τότε:
Εδώ στη μάσκα (κατώτερος αριθμός) έχουμε γράψει ένα στο έβδομο και το έκτο bit. Τα υπόλοιπα bit περιέχουν μηδενικά και, επομένως, δεν μπορούν να αλλάξουν την αρχική κατάσταση του αρχικού αριθμού, που βλέπουμε στον αριθμό που προκύπτει κάτω από τη γραμμή.
Η πρώτη και η τελευταία έκφραση του νόμου των μεμονωμένων στοιχείων επιτρέπουν τη χρήση με περισσότερες εισόδους ως λογικά στοιχεία με λιγότερες εισόδους. Για να γίνει αυτό, οι αχρησιμοποίητες είσοδοι στο κύκλωμα "AND" πρέπει να συνδεθούν σε μια πηγή ρεύματος, όπως φαίνεται στο Σχήμα 1:
Εικόνα 1. Σχέδιο "2I-NOT" που εφαρμόζεται στο λογικό στοιχείο "3I-NOT"
Ταυτόχρονα, οι αχρησιμοποίητες είσοδοι στο κύκλωμα "OR", σύμφωνα με το νόμο των μεμονωμένων στοιχείων, πρέπει να συνδεθούν στο κοινό καλώδιο του κυκλώματος, όπως φαίνεται στο σχήμα 2.
Σχήμα 2. Το κύκλωμα "NOT" υλοποιείται στο στοιχείο "2I-NOT".
Οι παρακάτω νόμοι της άλγεβρας της λογικής, που προέρχονται από τα αξιώματα της άλγεβρας της λογικής, είναι οι νόμοι της άρνησης.
2. Νόμοι άρνησης
ένα. Νόμος των Συμπληρωματικών Στοιχείων
Οι εκφράσεις αυτού του νόμου της άλγεβρας της λογικής χρησιμοποιούνται ευρέως για την ελαχιστοποίηση των λογικών κυκλωμάτων. Εάν είναι δυνατό να απομονωθούν τέτοιες υποεκφράσεις από τη γενική έκφραση μιας λογικής συνάρτησης, τότε είναι δυνατό να μειωθεί ο απαιτούμενος αριθμός εισόδων των στοιχείων του ψηφιακού κυκλώματος και μερικές φορές ακόμη και να μειωθεί ολόκληρη η έκφραση σε μια λογική σταθερά.
Ένας άλλος ευρέως χρησιμοποιούμενος νόμος της άλγεβρας της λογικής είναι ο νόμος της διπλής άρνησης.
σι. Δύο φορές όχι
Ο νόμος της διπλής άρνησης χρησιμοποιείται τόσο για την απλοποίηση λογικών εκφράσεων (και ως αποτέλεσμα της απλοποίησης και μείωσης του κόστους των ψηφιακών συνδυαστικών κυκλωμάτων), όσο και για την εξάλειψη της αντιστροφής των σημάτων μετά από λογικά στοιχεία όπως "2I-NOT" και "2OR- ΔΕΝ". Σε αυτή την περίπτωση, οι νόμοι της άλγεβρας της λογικής καθιστούν δυνατή την υλοποίηση δεδομένων ψηφιακών κυκλωμάτων χρησιμοποιώντας ένα περιορισμένο σύνολο λογικών στοιχείων.
ντο. Νόμος της Αρνητικής Λογικής
Ο νόμος της αρνητικής λογικής ισχύει για οποιονδήποτε αριθμό μεταβλητών. Αυτός ο νόμος της άλγεβρας της λογικής σας επιτρέπει να εφαρμόσετε χρησιμοποιώντας τα λογικά στοιχεία "OR" και αντίστροφα: να εφαρμόσετε τη λογική συνάρτηση "OR" χρησιμοποιώντας τα λογικά στοιχεία "AND". Αυτό είναι ιδιαίτερα χρήσιμο στα κυκλώματα TTL, καθώς είναι εύκολο να εφαρμοστούν πύλες AND, αλλά είναι μάλλον δύσκολο να εφαρμοστούν πύλες OR. Χάρη στον νόμο της αρνητικής λογικής, είναι δυνατή η εφαρμογή των στοιχείων "OR" στα λογικά στοιχεία "AND". Το σχήμα 3 δείχνει την υλοποίηση του λογικού στοιχείου "2OR" στο στοιχείο " " και δύο μετατροπείς.
Εικόνα 3. Λογικό στοιχείο "2OR" που εφαρμόζεται στο στοιχείο "2I-NOT" και δύο μετατροπείς
Το ίδιο μπορεί να ειπωθεί για το σχήμα στερέωσης "OR". Εάν είναι απαραίτητο, μπορεί να μετατραπεί σε "AND" τοποθέτησης χρησιμοποιώντας μετατροπείς στην είσοδο και στην έξοδο αυτού του κυκλώματος.
3. Συνδυαστικοί νόμοι
Οι συνδυαστικοί νόμοι της άλγεβρας της λογικής αντιστοιχούν σε μεγάλο βαθμό στους συνδυαστικούς νόμους της συνηθισμένης άλγεβρας, αλλά υπάρχουν και διαφορές.
ένα. νόμος ταυτολογίας (πολλαπλή επανάληψη)
Χ + Χ + Χ + Χ = ΧX * X * X * X = X
Αυτός ο νόμος της άλγεβρας της λογικής επιτρέπει λογικές πύλες με περισσότερες εισόδους να χρησιμοποιηθούν ως πύλες με λιγότερες εισόδους. Για παράδειγμα, μπορείτε να εφαρμόσετε ένα κύκλωμα δύο εισόδων "2I" σε ένα λογικό στοιχείο "3I", όπως φαίνεται στο Σχήμα 4:
Εικόνα 4. Σχέδιο "2I-NOT" που εφαρμόζεται στο λογικό στοιχείο "3I-NOT"
ή χρησιμοποιήστε το κύκλωμα "2NAND-NOT" ως κανονικό μετατροπέα, όπως φαίνεται στην Εικόνα 5:
Εικόνα 5. Κύκλωμα "NOT" που υλοποιείται στο λογικό στοιχείο "2I-NOT"
Ωστόσο, θα πρέπει να προειδοποιηθεί ότι ο συνδυασμός πολλών εισόδων αυξάνει τα ρεύματα εισόδου του λογικού στοιχείου και τη χωρητικότητά του, γεγονός που αυξάνει την κατανάλωση ρεύματος των προηγούμενων στοιχείων και επηρεάζει αρνητικά την ταχύτητα του ψηφιακού κυκλώματος στο σύνολό του.
Για να μειώσετε τον αριθμό των εισόδων σε ένα λογικό στοιχείο, είναι καλύτερο να χρησιμοποιήσετε έναν άλλο νόμο της άλγεβρας της λογικής - τον νόμο των μεμονωμένων στοιχείων, όπως φαίνεται παραπάνω.
Συνεχίζουμε την εξέταση των νόμων της άλγεβρας της λογικής:
σι. νόμος της κινητικότητας
Α + Β + Γ + Δ = Α + Γ + Β + Δντο. νόμος συνδυασμού
Α + Β + Γ + Δ = Α + (Β + Γ) + Δ = Α + Β + (Γ + Δ)ρε. νόμος διανομής
X1(X2 + X3) = X1X2 + X1X3 X1 + X2X3 = (X1 + X2)(X1 + X3) = /ας το αποδείξουμε επεκτείνοντας τις αγκύλες/ == X1X1 + X1X3 + X1X2 + X2X3 = X1(1 + X3 + X2) + X2X3 = X1 + X2X3
4. Κανόνας απορρόφησης (μία μεταβλητή απορροφά άλλες)
Χ1 + Χ1Χ2Χ3 =Χ1(1 + Χ2Χ3) = Χ15. Κανόνας κόλλησης (εκτελείται μόνο από μία μεταβλητή)
Όπως και στα συνηθισμένα μαθηματικά, στην άλγεβρα της λογικής υπάρχει προτεραιότητα των πράξεων. Αυτό γίνεται πρώτα:
- Ενέργεια σε παρένθεση
- Λειτουργία με έναν τελεστή (μία λειτουργία) - "NOT"
- Σύνδεσμος - "και"
- Disjunction - "OR"
- Άθροισμα δύο.
Πράξεις της ίδιας τάξης εκτελούνται από αριστερά προς τα δεξιά με τη σειρά που γράφεται η λογική έκφραση. Η άλγεβρα της λογικής είναι γραμμική και ισχύει για αυτήν η αρχή της υπέρθεσης.
Λογοτεχνία:
Μαζί με το άρθρο «Νόμοι της άλγεβρας της λογικής» διαβάζουν:
Οποιοδήποτε λογικό κύκλωμα χωρίς μνήμη περιγράφεται πλήρως από έναν πίνακα αλήθειας... Για να εφαρμόσετε έναν πίνακα αλήθειας, αρκεί να λάβετε υπόψη μόνο αυτές τις γραμμές...
http://website/digital/SintSxem.php
Οι αποκωδικοποιητές (αποκωδικοποιητές) σας επιτρέπουν να μετατρέψετε έναν τύπο δυαδικού κώδικα σε έναν άλλο. Για παράδειγμα...
http://website/digital/DC.php
Πολύ συχνά, οι προγραμματιστές ψηφιακού εξοπλισμού αντιμετωπίζουν το αντίθετο πρόβλημα. Θέλετε να μετατρέψετε έναν οκταδικό ή δεκαδικό κωδικό σε...
http://website/digital/coder.php
Οι πολυπλέκτης είναι συσκευές που σας επιτρέπουν να συνδέσετε πολλές εισόδους σε μία έξοδο ...
http://website/digital/MS.php
Οι συσκευές ονομάζονται αποπολυπλέκτες ... Μια σημαντική διαφορά από έναν πολυπλέκτη είναι ...
http://website/digital/DMS.php
Για να μετασχηματίσετε συναρτήσεις, να απλοποιήσετε τους τύπους που λαμβάνονται με την επισημοποίηση των συνθηκών των λογικών προβλημάτων, πραγματοποιούνται ισοδύναμοι μετασχηματισμοί στην άλγεβρα της λογικής, με βάση τους βασικούς λογικούς νόμους. Μερικοί από αυτούς τους νόμους διατυπώνονται και γράφονται με τον ίδιο τρόπο με παρόμοιους νόμους στην αριθμητική και την άλγεβρα, άλλοι φαίνονται ασυνήθιστοι.
Οι νόμοι της άλγεβρας της λογικής ονομάζονται μερικές φορές θεωρήματα.
Στην προτασιακή άλγεβρα, οι λογικοί νόμοι εκφράζονται ως ισότητα ισοδύναμων τύπων.
Η εγκυρότητα όλων των νόμων μπορεί να επαληθευτεί με την κατασκευή πινάκων αλήθειας για το αριστερό και το δεξί μέρος του γραπτού νόμου. Μετά την απλοποίηση της έκφρασης χρησιμοποιώντας τους νόμους της άλγεβρας της λογικής, οι πίνακες αλήθειας είναι οι ίδιοι.
Η εγκυρότητα ορισμένων νόμων μπορεί να αποδειχθεί χρησιμοποιώντας τα εργαλεία των πινάκων αλήθειας.
Εικόνα 1.
Παραδείγματα
Εικόνα 3
Ας απλοποιήσουμε την αρχική έκφραση χρησιμοποιώντας τους βασικούς νόμους της άλγεβρας της λογικής:
Εικόνα 4
(Νόμος του De Morgan, διανεμητικός νόμος για το ΚΑΙ, νόμος της ανικανότητας, λειτουργία μεταβλητής με την αντιστροφή της).
Ο πίνακας δείχνει ότι για όλα τα σύνολα τιμών των μεταβλητών $x$ και $y$, ο τύπος στο Σχήμα 2 παίρνει την τιμή $1$, δηλαδή είναι πανομοιότυπα αληθής.
Εικόνα 6
Από τον πίνακα φαίνεται ότι η έκφραση Source παίρνει τις ίδιες τιμές με την Απλοποιημένη έκφραση στις αντίστοιχες τιμές των μεταβλητών $x$ και $y$.
Ας απλοποιήσουμε την έκφραση στο Σχ. 5 εφαρμόζοντας τους βασικούς νόμους της άλγεβρας της λογικής.
Εικόνα 7
(νόμος De Morgan, νόμος απορρόφησης, νόμος διανομής για το I).
Εικόνα 9
Ο πίνακας δείχνει ότι για όλα τα σύνολα τιμών των μεταβλητών $x$ και $y$, ο τύπος στο Σχήμα 8 παίρνει την τιμή $0$, δηλαδή είναι πανομοιότυπα ψευδής.
Ας απλοποιήσουμε την έκφραση εφαρμόζοντας τους νόμους της άλγεβρας της λογικής:
Εικόνα 10.
Εικόνα 12.
(νόμος De Mogrgan, διανεμητικός).
Ας φτιάξουμε έναν πίνακα αλήθειας για την έκφραση στο Σχ. 11:
Εικόνα 13.
Μπορεί να φανεί από τον πίνακα ότι η έκφραση στο Σχ. 11 σε ορισμένες περιπτώσεις παίρνει την τιμή $1$, και σε ορισμένες - $0$, δηλαδή, είναι εφικτή.
(κανόνας de Morgan, βγάζουμε τον κοινό παράγοντα, τον κανόνα των πράξεων μιας μεταβλητής με την αντιστροφή της).
(ο δεύτερος παράγοντας επαναλαμβάνεται, κάτι που είναι δυνατό με χρήση του νόμου του idempotent· μετά συνδυάζονται οι δύο πρώτοι και οι δύο τελευταίοι παράγοντες και χρησιμοποιείται ο νόμος της κόλλησης).
(εισάγουμε έναν βοηθητικό λογικό παράγοντα
Νόμοι της Προτασιακής Άλγεβρας
Η άλγεβρα προτάσεων (άλγεβρα λογικής) είναι ένα τμήμα της μαθηματικής λογικής που μελετά τις λογικές πράξεις σε προτάσεις και τους κανόνες μετασχηματισμού σύνθετων προτάσεων.
Κατά την επίλυση πολλών λογικών προβλημάτων, είναι συχνά απαραίτητο να απλοποιηθούν οι τύποι που λαμβάνονται με την επισημοποίηση των συνθηκών τους. Η απλοποίηση των τύπων στην άλγεβρα των προτάσεων πραγματοποιείται με βάση ισοδύναμους μετασχηματισμούς που βασίζονται στους βασικούς λογικούς νόμους.
Νόμοι της προτασιακής άλγεβρας (άλγεβρα της λογικής) είναι ταυτολογίες.
Μερικές φορές αυτοί οι νόμοι ονομάζονται θεωρήματα.
Στην προτασιακή άλγεβρα, οι λογικοί νόμοι εκφράζονται ως ισότητα ισοδύναμων τύπων. Μεταξύ των νόμων διακρίνονται ιδιαίτερα εκείνοι που περιέχουν μία μεταβλητή.
Οι τέσσερις πρώτοι από τους παρακάτω νόμους είναι οι βασικοί νόμοι της προτασιακής άλγεβρας.
Νόμος ταυτότητας:
Α=Α
Κάθε έννοια και κρίση είναι πανομοιότυπη με τον εαυτό της.
Ο νόμος της ταυτότητας σημαίνει ότι στη διαδικασία του συλλογισμού δεν μπορεί κανείς να αντικαταστήσει μια σκέψη με μια άλλη, μια έννοια με μια άλλη. Εάν παραβιαστεί αυτός ο νόμος, είναι πιθανά λογικά σφάλματα.
Για παράδειγμα, ο συλλογισμός Σωστά λέει ότι η γλώσσα θα σας φέρει στο Κίεβο, αλλά αγόρασα μια καπνιστή γλώσσα χθες, πράγμα που σημαίνει ότι τώρα μπορώ να πάω με ασφάλεια στο Κίεβο λανθασμένα, καθώς η πρώτη και η δεύτερη λέξη "γλώσσα" υποδηλώνουν διαφορετικές έννοιες.
Στο συλλογισμό: Η κίνηση είναι αιώνια. Το να πηγαίνεις στο σχολείο είναι κίνηση. Επομένως, πηγαίνοντας στο σχολείο για πάντα, η λέξη "κίνηση" χρησιμοποιείται με δύο διαφορετικές έννοιες (η πρώτη - με τη φιλοσοφική έννοια - ως χαρακτηριστικό της ύλης, η δεύτερη - με τη συνηθισμένη έννοια - ως μια ενέργεια για κίνηση στο διάστημα), η οποία οδηγεί σε ψευδές συμπέρασμα.
Νόμος της μη αντίφασης :
Την ίδια στιγμή, η δήλωση μπορεί να είναι είτε αληθινή είτε ψευδής, δεν υπάρχει τρίτο. Είτε το Α είναι αληθές είτε όχι το Α. Παραδείγματα εφαρμογής του νόμου της εξαιρούμενης μέσης:
1. Ο αριθμός 12345 είναι είτε άρτιος είτε μονός, ο τρίτος δεν δίνεται.
2. Η εταιρεία λειτουργεί με ζημιές ή ζημία.
3. Αυτό το υγρό μπορεί να είναι οξύ ή όχι.
Ο νόμος του αποκλεισμένου μέσου δεν είναι νόμος που αναγνωρίζεται από όλους τους λογικούς ως παγκόσμιος νόμος της λογικής. Αυτός ο νόμος εφαρμόζεται όταν η γνώση ασχολείται με μια άκαμπτη κατάσταση: "είτε-ή", "αληθές-λάθος". Όπου υπάρχει αβεβαιότητα (για παράδειγμα, στο συλλογισμό για το μέλλον), ο νόμος της εξαιρούμενης μέσης συχνά δεν μπορεί να εφαρμοστεί.
Σκεφτείτε την ακόλουθη πρόταση: Αυτή η πρόταση είναι λανθασμένη. Δεν μπορεί να είναι αληθινό γιατί ισχυρίζεται ότι είναι ψευδές. Αλλά δεν μπορεί να είναι ούτε ψευδές, γιατί τότε θα ήταν αλήθεια. Αυτή η δήλωση δεν είναι ούτε αληθής ούτε ψευδής, και ως εκ τούτου παραβιάζεται ο νόμος του εξαιρούμενου μέσου.
Το παράδοξο (ελληνικά paradoxos - απροσδόκητο, περίεργο) σε αυτό το παράδειγμα προκύπτει από το γεγονός ότι η πρόταση αναφέρεται στον εαυτό της. Ένα άλλο γνωστό παράδοξο είναι το πρόβλημα του κουρέα: Σε μια πόλη, ο κουρέας κόβει τα μαλλιά όλων των κατοίκων, εκτός από αυτούς που κουρεύουν μόνοι τους. Ποιος κόβει τα μαλλιά του κουρέα; Στη λογική, λόγω της τυπικότητάς της, δεν είναι δυνατό να ληφθεί η μορφή μιας τέτοιας αυτοαναφορικής δήλωσης. Αυτό επιβεβαιώνει για άλλη μια φορά την ιδέα ότι με τη βοήθεια της άλγεβρας της λογικής είναι αδύνατο να εκφραστούν όλες οι πιθανές σκέψεις και επιχειρήματα. Ας δείξουμε πώς, με βάση τον ορισμό της προτασιακής ισοδυναμίας, μπορούν να ληφθούν οι υπόλοιποι νόμοι της προτασιακής άλγεβρας.
Για παράδειγμα, ας προσδιορίσουμε τι είναι ισοδύναμο (ισοδύναμο) Α (διπλή άρνηση Α, δηλαδή άρνηση της άρνησης Α). Για να γίνει αυτό, θα δημιουργήσουμε έναν πίνακα αλήθειας:
Εξ ορισμού της ισοδυναμίας, πρέπει να βρούμε τη στήλη της οποίας οι τιμές ταιριάζουν με τις τιμές της στήλης Α. Αυτή θα είναι η στήλη Α.
Έτσι, μπορούμε να διατυπώσουμε τον νόμο της διπλής άρνησης:
Αν αρνηθούμε κάποια πρόταση δύο φορές, τότε το αποτέλεσμα είναι η αρχική πρόταση. Για παράδειγμα, η δήλωση A = Matroskin - γάταισοδυναμεί με το Α = Δεν είναι αλήθεια ότι ο Matroskin δεν είναι γάτα.
Ομοίως, οι ακόλουθοι νόμοι μπορούν να εξαχθούν και να επαληθευτούν:
Σταθερές ιδιότητες:
Νόμοι της ανικανότητας:
Όσες φορές κι αν επαναλάβουμε: η τηλεόραση είναι ανοιχτή ή η τηλεόραση ή η τηλεόραση είναι ανοιχτή... το νόημα της δήλωσης δεν θα αλλάξει. Ομοίως, από την επανάληψη είναι ζεστό έξω, είναι ζεστό έξω, ... δεν θα γίνει ένα βαθμό πιο ζεστό.
Οι νόμοι της ανταλλαγής:
A v B = B v A
A & B = B & A
Οι τελεστές Α και Β στις πράξεις του διαχωρισμού και του συνδέσμου μπορούν να εναλλάσσονται.
Συνεταιριστικοί νόμοι:
A v(B v C) = (A v B) v C;
A & (B & C) = (A & B) & C.
Εάν η έκφραση χρησιμοποιεί μόνο τη λειτουργία διαχωρισμού ή μόνο τη λειτουργία σύνδεσης, τότε μπορείτε να παραμελήσετε τις αγκύλες ή να τις τακτοποιήσετε αυθαίρετα.
Νόμοι για τη διανομή:
A v (B & C) = (A v B) & (A v C)
(διανεμητικός διαχωρισμός
σχετικά με τη σύνδεση)
A & (B v C) = (A & B) v (A & C)
(κατανομή του συνδέσμου
σχετικά με τη διάσπαση)
Ο κατανεμητικός νόμος του συνδέσμου ως προς τη διάζευξη είναι παρόμοιος με τον κατανεμητικό νόμο στην άλγεβρα, αλλά ο νόμος του κατανεμητικού διαχωρισμού ως προς τον σύνδεσμο δεν έχει ανάλογο, ισχύει μόνο στη λογική. Επομένως, πρέπει να αποδειχθεί. Η απόδειξη γίνεται καλύτερα χρησιμοποιώντας έναν πίνακα αλήθειας:
Νόμοι απορρόφησης:
A v (A & B) = A
A & (A v B) = A
Πραγματοποιήστε μόνοι σας την απόδειξη των νόμων απορρόφησης.
Οι νόμοι του De Morgan:
Προφορικές διατυπώσεις των νόμων του de Morgan:
Μνημονικός κανόνας: στην αριστερή πλευρά της ταυτότητας, η λειτουργία άρνησης βρίσκεται πάνω από ολόκληρη τη δήλωση. Στη δεξιά πλευρά, φαίνεται να έχει σπάσει και η άρνηση στέκεται πάνω από κάθε μία από τις απλές προτάσεις, αλλά ταυτόχρονα αλλάζει η πράξη: διαχωρισμός σε σύνδεσμο και αντίστροφα.
Παραδείγματα εφαρμογής του νόμου του de Morgan:
1) Η δήλωση Δεν είναι αλήθεια ότι ξέρω αραβικά ή κινέζικα είναι πανομοιότυπη με τη δήλωση δεν ξέρω αραβικά και δεν ξέρω κινέζικα.
2) Η δήλωση Δεν είναι αλήθεια ότι έμαθα το μάθημα και πήρα ένα δισάκι γιατί είναι πανομοιότυπο με τη δήλωση Είτε δεν έμαθα το μάθημα, είτε δεν πήρα ένα δισάκι για αυτό.
Αντικατάσταση συνεπειών και πράξεων ισοδυναμίας
Οι πράξεις συνεπαγωγής και ισοδυναμίας μερικές φορές δεν περιλαμβάνονται στις λογικές λειτουργίες ενός συγκεκριμένου υπολογιστή ή μεταγλωττιστή από μια γλώσσα προγραμματισμού. Ωστόσο, αυτές οι λειτουργίες είναι απαραίτητες για την επίλυση πολλών προβλημάτων. Υπάρχουν κανόνες για την αντικατάσταση αυτών των πράξεων με ακολουθίες πράξεων άρνησης, διαχωρισμού και συνδέσμου.
Έτσι, μπορείτε να αντικαταστήσετε τη λειτουργία υπονοούμενων σύμφωνα με τον ακόλουθο κανόνα:
Υπάρχουν δύο κανόνες για την αντικατάσταση της πράξης ισοδυναμίας:
Είναι εύκολο να επαληθευτεί η εγκυρότητα αυτών των τύπων κατασκευάζοντας πίνακες αλήθειας για τη δεξιά και την αριστερή πλευρά και των δύο ταυτοτήτων.
Η γνώση των κανόνων για την αντικατάσταση των πράξεων συνεπαγωγής και ισοδυναμίας βοηθά, για παράδειγμα, στη σωστή κατασκευή της άρνησης μιας συνεπαγωγής.
Εξετάστε το ακόλουθο παράδειγμα.
Ας δοθεί η δήλωση:
Ε = Δεν είναι αλήθεια ότι αν κερδίσω τον διαγωνισμό, θα πάρω βραβείο.
Αφήνω Α = Θα κερδίσω τον διαγωνισμό,
Β = Θα λάβω ένα έπαθλο.
Τότε
Από εδώ, Ε = Θα κερδίσω τον διαγωνισμό, αλλά δεν θα λάβω έπαθλο.