1.2 Η ΔΙΤΙΜΗ ΑΛΓΕΒΡΑ BOOLE
1.2.1 Ορισμός
Η Αλγεβρα Boole (Boolean algebra) πήρε το όνομά της από τον G. Boole (1815-1864), ο οποίος ανέπτυξε ένα αλγεβρικό σύστημα (1854) για τη συστηματική αντιμετώπιση της λογικής. Τα αξιώματα της Αλγεβρας Boole διατυπώθηκαν από τον E. V. Huntington (1904).
Οι μεταβλητές που χρησιμοποιούνται στην Αλγεβρα Boole ονομάζονται λογικές μεταβλητές γιατί μπορούν να πάρουν δύο (2) μόνο τιμές: 0 και 1. Αυτός είναι ο λόγος που η Αλγεβρα Boole αποτελεί τη βάση για τα ψηφιακά ηλεκτρονικά κυκλώματα.
Στην Αλγεβρα Boole ορίζονται τρεις βασικές πράξεις:
α) η πράξη NOT (ΟΧΙ) με σύμβολο - (π.χ. Ã ) και διαβάζεται συμπλήρωμα Α
β) η πράξη AND (ΚΑΙ) με σύμβολο ·
γ) η πράξη OR (Η) με σύμβολο +
Η πράξη NOT
Στην πράξη NOT συμμετέχει μία μόνο λογική μεταβλητή και το αποτέλεσμα της πράξης είναι το συμπλήρωμα (αντίστροφο) της μεταβλητής αυτής, δηλαδή αν η μεταβλητή έχει την τιμή “0”, τότε το αποτέλεσμα είναι “1” και αντίστροφα αν η μεταβλητή έχει την τιμή “1”, τότε το αποτέλεσμα είναι “0”.
Αν A είναι μία λογική μεταβλητή, τότε η πράξη NOT εκφράζεται με τη σχέση: Υ=Ã
Ο πίνακας αληθείας της πράξης NOT παρουσιάζεται στον Πίνακα 1.2.1.
|
A |
Υ=Ã |
|
0 |
1 |
|
1 |
0 |
Πίνανας 1.2.1 Πίνακας Αληθείας της πράξης NOT
Η πράξη AND
Στην πράξη AND συμμετέχουν δύο λογικές μεταβλητές και το αποτέλεσμα της πράξης είναι “1”, αν και οι δύο μεταβλητές είναι “1”.
Αν A και B είναι δύο λογικές μεταβλητές, τότε η πράξη AND εκφράζεται με τη σχέση:
Y=A·B
Σημείωση: το σύμβολο της πράξης AND (·) μπορεί να παραλείπεται στις εκφράσεις της Αλγεβρας Boole (A·B=AB).
Ο πίνακας αληθείας της πράξης AND παρουσιάζεται στον Πίνακα 1.2.2.
|
A |
B |
Y=A·B |
|
0 |
0 |
0 |
|
0 |
1 |
0 |
|
1 |
0 |
0 |
|
1 |
1 |
1 |
Πίνανας 1.2.2 Πίνακας Αληθείας της πράξης AND
Η πράξη OR
Στην πράξη OR συμμετέχουν δύο λογικές μεταβλητές και το αποτέλεσμα της πράξης είναι “1”, αν τουλάχιστον μία από τις δύο μεταβλητές είναι “1”.
Αν A και B είναι δύο λογικές μεταβλητές, τότε η πράξη OR εκφράζεται με τη σχέση:
Y=A+B
Ο πίνακας αληθείας της πράξης OR παρουσιάζεται στον Πίνακα 1.2.3.
|
A |
B |
Y=A+B |
|
0 |
0 |
0 |
|
0 |
1 |
1 |
|
1 |
0 |
1 |
|
1 |
1 |
1 |
Πίνανας 1.2.3 Πίνακας Αληθείας της πράξης OR
1.2.2 Αξιώματα Huntington
1. Ουδέτερα στοιχεία των πράξεων AND και OR
Το ουδέτερο στοιχείο της πράξης AND είναι το 1 και το ουδέτερο στοιχείο της πράξης OR είναι το 0.
α. x·1=1·x=x
β. x+0=0+x=x
Το αξίωμα αυτό μπορεί να επαληθευτεί από τους πίνακες αληθείας των πράξεων AND και OR, από όπου φαίνεται ότι:
0·1=1·0=0 και 1·1=1
και
0+0=0 και 1+0=0+1=1
2. Αντιμεταθετική ιδιότητα των πράξεων AND και OR
Οι πράξεις AND και OR έχουν την αντιμεταθετική ιδιότητα.
α. x·y=y·x
β. x+y=y+x
3. Επιμεριστική ιδιότητα των πράξεων AND και OR
Η πράξη AND έχει την επιμεριστική ιδιότητα ως προς την πράξη OR και η πράξη OR έχει την επιμεριστική ιδιότητα ως προς την πράξη AND.
α. x· (y+z)=(x·y)+(x·z)
β. x+(y·z)=(x+y)·(x+z)
4. Μοναδικό Συμπλήρωμα (NOT)
Κάθε λογική μεταβλητή x έχει ένα μοναδικό συμπλήρωμα με τις ακόλουθες ιδιότητες:
α. Α· Ã=0
β. Α+Ã=1
Το αξίωμα αυτό μπορεί να επαληθευτεί από τους πίνακες αληθείας της πράξης NOT, από όπου φαίνεται ότι:
0·ΣΥΜΠΛ 0 =0·1=0 και 1·ΣΥΜΠΛ 1 =1·0=0
και
0+ΣΥΜΠΛ 0=0+1=1 και 1+ΣΥΜΠΛ 1=1+0=1
1.2.3 Αρχή Δυισμού
Η ισχύς των εκφράσεων της Αλγεβρας Boole εξακολουθεί να υφίσταται, αν γίνει αλλαγή των πράξεων AND και OR και των ουδέτερων στοιχείων μεταξύ τους ( · « + και 0 « 1 ).
Για παράδειγμα, αν ισχύει η έκφραση x+1=1, τότε ισχύει και η έκφραση x·0=0 και η μία έκφραση ονομάζεται δυική της άλλης.
1.2.4 Θεωρήματα Αλγεβρας Boole
Θεώρημα 1.
α. x·x=x
β. x+x=x
Θεώρημα 2.
α. x·0=0
β. x+1=1
Θεώρημα 3.
x=
Θεώρημα 4. Προσεταιριστική ιδιότητα
α. x·y·z=x·(y·z)=(x·y)·z
β. x+y+z=x+(y+z)=(x+y)+z
Θεώρημα 5. Θεώρημα απορρόφησης
α. x+x·y=x
β. x·(x+y)=x
Θεώρημα 6. Θεώρημα De Morgan
α.
β.
Παρατήρηση:
Το Θεώρημα De Morgan ισχύει και για περισσότερες από δύο μεταβλητές:
α.
β.
1.2.5. Προτεραιότητα πράξεων
Για την εκτέλεση των πράξεων στις εκφράσεις της Αλγεβρας Boole είναι ανάγκη να καθορισθεί η προτεραιότητα της εκτέλεσής τους, όπως γίνεται στην γνωστή από τα μαθηματικά άλγεβρα.
Ο Πίνακας προτεραιότητας των πράξεων παρουσιάζεται στον Πίνακα 1.2.4.
|
Προτεραιότητα |
Πράξη |
|
1 |
( ) |
|
2 |
NOT |
|
3 |
AND |
|
4 |
OR |
Πίνακας 1.2.4. Προτεραιότητα πράξεων
Από τον Πίνακα προτεραιότητας των πράξεων προκύπτει ότι σε μία έκφραση της Αλγεβρας Boole εκτελούνται πρώτα οι πράξεις μέσα σε παρενθέσεις, μετά υπολογίζονται τα συμπληρώματα, στην συνέχεια εκτελούνται οι πράξεις AND και τέλος εκτελούνται οι πράξεις OR.
