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

Στα μαθηματικά και την μαθηματική λογική, Άλγεβρα Μπουλ είναι η υποπεριοχή της άλγεβρας όπου οι τιμές των μεταβλητών είναι οι δυαδικές, είτε αληθές και ψευδές, που συνήθως αναπαρίστανται με 1 και 0 αντίστοιχα. Σε αντίθεση με τη στοιχειώδη άλγεβρα όπου οι τιμές των μεταβλητών είναι αριθμοί και οι κύριες πράξεις είναι η πρόσθεση και ο πολλαπλασιασμός, στην άλγεβρα Μπουλ υπάρχουν τρεις κύριες πράξεις: η σύζευξη και (συμβ. ∧), η διάζευξη ή (συμβ. ∨) και η άρνηση όχι (σύμβ. ¬).

Η άλγεβρα Μπουλ εισήχθη το 1854 από τον Τζορτζ Μπουλ με το έργο του An Investigation of the Laws of Thought (Διερεύνηση των νόμων της σκέψης). Σύμφωνα με τον Huntington ο όρος «Άλγεβρα Μπουλ» χρησιμοποιήθηκε για πρώτη φορά από τον Sheffer το 1913.

Η άλγεβρα Μπουλ είναι θεμελιώδους σημασίας για την πληροφορική και αποτελεί τη βάση για τη θεωρητική μελέτη του πεδίου της λογικής σχεδίασης. Επιπλέον, είναι σημαντική σε άλλα πεδία όπως η στατιστική, η Θεωρία συνόλων και ο προγραμματισμός.

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

Ο μαθηματικός Τζορτζ Μπουλ (1815-1864) παρουσίασε το 1847 μια άλγεβρα με μεταβλητές δύο τιμών (που καλούνται "λογικές μεταβλητές"). Ουσιαστικά παρουσίασε με τα μαθηματικά της εποχής του, την Αριστοτέλεια λογική, του είναι ή δεν είναι. Σήμερα η άλγεβρα αυτή ονομάζεται άλγεβρα Μπουλ, ή δυαδική άλγεβρα, ή διακοπτική άλγεβρα και έχει βρει ευρεία εφαρμογή στη σχεδίαση του λογισμικού και των κυκλωμάτων των ηλεκτρονικών υπολογιστών, επειδή είναι ιδανική για χειρισμό λογικών συναρτήσεων και πράξεων στο δυαδικό σύστημα. Ο παρακάτω ορισμός της άλγεβρας Μπουλ στηρίζεται σε συγκεκριμένα αξιώματα που παρουσίασε το 1933 ο μαθηματικός Έντουαρντ Χάντινγκτον (Edward Vermilye Huntington, 1874-1952).

Πράξεις

Βασικές πράξεις

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

• Λογική σύζευξη (Και): συμβολίζεται με $x\wedge y$ (μερικές φορές $x$ και $y$ ή $K\ xy$) και ορίζεται ως

$x\wedge y={\begin{cases}1&{\text{αν }}x=y=1,\\0&{\text{διαφορετικά}}.\end{cases}}$

• Λογική διάζευξη (Ή): συμβολίζεται με $x\vee y$ (μερικές φορές $x$ ή $y$ ή $1xy$) και ορίζεται ως

$x\vee y={\begin{cases}0&{\text{αν }}x=y=0,\\1&{\text{διαφορετικά}}.\end{cases}}$

• Λογική άρνηση (Όχι): συμβολίζεται με $\neg x$ (μερικές φορές όχι $x$, $N\ x$ ή $!x$) και ορίζεται ως

$\neg x={\begin{cases}0&{\text{αν }}x=1,\\1&{\text{αν }}x=0.\end{cases}}$

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

• $x\wedge y=xy$,
• $x\vee y=x+y-xy$,
• $\neg x=1-x$.

Εναλλακτικά, οι τιμές των $x\wedge y$, $x\vee y$ και $\neg x$ μπορούν να οριστούν με τους εξής πίνακες αληθείας:

$x$	$y$	$x\land y$	$x\lor y$
0	0	0	0
0	1	0	1
1	0	0	1
1	1	1	1

$x$	$\neg x$
0	1
1	0

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

• $x\wedge y=\neg (\neg x\vee \neg y)$
• $x\vee y=\neg (\neg x\wedge \neg y)$

Νόμοι

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

