Άλγεβρα Μπουλ
 |
Αυτό το λήμμα χρειάζεται μορφοποίηση ώστε να ανταποκρίνεται στις προδιαγραφές μορφοποίησης της Βικιπαίδειας. |
 |
Το λήμμα δεν περιέχει πηγές ή αυτές που περιέχει δεν επαρκούν. |
Στα Μαθηματικά και την Μαθηματική λογική, Άλγεβρα Μπουλ είναι η υποπεριοχή της άλγεβρας όπου οι τιμές των μεταβλητών είναι οι τιμές αληθείας αληθές και ψευδές, που συνήθως αναπαρίστανται με 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 0 0 0 0 1 0 0 1 0 1 0 1 1 1 1 1 x ¬x 0 1 1 0 Πίνακες αληθείας
Λόγω των επόμενων ταυτοτήτων μπορεί κανείς να πει ότι μόνο η άρνηση και μία από τις άλλες δύο πράξεις είναι βασικές:
- 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 είναι άρτιος] είναι λογική πρόταση και έχει αληθοτιμή = «αληθής».
Θα μπορούσαμε να δούμε την προτασιακή λογική (πράξεις με λογικές προτάσεις) ως μια άλγεβρα Μπουλ. Ας δούμε τις αντιστοιχίες:
- Τα στοιχεία του Κ στην προτασιακή λογική είναι λογικές προτάσεις.
- Η πρόσθεση αντιστοιχεί σε διάζευξη (Ή).
- Ο πολλαπλασιασμός αντιστοιχεί σε σύζευξη (ΚΑΙ).
- Το μηδέν αντιστοιχεί στο ψευδής.
- Το ένα αντιστοιχεί στο αληθής.
- Το συμπλήρωμα αντιστοιχεί στην άρνηση της πρότασης.
| Πίνακας αντιστοιχιών άλγεβρας Μπουλ, συνολοθεωρίας και προτασιακής λογικής | |||||
|---|---|---|---|---|---|
| Άλγεβρα Μπουλ | Θεωρία Συνόλων | Προτασιακή Λογική | |||
| Πρόσθεση | + | Ένωση | Διάζευξη, Είτε | ∨ | |
| Πολλαπλασιασμός | • | Τομή | Σύζευξη, Και | ∧ | |
| Μηδέν | 0 | Κενό σύνολο | Ψευδής | F | |
| Ένα | 1 | Παγκόσμιο σύνολο | C | Αληθής | T |
| Στοιχεία | α,β | Σύνολα | A,B | Προτάσεις | p,q |
| Συμπλήρωμα του α | α’ | Συμπληρωματικό του A | Άρνηση της p | ¬p | |
| Παραδείγματα όμοιων προτάσεων σε διάφορους συμβολισμούς | ||
|---|---|---|
| Άλγεβρα Μπουλ | Θεωρία Συνόλων | Προτασιακή Λογική |
| αα’ = 0 | p ∧ ¬p = F | |
| α + αβ = α | p ∨ (p ∧ q) = p | |
| (αβ)’ = α’ + β’ | ¬(p ∧ q) = ¬p ∨ ¬q | |
Ψηφιακές λογικές πύλες
[Επεξεργασία | επεξεργασία κώδικα]Ψηφιακή λογική είναι η εφαρμογή της Άλγεβρας Μπουλ σε υλικό υπολογιστή που αποτελείται από λογικές πύλες που συνδέονται μεταξύ τους προκειμένου να σχηματισθούν πιο σύνθετα κυκλώματα. Κάθε λογική πύλη αντιστοιχεί σε μια από τις πράξεις της Άλγεβρας Μπουλ και αναπαρίσταται γραφικά με διαφορετικό σχήμα. Στην επόμενη εικόνα φαίνονται τα σχήματα για τις πύλες ΚΑΙ (AND), Ή (OR) και ΟΧΙ (ΝΟΤ).
Οι γραμμές στα αριστερά κάθε λογικής πύλης αναπαριστούν καλώδια εισόδου (ή αλλιώς ports). Η τιμή της εισόδου είναι η τιμή της τάσης (διαφορά δυναμικού). Για παράδειγμα, τάση κοντά στο μηδέν θα μπορούσε να αντιστοιχισθεί στην αληθοτιμή 0 και υψηλότερη διαφορά δυναμικού στην αληθοτιμή 1. Αυτός είναι ένας από τους τρόπους αντιστοίχισης τάσης με αληθοτιμές. Η γραμμή στα δεξιά κάθε πύλης αναπαριστά την έξοδο της λογικής πύλης. Συνήθως ακολουθείται η ίδια σύμβαση αντιστοίχισης τάσης-αληθοτιμών στις εισόδους και στην έξοδο.
Η λογική άρνηση υλοποιείται με τη χρήση ενός αντιστροφέα, ο οποίος συμβολίζεται με ένα κυκλίσκο. Το τρίγωνο μπροστά από τον κυκλίσκο υποδηλώνει απλώς αντιγραφή της εισόδου.
Εάν χρησιμοποιήσουμε το συμπλήρωμα σε όλες τις θύρες (ports) κάθε λογικής πύλης, και χρησιμοποιήσουμε την πύλη ΚΑΙ στη θέση της πύλης Ή και αντίστροφα, τότε θα έχουμε υλοποιήσει ισοδύναμα τις τρεις αρχικές πράξεις. Το γεγονός αυτό επιδεικνύει την εφαρμογή των δύο νόμων De Morgan καθώς και της αρχής της δυαδικότητας.
Δείτε επίσης
[Επεξεργασία | επεξεργασία κώδικα]Εξωτερικοί σύνδεσμοι
[Επεξεργασία | επεξεργασία κώδικα]
- Monk, J. Donald, The Mathematics of Boolean Algebra