Η άλγεβρα Boole, σαν μαθηματικό σύστημα, ορίζεται πάνω σε ένα σύνολο δυο στοιχείων B={0, 1} στο οποίο έχουμε ορίσει κανόνες για δυο δυαδικούς τελεστές + και ‧ ακριβώς όπως φαίνεται στους παρακάτω πίνακες. Αυτοί οι κανόνες για τους τελεστές + και ‧ είναι οι ίδιοι με τις λογικές πράξεις AND (KAI) και OR (‘Η) αντίστοιχα, της δυαδικής λογικής.

Οι ιδιότητες των τελεστών + και ‧ στην άλγεβρα Boole αποτελούνται από αξιώματα και θεωρήματα. Τα αξιώματα θεωρούνται πρωταρχικά και επαληθεύονται με τον πίνακα αληθείας, ενώ τα θεωρήματα επαληθεύονται με αλγεβρικές πράξεις πάνω στα αξιώματα και σε άλλα θεωρήματα.

Αξιώματα της άλγεβρας Boole

Αξίωμα 1^ο :
(α) το σύνολο Β={0, 1} είναι κλειστό ως προς τον τελεστή +
(β) το σύνολο Β={0, 1} είναι κλειστό ως προς τον τελεστή ‧

Αξίωμα 2^ο :
(α) το ουδέτερο στοιχείο ως προς τον τελεστή + είναι το 0 διότι x + 0 = 0 + x = x
       πράγματι:  για x=0 είναι 0 + 0 = 0 και για x=1 είναι 1 + 0 = 0 + 1 = 1
(β) το ουδέτερο στοιχείο ως προς τον τελεστή ‧ είναι το 1 διότι x ‧ 1 = 1 ‧ x = x
       πράγματι:  για x=0  είναι 0 ‧ 1 = 1 ‧ 0 = 0 και για x = 1 είναι 1 ‧ 1 = 1

Αξίωμα 3^ο :
(α) αντιμεταθετική ως προς + διότι: x + y = y + x
(β) αντιμεταθετική ως προς ‧  διότι: x ‧ y = y ‧ x
Πράγματι οι αντιμεταθετικοί νόμοι είναι φανεροί από την συμμετρία των πινάκων των δυαδικών τελεστών.

Αξίωμα 4^ο :
(α) ο τελεστής ‧ είναι επιμεριστικός ως προς τον +: x ‧ (y + z) = (x ‧ y) + (x ‧ z)
το αξίωμα αυτό μπορεί να επαληθευτεί από τους πίνακες τελεστών, σχηματίζοντας ένα πίνακα αληθείας με όλες τις δυνατές τιμές των x, y και z. Για κάθε συνδυασμό βρίσκουμε το x ‧ (y + z) και δείχνουμε ότι η τιμή του είναι η ίδια με την τιμή του (x ‧ y) + (x ‧ z)
(β) ο τελεστής + είναι επιμεριστικός ως προς τον ‧ : x + (y ‧ z) = (x + y) ‧ (x + z)

Αξίωμα 5^ο :
Για κάθε στοιχείο x του συνόλου Β={0, 1} υπάρχει ένα στοιχείο x’ του συνόλου Β που ονομάζεται «συμπλήρωμα» του x συγκεκριμένα ισχύει 0’ = 1  και 1’ = 0
(α) x + x’ = 1  πράγματι: για x = 0 είναι: 0 + 0’ = 0 + 1 = 1  για x = 1 είναι: 1 + 1’ = 1 + 0 = 1
(β) x ‧ x’ = 0  πράγματι: για x = 0 είναι 0 ‧ 0’ = 0 ‧ 1 = 0 για x = 1 είναι:  1 ‧ 1’ = 1 ‧ 0 = 0

Θεωρήματα της άλγεβρας Boole