Μονότονοι νόμοι

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

(Προσεταιριστική ιδιότητα της $\vee$)	$x\vee (y\vee z)$	$=$	$(x\vee y)\vee z$
(Προσεταιριστική ιδιότητα της $\wedge$)	$x\wedge (y\wedge z)$	$=$	$(x\wedge y)\wedge z$
(Αντιμεταθετική ιδιότητα της $\vee$)	$x\vee y$	$=$	$y\vee x$
(Αντιμεταθετική ιδιότητα της $\wedge$)	$x\wedge y$	$=$	$y\wedge x$
(Επιμεριστική ιδιότητα της ∧ ως προς την ∨)	$x\wedge (y\vee z)$	$=$	$(x\wedge y)\vee (x\wedge z)$
(Ουδέτερο στοιχείο της $\vee$)	$x\vee 0$	$=$	$x$
(Ουδέτερο στοιχείο της $\wedge$)	$x\wedge 1$	$=$	$x$
(Απορροφητικό στοιχείο της $\wedge$)	$x\wedge 0$	$=$	$0$

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

(Ταυτοδυναμία της $\vee$)	$x\vee x$	$=$	$x$
(Ταυτοδυναμία της $\wedge$)	$x\wedge x$	$=$	$x$
(Νόμος της απορρόφησης 1)	$x\wedge (x\vee y)$	$=$	$x$
(Νόμος της απορρόφησης 2)	$x\vee (x\wedge y)$	$=$	$x$
(Επιμεριστική ιδιότητα της $\vee$ ως προς την $\wedge$)	$x\vee (y\wedge z)$	$=$	$(x\vee y)\wedge (x\vee z)$
(Απορροφητικό στοιχείο της $\vee$)	$x\vee 1$	$=$	$1$

Μη μονότονοι νόμοι

Οι δύο νόμοι για το συμπλήρωμα είναι οι εξής:

• (Συμπλήρωμα 1) $x\wedge \neg x=0$,
• (Συμπλήρωμα 2) $x\vee \neg x=1$.

Και στη στοιχειώδη και στην Άλγεβρα Μπουλ ισχύει ο νόμος της διπλής άρνησης:

• (Διπλή άρνηση) $\neg \neg x=x$.

Αλλά, ενώ η στοιχειώδης Άλγεβρα πληροί τους δύο νόμους:

• $(-x)(-y)=xy$,
• $(-x)+(-y)=-(x+y)$.

η άλγεβρα Μπουλ πληροί τους δύο νόμους Ντε Μόργκαν:

• (Ντε Μόργκαν 1) $(\neg x)\wedge (\neg y)=\neg (x\vee y)$,
• (Ντε Μόργκαν 2) $(\neg x)\vee (\neg y)=\neg (x\wedge y)$.

Αρχή του δυϊσμού

Αν σε μια λογική έκφραση αντικατασταθούν το (συν +) με (επί •) και το (επί •) με (συν +) και το (μηδέν 0) με (ένα 1) και το (ένα 1) με (μηδέν 0) δημιουργείται η δυϊκή έκφραση, που ισχύει όπως και η αρχική. Η αρχή του δυϊσμού εμφανίζεται και στα αξιώματα του Χάντινγκτον, που δίνονται κατά ζεύγη.

Άλγεβρα Μπουλ και θεωρία συνόλων

Θα μπορούσαμε να δούμε τη θεωρία συνόλων (τις πράξεις με σύνολα) ως μια άλγεβρα Μπουλ. Ας δούμε τις αντιστοιχίες:

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

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

Άλγεβρα Μπουλ και προτασιακή λογική

Λογική πρόταση είναι κάθε σύνολο χαρακτήρων ή λέξεων που μπορούμε να του δώσουμε την τιμή «ψευδής» ή «αληθής».

Η πρόταση p=[Θα κερδίσω το λαχείο μεθαύριο] δεν είναι λογική πρόταση.

Η πρόταση q=[Ο ακέραιος αριθμός 4 είναι άρτιος] είναι λογική πρόταση και έχει αληθοτιμή = «αληθής».

Θα μπορούσαμε να δούμε την προτασιακή λογική (πράξεις με λογικές προτάσεις) ως μια άλγεβρα Μπουλ. Ας δούμε τις αντιστοιχίες:

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

