Science Wiki
Register
Advertisement

Άλγεβρα Boole

Boolean Algebra, Άλγεβρα Μπουλ


Boolean-Logic-01-goog

Άλγεβρα Boole
Προτασιακή Λογική

Boolean-Logic-02-goog

Άλγεβρα Boole
The first three laws of Boolean algebra
are very similar to the laws of regular algebra
if you think of
the OR operator producing a sum and
the AND operator producing a product.
The rest of the laws
are applicable only to Boolean algebra.
De Morgan’s theorem
is especially useful
as it allows us
to swap AND and OR operators with
a bit of negation

- Ένας Επιστημονικός Κλάδος της Άλγεβρας που οι μεταβλητές λαμβάνουν μόνον δύο τιμές π.χ. 0,1

Ετυμολογία[]

Η ονομασία "άλγεβρα" σχετίζεται ετυμολογικά με την λέξη "[[]]".

Ιστορία[]

Ο μαθηματικός George Boole, 1815-1864) παρουσίασε το 1847 μια άλγεβρα με μεταβλητές δύο τιμών (που καλούνται "λογικές μεταβλητές").

Ουσιαστικά παρουσίασε με τα μαθηματικά της εποχής του την Αριστοτέλεια λογική του είναι ή δεν είναι.

Σήμερα η άλγεβρα αυτή ονομάζεται άλγεβρα Boole, ή δυαδική άλγεβρα, ή διακοπτική άλγεβρα και έχει βρει ευρεία εφαρμογή στην σχεδίαση του λογισμικού και των κυκλωμάτων των Ηλεκτρονικών Υπολογιστών, επειδή είναι ιδανική για χειρισμό λογικών συναρτήσεων και πράξεων στο Δυαδικό Σύστημα.

Ο παρακάτω ορισμός της άλγεβρας Boole στηρίζεται σε συγκεκριμένα αξιώματα που παρουσίασε το 1933 ο μαθηματικός Edward Vermilye Huntington, 1874-1952).

Άλγεβρα Boole[]

Any set of sets, closed under the set-theoretic operations, forms a Boolean algebra with:

  • the join operator being union,
  • the meet operator being intersection,
  • the complement operator being set complement,
  • the bottom being empty set and
  • the top being the universal set under consideration.

Αξιώματα του Huntington[]

  • Αξίωμα Α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)

δημιουργείται η δυϊκή έκφραση, που ισχύει όπως και η αρχική.

Η αρχή του δυϊσμού εμφανίζεται και στα αξιώματα του Huntington, που εμφανίζονται κατά ζεύγη.

Συνολοθεωρία[]

Η Συνολοθεωρία (set theory)είναι στην πραγματικότητα μια Άλγεβρα Boole.

Ας δούμε τις αντιστοιχίες:

  • Τα ονόματα στοιχείων του Κ στην θεωρία συνόλων είναι ονόματα συνόλων.
  • Η πράξη πρόσθεση αντιστοιχεί στην ένωση συνόλων.
  • Η πράξη πολλαπλασιασμός αντιστοιχεί στην τομή συνόλων.
  • Το στοιχείο μηδέν αντιστοιχεί στο κενό σύνολο.
  • Το στοιχείο μονάδα αντιστοιχεί στο παγκόσμιο σύνολο C. (Όπως είναι γνωστό, δεν ορίζεται το σύνολο όλων των συνόλων).
  • Το συμπλήρωμα στοιχείου αντιστοιχεί στο συμπληρωματικό συνόλου ως προς το U.

Με τις αντιστοιχίσεις αυτές, κάθε σχέση της άλγεβρας Boole μπορεί να μετατραπεί σε συνολοθεωρητική σχέση. Υπάρχει συγκριτικός πίνακας παρακάτω.

Άλγεβρα Boole και Προτασιακή Λογική[]

Η Προτασιακή Λογική (propositional calculus) είναι στην πραγματικότητα και αυτή μία Άλγεβρα Boole.

Λογική πρόταση είναι κάθε σύνολο χαρακτήρων ή λέξεων που μπορούμε να του δώσουμε την τιμή «ψευδής» ή «αληθής». Η πρόταση p=[Θα κερδίσω το λαχείο μεθαύριο] δεν είναι λογική πρόταση. Η πρόταση q=[Ο ακέραιος αριθμός 4 είναι άρτιος] είναι λογική πρόταση και έχει αληθοτιμή = «αληθής». Θα μπορούσαμε να δούμε την προτασιακή λογική (πράξεις με λογικές προτάσεις) ως μια άλγεβρα Boole. Ας δούμε τις αντιστοιχίες:

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


