Algebra Boole’a — prawa, twierdzenia i upraszczanie

Algebra Boole’a to system używany do łączenia i upraszczania wyrażeń prawda/fałsz. Jeśli próbujesz zredukować wyrażenie logiczne takie jak $AB + A\overline{B}$, głównymi narzędziami są prawa, takie jak dopełnienie, rozdzielność, absorpcja oraz twierdzenia de Morgana.

W jednym z popularnych zapisów $x + y$ oznacza OR, $xy$ oznacza AND, a $\overline{x}$ oznacza NOT $x$. W niektórych książkach NOT zapisuje się jako $x'$, ale podstawowe reguły pozostają takie same.

Co oznacza algebra Boole’a

Zwykła algebra operuje na liczbach. Algebra Boole’a działa na zdaniach lub zmiennych binarnych, które mogą przyjmować tylko dwie wartości: prawda/fałsz albo $1/0$.

To zmienia reguły. W algebrze Boole’a

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

Obie tożsamości mówią to samo: powtórzenie warunku nie tworzy nowego wyniku. Jeśli przełącznik jest już włączony, powiedzenie „włączony OR włączony” niczego nie zmienia.

Prawa algebry Boole’a, których naprawdę używasz

To są prawa, które pojawiają się najczęściej podczas upraszczania wyrażenia boolowskiego.

Prawa identyczności

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

Dodanie fałszu nic nie zmienia, a AND z prawdą nic nie zmienia.

Prawa zera i jedynki

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

Jeśli OR zawiera już prawdę, cały wynik jest prawdziwy. Jeśli AND zawiera fałsz, cały wynik jest fałszywy.

Prawa idempotentności

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

Powtórzenie tej samej zmiennej nie zmienia wyrażenia.

Prawa dopełnienia

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

Zmienna i jej przeciwieństwo obejmują każdy przypadek w OR, ale nigdy nie zachodzą jednocześnie w AND.

Prawa przemienności i łączności

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

Pozwalają one zmieniać kolejność lub grupowanie składników bez zmiany wyniku.

Prawa rozdzielności

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

Druga postać często wydaje się mniej znajoma, ale jest standardową tożsamością boolowską i pojawia się przy wyłączaniu wspólnych czynników.

Prawa absorpcji

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

Są one szczególnie przydatne, gdy wyrażenie wygląda na dłuższe, niż jest w rzeczywistości.

Twierdzenia de Morgana

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

Mówią one, jak negacja przechodzi przez OR i AND. Gdy NOT przechodzi przez nawias, OR i AND zamieniają się rolami.

Przykład: uprość $AB + A\overline{B}$

Zacznij od

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

Wyłącz wspólne $A$:

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

Teraz użyj prawa dopełnienia:

$$F = A \cdot 1$$

Następnie użyj prawa identyczności:

$$F = A$$

Zatem $AB + A\overline{B} = A$. Intuicyjnie, jeśli $A = 1$, to albo $B = 1$, albo $\overline{B} = 1$, więc jeden z wyrazów musi być prawdziwy. Jeśli $A = 0$, oba wyrazy są fałszywe. Całe wyrażenie zależy tylko od $A$.

Typowe błędy w algebrze Boole’a

Jednym z częstych błędów jest przenoszenie nawyków ze zwykłej algebry do algebry Boole’a. Na przykład $x + x = 2x$ nie jest regułą boolowską. Tutaj poprawny wynik to $x$.

Innym błędem jest stosowanie prawa bez sprawdzenia notacji. W wielu tekstach $+$ oznacza OR, a nie dodawanie arytmetyczne, a zapisanie zmiennych obok siebie oznacza AND.

Uczniowie często też źle stosują twierdzenia de Morgana, negując każdą zmienną, ale zapominając zamienić OR i AND. Obie części są ważne.

Gdzie używa się algebry Boole’a

Algebra Boole’a jest podstawą logiki cyfrowej, gdzie zmienne reprezentują stany włączony/wyłączony albo prawda/fałsz. Używa się jej do upraszczania projektów układów, zapisywania czytelniejszych warunków logicznych w oprogramowaniu oraz analizowania filtrów wyszukiwania lub zapytań do baz danych.

Jeśli zmienne nie są binarne albo działania są zwykłą arytmetyką, prawa Boole’a nie mają bezpośredniego zastosowania. Warunek dwóch wartości jest tym, co sprawia, że ten system działa.

Spróbuj podobnego uproszczenia

Spróbuj uprościć $(A + B)(A + \overline{B})$. Jeśli uważnie zastosujesz powyższe prawa, wyrażenie uprości się bardziej, niż początkowo wygląda. Jeśli chcesz pójść o krok dalej, zbuduj tabelę prawdy i sprawdź, czy uproszczona postać zgadza się z każdym wierszem.