Πίνακας αντιστοιχιών άλγεβρας Μπουλ, συνολοθεωρίας και προτασιακής λογικής
Άλγεβρα Μπουλ		Θεωρία Συνόλων		Προτασιακή Λογική
Πρόσθεση	$+$	Ένωση	$\cup$	Διάζευξη	$\vee$
Πολλαπλασιασμός	$\cdot$	Τομή	$\cap$	Σύζευξη	$\wedge$
Μηδέν	$0$	Κενό σύνολο	$\varnothing$	Ψευδής	F
Ένα	$1$	καθολικό σύνολο	$U$	Αληθής	${\rm {T}}$
Στοιχεία	$\alpha ,\beta$	Σύνολα	$A,B$	Προτάσεις	$p,q$
Συμπλήρωμα του $\alpha$	$\alpha '$	Σχετικό συμπλήρωμα του $A$	$A^{C}$	Λογική άρνηση	$\neg p$

Παραδείγματα όμοιων προτάσεων σε διάφορους συμβολισμούς
Άλγεβρα Μπουλ	Θεωρία Συνόλων	Προτασιακή Λογική
$\alpha \alpha '=0$	$A\cap A^{C}=\varnothing$	$p\wedge \neg p={\rm {F}}$
$\alpha +\alpha \beta =\alpha$	$A\cup (A\cap B)=A$	$p\vee (p\wedge q)=p$
$(\alpha \beta )'=\alpha '+\beta '$	$(A\cap B)^{C}=A^{C}\cup B^{C}$	$\neg (p\wedge q)=\neg p\vee \neg q$

Ψηφιακές λογικές πύλες

Ψηφιακή λογική είναι η εφαρμογή της Άλγεβρας Μπουλ σε υλικό υπολογιστή που αποτελείται από λογικές πύλες που συνδέονται μεταξύ τους προκειμένου να σχηματισθούν πιο σύνθετα κυκλώματα. Κάθε λογική πύλη αντιστοιχεί σε μια από τις πράξεις της Άλγεβρας Μπουλ και αναπαρίσταται γραφικά με διαφορετικό σχήμα. Στην επόμενη εικόνα φαίνονται τα σχήματα για τις πύλες ΚΑΙ (AND), Ή (OR) και ΟΧΙ (ΝΟΤ).

Σχηματική αναπαράσταση των λογικών πυλών ΚΑΙ, 'Η, ΟΧΙ (από αριστερά προς τα δεξιά)

Οι γραμμές στα αριστερά κάθε λογικής πύλης αναπαριστούν καλώδια εισόδου (ή αλλιώς ports). Η τιμή της εισόδου είναι η τιμή της τάσης (διαφορά δυναμικού). Για παράδειγμα, τάση κοντά στο μηδέν θα μπορούσε να αντιστοιχισθεί στην αληθοτιμή 0 και υψηλότερη διαφορά δυναμικού στην αληθοτιμή 1. Αυτός είναι ένας από τους τρόπους αντιστοίχισης τάσης με αληθοτιμές. Η γραμμή στα δεξιά κάθε πύλης αναπαριστά την έξοδο της λογικής πύλης. Συνήθως ακολουθείται η ίδια σύμβαση αντιστοίχισης τάσης-αληθοτιμών στις εισόδους και στην έξοδο.

Η λογική άρνηση υλοποιείται με τη χρήση ενός αντιστροφέα, ο οποίος συμβολίζεται με ένα κυκλίσκο. Το τρίγωνο μπροστά από τον κυκλίσκο υποδηλώνει απλώς αντιγραφή της εισόδου.

Εάν χρησιμοποιήσουμε το συμπλήρωμα σε όλες τις θύρες (ports) κάθε λογικής πύλης, και χρησιμοποιήσουμε την πύλη ΚΑΙ στη θέση της πύλης Ή και αντίστροφα, τότε θα έχουμε υλοποιήσει ισοδύναμα τις τρεις αρχικές πράξεις. Το γεγονός αυτό επιδεικνύει την εφαρμογή των δύο νόμων De Morgan καθώς και της αρχής της δυαδικότητας.

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

Δείτε επίσης

• Τζορτζ Μπουλ
• Λογική Σχεδίαση
• Λογική Πύλη
• Θεωρία συνόλων

Εξωτερικοί σύνδεσμοι

• Monk, J. Donald, The Mathematics of Boolean Algebra