Πίνακας αντιστοιχιών άλγεβρας Μπουλ, συνολοθεωρίας και προτασιακής λογικής
Άλγεβρα Μπουλ
Θεωρία Συνόλων
Προτασιακή Λογική
Πρόσθεση + Ένωση Διάζευξη, Ή
Πολλαπλασιασμός Τομή Σύζευξη, Και
Μηδέν 0 Κενό σύνολο Ψευδής F
Ένα 1 Παγκόσμιο σύνολο C Αληθής T
Στοιχεία α,β Σύνολα A,B Προτάσεις p,q
Συμπλήρωμα του α α’ Συμπληρωματικό του A Άρνηση της p ¬p
Παραδείγματα όμοιων προτάσεων σε διάφορους συμβολισμούς
Άλγεβρα Μπουλ Θεωρία Συνόλων Προτασιακή Λογική
αα’ = 0 p ∧ ¬p = F
α + αβ = α p ∨ (p ∧ q) = p
(αβ)’ = α’ + β’ ¬(p ∧ q) = ¬p ∨ ¬q

Υποσημειώσεις[]

Εσωτερική Αρθρογραφία[]

Βιβλιογραφία[]

  • Cori, Rene, and Lascar, Daniel, 2000. Mathematical Logic: A Course with Exercises. Oxford Univ. Press. Chpt. 2.
  • Dahn, B. I. (1998) “Robbins algebras are Boolean: A revision of McCune’s computer-generated solution of the Robbins problem,” Journal of Algebra 208: 526-32.
  • Paul Halmos, 1963. Lectures on Boolean Algebras. Van Nostrand.
  • Paul Halmos and Steven Givant, 1998. Logic as Algebra. Dolciani Mathematical Expositions No. 21, Mathematical Association of America.
  • Stoll, R. R., 1979 (1963). Set Theory and Logic. Dover.

Ιστογραφία[]

A monograph available free online:


Ikl Κίνδυνοι ΧρήσηςIkl

Αν και θα βρείτε εξακριβωμένες πληροφορίες
σε αυτήν την εγκυκλοπαίδεια
ωστόσο, παρακαλούμε να λάβετε σοβαρά υπ' όψη ότι
η "Sciencepedia" δεν μπορεί να εγγυηθεί, από καμιά άποψη,
την εγκυρότητα των πληροφοριών που περιλαμβάνει.

"Οι πληροφορίες αυτές μπορεί πρόσφατα
να έχουν αλλοιωθεί, βανδαλισθεί ή μεταβληθεί από κάποιο άτομο,
η άποψη του οποίου δεν συνάδει με το "επίπεδο γνώσης"
του ιδιαίτερου γνωστικού τομέα που σας ενδιαφέρει."

Πρέπει να λάβετε υπ' όψη ότι
όλα τα άρθρα μπορεί να είναι ακριβή, γενικώς,
και για μακρά χρονική περίοδο,
αλλά να υποστούν κάποιο βανδαλισμό ή ακατάλληλη επεξεργασία,
ελάχιστο χρονικό διάστημα, πριν τα δείτε.



Επίσης,
Οι διάφοροι "Εξωτερικοί Σύνδεσμοι (Links)"
(όχι μόνον, της Sciencepedia
αλλά και κάθε διαδικτυακού ιστότοπου (ή αλλιώς site)),
αν και άκρως απαραίτητοι,
είναι αδύνατον να ελεγχθούν
(λόγω της ρευστής φύσης του Web),
και επομένως είναι ενδεχόμενο να οδηγήσουν
σε παραπλανητικό, κακόβουλο ή άσεμνο περιεχόμενο.
Ο αναγνώστης πρέπει να είναι
εξαιρετικά προσεκτικός όταν τους χρησιμοποιεί.

- Μην κάνετε χρήση του περιεχομένου της παρούσας εγκυκλοπαίδειας
αν διαφωνείτε με όσα αναγράφονται σε αυτήν

IonnKorr-System-00-goog



>>Διαμαρτυρία προς την wikia<<

- Όχι, στις διαφημίσεις που περιέχουν απαράδεκτο περιεχόμενο (άσεμνες εικόνες, ροζ αγγελίες κλπ.)


Advertisement