Wydział Inżynierii Materiałowej i Ceramiki AGH

Katedra Chemii Analitycznej

Algebra Boole'a

Instrukcja do ćwiczenia z przedmiotu Komputery w pracach eksperymentalnych

Opracowanie:

dr Małgorzata Jakubowska

Kraków 2002

Algebra Boole'a

Fundamentem teoretycznym dla techniki cyfrowej jest algebra Boole'a. Jej podstawy przedstawił matematyk angielski George Boole w opracowaniu pt. "An Investigation of the Laws of Thought" z 1854 roku. Dzieło to przeleżało na półkach ponad pół wieku, zanim znalazło zastosowanie w technice do analizy i syntezy układów przełączających. Jest to nie pierwszy przykład w historii nauki, że dopiero po wielu latach niektóre teorie abstrakcyjne stają się teoriami o wyraźnie zaznaczonym aplikacyjnym charakterze. Teoria układów logicznych wykorzystuje również pewne wyniki osiągnięte w XIX wieku w dziedzinie logiki teoretycznej przez takich matematyków jak de'Morgan czy też Polak Łukasiewicz, który jest twórcą znanego i stosowanego do dziś sposobu zapisu algorytmu, określanego jako tzw. odwrotna notacja polska.

Algebrą Boole'a B = <B, +, ∗, ¬, 0, 1> nazywamy zbiór B zawierający przynajmniej dwa elementy i spełniający następujące aksjomaty (dla x, y, z ∈B):

A1: x + 0 = x A2: x ∗ 1 = x element neutralny

A3: x + (¬x) = 1 A4: x ∗ (¬x) = 0 uzupełnienie

A5: x + y = y + x A6: x ∗ y = y ∗ x przemienność

A7: (x + y) + z = x + (y + z) łączność

A8: (x ∗ y) ∗ z = x ∗ (y ∗ z) łączność

A9: x ∗ (y + z) = x ∗ y + x ∗ z rozdzielność

A10: x + y ∗ z = (x + y) ∗ (x + z) rozdzielność

Twierdzenia

T1: x + x = x T2: x ∗ x = x idempotentność

T3: x + 1 = 1 T4: x ∗ 0 = 0 własności „zera” i „jedynki”

