Μια δυαδική μεταβλητή μπορεί να πάρει την τιμή 0 ή 1. Μια συνάρτηση Boole μπορεί να γραφεί σαν μια αλγεβρική έκφραση που σχηματίζεται από δυαδικές μεταβλητές, τους δυο δυαδικούς τελεστές OR και AND τον τελεστή ΝΟΤ και παρενθέσεις. Για μια δεδομένη τιμή των μεταβλητών, η συνάρτηση μπορεί να είναι είτε 0 είτε 1.
Κάθε συνάρτηση Boole, πέρα από την αλγεβρική έκφραση της, μπορεί να παρασταθεί με ένα πίνακα αληθείας. Ο αριθμός των γραμμών στον πίνακα είναι 2n, όπου n ο αριθμός των ανεξάρτητων δυαδικών μεταβλητών στη συνάρτηση. Οι συνδυασμοί 1 και 0 για κάθε γραμμή βγαίνουν εύκολα από τους δυαδικούς αριθμούς, μετρώντας από το 0 ως το 2n-1. Για κάθε γραμμή του πίνακα υπάρχει μια τιμή για τη συνάρτηση.
Υπάρχουν περιπτώσεις που ή ίδια συνάρτηση Boole μπορεί να περιγραφεί από διαφορετικές αλγεβρικές εκφράσεις Boole. Εδώ συμβαίνει η σημαντικότερη εφαρμογή της άλγεβρας Boole. Είναι το πρόβλημα της εύρεσης απλούστερων εκφράσεων για την ίδια συνάρτηση.
Για παράδειγμα θεωρούμε τις δυο συναρτήσεις Boole, όπου στο σχήμα φαίνονται οι πίνακες αληθείας τους.
F1=x’y’z+x’yz+xy’ και F2=xy’+x’z
Από τους πινάκες αληθείας τους βρίσκουμε ότι η F1 είναι ίδια με τη F2 εφόσον ταυτίζονται τα 1 και 0 τους για κάθε συνδυασμό τιμών των τριών μεταβλητών τους. Γενικά, δυο συναρτήσεις n δυαδικών μεταβλητών λέγονται ίσες, αν παίρνουν την ίδια τιμή και για τους 2n δυνατούς συνδυασμούς των n μεταβλητών.
Μια συνάρτηση Boole μπορεί να μετασχηματιστεί από αλγεβρική έκφραση σ’ ένα διάγραμμα (κύκλωμα) αποτελούμενο από πύλες AND, OR και ΝΟΤ. Η υλοποίηση των δυο συναρτήσεων που είδαμε παραπάνω δίνεται στο ακόλουθο σχήμα. Το διάγραμμα περιλαμβάνει ένα αντιστροφέα για κάθε μεταβλητή της οποίας χρειαζόμαστε το συμπλήρωμα. Υπάρχει μια πύλη AND για κάθε «γινόμενο» μέσα στην έκφραση και μια πύλη OR χρησιμοποιείται για να συνδυάσει δυο ή περισσότερα «γινόμενα».
Από τα διαγράμματα είναι προφανές ότι η υλοποίηση της F2 απαιτεί λιγότερες πύλες, με λιγότερες εισόδους από ότι η υλοποίηση της F1. Εφόσον η F1 και F2 είναι ίσες η μια με την άλλη, συμφέρει περισσότερο να χρησιμοποιήσουμε τη μορφή F2 παρά την F1. Για να βρίσκουμε απλούστερα κυκλώματα που να μας κάνουν την ίδια δουλειά, πρέπει να ξέρουμε πώς να μετατρέπουμε τις συναρτήσεις Boole, έτσι ώστε να βρίσκουμε ισοδύναμες και απλούστερες εκφράσεις. Τώρα, το ποια μορφή μιας συνάρτησης Boole είναι «καλύτερη» και το ποια είναι «χειρότερη», εξαρτάται από την συγκεκριμένη εφαρμογή. Αυτή την στιγμή εμείς εδώ χρησιμοποιούμε το κριτήριο της ελαχιστοποίησης των εξαρτημάτων.
Παράδειγμα
Χρησιμοποιώντας αλγεβρικούς μετασχηματισμούς, απλοποιείστε τις ακόλουθες συναρτήσεις σε έναν ελάχιστο αριθμό «παραγόντων»
1] x + x’y = (x + x’)(x + y) = 1‧(x + y) = x + y
2] x(x’ +y) = xx’ + xy =0 + xy = xy
3] x’y’z + x’yz + xy’ = x’z(y’ + y) + xy’ = x’z + xy’
4] xy +x’z +yz = xy +x’z + yz(x + x’) = xy + x’z + xyz + x’yz = xy(1 + z) + x’z(1 + y) = xy + x’z
5] (x + y)(x’ + z)(y + z) = (x + y)(x’ + z) λόγω δυϊσμού από την συνάρτηση 4.
Οι συναρτήσεις 1 και 2 είναι δυϊκές η μια της άλλης και χρησιμοποιούν δυϊκές εκφράσεις στα αντίστοιχα βήματα. Στο 3 βλέπουμε μιαν απόδειξη της ισότητας των F1 και F2 που αναφέραμε παραπάνω. Στο 4 βλέπουμε ένα παράδειγμα περίπτωσης όπου μια αύξηση του αριθμού των «παραγόντων» μπορεί τελικά να οδηγήσει σε απλούστευση της αρχικής έκφρασης. Στο 5, αντί να κάνουμε την απλοποίηση κανονικά, χρησιμοποιούμε το δυϊκό της 4.
Συμπλήρωμα συνάρτησης
Το συμπλήρωμα μιας συνάρτησης F, που συμβολίζεται με το F’, είναι η συνάρτηση εκείνη που ισούται με 0, όταν F=1 και με 1 όταν F=0. Το συμπλήρωμα μιας συνάρτησης μπορεί να βγει αλγεβρικά, χρησιμοποιώντας το θεώρημα De Morgan, όπως το παρουσιάσαμε σε προηγούμενη ενότητα για δυο μεταβλητές.
Αποδεικνύεται ότι το ζευγάρι των εξισώσεων για δυο ή περισσότερες μεταβλητές, μπορεί να εκφραστεί με το ακόλουθο ζευγάρι εξισώσεων:
(A + B + C + D + … +F)’ = A’B’C’D’‧‧‧F’
(ABCD ‧‧‧ F)’ = A’ + B’ + C’ + D’ + … + F’
Η γενικευμένη μορφή του θεωρήματος De Morgan λέει ότι το συμπλήρωμα μιας συνάρτησης μπορεί να βγει εναλλάσσοντας τα AND με τα OR και συμπληρώνοντας κάθε όρο (παράγοντα)
Παράδειγμα:
Βρείτε το συμπλήρωμα των συναρτήσεων:
1] F1 = x’yz’ +x’y’z και 2] F2 = x(y’z’ + yz)
Εφαρμόζοντας το θεώρημα De Morgan, όσες φορές χρειαστεί, τα συμπληρώματα βγαίνουν ως εξής:
F1’ = (x’yz’ + x’y’z)’ = (x’yz’)’(x’y’z)’ = (x + y’ + z)(x + y + z’)
F2’ = [x(y’z’ + yz)]’ = x’ + (y’z’ + yz)’ = x’ + (y’z’)’‧(yz)’ = x’ + (y + z)(y’ + z’)
Ένας απλούστερος τρόπος να βρούμε το συμπλήρωμα μιας συνάρτησης είναι να παίρνουμε το δυϊκό της και συγχρόνως το συμπλήρωμα κάθε παράγοντα. Ας θυμηθούμε ότι το δυϊκό μιας συνάρτησης το παίρνουμε αν εναλλάξουμε τους τελεστές AND και OR, καθώς και τα 1 και 0.