Υπολογιστής Άλγεβρας Μπουλ

Ένας υπολογιστής άλγεβρας Boolean αξιολογεί και απλοποιεί λογικές εκφράσεις χρησιμοποιώντας τους κανόνες της άλγεβρας Boolean.

Δημιουργεί πίνακες αληθείας που εμφανίζουν κάθε συνδυασμό εισόδου/εξόδου, εντοπίζει τους ελάχιστους και μέγιστους όρους (minterms και maxterms) και εφαρμόζει αλγόριθμους ελαχιστοποίησης όπως ο Quine-McCluskey για την εύρεση της απλούστερης ισοδύναμης έκφρασης.

Αυτός ο υπολογιστής δέχεται πολλαπλά στυλ συμβολισμού:

• AND (*, ·, AND, &&)
• OR (+, OR, ||)
• NOT (', !, ~, NOT)
• XOR (^, XOR)
• NAND
• NOR
• XNOR

Οι μεταβλητές είναι μεμονωμένα γράμματα από το A έως το D. Υποστηρίζονται παρενθέσεις για ομαδοποίηση.

Παραδείγματα: A*B+C', (A OR B) AND NOT C, A NAND B.

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

Ξεκινήστε με τους νόμους ταυτότητας και συμπληρώματος (A + A' = 1, A · A' = 0), στη συνέχεια χρησιμοποιήστε την απορρόφηση (A + A·B = A) και την επιμεριστική ιδιότητα για την εξαγωγή κοινών μεταβλητών. Τα θεωρήματα De Morgan μετατρέπουν συμπληρωματικές ομάδες, ενώ το θεώρημα συναίνεσης αφαιρεί τους περιττούς όρους. Για ένα συστηματικό αποτέλεσμα, καταγράψτε τους ελάχιστους όρους (minterms) και συνδυάστε εκείνους που διαφέρουν κατά ένα bit.

Όπως εισήγαγε ο George Boole στο έργο του το 1854, σύμφωνα με την Encyclopaedia Britannica, αυτοί οι νόμοι σχηματίζουν μια κλειστή άλγεβρα όπου κάθε έκφραση μπορεί να αναχθεί σε μια ελάχιστη μορφή (όχι πάντα μοναδική). Αυτός ο υπολογιστής εμφανίζει κάθε κανόνα που εφαρμόζεται στη σειρά.

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

Για n μεταβλητές υπάρχουν 2^n γραμμές, επομένως δύο μεταβλητές παράγουν 4 γραμμές και τέσσερις μεταβλητές παράγουν 16 γραμμές. Αντίστροφα, ο αριθμός των μεταβλητών ισούται με τον λογάριθμο με βάση το 2 του πλήθους των γραμμών, τον οποίο ο υπολογιστής λογαρίθμων μας μπορεί να αξιολογήσει για μεγαλύτερες συναρτήσεις. Ταξινομήστε τις εισόδους σε τυπική δυαδική ακολουθία μέτρησης (00, 01, 10, 11) και υπολογίστε την έκφραση για κάθε γραμμή.

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

Το Άθροισμα Προϊόντων (SOP) εκφράζει μια συνάρτηση Boole ως μια πύλη OR όρων AND, έναν ελάχιστο όρο (minterm) για κάθε γραμμή όπου η έξοδος ισούται με 1. Το Προϊόν Αθροισμάτων (POS) είναι το δυϊκό του: μια πύλη AND όρων OR, ένας μέγιστος όρος (maxterm) για κάθε γραμμή όπου η έξοδος ισούται με 0.

Και οι δύο είναι κανονικές μορφές που περιγράφουν την ίδια συνάρτηση και οποιαδήποτε από τις δύο μπορεί να ελαχιστοποιηθεί. Τα εγχειρίδια ψηφιακού σχεδιασμού, όπως αυτά που αναφέρονται στο All About Circuits, σημειώνουν ότι το SOP αντιστοιχίζεται φυσικά σε δίκτυα πυλών δύο επιπέδων AND-OR, ενώ το POS αντιστοιχίζεται σε δίκτυα OR-AND.

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

Ένας χάρτης Karnaugh είναι ένα πλέγμα που διατάσσει τις εξόδους του πίνακα αληθείας έτσι ώστε τα φυσικά γειτονικά κελιά να διαφέρουν κατά μία ακριβώς μεταβλητή, χρησιμοποιώντας διάταξη κώδικα Gray (00, 01, 11, 10).

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

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

Η μέθοδος Quine-McCluskey είναι μια πινακοειδής διαδικασία που εγγυάται το ελάχιστο Άθροισμα Προϊόντων, καθιστώντας τη πιο αξιόπιστη από τους χάρτες Karnaugh για συναρτήσεις με πολλές μεταβλητές.

Παραθέτει κάθε minterm σε δυαδική μορφή, τα ομαδοποιεί με βάση τον αριθμό των ψηφίων 1, και στη συνέχεια συνδυάζει κατ' επανάληψη όρους που διαφέρουν κατά ένα μόνο ψηφίο, σημειώνοντας την αφαίρεση με μια παύλα. Οι όροι που δεν μπορούν να συνδυαστούν περαιτέρω είναι οι πρώτοι συνεπαγωγείς (prime implicants). Στη συνέχεια, ένας πίνακας πρώτων συνεπαγωγέων επιλέγει το μικρότερο σύνολο ουσιωδών πρώτων συνεπαγωγέων που καλύπτει όλα τα minterms.

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

Τα θεωρήματα De Morgan ορίζουν ότι (A·B)' = A' + B' και (A+B)' = A'·B' — το συμπλήρωμα μιας ομάδας αντιστρέφει τον τελεστή και συμπληρώνει κάθε μεταβλητή. Αυτοί οι νόμοι αποτελούν τη βάση για τη μετατροπή οποιουδήποτε κυκλώματος σε μορφή αποκλειστικά με πύλες NAND ή NOR.

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

Ο υπολογιστής εφαρμόζει αυτόματα τους νόμους του De Morgan όταν εισάγετε τελεστές NAND, NOR ή XNOR, εμφανίζοντας την ισοδύναμη ανάπτυξη AND/OR/NOT.

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

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

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

Η απλοποίηση εκφράσεων Boole ενέχει ορισμένα συχνά λάθη:

• Το πιο συνηθισμένο λάθος είναι η σύγχυση της πύλης OR (+) με την αριθμητική πρόσθεση — στην άλγεβρα Boole 1 + 1 = 1, όχι 2.
• Ένα άλλο λάθος είναι η παράλειψη παρενθέσεων, η οποία αλλάζει την προτεραιότητα των τελεστών και παράγει διαφορετική συνάρτηση· η NOT έχει την υψηλότερη προτεραιότητα, μετά η AND, και μετά η OR.
• Οι φοιτητές συχνά σταματούν την απλοποίηση πολύ νωρίς, χάνοντας έναν όρο συναίνεσης (consensus term) ή μια απορρόφηση που αφαιρεί μια ολόκληρη μεταβλητή, ή πολύ αργά, υπερ-παραγοντοποιώντας σε μια μεγαλύτερη έκφραση.
• Η εσφαλμένη σειρά των στηλών στον χάρτη Karnaugh (χρησιμοποιώντας δυαδικό 00, 01, 10, 11 αντί για κώδικα Gray 00, 01, 11, 10) καταστρέφει τη γειτνίαση και οδηγεί σε λανθασμένες ομαδοποιήσεις.

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

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

Έτσι το A + B·C σημαίνει A OR (B AND C), και το A·B' σημαίνει A AND (NOT B), όχι (A AND B)'. Η XOR συνήθως αντιμετωπίζεται στο ίδιο επίπεδο με την AND ή χαμηλότερα, επομένως συνιστώνται παρενθέσεις κάθε φορά που η XOR συνδυάζεται με άλλους τελεστές για να αποφευχθεί η ασαφήεια.

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