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

Από τη Βικιπαίδεια, την ελεύθερη εγκυκλοπαίδεια
Μετάβαση σε: πλοήγηση, αναζήτηση
Άλγεβρα Μπουλ
Ταξινόμηση
Dewey 512
MSC2010 06Exx

Στα Μαθηματικά και την Μαθηματική λογική, Άλγεβρα Μπουλ είναι η υποπεριοχή της άλγεβρας όπου οι τιμές των μεταβλητών είναι οι τιμές αληθείας αληθές και ψευδές, που συνήθως αναπαρίστανται με 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).

Πράξεις[Επεξεργασία | επεξεργασία κώδικα]

Βασικές πράξεις[Επεξεργασία | επεξεργασία κώδικα]

Οι βασικές πράξεις της Άλγεβρας Μπουλ είναι:

  • Και (συνδυασμός ή σύζευξη), συμβολίζεται xy (μερικές φορές x και y ή K xy). Είναι xy = 1 αν x = y = 1 και xy = 0 διαφορετικά.
  • Ή (διάζευξη), συμβολίζεται xy (μερικές φορές x ήy ή ένα xy). Είναι xy = 0 αν x = y = 0 και xy = 1 διαφορετικά.
  • Όχι (άρνηση), συμβολίζεται ¬x (μερικές φορές όχι x, Ν x ή !x). Είναι ¬x = 0 αν x = 1 και ¬ x = 1 αν x = 0.

Αν οι τιμές αληθείας 0 και 1 ερμηνευθούν ως ακέραιοι, οι παραπάνω πράξεις μπορούν να εκφραστούν με τις συνήθεις πράξεις της αριθμητικής:

  • xy = xy,
  • xy =x + y - xy,
  • ¬x = 1 - x.

Εναλλακτικά, οι τιμές των xy, xy και ¬x μπορούν να εκφράζονται με χρήση πίνακα αλήθειας:

Πίνακες αληθείας
x y xy xy
0 0 0 0
1 0 0 1
0 1 0 1
1 1 1 1
x ¬x
0 1
1 0

Λόγω των επόμενων ταυτοτήτων μπορεί κανείς να πει ότι μόνο η άρνηση και μία από τις άλλες δύο πράξεις είναι βασικές:

  • xy = ¬(¬x∨¬y)
  • xy = ¬(¬x∧¬y)

Νόμοι[Επεξεργασία | επεξεργασία κώδικα]

Ένας νόμος της άλγεβρας Μπουλ είναι μια ταυτότητα, όπως x∨(yz) = (xy)∨z μεταξύ δύο Boolean όρων, όπου σαν Boolean όρος ορίζεται μια έκφραση που αποτελείται από μεταβλητές και τις σταθερές 0 και 1, χρησιμοποιώντας τις πράξεις ∧, ∨ και ¬. Η ιδέα μπορεί να επεκταθεί στους όρους που αφορούν άλλες Boolean πράξεις όπως τις ⊕, →, και ≡, αλλά οι επεκτάσεις αυτές δεν είναι αναγκαίες για τους σκοπούς για τους οποίους έχουν τεθεί οι νόμοι.

Μονότονοι νόμοι[Επεξεργασία | επεξεργασία κώδικα]

Η Άλγεβρα Μπουλ ικανοποιεί πολλούς από τους ίδιους νόμους όπως και η συνήθης Άλγεβρα, εάν γίνει αντιστοίχιση του ∨ με την πρόσθεση και του ∧ με τον πολλαπλασιασμό. Ειδικότερα, οι ακόλουθοι νόμοι είναι κοινοί για τα δύο είδη άλγεβρας:

(Προσεταιριστική ιδιότητα του ∨) x∨(yz) = (xy)∨z
(Προσεταιριστική ιδιότητα του ∧) x∧(yz) = (xy)∧z
(Αντιμεταθετική ιδιότητα του ∨) xy = yx
(Αντιμεταθετική ιδιότητα του ∧) xy = yx
(Επιμεριστική ιδιότητα του ∧ στο ∨) x∧(yz) = (xy)∨(xz)
(Ταυτότητα για το ∨) x∨0 = x
(Ταυτότητα για το ∧) x∧1 = x
(Annihilator for ∧) x∧0 = 0

Στην άλγεβρα Μπουλ ισχύουν και επιπλέον νόμοι:

(Αυτοδυναμία του ∨) xx = x
(Αυτοδυναμία του ∧) xx = x
(Νόμος της απορρόφησης 1) x∧(xy) = x
(Νόμος της απορρόφησης 2) x∨(xy) = x
(Επιμεριστική ιδιότητα του ∨ στο ∧) x∨(yz) = (xy)∧(xz)
(Annihilator for ∨) 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) = ¬(xy)
  • (De Morgan 2) (¬x) ∨ (¬y) = ¬(xy)

Αρχή του δυϊσμού[Επεξεργασία | επεξεργασία κώδικα]

Αν σε μια λογική έκφραση αντικατασταθούν το (συν +) με (επί •) και το (επί •) με (συν +) και το (μηδέν 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 καθώς και της αρχής της δυαδικότητας.

Ισοδύναμες πύλες ΚΑΙ, Ή, ΟΧΙ (από αριστερά προς τα δεξιά)

Δείτε επίσης[Επεξεργασία | επεξεργασία κώδικα]

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


Στο λήμμα αυτό έχει ενσωματωθεί κείμενο από το λήμμα Boolean algebra της Αγγλικής Βικιπαίδειας, η οποία διανέμεται υπό την GNU FDL και την CC-BY-SA 3.0. (ιστορικό/συντάκτες).