4. Niech F₂ oznacza zbiór wszystkich możliwych funkcji odwzorowujących zbiór X= {0,1} x {0,1} w zbiór {0,1}, czyli F₂ ={0,1}^{0,1}x{0,1} Nadto niech dla dowolnych f , g ∈ F₂ określone będą działania boolowskie następująco: f '(x)=1-f(x),

dla x∈X;

f(x) ∨ g(x) = max (f(x), g(x)) dla x∈X;

f(x) ∧ g(x) = min (f(x) , g(x)) dla x∈X.

Rozważmy poniższą tabelę przedstawiającą elementy zbioru F₂:

Nr	F2 F2 X	00	01	10	11	Uwagi
1	g	0	0	1	1	f1
2	h	0	1	0	1	Generatory algebry Boole'a to są funkcje g i h F2
3	g'	1	1	0	0
4	h'	1	0	1	0
5	g ∧ h	0	0	0	1
6	g ∧ h'	0	0	1	0
7	g'∧ h	0	1	0	0
8	g'∧ h'	1	0	0	0
9	α = g'∧ h ∨g∧h'	0	1	1	0
10	g ∨ h	0	1	1	1
11	g ∨ h'	1	0	1	1
12	g' ∨ h	1	1	0	1
13	g' ∨ h'	1	1	1	0
14	0=h ∧ h'	0	0	0	0	h∨h'=0 jest stałą „zero”
15	1=h ∨ h'	1	1	1	1	h∨h'=1 jest stałą „jeden”
16	(g'∧h∨ g∧h')'	1	0	0	1

