016 5

16 Sterowanie logiczne i sekwencyjne

Funkcje boolowskie

Funkcją boolowską nazywa się odwzorowanie zbioru B" w zbiór B gdzie: B ~ {0,1}. Parametr n oznacza liczbę argumentów. Odwzorowanie jest dobrać określone przez podanie tabeli przyporządkowań⁵: kolejno dla wszystkich wartości argumentów podawane są wartości funkcji. Odwzorowanie można także określić przez podanie wyrażenia boolowskiego pozwalającego obliczyć wartość funkcji f(u_ltu₂,...,u,_t) w punkcie (i/_Ł,u₂,...,u„). Wyrażenie boolow^rskie generowane przez zmienne (boolowskie^{1 2}) u_l,u₂,...,u_n jest budowane według następujących zasad:

1.    Elementy 0 i 1 są wyrażeniami boolowskimi.

2. Jeżeli u, jest zmienną, to u, jest wyrażeniem boolowskim (i = 1,2,

3.    Jeżeli A jest wyrażeniem bookwskim, to A jest wyrażeniem boolowskim.

4.    Jeżeli A i B są wyrażeniami bookrwskimi, to A + B jest wyrażeniem boolowskim.

5.    Jeżeli A i B są wyrażeniami boolowskimi, to AB jest wyrażeniem boolowskim.

6.    Wyrażeniami boolowskimi są jedynie te wyrażenia, które wynikają z punktów (l)-(5).

W przypadku stosowania reguł 4-5, złożone wyrażenia składowe A i B są zapisywane w- nawiasach, aby wskazać kolejność obliczeń (najpierw oblicza się wartości wyrażeń składowych). Przyjęte jest opuszczanie nawiasów, jeśli nie prowadzi to do zmiany wartości wyrażenia przy stosowaniu następującej kolejności wykonywania działań: najpierw iloczyn, potem suma. Równoważne są więc np. zapisy: (X + F) + (WZ) - X + Y + W7.

Głównym celem tworzenia reguł zapisywania wyrażeń jest uzyskanie na podstawie tabeli przyporządkowań schematu odpowiedniego układu logicznego lub odpowiedniego schematu obliczeń. Podstawkowe pytania dotyczą problemu, czy każdą funkcję boolowską można określić za pomocą odpowiedniego wyrażenia algebraicznego? Problem ten rozwiążemy pokazując, że dla każdej funkcji boolowskiej istnieje postać kanoniczna wyrażenia algebraicznego. Dodatkowo podanie postaci kanonicznej wyrażenia daje możliwość stwierdzenia równoważności funkcji boolow^rskich (wyrażeń algebraicznych, schematów' układów

1

Tabela przyporządkowań dla funkcji boolowskiej jest nazywana tablicą prawdy.

2

' Zmienna boolowską to zmienna mogąca przyjmować wartości ze zbioru B = { 0. 1}.