.
Στα Μαθηματικά και την Μαθηματική λογική, Άλγεβρα Μπουλ είναι η υποπεριοχή της άλγεβρας όπου οι τιμές των μεταβλητών είναι οι τιμές αληθείας αληθές και ψευδές, που συνήθως αναπαρίστανται με 1 και 0 αντίστοιχα. Σε αντίθεση με την στοιχειώδη άλγεβρα όπου οι τιμές των μεταβλητών είναι αριθμοί και οι κύριες πράξεις είναι η πρόσθεση και ο πολλαπλασιασμός, στην άλγεβρα Μπουλ υπάρχουν τρεις κύριες πράξεις: η σύζευξη και (συμβ. ∧), η διάζευξη ή (συμβ. ∨) και η άρνηση όχι (σύμβ. ¬).
Η άλγεβρα Μπουλ εισήχθη το 1854 από τον Τζορτζ Μπουλ (George Boole) με το έργο του An Investigation of the Laws of Thought (Διερεύνηση των νόμων της σκέψης). Σύμφωνα με τον Huntington ο όρος «Άλγεβρα Μπουλ» χρησιμοποιήθηκε για πρώτη φορά από τον Sheffer το 1913.
Η άλγεβρα Μπουλ είναι θεμελιώδους σημασίας για την επιστήμη της Πληροφορικής και αποτελεί την βάση για την θεωρητική μελέτη του πεδίου της λογικής σχεδίασης. Επιπλέον είναι σημαντική σε άλλα πεδία όπως η Στατιστική, η Θεωρία συνόλων και ο προγραμματισμός.
Ιστορικά στοιχεία
Ο μαθηματικός Τζορτζ Μπουλ (George Boole, 1815-1864) παρουσίασε το 1847 μια άλγεβρα με μεταβλητές δύο τιμών (που καλούνται "λογικές μεταβλητές"). Ουσιαστικά παρουσίασε με τα μαθηματικά της εποχής του, την Αριστοτέλεια λογική, του είναι ή δεν είναι. Σήμερα η άλγεβρα αυτή ονομάζεται άλγεβρα Μπουλ, ή δυαδική άλγεβρα, ή διακοπτική άλγεβρα και έχει βρει ευρεία εφαρμογή στην σχεδίαση του λογισμικού και των κυκλωμάτων των ηλεκτρονικών υπολογιστών, επειδή είναι ιδανική για χειρισμό λογικών συναρτήσεων και πράξεων στο δυαδικό σύστημα. Ο παρακάτω ορισμός της άλγεβρας Μπουλ στηρίζεται σε συγκεκριμένα αξιώματα που παρουσίασε το 1933 ο μαθηματικός Έντουαρντ Χάντινγκτον (Edward Vermilye Huntington, 1874-1952).
Πράξεις
Βασικές πράξεις
Οι βασικές πράξεις της Άλγεβρας Μπουλ είναι:
Και (συνδυασμός ή σύζευξη), συμβολίζεται x∧y (μερικές φορές x και y ή K xy). Είναι x∧y = 1, αν x = y = 1, και x∧ y = 0 διαφορετικά.
Ή (διάζευξη), συμβολίζεται x∨y (μερικές φορές x ή y ή ένα xy). Είναι x∨ y = 0, αν x = y = 0, και x ∨ y = 1 διαφορετικά.
Όχι (άρνηση), συμβολίζεται ¬x (μερικές φορές όχι x, Ν x ή !x). Είναι ¬x = 0, αν x = 1, και ¬ x = 1 αν x = 0.
Αν οι τιμές αληθείας 0 και 1 ερμηνευθούν ως ακέραιοι, οι παραπάνω πράξεις μπορούν να εκφραστούν με τις συνήθεις πράξεις της αριθμητικής:
x∧y = xy,
x∨y =x + y - xy,
¬x = 1 - x.
Εναλλακτικά, οι τιμές των x∧y, x∨y και ¬x μπορούν να εκφράζονται με χρήση πίνακα αλήθειας:
Πίνακες αληθείας
|
|
|||||||||||||||||||||||||||||||||||||||||
Λόγω των επόμενων ταυτοτήτων μπορεί κανείς να πει ότι μόνο η άρνηση και μία από τις άλλες δύο πράξεις είναι βασικές:
x∧y = ¬(¬x∨¬y)
x∨y = ¬(¬x∧¬y)
Νόμοι
Ένας νόμος της άλγεβρας Μπουλ είναι μια ταυτότητα, όπως x∨(y∨z) = (x∨y)∨z μεταξύ δύο όρων Μπουλ, όπου ο όρος Μπουλ ορίζεται ως μια έκφραση που αποτελείται από μεταβλητές και τις σταθερές 0 και 1, χρησιμοποιώντας τις πράξεις ∧, ∨ και ¬. Η ιδέα μπορεί να επεκταθεί στους όρους που αφορούν άλλες πράξεις της Άλγεβρας Μπουλ, όπως τις ⊕, →, και ≡, αλλά οι επεκτάσεις αυτές δεν είναι αναγκαίες για τους σκοπούς για τους οποίους έχουν τεθεί οι νόμοι.
Μονότονοι νόμοι
Η Άλγεβρα Μπουλ πληροί πολλούς από τους ίδιους νόμους όπως και η στοιχειώδης Άλγεβρα, εάν γίνει αντιστοίχιση του ∨ με την πρόσθεση και του ∧ με τον πολλαπλασιασμό. Ειδικότερα, οι ακόλουθοι νόμοι είναι κοινοί για τα δύο είδη άλγεβρας:
(Προσεταιριστική ιδιότητα της ∨) x∨(y∨z) = (x∨y)∨z
(Προσεταιριστική ιδιότητα της ∧) x∧(y∧z) = (x∧y)∧z
(Αντιμεταθετική ιδιότητα της ∨) x∨y = y∨x
(Αντιμεταθετική ιδιότητα της ∧) x∧y = y∧x
(Επιμεριστική ιδιότητα της ∧ στη ∨) x∧(y∨z) = (x∧y)∨(x∧z)
(Ουδέτερο στοιχείο της ∨) x∨0 = x
(Ουδέτερο στοιχείο της ∧) x∧1 = x
(Απορροφητικό στοιχείο της ∧) x∧0 = 0
Στην άλγεβρα Μπουλ ισχύουν και επιπλέον νόμοι:
(Αυτοδυναμία της ∨) x∨x = x
(Αυτοδυναμία της ∧) x∧x = x
(Νόμος της απορρόφησης 1) x∧(x∨y) = x
(Νόμος της απορρόφησης 2) x∨(x∧y) = x
(Επιμεριστική ιδιότητα της ∨ στη ∧) x∨(y∧z) = (x∨y)∧(x∨z)
(Απορροφητικό στοιχείο της ∨) x∨1 = 1
Μη μονότονοι νόμοι
Η λειτουργία της συμπλήρωσης ορίζεται από τους ακόλουθους δύο νόμους:
(Συμπλήρωση 1) x ∧ ¬ x = 0
(Συμπλήρωση 2) x ∨ ¬ x = 1.
Και στη στοιχειώδη και στην Άλγεβρα Μπουλ ισχύει ο νόμος της διπλής άρνησης:
(Διπλή άρνηση) ¬¬x = x
Αλλά, ενώ η στοιχειώδης Άλγεβρα πληροί τους δύο νόμους:
(-x) (-y) = xy
(-x) + (-y) = -(x +y)
η Άλγεβρα Μπουλ πληροί τους δύο νόμους De Morgan:
(De Morgan 1) (¬x) ∧ (¬y) = ¬(x∨y)
(De Morgan 2) (¬x) ∨ (¬y) = ¬(x∧y)
Αρχή του δυϊσμού
Αν σε μια λογική έκφραση αντικατασταθούν το (συν +) με (επί •) και το (επί •) με (συν +) και το (μηδέν 0) με (ένα 1) και το (ένα 1) με (μηδέν 0) δημιουργείται η δυϊκή έκφραση, που ισχύει όπως και η αρχική. Η αρχή του δυϊσμού εμφανίζεται και στα αξιώματα του Χάντινγκτον, που δίνονται κατά ζεύγη.
Άλγεβρα Μπουλ και θεωρία συνόλων (set theory)
Θα μπορούσαμε να δούμε την θεωρία συνόλων (τις πράξεις με σύνολα) ως μια άλγεβρα Μπουλ. Ας δούμε τις αντιστοιχίες:
Τα ονόματα στοιχείων του Κ στην θεωρία συνόλων είναι ονόματα συνόλων.
Η πράξη πρόσθεση αντιστοιχεί στην ένωση συνόλων.
Η πράξη πολλαπλασιασμός αντιστοιχεί στην τομή συνόλων.
Το στοιχείο μηδέν αντιστοιχεί στο κενό σύνολο.
Το στοιχείο ένα αντιστοιχεί στο παγκόσμιο σύνολο C. (Όπως είναι γνωστό, δεν ορίζεται το σύνολο όλων των συνόλων).
Το συμπλήρωμα στοιχείου αντιστοιχεί στο συμπληρωματικό συνόλου ως προς το U.
Με τις αντιστοιχήσεις αυτές, κάθε σχέση της άλγεβρας Μπουλ μπορεί να μετατραπεί σε συνολοθεωρητική σχέση. Υπάρχει συγκριτικός πίνακας παρακάτω.
Άλγεβρα Μπουλ και προτασιακή λογική (propositional calculus)
Λογική πρόταση είναι κάθε σύνολο χαρακτήρων ή λέξεων που μπορούμε να του δώσουμε την τιμή «ψευδής» ή «αληθής». Η πρόταση p=[Θα κερδίσω το λαχείο μεθαύριο] δεν είναι λογική πρόταση. Η πρόταση q=[Ο ακέραιος αριθμός 4 είναι άρτιος] είναι λογική πρόταση και έχει αληθοτιμή = «αληθής». Θα μπορούσαμε να δούμε την προτασιακή λογική (πράξεις με λογικές προτάσεις) ως μια άλγεβρα Μπουλ. Ας δούμε τις αντιστοιχίες:
Τα στοιχεία του Κ στην προτασιακή λογική είναι λογικές προτάσεις.
Η πρόσθεση αντιστοιχεί σε διάζευξη (Ή).
Ο πολλαπλασιασμός αντιστοιχεί σε σύζευξη (ΚΑΙ).
Το μηδέν αντιστοιχεί στο ψευδής.
Το ένα αντιστοιχεί στο αληθής.
Το συμπλήρωμα αντιστοιχεί στην άρνηση της πρότασης.
Πίνακας αντιστοιχιών άλγεβρας Μπουλ, συνολοθεωρίας και προτασιακής λογικής
| Πίνακας αντιστοιχιών άλγεβρας Μπουλ, συνολοθεωρίας και προτασιακής λογικής | |||||
|---|---|---|---|---|---|
| Άλγεβρα Μπουλ | Θεωρία Συνόλων | Προτασιακή Λογική | |||
| Πρόσθεση | + | Ένωση | \( \cup \,\!\) | Διάζευξη, Ή | ∨ |
| Πολλαπλασιασμός | • | Τομή | \( \cap \,\!\) | Σύζευξη, Και | ∧ |
| Μηδέν | 0 | Κενό σύνολο | \( \varnothing \,\! \) | Ψευδής | F |
| Ένα | 1 | Παγκόσμιο σύνολο | C | Αληθής | T |
| Στοιχεία | α,β | Σύνολα | A,B | Προτάσεις | p,q |
| Συμπλήρωμα του α | α’ | Συμπληρωματικό του A | \( A^C \,\!\) | Άρνηση της p | ¬p |
Παραδείγματα όμοιων προτάσεων σε διάφορους συμβολισμούς
| Παραδείγματα όμοιων προτάσεων σε διάφορους συμβολισμούς | ||
|---|---|---|
| Άλγεβρα Μπουλ | Θεωρία Συνόλων | Προτασιακή Λογική |
| αα’ = 0 | \( A \cap A^C = \varnothing \,\!\) | p ∧ ¬p = F |
| α + αβ = α | \( A \cup (A \cap B) = A \,\!\) | p ∨ (p ∧ q) = p |
| (αβ)’ = α’ + β’ | \( (A \cap B)^C = A^C \cup B^C \,\!\) | ¬(p ∧ q) = ¬p ∨ ¬q |
Ψηφιακές λογικές πύλες
Κύρια λήμματα: Λογική Σχεδίαση και Λογική Πύλη
Ψηφιακή λογική είναι η εφαρμογή της Άλγεβρας Μπουλ σε hardware που αποτελείται από λογικές πύλες που συνδέονται μεταξύ τους προκειμένου να σχηματισθούν πιο σύνθετα κυκλώματα. Κάθε λογική πύλη αντιστοιχεί σε μια από τις πράξεις της Άλγεβρας Μπουλ και αναπαρίσταται γραφικά με διαφορετικό σχήμα. Στην επόμενη εικόνα φαίνονται τα σχήματα για τις πύλες ΚΑΙ (AND), Ή (OR) και ΟΧΙ (ΝΟΤ).
Σχηματική αναπαράσταση των λογικών πυλών ΚΑΙ, 'Η, ΟΧΙ (από αριστερά προς τα δεξιά)
Οι γραμμές στα αριστερά κάθε λογικής πύλης αναπαριστούν καλώδια εισόδου (ή αλλιώς ports). Η τιμή της εισόδου είναι η τιμή του voltage. Για παράδειγμα voltage κοντά στο μηδέν θα μπορούσε να αντιστοιχισθεί στην αληθοτιμή 0 και υψηλότερο voltage στην αληθοτιμή 1. Αυτός είναι ένας από τους τρόπους αντιστοίχισης voltage-αληθοτιμών. Η γραμμή στα δεξιά κάθε πύλης αναπαριστά την έξοδο της λογικής πύλης. Συνήθως ακολουθείται η ίδια σύμβαση αντιστοίχισης voltage-αληθοτιμών στις εισόδους και στην έξοδο. Η λογική άρνηση υλοποιείται με την χρήση ενός αντιστροφέα, ο οποίος συμβολίζεται με ένα κυκλίσκο. Το τρίγωνο μπροστά από τον κυκλίσκο υποδηλώνει απλώς αντιγραφή της εισόδου.
Εάν χρησιμοποιήσουμε το συμπλήρωμα σε όλες τις θύρες (ports) κάθε λογικής πύλης, και χρησιμοποιήσουμε την πύλη ΚΑΙ στην θέση της πύλης Ή και αντίστροφα, τότε θα έχουμε υλοποιήσει ισοδυνάμως τις τρεις αρχικές πράξεις. Το γεγονός αυτό επιδεικνύει την εφαρμογή των δύο νόμων De Morgan καθώς και της αρχής της δυαδικότητας.
Ισοδύναμες πύλες ΚΑΙ, Ή, ΟΧΙ (από αριστερά προς τα δεξιά)
Δείτε επίσης
Τζορτζ Μπουλ
Λογική Σχεδίαση
Λογική Πύλη
Θεωρία συνόλων
Εξωτερικοί σύνδεσμοι
Monk, J. Donald, The Mathematics of Boolean Algebra
Hellenica World - Scientific Library
Από τη ελληνική Βικιπαίδεια http://el.wikipedia.org . Όλα τα κείμενα είναι διαθέσιμα υπό την GNU Free Documentation License
