Άλγεβρα Μπουλ

Ιστορικά στοιχεία

Ο μαθηματικός Τζορτζ Μπουλ (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 είναι άρτιος] είναι λογική πρόταση και έχει αληθοτιμή = «αληθής». Θα μπορούσαμε να δούμε την προτασιακή λογική (πράξεις με λογικές προτάσεις) ως μια άλγεβρα Μπουλ. Ας δούμε τις αντιστοιχίες:

Τα στοιχεία του Κ στην προτασιακή λογική είναι λογικές προτάσεις.
Η πρόσθεση αντιστοιχεί σε διάζευξη (Ή).
Ο πολλαπλασιασμός αντιστοιχεί σε σύζευξη (ΚΑΙ).
Το μηδέν αντιστοιχεί στο ψευδής.
Το ένα αντιστοιχεί στο αληθής.
Το συμπλήρωμα αντιστοιχεί στην άρνηση της πρότασης.

Πίνακας αντιστοιχιών άλγεβρας Μπουλ, συνολοθεωρίας και προτασιακής λογικής
Άλγεβρα Μπουλ		Θεωρία Συνόλων		Προτασιακή Λογική
Πρόσθεση	+	Ένωση	\( \cup \,\! \)	Διάζευξη, Ή	∨
Πολλαπλασιασμός	•	Τομή	\( \cap \,\! \)	Σύζευξη, Και	∧
Μηδέν	0	Κενό σύνολο	\( \cap \,\! \)	Ψευδής	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

Monk, J. Donald, The Mathematics of Boolean Algebra