Podstawy i prawa algebry logiki

Irlandzki matematyk z połowy XIX wieku Jerzego Bulla opracował algebrę logiki („Studium praw myślenia”). Stąd też nazywa się algebra logiki algebra Boole'a.

Poprzez nadawanie oznaczeń literowych, wyrażanie operacji przekształceń logicznych w symbolach działań oraz stosowanie reguł i aksjomatów ustanowionych dla tych działań, algebra logiki pozwala w pełni opisać proces wnioskowania w rozwiązywaniu problemu zadanego w kategoriach logiki zdań w algorytmach , to znaczy mieć matematycznie napisany program rozwiązujący ten problem.

Aby oznaczyć prawdziwość lub fałszywość stwierdzeń (to znaczy wprowadzić wartości do oceny stwierdzeń), algebra logiki wykorzystuje wygodny w tym przypadku system binarny. Jeśli zdanie jest prawdziwe, przyjmuje wartość 1, jeśli jest fałszywe, przyjmuje wartość 0. W przeciwieństwie do liczb binarnych, logiczne 1 i 0 nie wyrażają ilości, ale stan.

Tak więc w obwodach elektrycznych opisanych za pomocą algebry Boole'a, gdzie 1 oznacza obecność napięcia, a 0 jego brak, dostarczenie napięć z kilku źródeł do jednego węzła obwodu (czyli przybycie kilku jego jednostek logicznych) jest pokazuje również jako jednostkę logiczną, która wskazuje nie całkowite napięcie w węźle, ale tylko jego obecność.

Przy opisie sygnałów wejściowych i wyjściowych układów logicznych stosuje się zmienne, które przyjmują wartości tylko logicznego 0 lub 1. Określa się zależność sygnałów wyjściowych od wejścia operacja logiczna (funkcja)… Oznaczmy zmienne wejściowe przez X1 i X2, a wynik operacji logicznej na nich przez y.

Przemyśl to trzy podstawowe elementarne operacje logiczne, za pomocą których można opisać coraz bardziej złożone.

1. Operacja OR — dodawanie logiczne:

Biorąc pod uwagę wszystkie możliwe wartości zmiennych, można zdefiniować operację OR jako wystarczającą ilość przynajmniej jednej jednostki na wejściu do wytworzenia jednej na wyjściu. Nazwę operacji wyjaśnia semantyczne znaczenie związku LUB w zdaniu: „Jeśli LUB to jedno wejście LUB drugie to jeden, to wyjście to jeden”.

2. Operacja AND — mnożenie logiczne:

Biorąc pod uwagę pełny zestaw wartości zmiennych, operacja AND jest zdefiniowana jako potrzeba dopasowania wszystkich jedynek na wejściach, aby uzyskać jedynkę na wyjściu: „Jeśli AND to jedno wejście, a drugie to jedynki, to wyjście jest jedno. «

3. Operacja NOT — logiczna negacja lub inwersja. Wskazuje na to pasek nad zmienną.

Po odwróceniu wartość zmiennej jest odwrócona.

Podstawowe prawa algebry logicznej:

1. Prawo zbioru zerowego: iloczyn dowolnej liczby zmiennych znika, jeśli którakolwiek ze zmiennych wynosi zero, niezależnie od wartości innych zmiennych:

2. Prawo zbioru uniwersalnego — suma dowolnej liczby zmiennych staje się jedynką, jeżeli przynajmniej jedna ze zmiennych ma wartość jeden, niezależnie od innych zmiennych:

3. Prawo powtórzeń — powtarzające się zmienne w wyrażeniu można pominąć (innymi słowy, w algebrze Boole'a nie ma potęgowania i mnożenia przez współczynnik numeryczny):

4. Prawo podwójnej inwersji — dwukrotna inwersja jest operacją pustą:

5. Prawo komplementarności — iloczyn każdej zmiennej i jej odwrotności wynosi zero:

6. Suma każdej zmiennej i jej odwrotności wynosi jeden:

7. Prawa ochronne — wynik operacji mnożenia i dodawania nie zależy od kolejności występowania zmiennych:

8. Połączone prawa — podczas operacji mnożenia i dodawania zmienne można grupować w dowolnej kolejności:

9. Prawa dystrybucji — dopuszcza się umieszczenie całkowitego współczynnika poza nawiasami:

10. Prawa absorpcji — wskazać sposoby uproszczenia wyrażeń zawierających zmienną we wszystkich czynnikach i terminach:

11. Prawa De Morgana — inwersja iloczynu jest sumą inwersji zmiennych:

odwrócenie sumy jest iloczynem odwrócenia zmiennych: