Funkcja boolowska

Ten artykuł od 2012-11 wymaga zweryfikowania podanych informacji. Należy podać wiarygodne źródła w formie przypisów bibliograficznych. Część lub nawet wszystkie informacje w artykule mogą być nieprawdziwe. Jako pozbawione źródeł mogą zostać zakwestionowane i usunięte. Sprawdź w źródłach: Encyklopedia PWN • Google Books • Google Scholar • Federacja Bibliotek Cyfrowych • BazHum • BazTech • RCIN • Internet Archive (texts / inlibrary) Dokładniejsze informacje o tym, co należy poprawić, być może znajdują się w dyskusji tego artykułu. Po wyeliminowaniu niedoskonałości należy usunąć szablon {{Dopracować}} z tego artykułu.

Funkcja boolowska (funkcja logiczna) – dowolne odwzorowanie ${\displaystyle f\colon X\to Y,}$ gdzie ${\displaystyle B=\{0,1\},\ X}$ jest podzbiorem ${\displaystyle B^{n},}$ zaś ${\displaystyle Y}$ jest podzbiorem ${\displaystyle B^{m}.}$

Jeżeli funkcja boolowska jest określona dla każdego elementu zbioru ${\displaystyle B^{n}}$ (czyli ${\displaystyle X=B^{n}}$), to nazywamy ją funkcją zupełną. Analogicznie, jeśli ${\displaystyle X}$ jest właściwym podzbiorem ${\displaystyle B^{n},}$ to funkcja jest nazywana niezupełną lub też nie w pełni określoną.

Liczba wszystkich ${\displaystyle n}$-argumentowych funkcji zupełnych jest równa: ${\displaystyle 2^{2^{n}}.}$

Funkcja boolowska jest matematycznym modelem układu kombinacyjnego. Układy tego typu są używane do budowy między innymi multiplekserów, mikroprocesorów, do sterowania na przykład wyświetlaczami LED i w wielu innych urządzeniach elektronicznych.

Zapis funkcji boolowskiej

W opisie funkcji boolowskich używa się następujących elementów: literałów i wartości ze zbioru ${\displaystyle \{0,1,-\}.}$ 0 i 1 są tutaj umownymi oznaczeniami dla wartości funkcji i nie należy ich wiązać z liczbami 0 (zero) i 1 (jeden); kreska oznacza, że funkcja nie jest dla danego wektora określona.

Literały

Literał definiuje się jako:

${\displaystyle x^{e}=\left\{{\begin{matrix}x&{\textrm {dla}}&e=1\\{\overline {x}}&{\textrm {dla}}&e=0\\1&{\textrm {dla}}&e=-\end{matrix}}\right.}$

gdzie ${\displaystyle x}$ jest symbolem zmiennej, natomiast ${\displaystyle e}$ wskaźnikiem literału. Mając dowolne ${\displaystyle n}$ zmiennych można przedstawić je w postaci literałów:

${\displaystyle x_{1}^{e_{1}}x_{2}^{e_{2}}\ldots x_{n}^{e_{n}}.}$

W niektórych zastosowaniach często przedstawia się funkcję (lub jej elementy) wyłącznie za pomocą wektorów wskaźników literałów:

${\displaystyle x_{1}^{e_{1}}x_{2}^{e_{2}}\ldots x_{n}^{e_{n}}\to e_{1}e_{2}\dots e_{n},}$

np.

${\displaystyle a{\bar {b}}{\bar {c}}d{\bar {e}}=a^{1}b^{0}c^{0}d^{1}e^{0}\to 10010_{b},}$

${\displaystyle 110_{b}\to x_{1}^{1}x_{2}^{1}x_{3}^{0}=x_{1}x_{2}{\bar {x_{3}}}.}$

W przypadku drugiej konwersji przypisanie poszczególnym bitom zmiennych jest czysto umowne.

Termy

Termem (wyrazem) iloczynowym/sumowym nazywamy iloczyn (np. ${\displaystyle ab{\bar {z}}}$)/sumę (np. ${\displaystyle {\bar {d}}+{\bar {e}}+z+y}$) w którym żadna ze zmiennych nie występuje więcej niż raz. Np. jeśli funkcja ma trzy argumenty ${\displaystyle a,}$ ${\displaystyle b}$ i ${\displaystyle c,}$ to termem jest ${\displaystyle abc,}$ ${\displaystyle ac}$ itp.

Iloczyn nazywany jest pełnym, gdy zawiera wszystkie literały; analogicznie definiuje się sumę pełną. Miniterm jest innym określeniem dla iloczynu pełnego, maxterm dla sumy pełnej.

Jeśli miniterm (analogicznie maxterm) zostanie przedstawiony za pomocą wektora wskaźników literałów, to wartość dwójkowa tego wektora nazywana jest indeksem dwójkowym iloczynu (sumy), natomiast wartość dziesiętna indeksem dziesiętnym iloczynu (sumy); czasem pomija się przymiotniki „dwójkowy” i „dziesiętny”, mówiąc po prostu „indeks iloczynu (sumy)”.

Formy zapisu funkcji

W przykładach zakładamy, że funkcja ${\displaystyle f}$ ma trzy argumenty: ${\displaystyle a,}$ ${\displaystyle b}$ i ${\displaystyle c.}$

Opis słowny

Ten sposób stosowany jest w przypadku prostych funkcji, lub gdy charakteryzowane są pewne specyficzne własności funkcji. Np. „funkcja ma wartość jeden, gdy a jest różne od b, lub c jest równe b” lub „dla indeksów nieparzystych funkcja jest równa zero”.

Tablica prawdy

W tablicy wypisuje się wszystkie kombinacje zmiennych wejściowych oraz odpowiadające im wartości funkcji. W pierwszej kolumnie (oznaczonej #) można wpisać odpowiednie indeksy dziesiętne.

Gdy funkcja posiada niewiele jedynek (zer), wówczas do tablicy wpisuje się tylko te wiersze dla których funkcja jest równa jeden (zero).

Mapa Karnaugha

 Osobny artykuł: metoda Karnaugha.

Jest to przekształcona tablica prawdy, przedstawiona w postaci prostokątnej tablicy, gdzie indeksy dwójkowe zostały pogrupowane tak, by spełniały własności kodu Graya.

Kanoniczna postać sumy

Dowolną funkcję boolowską można rozłożyć na dwa składniki w następujący sposób (jest to tak zwane twierdzenie o rozkładzie):

${\displaystyle f(x_{1},x_{2},\dots ,x_{n})=x_{1}f(1,x_{2},\dots ,x_{n})+{\overline {x_{1}}}f(0,x_{2},\dots ,x_{n})}$

Postępując w ten sposób, dla wszystkich ${\displaystyle n}$ argumentów otrzymamy ${\displaystyle 2^{n}}$ sum iloczynów minitermów i wartości funkcji o stałych argumentach, np.

${\displaystyle f(a,b)={\overline {a}}{\overline {b}}f(0,0)+{\overline {a}}bf(0,1)+a{\overline {b}}f(1,0)+abf(1,1).}$

Ponieważ iloczyn ${\displaystyle 0\cdot x=0,}$ można zatem usunąć (nie pisać) wszystkie iloczyny w których funkcja ma wartość zero.

Np. jeśli funkcja ${\displaystyle f(a,b)}$ przyjmuje wartości 1 dla a=1, b=0 dla pozostałych kombinacji zero, to jej kanoniczna postać sumy będzie miała postać:

${\displaystyle f(a,b)={\overline {a}}{\overline {b}}f(0,0)+{\overline {a}}bf(0,1)+a{\overline {b}}f(1,0)+abf(1,1)=}$

${\displaystyle {\overline {a}}{\overline {b}}0+{\overline {a}}b0+a{\overline {b}}1+ab0=a{\overline {b}}1=a{\overline {b}}.}$

Zatem w ostatecznej postaci funkcji pozostają jedynie te minitermy (iloczyny pełne) dla których funkcja ma wartość jeden. Często, w skróconej formie, opisuję się funkcję wyłącznie za pomocą zbioru ich indeksów dziesiętnych, np.: ${\displaystyle f(a,b)=\sum [0,1,2,4,6,(3)].}$ Wartość w nawiasie oznacza, że dla tego indeksu funkcja ma wartość nieokreśloną.

W polskiej literaturze kanoniczna postać sumy oznaczana jest skrótem KPS, a w angielskiej SOP.

Kanoniczna postać iloczynu

Twierdzenie o rozkładzie ma również inną postać:

${\displaystyle f(x_{1},x_{2},\dots ,x_{n})=[{\overline {x_{1}}}+f(1,x_{2},\dots ,x_{n})][x_{1}+f(0,x_{2},\dots ,x_{n})]}$

Postać wynikowa kanonicznej postaci iloczynu zawiera iloczyn wszystkich maxtermów (sum pełnych) dla których funkcja przyjmuje wartość zero.

W polskiej literaturze kanoniczna postać iloczynu oznaczana jest skrótem KPI, a w angielskiej POS.

Macierz kostek

${\displaystyle f={\begin{Bmatrix}0&0&*\\1&*&0\\0&1&0\end{Bmatrix}}}$

Funkcja boolowska samodwoista

Funkcja boolowska ${\displaystyle f}$ jest samodwoista, jeśli ${\displaystyle f(x_{0},x_{1},...,x_{n})=\neg {f({\bar {x_{0}}},{\bar {x_{1}}},...,{\bar {x_{n}}})}}$

Łatwą do zapamiętania analogią do zbioru liczb rzeczywistych jest funkcja nieparzysta.

Podsumowanie

Powyższe zapisy niosą z sobą nadmiar informacji. W tym przykładzie możliwa jest minimalizacja funkcji ${\displaystyle f,}$ czyli sprowadzenie jej do prostszej, jakkolwiek równoważnej postaci:

${\displaystyle f(A,B,C)={\bar {A}}+{\bar {C}}.}$

Oprócz minimalizacji istnieją inne ważne zagadnienia z dziedziny syntezy logicznej – redukcja argumentów i dekompozycja funkcji boolowskich. Dzięki nim możliwe jest budowanie szybszych, tańszych i mniej zawodnych układów cyfrowych.

Najczęściej używane funkcje boolowskie:

• NOT
• AND i NAND
• OR i NOR
• XOR

Zobacz też

• algebra Boole’a
• kostka boolowska
• system funkcjonalnie pełny
• układ cyfrowy
• układ kombinacyjny

Przypisy

• Eric W.E.W. Weisstein Eric W.E.W., Boolean Function, [w:] MathWorld, Wolfram Research  (ang.). [dostęp 2023-08-29].
• Boolean function (ang.), Encyclopedia of Mathematics, encyclopediaofmath.org, [dostęp 2023-08-29].