T5: ¬(x + y) = (¬x) ∗ (¬y) T6: ¬(x ∗ y) = (¬x) + (¬y) dualność (prawa d'Morgana)

T7: x + (x ∗ y) = x T8 x ∗ (x + y) = x absorpcja

T9: ¬(¬x) = x inwolucja

Przykłady

B = <B, ∨, ∧, ¬, 0, 1>, gdzie B = {0, 1}

B = <B, ∨, ∧, ¬, F, T>, gdzie B = {T, F}

B = <B, ∨, ∧, ¬, 0, 1>, gdzie B = {F_n} oraz F_n - zbiór funkcji boolowskich

W dalszym tekście pod nazwą „algebra Boole'a” będzie rozumiana zerojedynkowa algebra sygnałów binarnych, sformułowana do tego celu przez C.E. Shannona w 1938 r. W algebrze tej operację sumy oznacza się symbolem `+' lub `∨', operację iloczynu symbolem `*' lub `∧' i operację negacji (uzupełnienia) znakiem `¬' lub kreska nad zmienną. W dalszym tekście będą przyjęte operatory binarne `+' i `*' aby uniknąć dwuznaczności przy jednoczesnym stosowaniu operatorów arytmetycznych. Znaki `*' będą w tekście pomijane, jeżeli nie utrudni to właściwej interpretacji danego zapisu. Kreska nad zmienną oznaczać będzie negację (uzupełnienie).

Z uwagi na silny związek algebry sygnałów binarnych z rachunkiem zdań (zwanym również rachunkiem logicznym) przy operowaniu algebrą Boole'a często stosuje się przymiotnik „logiczny” w znaczeniu „boolowski” (np. iloczyn logiczny, mnożenie logiczne, stan logiczny, logiczne „0” i „1”).

Operator `∨ ` wymawia się jako „plus” (logiczny) albo „lub”, np. a ∨ b czytamy „a plus b” (wiedząc, że jest to dodawanie logiczne) albo „a lub b”. Operator „*” wymawia się jako „razy” (mnożenie logiczne) albo „i”, np. a*b czytamy „ab” lub „a razy b” (wiedząc, że jest to mnożenie logiczne) albo „a i b”. Symbol negacji `¬' wymawia się jako „nie”, np. a czytamy „nie a”.

Zerojedynkowa algebra Boole'a sygnałów binarnych jest zatem opisana przez system B = <B, +, ∗, ¬, 0, 1>, gdzie B = {0,1} jest zbiorem, w którym są określone operacje dwuargumentowe `+' i `*' oraz operacja jednoargumentowa `¬'.

Funkcje boolowskie

Algebra może być określona na zbiorze funkcji Boole'a F_n. Przez funkcję boolowska będziemy rozumieć funkcję, której argumenty i wartości należą do zbioru {0, 1}

Sposoby definiowania funkcji boolowskich

Istnieje kilka sposobów określenia funkcji boolowskiej.

1. Wyrażenie boolowskie n zmiennych jest to napis utworzony z tych zmiennych i stałych 0, 1 oraz skończonej liczby razy użytych operacji logicznych. Np.:

.

2. Tabela stanów przypisuje każdej kombinacji argumentów wartość funkcji. Np.:

x1	x2	f(x1, x2)
0	0	0
0	1	0
1	0	1
1	1	1

3. Definicja poprzez określenie zbiorów argumentów, dla których wartość funkcji wynosi 1, 0 lub jest nieokreślona.

4. Skrócony zapis funkcji. Liczby umieszczone w nawiasie odpowiadają zamienionym na system dziesiętny kombinacjom argumentów, dla których wartość funkcji wynosi 1. Np.:

.

Postać kanoniczna funkcji boolowskiej

Tą samą funkcję Boole'a można przedstawić przy pomocy różnych wyrażeń boolowskich. Np.:

.

Stwierdzenie czy wyrażenia Boole'a odpowiadają tej samej funkcji (są równoważne) jest możliwe dwoma sposobami:

• utworzyć dla nich tabele stanów i porównać czy są takie same

• doprowadzić do postaci kanonicznych i stwierdzić czy są identyczne.

Drugi sposób opiera się na twierdzeniu, że dwa wyrażenia boolowskie są równoważne, gdy mają takie same wyrażenia kanoniczne.

Iloczynem elementarnym n zmiennych nazywamy taki iloczyn tych zmiennych, w którym każdy argument występuje dokładnie raz - w postaci prostej lub zaprzeczonej. Wyrażenie kanoniczne jest sumą iloczynów elementarnych, dla których wartość funkcji wynosi 1.

Sposób sprowadzania wyrażenia boolowskiego do postaci kanonicznej na przykładzie funkcji boolowskiej
, został zaprezentowany w tabeli 1.

Algorytm	Przykład
1. Zapisać wyrażenie w postaci sumy iloczynów
2. Iloczyny, które nie są elementarne pomnożyć przez ,gdzie xi jest brakującym ogniwem
3. Wykonać mnożenie i zredukować powtarzające się iloczyny

Tabela 1. Algorytm sprowadzania wyrażenia boolowskiego do postaci kanonicznej

Minimalizacja funkcji boolowskich

Ważnym zagadnieniem w teorii sieci jest minimalizacja. Zagadnienie to można sformułować następująco: daną funkcję Boole'a zapisaną w postaci kanonicznej przedstawić w postaci takiego wyrażenia boolowskiego, aby funkcja kosztów była w minimum. Funkcja kosztów może być zdefiniowana w rozmaity sposób. Najczęściej jednak sprowadza się do tego, że w wyrażeniu powinna występować jak najmniejsza liczba elementów (zmiennych oraz operatorów). W rozwiązywaniu zadania minimalizacji stosowane są różne metody:

• metoda algebraiczna, wykorzystująca podstawowe własności algebry Boole'a

• metoda tablic Karnaugha

• algorytm minimalizacji Quina - McCluskeya.

W niektórych przypadkach należy rozwiązać problem sformułowany następująco: przedstawić funkcję w postaci zapisu zawierającego tylko iloczyny i negacje zmiennych. Przekształcenie wyrażenia boolowskiego do pożądanej postaci można przeprowadzić poprzez dwukrotne zanegowanie sumy iloczynów i zastosowanie prawa d'Mograna. Np.:

.

3

---