LOGIKA BOOLE'A


Algebra Boole'a to dział matematyki zajmujący się operacjami na zmiennych dwuargumentowych. Umownie przyjęto, że do oznaczenia wartości tych zmiennych używa się symboli 0 oraz 1. Tutaj do oznaczania zmiennych będę używał liter alfabetu (a; b; c; ....).


Spis treści

1 Operacje na zmiennych dwuargumentowych 2 Algebra Boole'a i elektronika cyfrowa

3 Konstruowanie układów odzwierciedlających operacje logiczne

4 Tabele prawdy


1. Operacje na zmiennych dwuagrumentowych

1.1 Trzy podstawowe operacje

Na zmiennych dwuargumentowych można przeprowadzić kilka operacji, z czego trzy są "podstawowe" :

Suma logiczna (znana także jako alternatywa oraz dysjunkcja) oznaczana jest operatorem + lub jako OR. Wartość sumy logicznej jest równa 1, gdy przynajmniej jedna z sumowanych zmiennych ma wartość 1.

Iloczyn logiczny (koniukcja) oznaczany jest operatorem mnożenia ( * ) lub jako AND. Wartość iloczynu logicznego równa jest 1, tylko gdy wszystkie argumenty operacji mają wartość 1.

Negacja (znana również jako dopełnienie) to operacja jednoargumentowa, której wynikiem jest 1, gdy argument ma wartość 0, a 0, gdy argument ma wartość 1. Negacja oznaczana jest najczęściej symbolem ~ (tylda) lub ! (wykrzyknik).

Podsumowując informacje o trzech podstawowych operacjach logicznych: OR, AND oraz NOT (negacja) przedstawiam tabelkę ukazującą wyniki tych operacji w zależności od wartości argumentów.

A
B
A+B
A*B
!A
0
0
0
0
1
0
1
1
0
1
1
0
1
0
0
1
1
1
1
0


1.2 Kilka przydatnych wzorów

No to teraz troche tego co najgorsze, czyli przydatne wzory:

a * 0 = 0
a * 1 = a
a + !a = 1
a + 1 = 1
a + 0 = a
a * !a = 0
!(!a) = a
a * (b + c) = a * b + a * c !(a * b) = !a + !b // pierwsze prawo Demorgana
!(a + b) = !a * !b // drugie prawo Demorgana


1.3 Inne operacje logiczne

Oprócz tych już opisanycyh funkcji istnieje jeszcze kilka mniej popularnych, które mogą się jednak przydać:

Funkcja Pierce'a, która przyjmuje wartość 1, gdy oba argumeny mają wartość 0. Funkcję tę można zastąpić wyrażeniem !(a + b), ponieważ wyniki oby dwóch są takie same.

Funkcja Schaffera, która przyjmuje wartość 1, gdy przynajmniej jeden argument ma wartość 0. Oznaczenie funkcji Schaffera to | (np. a | b). Funkcję tę można zastąpić także wyrażeniem !(a * b).

Suma modulo, która przyjmuje wartość 1, gdy tylko jeden z jej argumentów ma wartość 1, a drugi ma wartość 0. Do oznaczania tej funkcji używa się symbolu % (procent).


2. Algebra Boole'a i elektronika cyfrowa

Elektronika cyfrowa przetwarza informacje opierając się na dwóch podstawowych stanach sygnału, które mogą zaistnieć. Te stany to stan niski oraz stan wysoki. Nie trudno się domyśleć, że jeślibyśmy oznaczyli stan niski jako 0, a stan wysoki odpowiednio jako 1, to zasady algebry Boole'a można by także wykorzystywać do projektowania układów, przez które przechodzić będą sygnały. O tym troche później. Teraz wystarczy że wyobrazisz sobie, w jaki sposób sygnał można przedstawić jako ciąg zer i jedynek. Przyjmijmy więc, że sygnał to stan napięcia (0 - nie ma, 1 - jest) w pewnej jednostce czasu:

Jesli przyjrzałeś się rysunkowi to chyba wszystko już jarzysz.


3. Konstruowanie układów odzwierciedlających operacje logiczne

Układy takie, to nic innego jak tylko graficzne przedstawienie operacji logicznych wykonywanych na jednym lub większej liczbie sygnałów. Tak będę przedstawiał graficznie sygnały, oraz operacje wykonywane na nich:

Tak więc przedstawione graficznie (po obu stronach znaku =) pierwsze prawo Demorgana wyglądałoby tak:

A graficzne przedstawienie wyrażenia a + !b tak:

Dobra chyba konstruowanie układów już zajażyłeś :) .


4. "Tabelki prawdy"

Tabele prawdy to tabele budowane, aby potwierdzić możliwość zamiany jednego wyrażenia na drugie. Jeżeli oba te wyrażenia dają identyczne wyniki dla wszystkich możliwości wartości argumentów, oznacza to że taka możliwość istnieje.
Spróbujmy więc udowodnić że a + b * c = (a + b) * (a + c).
W pierwszym wierszu opisana będzie kolejność wykonywanych operacji, w drugim wykonywana operacja, a w pozostałych wyniki operacji, w zależności od wartości argumentów. Na zielono zaznaczono operacje dotyczące prawej strony równości, a na niebiesko operacje dotyczące lewej strony równości.

1
1
1
2
2
2
3
3
A
B
C
A+B
A+C
B*C
(A+B)*(A+C)
A+B*C
0
0
0
0
0
0
0
0
0
0
1
0
1
0
0
0
0
1
0
1
0
0
0
0
0
1
1
1
1
1
1
1
1
0
0
1
1
0
1
1
1
0
1
1
1
0
1
1
1
1
0
1
1
0
1
1
1
1
1
1
1
1
1
1


Jak widać ostateczne wyniki - (A+B)*(A+C) oraz A+B*C - są takie same, więc "tabela prawdy" udowodniła tę prawidłowość. Gdyby chociaż w jednym wierszu, ostateczne wyniki różniły się, oznaczałoby to, że równanie nie jest prawdziwe.