Podręcznik: Kostki, systemy zbiorów i podziały

3. Kostki, systemy zbiorów i podziały

Zajmiemy się rachunkiem kostek i rachunkiem podziałów, których podstawy wynikają z jednej strony z klasycznej algebry Boole’a, a z drugiej z algebry ternarnej [1.4] i algebry zbiorów. Oprócz typowych wartości logicznych 0 i 1, stosować będziemy wartość nieokreśloną, którą oznaczać będziemy, w zależności od interpretacji: * lub –.

Na zbiorze {0, 1, *} definiujemy częściowy porządek Í, w którym:

0 Í 0, * Í * , 1 Í 1, 0 Í *, 1 Í *,

oraz żadna inna para nie występuje w relacji Í.

Ciągi elementów ze zbioru {0, 1, *} nazywać będziemy kostkami. Kostki będziemy oznaczać nieindeksowanymi literami, na przykład k, a ich składowe będziemy indeksowali, na przykład k_i. Również, w celu uproszczenia oznaczeń kostki (i wektory) będziemy zapisywać bez nawiasów i przecinków. Na przykład (*, 1, *, 0, 1) zapiszemy jako *1*01.

Częściowy porządek Í rozszerzamy na zbiór {0, 1,*}ⁿ:

k Í k’ wtedy i tylko wtedy, gdy k_iÍ k’_i dla każdego i, 1 £ i £ n.

Na przykład 01* Í *1*.

W zbiorze częściowo uporządkowanym á{0, 1, *}, Í ñ, definiujemy typowe pojęcie najmniejszego górnego ograniczenia LUB (Least Upper Bound), a mianowicie LUB{0} = 0, LUB{1} = 1, a ponadto operacja LUB dla każdego niepustego podzbioru z {0,1,*} wynosi *. Operację LUB rozszerzamy na zbiór {0, 1, *}ⁿ jako najmniejsze górne ograniczenie obliczane dla poszczególnych składowych odpowiednich kostek. Na przykład:

LUB{*001, 1101, 0101} = **01.

Na zbiorze {0, 1,*} określamy operację binarną, È – sumowanie, dla której związek z najmniejszym górnym ograniczeniem jest następujący:

k È k’ = LUB{k, k’}.

Mamy wtedy:

k Í k’ wtedy i tylko wtedy, gdy k È k’ = k’.

Operacja È-sumowania jest idempotentna, przemienna i łączna. Jej uogólnienie dla każdego niepustego podzbioru S z {0, 1,*}ⁿ , jest następujące:

$LUB\ S=\bigcup\limits _{k\in S} \ k$

Na zbiorze {0, 1, *} definiujemy relację zgodności ~, gdzie:

0 ~ 0, * ~ *, 1 ~ 1, 0 ~ * , 1 ~ *, * ~ 0 , * ~ 1,

ale pary (0,1) i (1,0) nie podlegają relacji ~.

Zgodność jest zwrotna i symetryczna, to znaczy dla każdej k, k’ Î {0, 1, *}, k ~ k i k ~ k’ implikuje k’ ~ k. Jednak nie jest to relacja przechodnia, gdyż 0 ~ * i * ~ 1, ale 0 1.

Należy zauważyć, że:

k Í k’ implikuje k ~ k’,

oraz

k ~ k’ implikuje albo k Í k’ albo k’ Í k.

Relacja zgodności ~ może być rozszerzona na obiekty ze zbioru {0, 1, *}ⁿ:

k ~ k’ wtedy i tylko wtedy, gdy k_i ~ k_i^’dla każdego i, 1 £ i £ n.

Na przykład, 01** ~ *10*.

Największe dolne ograniczenie GLB (Greatest Lower Bound) istnieje wyłącznie dla pewnych podzbiorów zbioru {0, 1, *}. Na przykład GLB{0,1} nie istnieje, ale GLB{0,*} = 0. Wykorzystując GLB, definiujemy Ç-iloczyn w sposób następujący: k Ç k’ jest określony wtedy i tylko wtedy, gdy k i k’ są zgodne. Zatem w Ç-iloczynie wartości pewnej przez niepewną, wartość pewna przeważa. Ponadto,

k Í k’ wtedy i tylko wtedy, gdy k Ç k’ = k.

Jeśli k, k’, oraz k” są parami zgodne, to Ç-iloczyn (k Ç k’) Ç k” jest określony i wynosi k Ç (k’Ç k”). Zatem operacja Ç jest łączna. Operacja Ç-iloczynu może być rozszerzona na dowolny zbiór C elementów parami zgodnych:

$GLB\ C=\bigcup\limits _{k\in C} \ k$

Dalsze uogólnienie Ç-iloczynu dotyczy kostek zgodnych. Na przykład, 01** Ç *10* = 010*. Z każdym k Î {0,1,*}ⁿ kojarzymy zbiór bin k binarnych kostek (mintermów):

bin k = {b Î {0,1}ⁿ ú b Í k }.

Na przykład, jeśli k = 01**, wtedy bin k = {0100, 0101, 0110, 0111}.

Systemem zbiorów na zbiorze S nazywamy rodzinę zbiorów s = {B1,...,Bk}, w której podzbiory (tzw. bloki) są maksymalne w tym sensie, że inkluzja B_iÍ B_j implikuje i = j. Na przykład, jeśli S = {1,2,3}, to s = {{1,2}, {2, 3}} jest systemem zbiorów na S. Zapis ten upraszczamy następująco: $\sigma =\left\{\overline{1,2} ;\overline{2,3}\right\}$ . Zauważmy, że systemy zbiorów nie są zamknięte ze względu na operację iloczynu. Na przykład $\sigma =\left\{\overline{1,2} ;\overline{2,3}\right\}$ · $\sigma =\left\{\overline{1,2} ;\overline{2,3}\right\}$ nie jest systemem zbiorów.