Θεώρημα 1^ο :  (α) x + x = x    (β) x ‧ x = x
Θεώρημα 2^ο : (α) x + 1 = 1    (β) x ‧ 0 = 0
Θεώρημα 3^ο : (δύο αρνήσεις) (x’)’ = x
Θεώρημα 4^ο : (προσεταιριστική) (α) x + (y + z) = (x + y) +z  (β) x ‧ (y ‧ z) = (x ‧ y) ‧ z
Θεώρημα 5^ο : De Morgan (α) (x + y)’ = x’ ‧ y’   (β) (x ‧ y)’ = x’ + y’
Θεώρημα 6^ο : (απορρόφησης)  (α) x + x ‧ y = x   (β) x ‧ (x + y) = x

Αποδείξεις θεωρημάτων Boole

Θεώρημα 1^ο :
(α) x + x =
= (x + x) ‧ 1
=(x + x)(x + x’)  (από αξίωμα 5(α))
= x + xx’ =   (από αξίωμα 4(β))
= x + 0
= x
(β) x ‧ x = xx + 0
= xx + xx’
= x(x + x’)=  από αξίωμα 4(α)
= x ‧ 1=x
Παρατηρήστε ότι το θεώρημα 1(β) είναι το δυϊκό του θεωρήματος 1(α) και ότι κάθε βήμα της απόδειξης στο μέρος (β) είναι δυϊκό του αντίστοιχου στο μέρος (α). Οποιοδήποτε δυϊκό θεώρημα μπορεί να αποδειχτεί παρόμοια, παίρνοντας το δυϊκό της απόδειξης.

Θεώρημα 2^ο :
(α) x + 1
= 1 ‧ (x + 1)  (από αξίωμα 2(β))
= (x + x’)(x + 1)  (από αξίωμα 5(α))
= x + x’ ‧ 1   (από αξίωμα 4(β)) 
= x + x ’= 1

(β) x ‧ 0 = 0  (από τον δυϊσμό)

Θεώρημα 3^ο :
Από το αξίωμα 5 έχουμε ότι x + x’ = 1 και x ‧ x’ = 0 που ορίζουν το συμπλήρωμα του x. Άρα το συμπλήρωμα του x είναι το x’ και επίσης το (x’)’ Επομένως αφού το συμπλήρωμα είναι μοναδικό, έχουμε ότι (x’)’ = x.

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

Θεώρημα 6^ο :
(α) x + xy
= x ‧ 1 + xy      (από αξίωμα 2(β))
= x(1 + y)      (από αξίωμα  4(α))
= x ‧ 1            (από αξίωμα 2(β))
= x

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

Οι αλγεβρικές αποδείξεις του προσεταιριστικού νόμου και του θεωρήματος De Morgan είναι μεγάλες και δεν θα τις δώσουμε εδώ. Ωστόσο, η ισχύς τους μπορεί να αποδειχθεί εύκολα με τους πίνακες αληθείας. Για παράδειγμα, ο πίνακας αληθείας για το πρώτο θεώρημα De Morgan, (x+y)’=x’y’ δίνεται παρακάτω:

Προτεραιότητα Τελεστών

Η προτεραιότητα των τελεστών για τον υπολογισμό των εκφράσεων Boole ακολουθεί τη σειρά:
(1) παρενθέσεις (2) NOT (3) AND και(4) OR
Με άλλα λόγια, κάθε έκφραση μέσα σε παρενθέσεις πρέπει να υπολογίζεται πριν γίνουν άλλες πράξεις. Η επόμενη πράξη που έχει προτεραιότητα είναι το συμπλήρωμα, μετά ακολουθεί η πράξη AND και τέλος η OR.

Σαν παράδειγμα θεωρήστε την έκφραση του θεωρήματος De Morgan. Το αριστερό μέλος της έκφρασης είναι το (x+y)’. Επομένως, η έκφραση μέσα στις παρενθέσεις υπολογίζεται πρώτα και συμπληρώνεται το αποτέλεσμα. Το δεξιό μέλος της έκφρασης είναι x’y’. Άρα, πρώτα υπολογίζονται τα συμπληρώματα των x και y και μετά το «AND» τους.