Άλγεβρα Boole — Νόμοι, Θεωρήματα & Απλοποίηση

Η άλγεβρα Boole είναι το σύστημα που χρησιμοποιείται για να συνδυάζουμε και να απλοποιούμε εκφράσεις αληθές/ψευδές. Αν προσπαθείς να μειώσεις μια λογική έκφραση όπως η $AB + A\overline{B}$, τα βασικά εργαλεία είναι νόμοι όπως ο νόμος του συμπληρώματος, η επιμεριστική ιδιότητα, η απορρόφηση και τα θεωρήματα του De Morgan.

Σε μια συνηθισμένη σημειογραφία, το $x + y$ σημαίνει OR, το $xy$ σημαίνει AND και το $\overline{x}$ σημαίνει NOT $x$. Σε ορισμένα βιβλία το NOT γράφεται ως $x'$, αλλά οι βασικοί κανόνες είναι οι ίδιοι.

Τι σημαίνει η Άλγεβρα Boole

Η συνηθισμένη άλγεβρα δουλεύει με αριθμούς. Η άλγεβρα Boole δουλεύει με προτάσεις ή δυαδικές μεταβλητές που μπορούν να πάρουν μόνο δύο τιμές: αληθές/ψευδές ή $1/0$.

Αυτό αλλάζει τους κανόνες. Στην άλγεβρα Boole,

$$x + x = x \quad \text{and} \quad xx = x$$

Και οι δύο ταυτότητες λένε το ίδιο πράγμα: η επανάληψη μιας συνθήκης δεν δημιουργεί νέο αποτέλεσμα. Αν ένας διακόπτης είναι ήδη ανοιχτός, το να πεις "on OR on" δεν αλλάζει τίποτα.

Οι νόμοι της Άλγεβρας Boole που χρησιμοποιείς πραγματικά

Αυτοί είναι οι νόμοι που εμφανίζονται πιο συχνά όταν απλοποιείς μια έκφραση Boolean.

Νόμοι ταυτότητας

$$x + 0 = x, \qquad x \cdot 1 = x$$

Η πρόσθεση του false δεν αλλάζει τίποτα, και το AND με true δεν αλλάζει τίποτα.

Νόμοι μηδενισμού

$$x + 1 = 1, \qquad x \cdot 0 = 0$$

Αν ένα OR περιέχει ήδη true, όλο το αποτέλεσμα είναι true. Αν ένα AND περιέχει false, όλο το αποτέλεσμα είναι false.

Ιδιοδύναμοι νόμοι

$$x + x = x, \qquad x \cdot x = x$$

Η επανάληψη της ίδιας μεταβλητής δεν αλλάζει την έκφραση.

Νόμοι συμπληρώματος

$$x + \overline{x} = 1, \qquad x \cdot \overline{x} = 0$$

Μια μεταβλητή και το αντίθετό της καλύπτουν κάθε περίπτωση στο OR, αλλά δεν επικαλύπτονται ποτέ στο AND.

Αντιμεταθετικοί και προσεταιριστικοί νόμοι

$$x + y = y + x, \qquad xy = yx$$ $$(x + y) + z = x + (y + z), \qquad (xy)z = x(yz)$$

Αυτοί σου επιτρέπουν να αλλάζεις τη σειρά ή την ομαδοποίηση των όρων χωρίς να αλλάζει το αποτέλεσμα.

Επιμεριστικοί νόμοι

$$x(y + z) = xy + xz$$ $$x + yz = (x + y)(x + z)$$

Η δεύτερη μορφή συχνά φαίνεται λιγότερο οικεία, αλλά είναι μια τυπική Boolean ταυτότητα και εμφανίζεται στην παραγοντοποίηση.

Νόμοι απορρόφησης

$$x + xy = x, \qquad x(x + y) = x$$

Αυτοί είναι ιδιαίτερα χρήσιμοι όταν μια έκφραση φαίνεται πιο μεγάλη απ’ όσο πραγματικά είναι.

Θεωρήματα του De Morgan

$$\overline{x + y} = \overline{x}\,\overline{y}, \qquad \overline{xy} = \overline{x} + \overline{y}$$

Αυτά δείχνουν πώς μια άρνηση μετακινείται πάνω από OR και AND. Όταν το NOT περνά μέσα από παρενθέσεις, το OR και το AND αλλάζουν ρόλους.

Λυμένο παράδειγμα: Απλοποίησε το $AB + A\overline{B}$

Ξεκίνα με

$$F = AB + A\overline{B}$$

Βγάλε κοινό παράγοντα το $A$:

$$F = A(B + \overline{B})$$

Τώρα χρησιμοποίησε τον νόμο του συμπληρώματος:

$$F = A \cdot 1$$

Έπειτα χρησιμοποίησε τον νόμο ταυτότητας:

$$F = A$$

Άρα $AB + A\overline{B} = A$. Διαισθητικά, αν $A = 1$, τότε είτε $B = 1$ είτε $\overline{B} = 1$, οπότε ένας όρος πρέπει να είναι true. Αν $A = 0$, και οι δύο όροι είναι false. Όλη η έκφραση εξαρτάται μόνο από το $A$.

Συνηθισμένα λάθη στην Άλγεβρα Boole

Ένα συνηθισμένο λάθος είναι να μεταφέρεις συνήθειες της συνηθισμένης άλγεβρας στην άλγεβρα Boole. Για παράδειγμα, το $x + x = 2x$ δεν είναι κανόνας της Boolean άλγεβρας. Εδώ, το σωστό αποτέλεσμα είναι $x$.

Ένα άλλο λάθος είναι να εφαρμόζεις έναν νόμο χωρίς να ελέγχεις τη σημειογραφία. Σε πολλά κείμενα, το $+$ σημαίνει OR και όχι αριθμητική πρόσθεση, ενώ η παράθεση μεταβλητών σημαίνει AND.

Οι μαθητές επίσης κάνουν λάθος στα θεωρήματα του De Morgan, αρνούμενοι κάθε μεταβλητή αλλά ξεχνώντας να αλλάξουν το OR με AND και το αντίστροφο. Και τα δύο μέρη είναι απαραίτητα.

Πού χρησιμοποιείται η Άλγεβρα Boole

Η άλγεβρα Boole είναι θεμελιώδης στην ψηφιακή λογική, όπου οι μεταβλητές παριστάνουν καταστάσεις on/off ή true/false. Χρησιμοποιείται για την απλοποίηση σχεδίων κυκλωμάτων, για πιο καθαρές λογικές συνθήκες στο λογισμικό και για συλλογισμό πάνω σε φίλτρα αναζήτησης ή ερωτήματα βάσεων δεδομένων.

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

Δοκίμασε μια παρόμοια απλοποίηση

Δοκίμασε να απλοποιήσεις το $(A + B)(A + \overline{B})$. Αν χρησιμοποιήσεις προσεκτικά τους παραπάνω νόμους, απλοποιείται περισσότερο απ’ όσο φαίνεται αρχικά. Αν θέλεις να πας ένα βήμα παραπέρα, φτιάξε έναν πίνακα αλήθειας και έλεγξε ότι η απλοποιημένη μορφή ταιριάζει σε κάθε γραμμή.