Jeśli b = {Bi} jest dowolną rodziną zbiorów na S, to

max b = {B Í S½B = Bi dla pewnego i oraz B Í Bj implikuje Bj = B}.

Warto zauważyć, że operacja max odwzorowuje rodziny zbiorów w systemy zbiorów. Iloczyn dwóch systemów zbiorów s i s’ jest definiowany następująco:

s _° s’ = max(s·s’).

Na przykład: $\left\{\overline{1,2} ;\overline{3,4,5}\right\}$

$\left\{\overline{1,2,3} ;\overline{3,4,5}\right\} \ \bullet \ \left\{\overline{1,3,4} ;\overline{1,5} ,\overline{2,3,4}\right\} \ =\ \left\{\overline{1,3} ;\overline{2,3} ;\overline{3,4} ;\overline{5}\right\}$

Łatwo sprawdzić, że iloczyn systemów zbiorów jest idempotentny, łączny i przemienny. Kończąc powyższe rozważania przypomnijmy, że system zbiorów jest konsekwencją działania relacji zgodności.

Mając na uwadze, że relacja zgodności jest szczególnym przypadkiem relacji równoważności nietrudno stwierdzić, że wynikiem działania relacji równoważności jest podział zbioru na rozłączne podzbiory.

Formalnie, podziałem pzbioru S nazywać będziemy rodzinę rozłącznych podzbiorów zbioru S, których suma równa się S.

Niech S = {1, 2, 3, 4, 5, 6, 7, 8, 9}, to

t₁ = {{1, 2}, {3, 4}, {5, 6}, {7, 8, 9}},

t₂ = {{1, 6}, {2, 3}, {4, 5}, {7, 8}, {9}}

są podziałami zbioru S. Dla uproszczenia zapisów stosujemy zapis:

$\tau_1=\left(\overline{1,2};\overline{3,4};\overline{5,6};\overline{7,8,9};\right)$

$\tau_2=\left(\overline{1,6};\overline{2,3};\overline{4,5};\overline{7,8};\overline{9};\right)$

$\tau_3=\left(\overline{1,2};\bar{3};\bar{4};\overline{5,6};\overline{7,8};\bar{9}\right)$

Dla podziałów wprowadza się relację £ oraz działanie iloczynu i sumy:

$\Pi_1\le\Pi_2\Leftrightarrow\left(\forall B_i\in\Pi_1\right)\left(\exists B_j\in\Pi_2\right)\left(B_i\subseteq B_j\right)$

Największym i najmniejszym podziałem zbioru S są odpowiednio:

$\Pi\left(1\right)=\left(\bar{1,2,\ldots,n}\right)$

$\Pi\left(0\right)=\left(\bar{1};\bar{2};\ldots\right)$

Niech $\tau_3=\left(\overline{1,2};\overline{3};\overline{4};\overline{5,6};\overline{7,8};\overline{9}\right).\$ Wówczas t₃ £ t₁. Analogiczny związek nie zachodzi między t₁ i t₂, ani między t₂ i t₃.

Podział P nazywamy iloczynem podziałów P₁ i P₂ (P = P₁ × P₂), jeżeli P jest największym podziałem (tzn. podziałem mającym największe bloki) spełniającym warunki: P £ P₁ oraz P £ P₂. Podział P₁ × P₂ można wyznaczyć bardzo prosto wyznaczając wszystkie możliwe iloczyny w sensie teorii mnogości każdego bloku P₁, z każdym blokiem P₂; zbiór tak otrzymanych zbiorów jest poszukiwanym podziałem.

Sumą podziałów P₁ + P₂ nazywamy najmniejszy podział, nie mniejszy od P₁ oraz od P₂. Wyznaczenie P₁ + P₂jest nieco trudniejsze. Niech podziały P₁ i P₂ mają odpowiednio bloki B_i i B_jtakie, że B_i Ç B_j ¹ f. Tworzymy wtedy nowy blok B_ij = B_i È B_ji sprawdzamy, czy P₁ i P₂ zawiera taki blok B_k, że B_k Ç B_ij ¹ f. Jeżeli tak, to tworzymy nowy blok B_k È B_ij itd. w wyniku takiego postępowania otrzymamy stopniowo podział P₁ + P₂.

Dla wprowadzonych podziałów mamy:

$\tau_1\cdot\tau_2=\left(\bar{1};\bar{2};\bar{3};\bar{4};\bar{5};\bar{6};\overline{7,8};\bar{9}\right)$

${\tau_1+\tau}_2=\left(\overline{1,2,3,4,5,6};\overline{7,8,9}\right)$

$\tau_3\cdot\tau_1=\left(\overline{1,2};\bar{3};\bar{4};\overline{5,6};\overline{7,8};\bar{9}\right)=\tau_3$

$\tau_3+\tau_1=\left(\overline{1,2};\overline{3,4};\overline{5,6};\overline{7,8};\overline{7,8,9}\right)=\tau_1$

Wygodne w zastosowaniach jest również pojęcie ilorazu podziałów (podziału ilorazowego). Niech P₁ i P₂są podziałami na S. Podział P₁|P₂ jest podziałem ilorazowym P₁ i P₂, jeżeli jego elementy są blokami iloczynu P₁×P₂, a bloki są blokami P₁. Na przykład: dla S = {1,2,3,4,5,6}, $\Pi_1=\left\{\overline{1,2,5};\overline{3,4,6}\right\}$ , $\Pi_2=\left\{\overline{1,2};\overline{3,6;}\overline{4,5}\right\}$ podział ilorazowy będzie: