0000124

pod zmienno 1 wykonaniu wozystkich dziołoń, otrzymujemy wartość wyreZonio boolowokiogo, noleżęcę do zbioru D. Kożdę funkcję boolowskę n zmiennych nożna określić za pomocę odpowlodnlogo fryrożenie boolowoklogo. Dla przykładu woźmy pod uwagę funkcję boolowakę czterech zmiennych, okroślonę naetępujęcym wyroźoniea

t(*^<4)) • (*_ł^v*₂) a(x₂v x_g) v (x_xa x₃ ax₄) (0.1.14)

Funkcję boolowskę można również określić przez jej etabllcowonlo lub zo pomocę odpowlodnlogo wykresu.

Na przykłod, tablica D.1.4 przedstawia atabllcowonę funkcję f(t'⁴^), okroślonę wyraienio* (0.1.14).

Tablico 0.1.4

00000000111111 11 00001111000011 11 00110011001100 11 01010101010101 Ol

f    00001111001111    11

Przoględojęc powyżezę tablicę zauważamy, że funkcja ta nie zależy od zmiennej *₄ i w rzoczywiatości Jest to funkcjo trzech zmiennych.

»cy przedotawić funkcję f(X^) w postaci wykresu, należy przedstawić graficznie, odpowiednio uporządkowany, zbiór ale -mentów dziodziny tej funkcji, to znoczy zbiór n-wymiarowych wektorów binarnych    oraz odpowiednio wyróżnić podzbiór

x<"> . {■/"> , f(*‘ⁿ>) . »}.

Wielowymiarowo koetkę binarnę (zbiór X<">) można przedstawić graficznie w powien. wygodny w zastosowaniach, spooób uwidoczniony no rys.D.1.1, gdzie przód* stawiona jest kostko trójwymiarowo oraz na rys.O.1.2, przodsto-wiojęcyo kostkę binarnę czterowymiarowę. Analogicznie można narysować kootkę binarnę o większym wymiarze.

Kożdy wierzchołek kostki roprezontuje odpowiodnl n-wymiorowy woktor binarny. Wyróżniajęc (no przykłod innym kolorem) wiorz-

chołki zo zbioru    otrzymujomy wykroo funkcji boolowokiej.

No ryounku 0.1.2 zoczornlono bq to woktory    dlo których

funkcjo    okroólono wyro toniom (0.1.14), przyjmujo war-

toóć Jodon. W ton sposób rys.D.1.2 Joot wykroooo tej funkcji.

Rys.0.1.2

0.1.3. Monotonlczno funkcjo boolowokio

^Vl teorii grafów wykorzystywano sę głównie funkcjo boołows-klo nolezęco do kloey tak zwonych funkcji monotonicznych. Ola

247