Podręcznik

Algebra Boole’a jest modelem matematycznym operacji na sygnałach binarnych reprezentujących sygnały elektryczne o dwóch wartościach: 0 lub 1. Wartości te są przyporządkowane dwom poziomom napięcia wytwarzanego przez (elektroniczne) układy logiczne. Najczęściej przyjmuje się, że napięciu wysokiemu jest przyporządkowana wartość sygnału 1, natomiast napięciu niskiemu – wartość 0.

Algebra Boole’a jest algebrą z trzema operacjami na dwuwartościowych argumentach, które przyjmują wartości: 0 i 1. Rezultaty tych operacji są także dwuwartościowe. Te trzy operacje to:

• suma logiczna (suma boolowska, dysjunkcja),
• iloczyn logiczny (iloczyn boolowski, koniunkcja),
• negacja (inwersja).

Dwie pierwsze operacje są wieloargumentowe, a trzecia jest jednoargumentowa.

Operacja sumy logicznej (OR) jest zdefiniowana następująco: jeżeli co najmniej jeden z argumentów jest równy 1, to wynik jest równy 1, zatem suma logiczna jest równa 0 tylko dla przypadku, gdy wszystkie argumenty są równe 0. Działania te zapisujemy następująco:

0 + 0 = 0

0 + 1 = 1

1 + 0 = 1

1 + 1 = 1

gdzie + oznacza operację OR. Operację OR realizuje bramka OR o symbolu graficznym jak na rys. 1.1a.

Rys.  1.1.  Bramki logiczne a) OR, b) AND, c) NOT

Operacja iloczynu logicznego (AND) jest zdefiniowana następująco: wynik iloczynu jest równy 1 wtedy i tylko wtedy, gdy wszystkie argumenty przyjmują wartość 1, co zapisujemy w następujący sposób:

0 × 0 = 0

0 × 1 = 0

1 × 0 = 0

1 × 1 = 1

gdzie × oznacza operację AND. Operację AND realizuje bramka AND o symbolu graficznym podanym na rys. 1.1b.

Operacja negacji (NOT) zmienia wartość argumentu na przeciwny. Negacją 0 jest 1, a negacją 1 jest 0, co zapisujemy:

$\bar{1}=0$

$\bar{0}=1$

Operacja NOT zmiennej x, jest oznaczana x , a jej symbol graficzny (bramka NOT) podany jest na rys. 1.1c.

Z punktu widzenia syntezy logicznej w technice cyfrowej specjalnemu zainteresowaniu podlega dwuelementowa algebra Boole’a, którą będziemy rozumieli jako system <B, +, · , 0, 1>, gdzie zbiorem jest B = {0, 1}. Dwuwartościowa (zwana również binarną) algebra Boole’a stanowi podstawę nowoczesnej syntezy logicznej formułując prawa jakim podlegają zmienne boolowskie tj. zmienne ze zbioru B. Prawa te (z uwzględnieniem praw De Morgana) podajemy zbiorczo w formie zestawienia, w którym każde prawo jest zaopatrzone w odpowiednią nazwę.

Prawa algebry Boole’a

Własności stałych

$a+0=a$   $a\cdot0=0$

$a+1=1$   $a\cdot1=a$

Własności negacji

$a+\bar{a}=1$     $a\cdot\bar{a}=0$

Podwójna negacja

$\bar{\bar{a}}=a$

Idempotentność

$a+a=a$     $a\cdot\ a=a$

Przemienność

$a+b=b+a$    $a\cdot\ b=b\cdot\ a$

Łączność

$a+\left(b+c\right)=\left(a+b\right)+c$     $a\cdot\left(b\cdot c\right)=\left(a\cdot b\right)\cdot\ c$

Rozdzielność

$a+\left(b\cdot c\right)=\left(a+b\right)\cdot\left(a+c\right)$    $a\cdot\left(b+c\right)=a\cdot\ b+a\cdot\ c$

Prawa De Morgana

$y=\bar{a\cdot b}=\bar{a}+\bar{b}$     $y=\bar{a+b}=\bar{a}\cdot\bar{b}$

W algebrze Boole’a, operacje „+” (dysjunkcja) i „×” (koniunkcja) nazywa się również przez analogię do arytmetyki odpowiednio dodawaniem i mnożeniem. Operacje dodawania i mnożenia są przemienne oraz rozdzielne względem siebie. Elementy binarne 0 oraz 1 spełniają rolę elementu neutralnego odpowiednio względem operacji dodawania i mnożenia. Dla każdego elementu a istnieje element $\bar{a},$ , nazywany negacją, spełniający odpowiednie własności.

Starszeństwo działań w algebrze Boole’a jest takie same jak w zwykłej arytmetyce (np. wyrażenie a + b·c interpretujemy jako a + (bc), a nie jako (a + b)c, a nawiasy są opuszczane tam, gdzie nie prowadzi to do nieporozumień; opuszczamy także znak mnożenia „×”, a zamiast symbolu „+”, często jest używany symbol Ú.

Wyrażenie boolowskie to formuła, w której zmienne boolowskie połączone są operatorami: + (OR), · (AND),  $\bar{x}$ (NOT).

Na przykład:

a + b + c · d + e

a + b + cd + e

a + b(d + e)

W zapisie wyrażeń boolowskich kropkę często pomija się, a kolejność operacji przyjmuje się następująco:

1. NOT
2. AND
3. OR

Kolejność ta może być zmieniona przez stosowanie nawiasów.

Typowym zastosowaniem algebry Boole’a jest uproszczenie wyrażeń boolowskich. Na przykład:

$\begin{array}{{>{\displaystyle}l}} \overline{a} bc+a\overline{b}\overline{c} +a\overline{b} c+ab\overline{c} +abc=\overline{a} bc+a\overline{b}\left(\overline{c} +c\right) +ab\left(\overline{c} +c\right) =\\ \ \ \ \ \ =\overline{a} bc+a\overline{b} +ab=\overline{a} bc+a\left(\overline{b} +b\right) =\overline{a} bc+a= \end{array}$

(korzystamy z własności a + abc = a(1 + bc) = a)

$=a+\bar{a}bc+abc=a+bc$