1.Zbadać ,że (F₂ , ∧ , ∨ , ' , 0 , 1) jest algebrą Boole'a w sensie formalnej definicji algebry Boole'a, którą będziemy ozna-

czać F₂ .

2. Wykazać, że algebra Boole'a F₂ jest generowana przez funkcje g i h wymienione w powyższej tabeli elementów zbioru F₂ .

Wskazówka: Dla dowodu wystarczy wykazać, że każdy element algebry Boole'a F₂ może być przedstawiony jako boolowska kombinacja tych dwóch jej generatorów .

Rozwiązać samodzielnie następujące zadania:

1.Podać interpretację graficzną ( na schematach Venna) algebry Boole'a F₂.

2. Podać interpretację graficzną dla wyrażenia (wielomianu boolowskiego) B(g,h) określonego następująco:

B(g,h) = g ∧ h' ∨ g'∧ h dla g , h ∈ F₂ .

Wsk: Oto interpretacja graficzna np. wyrażena B(g,h)= g ∨ h

Wielomian boolowski

Df: Wielomianem boolowskim nazywamy dowolne wyrażenie,

które można otrzymać rekurencyjnie przez zastosowanie działań boolowskich ∧ , ∨ , ` do pewnego zbioru symboli x₁, x₂ ,……, x_n.

Stąd dowolny wielomian boolowski F(x₁, x₂ ,……,x_n) określa

funkcję F: Bⁿ B odwzorowującą zbiór Bⁿ na dowolną

algebrę Boole'a B, której wartości mogą być obliczone przez wstawienie elementu z Bⁿ do wielomianu. Przy czym do klu-

czowych pytań zaliczamy tutaj pytania:

Jakie są ”prawa tworzenia” zapisu wielomianów boolowskich? Jaki jest ten zbiór ”praw tworzenia” ?

Otóż ten zbiór ”praw tworzenia” daje nam postać kanoniczną Backusa wielomianu boolowskiego.

Przyjmijmy, że BOOLEPOLY przedstawia klasę wielomianów

boolowskich , wówczas używając postaci kanonicznej Backusa

możemy zapisać:

BOOLEPOLY :: = <litera> <BOOLEPOLY> ∧<BOOLEPOLY> <BOOLEPOLY> ∨<BOOLEPOLY> <BOOLEPOLY> '

UWAGA!

1. Powstaje tutaj problem redukcji wyrażeń języka symboli zdefiniowanego przez BOOLEPOLY, w szczególności skonstruowania algorytmu sprowadzającego każdy wielomian boolowski do postaci kanonicznej. Zadanie znalezienia takiej procedury nazywa się problemem słów.

2. Np. algebra Boole'a F₂ i jej interpretacja graficzna sugerują,

że istnieje 16 nierównoważnych funkcji boolowskich dwóch zmiennych g i h; Zaś 256 różnych nierównoważnych funkcji boolowskich trzech zmiennych. Wyjaśnij dlaczego?

Funkcje boolowskie

Df: Funkcje dowolnej, skończonej liczby zmiennych dwójkowych, przyjmujące tylko wartości 0 lub 1 nazywają się funkcjami boolowskimi lub przełączającymi.

Stąd obszarem określoności funkcji boolowskiej n zmiennych jest zbiór wszystkich możliwych wektorów o n współrzędnych x₁, x₂ ,……, x_n, przy czym x_i ∈{0,1} dla i ∈ {1,2,…,n}.

Każdy taki wektor można utożsamić z odpowiednim n wyrazowym ciągiem o wartościach ze zbioru{0,1} , który z

kolei można utożsamić z kodem zero - jedynkowym oznacza-

jącym odpowiednią liczbę całkowitą nieujemną wyrażoną w układzie dwójkowym.

Np. wektor (0,0,0,0,0) oznacza liczbę 0; wektor(0,1,1,0,1) oznacza liczbę 13, bo: 0•2⁴+1•2³+1•2²+0•2¹ +1•2⁰= 13.

W celu naturalnego uporządkowania ( rosnąco) takich n wyrazowych kodów dwójkowych stosuje się tak zwaną

n wywymiarową tablicę kombinacji).

Np. dla n=3 , wówczas otrzymujemy V³₂= 2³= 8 trzywyra-

zowych kodów dwójkowych.

n(10)	x1	x2	x3
0	0	0	0
1	0	0	1
2
3
4
5
6
7	1	1	1

Dla dużej liczby zmiennych dwójkowych przy przeliczaniu liczb w układzie dziesiętnym na liczby w układzie dwójkowym stosuje się specjalny algorytm!

Obecnie definiujemy pojęcia pomocnicze dla zarysowania rozwiązania problemu minimalizacji postaci funkcji boolowskiej.

Df. Iloczynem elementarnym nazywa się wyrażenie, które jest iloczynem dowolnego skończonego zbioru liter parami różnych, przy czym nad literami może być negacja. Litery mogą być indeksowane arytmetycznie.

Np. wyrażenia : a; uvy; abcde ; x₁x₂x₃ są iloczynami elementarnymi, natomiast wyrażenia: aa, zkxk ,a₁a₂ nie są iloczynami elementarnymi.

Df. Alternatywną postacią normalną (APN) funkcji boolowskiej nazywa się skończoną sumę parami różnych iloczynów elementarnych.

Przyjmujemy bez dowodu twierdzenie:

Tw: Każdą funkcję boolowską można zapisać w APN.

Np:

Df. Iloczyn elementarny jest kanoniczny dla danego zbioru zmiennych boolowskich, gdy zawiera wszystkie zmienne tego zbioru w postaci zwykłej lub zanegowanej.

Oto przykłady takich iloczynów dla zbioru trzech zmiennych boolowskich: x₁x₂x₃; x₁x₂x₃; x₁x₂x₃

Df. APN funkcji boolowskiej nazywa się kanoniczną alternatywną postacią normalną (KAPN), gdy składa się z kanonicznych iloczynów elementarnych dla tego samego zbioru zmiennych.

Stąd KAPN funkcji boolowskiej jest szczególnym przypadkiem jej APN.

Rozwiązać ćwiczenie:

Przedstawić funkcję boolowską f(x₁x₂x₃) = x₁x₂+ x₂x₃ w kano-

nicznej alternatywnej postaci normalnej(KAPN).

Dla rozwiązania ćwiczenia należy wprowadzić brakujące zmienne tak, by wartość logiczna tej funkcji boolowskiej nie zmieniła się (pozostała taka sama).

f(x₁,x₂,x₃)=x₁x₂ + x₂x₃ = x₁x₂·1 + 1x₂x₃ =

= x₁x₂ (x₃+x₃)+( x₁+x₁)x₂x₃= x₁x₂x₃+x₁x₂x₃ + x₁x₂x₃+x₁x₂x₃.

Wykorzystując tak zwany rozkład jedności można udowodnić twiedzenie:

Dowolna funkcja boolowska f(x₁, x₂ ,……,x_n) ma dokładnie jedną KAPN.

Df: Wyrażenie postaci :
= 1 nazywa się rozkładem jedności n zmiennych boolowskich. W szczególności dla n=2

otrzymujemy: x₁+x₁=1 , x₁+ x₂=1.

Ogólnie : dla ustalonych n zmiennych otrzymuje się wyrażenie:

,przy czym prawa strona tej równości zawiera 2ⁿ składników.

Rozwiązanie problemu minimalizacji postaci funkcji boolowskiej realizuje się algorytmicznie (np. algorytmem Quine'a, algorytmem Mc Cluskeya). Sam proces minimalizacji funkcji boolowskiej służy do znalezienia najprostszej funkcji równoważnej danej funkcji boolowskiej. To znaczy takiej funkcji boolowskiej która może być zapisana za pomocą najmniejszej liczby liter i symboli logicznych: ∧ , ∨, ~ ;

Czyli działań boolowskich.

•Algorytm opracowany przez Quine'a oparty jest na znajdowaniu implikantów pierwszych funkcji boolowskich,

które realizuje się w dwóch etapach:

1. poszukuje się wszystkich implikantów pierwszych danej funkcji;

2. tworzy się zredukowany system implikantów pierwszych, a następnie minimalną alternatywną postać normalną (MAPN)

funkcji boolowskiej.

Przy czym przez implikant pierwszy funkcji f(x₁, x₂ ,……, x _n)

rozumie się każdy implikant tej funkcji, którego żadna część własna ( to jest iloczyn otrzymany przez usunięcie jednego lub

kilku czynników) nie jest implikantem. Zaś funkcja boolowska

g(x₁, x₂ ,……, x _n) jest implikantem funkcji boolowskiej

f(x₁, x₂ ,……, x _n), gdy dla każdego zbioru wartości zmiennych

x₁, x₂ ,……, x _n, dla którego wartość g(x₁, x₂ ,……, x _n) jest

równa 1, wartość f(x₁, x₂ ,……, x _n) też jest równa 1.

Komentarz dydaktyczny

1. Przy stosowaniu algorytmu Quine'a, który realizuje rozwiązanie problemu minimalizacji funkcji boolowskiej, dla funkcji boolowskiej dużej liczby zmiennych pojawiaja się trudności związane ze sprawdzaniem a następnie przekształcaniem kanonicznej alternatywnej postaci normalnej (KAPN) tej funkcji. Wówczas w takim przypadku należy stosować algorytm Mc Cluskeya, gdyż występują tutaj kanoniczne wyrazy elementarne zapisane za pomocą liczb ,a nie ( jak poprzednio) literami.

2. W toku stosowania algorytmu Mc Cluskeya funkcje boolowskie określa się przez podanie w nawiasie zbioru numerów ich kanonicznych iloczynów elementarnych ,

np. f = ∑(5,9,11,12,13).

3.Dalsze szczegóły na temat zarysowanych tutaj pojęć (APN,

KAPN,SAPN,NAPN,HAPN) oraz algorytmów Quine'a i

Mc Cluskeya integralnie związanych z rozwiązaniem problemu minimalizacji postaci funkcji boolowskiej, z zastosowaniem zagadnień algebry Boole'a można znaleźć w skrypcie profesora Mariana Partyki, zobacz: M Partyka (1997):Zastosowanie zagadnień algebry Boole'a w strukturalizacji procesów decyzyjnych, Opole 1997

Wnioskowanie Boole'a

Obecnie na poniższym przykładzie zarysuję wnioskowanie Boole'a po uprzednim zdefiniowaniu niezbędnych w tym celu

pojęć.

Df: Parę=(U,A) zbiorów niepustych i skończonych nazywamy

systemem informacyjnym , w którym U jest uniwersum (zbiorem obiektów), zaś A={a: U V_a } zbiorem atrybutów.

Rozważmy system informacyjny opisany poniższą tabelą 1:

U A	a1	a2	a3	d
u1	0	α	biały	tak
u2	0	α	żółty	tak
u3	1	β	biały	nie
u4	1	γ	żółty	nie
u5	0	α	biały	tak

Stąd otrzymujemy:

U={ u₁,u₂,u₃,u₄ ,u₅};A={ a₁,a₂ ,a₃ ,d};

a₁: U {0,1}; a₂: U { α, β, γ};

a₃:U {biały, żółty}; a₄: U {tak,nie}

Df: System informacyjny z wyróżnionym podzbiorem atrybutów nazywamy systemem decyzyjnym.

W systemie informacyjnym z tabeli 1 zbiorem atrybutów warunkowych jest zbiór { a₁,a₂,a₃}, zaś zbiorem atrybutów decyzyjnych jest zbiór {d}.

Df: Niech S=(U,A) będzie systemem informacyjnym oraz

B
A. Relację IND(B)
U² taką, że :

IND(B)={(u,v) ∈ U² :
} nazywamy relacją niero-

zróżnialności.

Przykład zadania

Dla systemu informacyjnego opisanego powyższą tabelą 1 wyznaczyć wszystkie minimalne ( ze względu na relację inkluzji) podzbiory B zbioru atrybutów A, takie że:

IND(B)=IND(A).

Dla rozwiązania zadania rozważmy funkcję boolowską f postaci: f(a₁*,a₂*,a₃*,d*)=a₃*∧( a₁*∨a₂*∨d*)∧( a₁*∨a₂*∨a₃*∨d*)∧

∧a₃*∧ (a₂*∨a₃*)∧( a₁*∨a₂*∨d*)∧( a₁*∨a₂*∨a₃*∨d*)= (a₁*∧a₃*)∨

∨ (a₂*∧a₃*)∨ (a₃*∧d*).

Stąd rodzina zbiorów { {a₁,a₃}, {a₂,a₃}, {a₁,d}}jest rozwiązaniem tego zadania.

Rozważana w tym zadaniu funkcja boolowska jest funkcją rozróżnialności w danym systemie informacyjnym.

Df : Funkcją rozróżnialności w danym systemie informacyjnym

S=(U,A) nazywamy funkcję boolowską postaci:

F(a₁*,a₂*,…., a_n*)=∧{∨ a *_uv: u,v ∈U ∧ (u,v)∈ IND(A)}, gdzie

n oznacza liczbę atrybutów , zaś ∨ a *_uv jest alternatywą zmie-

nnych boolowskich odpowiadających tym atrybutom, które ro-

zróżniają obiekt u od obiektu v.

Warto dodać ,że ogólna strategia rozwiązywania zadań i pro-

blemów w oparciu o wnioskowanie Boole'a jest następująca:

1. Konstrukcja systemu informacyjnego, adekwatnego do ro-

związywanego zadania , bądź problemu.

2. Konstukcja funkcji rozróżnialności dla rozważanego systemu

informacyjnego ( opisanego w punkcie 1) i wyznaczenie jej

implikantów pierwszych.

3. Interpretacja otrzymanych implikantów pierwszych , które

prowadzą do rozwiązania zadania, bądź problemu.

Df. Regułą w systemie informacyjnym nazywamy każde wy-

rażenie postaci: P⇒Q , gdzie P:∧( ai_j= vi_j),Q :∧( a i_k= vi_k);

a i_j , ai_k∈A; vi_j∈V ai_j , vi_k ∈V ai_k , takie że dla dowolnego u∈U

zdanie : ∧( a i_j(u)= vi_j) ⇒∧ ( a i_k(u)= v i_k) jest prawdziwe.

Jeśli dla każdego takiego k : a i_k jest atrybutem decyzyjnym, to tę regułę nazywamy regułą decyzyjną. Jeśli natomiast jakiekolwiek zredukowanie wyrażenia P powoduje, że wyrażenie P⇒Q przestaje być regułą w danym systemie informacyjnym, to taką regułę nazywamy minimalną regułą.

Przykład zadania

W systemie informacyjnym opisanym powyższą tabelą 1

znaleźć minimalne reguły.

Stosując wnioskowanie Boole'a otrzymujemy zbiór wszystkich minimalnych reguł. Dla tego systemu informacyjnego minimalnymi regułami i to regułami decyzyjnymi są następują-

ce reguły:

Reguła R₁ : a₁ = 1 ⇒ d = nie;

Reguła R₂ : a₂ = β ⇒ d = nie;

Reguła R₃ : a₃ = γ ⇒ d = nie;

Reguła R₄ : a₄ = 0 ⇒ d = tak;

Reguła R₅ : a₅ = d ⇒ d = tak.

4

g

g∨h h

---