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

Από τη Βικιπαίδεια, την ελεύθερη εγκυκλοπαίδεια

Πίνακας περιεχομένων

[Επεξεργασία] Ιστορικά στοιχεία

Ο μαθηματικός Τζορτζ Μπουλ (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 Κενό σύνολο  \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

[Επεξεργασία] Εξωτερικοί σύνδεσμοι