Άλγεβρα Μπουλ
Από τη Βικιπαίδεια, την ελεύθερη εγκυκλοπαίδεια
Πίνακας περιεχομένων |
[Επεξεργασία] Ιστορικά στοιχεία
Ο μαθηματικός Τζορτζ Μπουλ (George Boole, 1815-1864) παρουσίασε το 1847 μια άλγεβρα με μεταβλητές δύο τιμών (που καλούνται "λογικές μεταβλητές"). Ουσιαστικά παρουσίασε με τα μαθηματικά της εποχής του την Αριστοτέλεια λογική του είναι ή δεν είναι. Σήμερα η άλγεβρα αυτή ονομάζεται άλγεβρα Μπουλ, ή δυαδική άλγεβρα, ή διακοπτική άλγεβρα και έχει βρει ευρεία εφαρμογή στην σχεδίαση του λογισμικού και των κυκλωμάτων των ηλεκτρονικών υπολογιστών, επειδή είναι ιδανική για χειρισμό λογικών συναρτήσεων και πράξεων στο δυαδικό σύστημα.
Ο παρακάτω ορισμός της άλγεβρας Μπουλ στηρίζεται σε συγκεκριμένα αξιώματα που παρουσίασε το 1933 ο μαθηματικός Έντουαρντ Χάντινγκτον (Edward Vermilye Huntington, 1874-1952).
[Επεξεργασία] Αξιώματα του Χάντινγκτον
- Αξίωμα Α1: Ισοδυναμία
Υπάρχει ένα σύνολο Κ με αντικείμενα ή στοιχεία, που υπακούουν σε μια σχέση ισοδυναμίας, α = β (όπου το σύμβολο ‘=’ διαβάζεται είναι ίσο με), που ικανοποιεί την αρχή της αντικατάστασης. Αν το στοιχείο α ανήκει στο σύνολο Κ, γράφουμε [α € Κ], (όπου το σύμβολο € διαβάζεται ανήκει στο). Γράφοντας α = β, εννοούμε ότι το α μπορεί να αντικατασταθεί από το β, σε οποιαδήποτε λογική έκφραση που περιέχει το α, χωρίς να επηρεαστεί η τιμή της έκφρασης αυτής. Ιδιότητες της σχέσης ισοδυναμίας είναι η ανακλαστική ιδιότητα (α = α), η συμμετρική ιδιότητα (α = β <=> β = α), (όπου το σύμβολο <=> διαβάζεται ταυτίζεται με το), και η μεταβατική ιδιότητα (α = β και β = γ => α = γ) , (όπου το σύμβολο => διαβάζεται συνεπάγεται).
- Αξίωμα Α2.1: Πράξη πρόσθεσης
Ένας κλειστός νόμος (σύμβολο ‘+’ διαβάζεται συν), που θα τον λέμε πρόσθεση, ορίζεται έτσι, ώστε αν α € Κ και β € Κ, τότε (α + β) € Κ.
- Αξίωμα Α2.2: Πράξη πολλαπλασιασμού
Ένας κλειστός νόμος (σύμβολο ‘•’ διαβάζεται επί), που θα τον λέμε πολλαπλασιασμό ορίζεται έτσι, ώστε αν α € Κ και β € Κ, τότε (α • β) € Κ.
- Αξίωμα Α3.1: Ουδέτερο στοιχείο πρόσθεσης
Υπάρχει μόνο ένα στοιχείο 0 € Κ τέτοιο, ώστε (για κάθε α € Κ) (α + 0) = α. Το 0 λέγεται ουδέτερο στοιχείο της πρόσθεσης.
- Αξίωμα Α3.2: Ουδέτερο στοιχείο πολλαπλασιασμού
Υπάρχει μόνο ένα στοιχείο 1 € Κ τέτοιο, ώστε (για κάθε α € Κ) (α • 1) = α. Το 1 λέγεται ουδέτερο στοιχείο του πολλαπλασιασμού.
- Αξίωμα Α4.1: Αντιμετάθεση προσθετέων
Η πρόσθεση είναι αντιμεταθετική, δηλαδή (α + β) = (β + α).
- Αξίωμα Α4.2: Αντιμετάθεση παραγόντων
Ο πολλαπλασιασμός είναι αντιμεταθετικός, δηλαδή (α • β) = (β • α).
- Αξίωμα Α5.1: Επιμεριστική πρόσθεση
Η πρόσθεση είναι επιμεριστική επί του πολλαπλασιασμού, δηλαδή α + (β • γ) = (α + β) • (α + γ). Αυτό είναι ένα αξίωμα της άλγεβρας Μπουλ που δεν ισχύει στην άλγεβρα των πραγματικών αριθμών!
- Αξίωμα Α5.2: Επιμεριστικός πολλαπλασιασμός
Ο πολλαπλασιασμός είναι επιμεριστικός επί της πρόσθεσης, δηλαδή α • (β + γ) = (α • β) + (α • γ). (Σημείωση : Όταν δεν υπάρχει περίπτωση παρανόησης, παραλείπουμε την αναγραφή του επί ‘•’ και χρησιμοποιούμε απλή παράθεση των παραγόντων. Για παράδειγμα, η σχέση εδώ μπορεί να γραφτεί έτσι : α (β + γ) = α β + α γ) .
- Αξίωμα Α6: Συμπληρώματα
Για κάθε στοιχείο α € Κ υπάρχει μόνο ένα στοιχείο α', για το οποίο ισχύει ότι α + α' = 1 (A6.1) και α • α' = 0 (A6.2)
- Αξίωμα Α7: Διάκριτα στοιχεία
Υπάρχουν τουλάχιστον δυο στοιχεία α και β μέσα στο Κ που δεν είναι ισοδύναμα. Ανάλογα με το πλήθος και το είδος των στοιχείων του Κ, καθορίζεται και μια άλγεβρα. Η απλούστερη άλγεβρα Μπουλ έχει μόνο δυο στοιχεία, δηλαδή το Κ = {0, 1}. Για τα στοιχεία αυτά ισχύουν τα εξής : 1' = 0 και 0' = 1, 0 + 0 = 0 και 1 • 1 = 1, 0 + 1 = 1 και 1 • 0 = 0, 1 + 0 = 1 και 0 • 1 = 0, 1 + 1 = 1 και 0 • 0 = 0 (Α7).
[Επεξεργασία] Αρχή του δυϊσμού
Αν σε μια λογική έκφραση αντικατασταθούν το (συν +) με (επί •) και το (επί •) με (συν +) και το (μηδέν 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 |
[Επεξεργασία] Εξωτερικοί σύνδεσμοι
- Monk, J. Donald, The Mathematics of Boolean Algebra
