Podręcznik

Strona:	SEZAM - System Edukacyjnych Zasobów Akademickich i Multimedialnych
Kurs:	Synteza logiczna - pojęcia podstawowe
Książka:	Podręcznik

Wydrukowane przez użytkownika:	Gość
Data:	piątek, 22 listopada 2024, 15:07

Spis treści

1. Rola i znaczenie syntezy logicznej
2. Algebra Boole’a i przekształcenia boolowskie
3. Kostki, systemy zbiorów i podziały
4. Przykładowe zadania

1. Rola i znaczenie syntezy logicznej

Synteza logiczna jest gałęzią wiedzy, która w ostatnich latach rozwijała się niezwykle intensywnie, a jej zastosowania szybko przekroczyły granice tradycyjnej dziedziny układów cyfrowych, dochodząc do obszarów wiedzy zaliczanej do szeroko rozumianych technik informacyjnych, a nawet informatyki. Przyczyną tej sytuacji jest z jednej strony rozwój technologii mikroelektronicznych, a z drugiej coraz większe zapotrzebowanie na analizę i eksplorację danych.

Rozwój technologii mikroelektronicznych zwiększa możliwości techniki cyfrowej, ale ich pełne wykorzystanie wymaga rozwoju nowych metod syntezy logicznej. Powszechnie stosowane tradycyjne metody syntezy logicznej np. minimalizacja funkcji boolowskich są niedostosowane do zasobów układów FPGA, wyposażonych w komórki LUT oraz pamięci ROM. Próby zaradzenia tej sytuacji podejmowane były od dawna, ale szczególnej intensywności nabrały stosunkowo niedawno. Mocnym głosem okazała się książka T. Sasao „Memory based logic synthesis” [1.17], w której po raz pierwszy tak wyraźnie stwierdzono, że jedynymi skutecznymi metodami syntezy są redukcja argumentów i dekompozycja funkcjonalna.

Wpływ zaawansowanych procedur syntezy logicznej na jakość implementacji sprzętowych układów cyfrowych jest najbardziej znaczący w algorytmach wykorzystujących nowoczesne struktury programowalne. Struktury takie są powszechnie stosowane w układach przetwarzania informacji i sygnałów np. w realizacjach algorytmów kryptograficznych, w filtrach cyfrowych, układach transformacji falkowej oraz w syntezie funkcji generowania indeksów. Zatem stosowanie zaawansowanych procedur syntezy logicznej – dostępnych głównie w oprogramowaniu uniwersyteckim – niejednokrotnie może się przyczynić do sukcesu rynkowego wielu urządzeń cyfrowych, w szczególności tych realizowanych w technologii układów programowalnych przez użytkownika FPLD. Należy jednak podkreślić, że w przypadku generatorów adresu stosowanie procedur syntezy logicznej jest niezbędne [1.11], [1.15].

Skuteczność procedur syntezy logicznej można wykazać nawet na najprostszych przykładach. Na przykład prosta 10-argumentowa funkcja boolowska TL27 (specyfikację tej funkcji podano w podrozdz. 2.6 ) syntezowana programem ISE 14.7 może być zrealizowana na 21 4-wejściowych komórkach logicznych układu Spartan-III. Nie jest to sytuacja odosobniona, gdyż synteza Synteza programem Vivado 2015.4.2 w układzie Virtex-7 wymaga zastosowania pięciu 6-wejściowych, trzech 5-wejściowych komorek oraz jednej 4-wejściowej komórki. Niewiele lepiej jest dla systemu Altera Quartus II i układu Cyclone III: siedmiu 4-wejściowych oraz trzech 3-wejściowych komórek logicznych.

Ta sama funkcja poddana zaawansowanym procedurom syntezy logicznej może być zrealizowana na 2 (dwóch!) 4 wejściowych komórkach logicznych . Do uzyskania tak prostej struktury trzeba zastosować dwie procedury syntezy logicznej: procedurę redukcji argumentów oraz procedurę dekompozycji funkcjonalnej.

Sytuacja nie poprawia się nawet dla układów specjalnie przygotowywanych do realizacji na pamięciach. Charakterystycznym przykładem może być układ arytmetyki rozproszonej [1.13] filtru f5 [1.5]. Układ ten w reprezentacji za pomocą w pełni określonych funkcji boolowskich jest opisany tablicą o 11 zmiennych wejściowych i 11 wyjściach. Jego implementacja w strukturze Virtex-7 wykonana programem Vivado 2015.4.2 wymaga zastosowania 531 komórek (w tym 330 6-wejściowych, 86 5-wejściowych). Ponieważ układ ten, poddany procedurze redukcji argumentów jest funkcją zaledwie 7 argumentów, jego realizacja (wykonywana w tej samej strukturze programem Vivado) zajmuje 9 komórek 6-wejściowych oraz po jednej 5-, 4-, i 2-wejściowej. Tak wielka różnica w jakości rozwiązania nie może być spowodowana tylko jakością wykonania oprogramowania – u jej podstaw musi leżeć odmienna metodyka syntezy. Potwierdzeniem tego przypuszczenia są najnowsze prace w tej dziedzinie [1.1], [1.15] wykazujące, że potencjalne możliwości redukcji argumentów i dekompozycji funkcjonalnej nie są jeszcze w pełni wykorzystane.

Zaawansowane procedury syntezy logicznej mogą być również stosowane w zagadnieniach związanych z klasyfikacją danych, obejmowanych nazwą eksploracji danych [1.7], [1.8]. Eksploracja danych (ang. data mining), nazywana często odkrywaniem wiedzy w bazach danych (ang. knowledge discovery in databases), jest dynamicznie rozwijającą się dziedziną informatyki o szerokich zastosowaniach, m.in. w telekomunikacji, inżynierii biomedycznej, bankowości, itp.

Jednym z ważniejszych zastosowań tych algorytmów są systemy wykrywania anomalii w sieciach telekomunikacyjnych. Są to systemy pracujące wg typowego schematu maszynowego uczenia, gdyż kombinacja reguł oraz algorytmów klasyfikacji służy do wykrywania anomalii na podstawie analizy danych treningowych.

Innym typowym zastosowaniem jest wspomaganie decyzji podejmowanych przy diagnozie różnych chorób. Polega to na generowaniu reguł decyzyjnych obliczanych na podstawie baz danych zgromadzonych z badań wielu pacjentów. Obliczone w ten sposób reguły decyzyjne (tzw. klasyfikatory) pozwalają diagnozować nowych pacjentów.

W eksploracji danych typowe zadanie polega na tworzeniu reguł (wyrażeń boolowskich) reprezentujących pierwotne obiekty zapisane w tablicach danych. w przypadku układów logicznych procesy takie są określane mianem minimalizacji funkcji boolowskich. Uzyskiwane w wyniku takiego procesu reguły są wykorzystywane do klasyfikacji danych albo do kolejnych etapów optymalizacji logicznej (w przypadku układów cyfrowych). Oczywiście dane wejściowe algorytmów uogólniania reguł są w obu przypadkach zasadniczo różne. Dla tablic danych mamy do czynienia z wielowartościowymi atrybutami warunkowymi i wielowartościowymi atrybutami decyzyjnymi. Dla tablic prawdy wartości argumentów i wartości funkcji są binarne. Jednocześnie całkowicie inaczej są interpretowane tzw. wartości nieokreślone. w tablicy danych wartość nieokreślona atrybutu warunkowego oznacza, że wartość tego atrybutu nie została ustalona [1.6], a w przypadku tablic funkcji logicznych nieokreśloność argumentu wektora wejściowego oznacza występowanie w specyfikacji wektorów o wszystkich możliwych wartościach danego argumentu [1.3].

Na abstrakcyjnym poziomie algorytmów eksploracja danych polega m.in. na tzw. uogólnianiu/generacji reguł decyzyjnych, redukcji atrybutów, hierarchicznym podejmowaniu decyzji. Można wykazać, że algorytmy te są odpowiednikami algorytmów syntezy logicznej, a w szczególności tych które powstały w czasie ostatnich 30 lat. Na przykład generacja/uogólnianie reguł decyzyjnych – jest to typowa procedura stosowana w eksploracji danych i odpowiada minimalizacji funkcji boolowskiej, redukcja atrybutów odpowiada redukcji argumentów, natomiast hierarchiczne podejmowanie decyzji jest to dekompozycja funkcjonalna.

2. Algebra Boole’a i przekształcenia boolowskie

Algebra Boole’a jest modelem matematycznym operacji na sygnałach binarnych reprezentujących sygnały elektryczne o dwóch wartościach: 0 lub 1. Wartości te są przyporządkowane dwom poziomom napięcia wytwarzanego przez (elektroniczne) układy logiczne. Najczęściej przyjmuje się, że napięciu wysokiemu jest przyporządkowana wartość sygnału 1, natomiast napięciu niskiemu – wartość 0.

2.1. Aksjomaty algebry Boole’a

Algebra Boole’a jest algebrą z trzema operacjami na dwuwartościowych argumentach, które przyjmują wartości: 0 i 1. Rezultaty tych operacji są także dwuwartościowe. Te trzy operacje to:

suma logiczna (suma boolowska, dysjunkcja),
iloczyn logiczny (iloczyn boolowski, koniunkcja),
negacja (inwersja).

Dwie pierwsze operacje są wieloargumentowe, a trzecia jest jednoargumentowa.

Operacja sumy logicznej (OR) jest zdefiniowana następująco: jeżeli co najmniej jeden z argumentów jest równy 1, to wynik jest równy 1, zatem suma logiczna jest równa 0 tylko dla przypadku, gdy wszystkie argumenty są równe 0. Działania te zapisujemy następująco:

0 + 0 = 0

0 + 1 = 1

1 + 0 = 1

1 + 1 = 1

gdzie + oznacza operację OR. Operację OR realizuje bramka OR o symbolu graficznym jak na rys. 1.1a.

Rys. 1.1. Bramki logiczne a) OR, b) AND, c) NOT

Operacja iloczynu logicznego (AND) jest zdefiniowana następująco: wynik iloczynu jest równy 1 wtedy i tylko wtedy, gdy wszystkie argumenty przyjmują wartość 1, co zapisujemy w następujący sposób:

0 × 0 = 0

0 × 1 = 0

1 × 0 = 0

1 × 1 = 1

gdzie × oznacza operację AND. Operację AND realizuje bramka AND o symbolu graficznym podanym na rys. 1.1b.

Operacja negacji (NOT) zmienia wartość argumentu na przeciwny. Negacją 0 jest 1, a negacją 1 jest 0, co zapisujemy:

$\bar{1}=0$

$\bar{0}=1$

Operacja NOT zmiennej x, jest oznaczana x , a jej symbol graficzny (bramka NOT) podany jest na rys. 1.1c.

Z punktu widzenia syntezy logicznej w technice cyfrowej specjalnemu zainteresowaniu podlega dwuelementowa algebra Boole’a, którą będziemy rozumieli jako system <B, +, · , 0, 1>, gdzie zbiorem jest B = {0, 1}. Dwuwartościowa (zwana również binarną) algebra Boole’a stanowi podstawę nowoczesnej syntezy logicznej formułując prawa jakim podlegają zmienne boolowskie tj. zmienne ze zbioru B. Prawa te (z uwzględnieniem praw De Morgana) podajemy zbiorczo w formie zestawienia, w którym każde prawo jest zaopatrzone w odpowiednią nazwę.

Prawa algebry Boole’a

Własności stałych

$a+0=a$ $a\cdot0=0$

$a+1=1$ $a\cdot1=a$

Własności negacji

$a+\bar{a}=1$ $a\cdot\bar{a}=0$

Podwójna negacja

$\bar{\bar{a}}=a$

Idempotentność

$a+a=a$ $a\cdot\ a=a$

Przemienność

$a+b=b+a$ $a\cdot\ b=b\cdot\ a$

Łączność

$a+\left(b+c\right)=\left(a+b\right)+c$ $a\cdot\left(b\cdot c\right)=\left(a\cdot b\right)\cdot\ c$

Rozdzielność

$a+\left(b\cdot c\right)=\left(a+b\right)\cdot\left(a+c\right)$ $a\cdot\left(b+c\right)=a\cdot\ b+a\cdot\ c$

Prawa De Morgana

$y=\bar{a\cdot b}=\bar{a}+\bar{b}$ $y=\bar{a+b}=\bar{a}\cdot\bar{b}$

W algebrze Boole’a, operacje „+” (dysjunkcja) i „×” (koniunkcja) nazywa się również przez analogię do arytmetyki odpowiednio dodawaniem i mnożeniem. Operacje dodawania i mnożenia są przemienne oraz rozdzielne względem siebie. Elementy binarne 0 oraz 1 spełniają rolę elementu neutralnego odpowiednio względem operacji dodawania i mnożenia. Dla każdego elementu a istnieje element $\bar{a},$ , nazywany negacją, spełniający odpowiednie własności.

Starszeństwo działań w algebrze Boole’a jest takie same jak w zwykłej arytmetyce (np. wyrażenie a + b·c interpretujemy jako a + (bc), a nie jako (a + b)c, a nawiasy są opuszczane tam, gdzie nie prowadzi to do nieporozumień; opuszczamy także znak mnożenia „×”, a zamiast symbolu „+”, często jest używany symbol Ú.

Wyrażenie boolowskie to formuła, w której zmienne boolowskie połączone są operatorami: + (OR), · (AND), $\bar{x}$ (NOT).

Na przykład:

a + b + c · d + e

a + b + cd + e

a + b(d + e)

W zapisie wyrażeń boolowskich kropkę często pomija się, a kolejność operacji przyjmuje się następująco:

Kolejność ta może być zmieniona przez stosowanie nawiasów.

Typowym zastosowaniem algebry Boole’a jest uproszczenie wyrażeń boolowskich. Na przykład:

$\begin{array}{{>{\displaystyle}l}} \overline{a} bc+a\overline{b}\overline{c} +a\overline{b} c+ab\overline{c} +abc=\overline{a} bc+a\overline{b}\left(\overline{c} +c\right) +ab\left(\overline{c} +c\right) =\\ \ \ \ \ \ =\overline{a} bc+a\overline{b} +ab=\overline{a} bc+a\left(\overline{b} +b\right) =\overline{a} bc+a= \end{array}$

(korzystamy z własności a + abc = a(1 + bc) = a)

$=a+\bar{a}bc+abc=a+bc$

2.2. Przekształcenia boolowskie

Innym typowym zastosowaniem algebry Boole’a jest przekształcanie wyrażeń boolowskich z postaci typu „iloczyn sum” (CNF – Conjunctive Normal Form) na postać typu „suma iloczynów” (DNF – Disjunctive Normal Form).

Korzysta się przy tym z zasad uproszczonego mnożenia, z których pierwsza jest omawianą już zasadą rozdzielności dodawania względem mnożenia, a drugą wykazujemy poniżej.

Wykazać, że: $\left(x+y\right)\left(\bar{x}+z\right)=\ xz+\bar{x}y$

$\begin{array}{{>{\displaystyle}l}} ( x+y)\left(\overline{x} +z\right) =x\overline{x} +xz+\overline{x} y+yz=xz+\overline{x} y+yz=\\ =xz+\overline{x} y+1yz=xz+\overline{x} y+\left( x+\overline{x}\right) yz=xz+\overline{x} y+xyz+\overline{x} yz=\\ =xz+xyz+\overline{x} y+\overline{x} yz=xz( 1+y) +\overline{x} yy( 1+1) =\ xz+\overline{x} y \end{array}$

Podane wyrażenie typu „iloczyn sum”:

$(A+B+\bar{C})\left(A+B+D\right)\left(A+B+E\right)(A+\bar{D}+E)\left(\bar{A}+C\right)$

przedstawić w postaci sumy iloczynów.

Rozwiązanie

$(A+B+\bar{C})\left(A+B+D\right)\left(A+B+E\right)(A+\bar{D}+E)\left(\bar{A}+C\right)$ =

$\begin{array}{{>{\displaystyle}l}} =\left( A+B+\overline{C} DE\right)\left( AC+\overline{A}\left(\overline{D} +E\right)\right) =\left( A+B+\overline{C} DE\right)\left( AC+\overline{A}\overline{D} +\overline{A} E\right) =\\ =AC+ABC+\overline{A} B\overline{D} +\overline{A} BE+\overline{A}\overline{C} DE=AC+\overline{A} B\overline{D} +\overline{A} BE+\overline{A}\overline{C} DE \end{array}$

Ogromne znaczenie w syntezie logicznej mają przekształcenia wyrażeń boolowskich jednorodnych, tzn. takich w których zmienne występują wyłącznie w postaci prostej albo zanegowanej.

Wyrażenie typu CNF:

(x₂+x₄)(x₃+x₄)(x₃+x₅)(x₁+x₂+x₃) można przekształcić do postaci DNF w sposób następujący:

(x₄+x₂)(x₄+x₃)(x₃+x₅)(x₃+x₁+x₂) = (x₄+x₂x₃)(x₃+x₁x₅+x₂x₅) = x₃x₄+x₁x₄x₅+x₂x₄x₅+x₂x₃

Nietrudno przypuszczać, że w praktycznych zastosowaniach będziemy mieli do czynienia z bardziej rozbudowanymi przekształceniami CNF na DNF. W celu ułatwienia skomplikowanych obliczeń i zapisów zmienne boolowskie x_i, x_j, x_k będziemy reprezentowali ich indeksami i, j, k.

(3 + 7)(2 + 5 + 8)(3 + 6 + 8)(6 + 7 + 8)(3 + 5 + 6) = (3 + 7) (3 + 6 + 58)(8 + (2 + 5)
(6 + 7)) = (3 + ~~36 + 358 + 37~~ + 67 + 578)(8 + 26 + 27 + 56 + 57) = 38 + 236 + 237 +

+ 356 + 357 + 678 + 267 + ~~267~~ + 567 + ~~567~~ + ~~578 + 25678 + 2578 + 5678~~ + 578

= 38 + 236 + 237 + 356 + 357 + 678 + 267 + 567 + 578

Transformacja CNF na DNF jest również wygodnym i często stosowanym narzędziem przy obliczaniu pokrycia kolumnowego binarnej macierzy M.

Pokryciem kolumnowym binarnej macierzy reprezentowanej tablicą M:

$M=\left[m_{ij}\right],\ i\in\left\{1,\ldots,w\right\},\ j\in\left\{1,\ldots,n\right\}$

jest zbiór $L\ \in\left\{1,\ldots,n\right\}$ taki, że dla każdego $i\in{1,\ldots,w}$ istnieje $\ j\in\ L,$ dla którego $m_{ij}=1$ . Jeżeli usunięcie którejkolwiek z kolumn skutkuje brakiem pokrycia, jest to minimalne pokrycie kolumnowe. Inaczej mówiąc elementami pokrywanymi są wiersze M, a pokrywającymi – kolumny tej macierzy. Jednak brak formalnych elementów pokrywanych i pokrywających skłania do wprowadzenia nazwy „pokrycie kolumnowe”.

W wyrażeniu CNF czynniki koniunkcji są dysjunkcjami zmiennych boolowskich etykietujących te kolumny M dla których w danym wierszu $m_{ij}=1$ . Liczba czynników jest równa liczbie wierszy macierzy M. Istotnym problemem jest transformacja CNF na DNF, gdyż składniki wyrażenia DNF są koniunkcjami zmiennych reprezentujących kolumny macierzy M.

Tabl. 1.1

L₁	L₂	L₃	L₄	L₅	L₆	L₇
0	0	0	0	0	1	1
0	0	1	1	0	0	0
0	1	0	1	0	0	0
0	1	1	0	0	0	1

Dla macierzy M (Tabl. 1.1) stosowne obliczenia są następujące:

(L₆ + L₇) (L₃ + L₄) (L₂ + L₄) (L₂ + L₃ + L₇) = (L₄ + L₂)(L₄ + L₃)(L₇ + L₆)(L₇ + L₂ + L₃) =

=(L₄ + L₂L₃)(L₇ + L₆(L₂ + L₃)) = (L₄ + L₂L₃)(L₇ + L₂L₆+ L₃L₆) = L₄L₇+ L₂L₄L₆+ L₃L₄L₆+ + L₂L₃L₇ + L₂L₃L₆

Na tej podstawie stwierdzamy, że wszystkie minimalne pokrycia kolumnowe macierzy z Tabl. 1.1 są reprezentowane zbiorami: {L4, L7}, {L2, L4, L6}, {L3, L4, L6}, {L2, L3, L7}, {L2, L3, L6}. Zauważmy, że dla każdego wiersza tej tablicy elementy wskazywane przez kolumny L_inależące do obliczonych podzbiorów zawierają zawsze co najmniej

2.3. Graf prosty, pojęcie relacji

Grafem prostym (niezorientowanym) nazywamy parę G = (V, E), gdzie V jest niepustym skończonym zbiorem wierzchołków, a E jest skończonym zbiorem krawędzi – nieuporządkowanych par różnych elementów ze zbioru V [1.18]. Przykład grafu podany jest na rys. 1.2. Jest to graf, w którym zbiór wierzchołków V = {v1, v2, v3, v4, v5, v6} oraz zbiór krawędzi E = {(v1,v6), (v2,v3), (v2,v4), (v2,v5), (v2,v6), (v3,v4), (v3,v6), (v5,v6)}.

Dowolny podzbiór wierzchołków, w którym każde dwa wierzchołki są połączone krawędzią nazywamy kliką. Klikę, która nie jest zawarta w żadnej istotnie innej klice, nazywamy maksymalną. Najliczniejszą klikę w danym grafie nazywamy największa kliką. Klikami dla grafu z rys. 1.2 są następujące zbiory:

V = {v2, v3, v4}, V = {v2, v3, v6}, V = {v2, v5, v6}.

Zbiorem niezależnym nazywamy dowolny zbiór wierzchołków, które nie są sąsiednie w danym grafie. Analogicznie określamy pojęcie maksymalnego zbioru niezależnego. Przykłady zbiorów niezależnych dla grafu z rys. 1.2:

V = {v1,v4, v5}, V = {v1, v3, v5}, V = {v4, v6}, V = {v1, v2}.

Rys. 1.2. Przykład grafu

Obliczanie klik nie jest zadaniem łatwym. Można się zastanawiać jak obliczyć maksymalne kliki w grafie podanym na rys. 1.3.

Rys. 1.3. Przykład grafu

Dlatego problem obliczania maksymalnych klik warto sprowadzić do problemu obliczania maksymalnych klas zgodności definiowanych dla danej relacji zgodności. Najpierw zdefiniujemy ważne pojęcie iloczynu kartezjańskiego.

Iloczynem kartezjańskim zbiorów A i B, oznaczanym A × B nazywamy zbiór wszystkich par uporządkowanych (a, b), takich że pierwszy element pary należy do zbioru A (a Î A), natomiast drugi do B (b Î B), czyli:

A × B = {(a,b): a Î A, b Î B}

Niech A = {p,q} oraz B = {r,s,t},

wtedy A × B = {(p,r), (p,s), (p,t), (q,r), (q,s), (q,t)}.

Relacją nazywamy dowolny podzbiór iloczynu kartezjańskiego zbiorów A, B. Typowe własności relacji na zbiorze A (czyli A × A) są definiowane następująco:

zwrotność: $\forall\ a\in\ A:aRa$
symetria: $\forall\ a,b\in\ A:aRb(bRa$
przechodniość: $\forall\ a,b,c\in\ A:aRb,\ bRc\ (bRc$

Najważniejszymi relacjami stosowanymi w syntezie logicznej są relacje równoważności i zgodności.

Relację, która jest zwrotna i symetryczna nazywamy relacją zgodności. Relacja zgodności jest również nazywana relacją nierozróżnialności. Relacja zgodności klasyfikuje elementy zbioru w nierozłączne podzbiory zwane Systemem zbiorów (więcej na ten temat w rozdz. 1.4).

Szczególnym przypadkiem relacji zgodności jest relacja równoważności. Relacja równoważności jest relacją zwrotną, symetryczną i przechodnią. Relacja równoważności dzieli zbiór A na rozłączne podzbiory, co w konsekwencji prowadzi do pojęcia podziału (zbioru) tworząc bardzo użyteczny w syntezie logicznej rachunek podziałów omawiany w następnym rozdziale.

Własności relacji zgodności pokrywają się z intuicyjnym rozumieniem zgodności:

a) każdy element jest zgodny z samym sobą,

b) jeśli element v₁ jest zgodny z v₂, to również v₂ jest zgodny z v₁,

c) jeśli v₁ jest zgodny z v₂ oraz v₂ jest zgodny z v₃, to z tego nie wynika, że v₁ jest zgodny z v₃.

Relacja zgodności umożliwia wprowadzenie pojęcia Maksymalnych Klas Zgodności (MKZ).

Zbiór par określających relację zgodności nazywa się zbiorem par zgodnych. Pary zgodne umożliwiają wyznaczenie maksymalnych zbiorów zgodnych.

Zbiór V = {v1,¼,vp} nazywamy maksymalnym zbiorem zgodności (maksymalną klasą zgodności), jeżeli każda para v_i, v_j wzięta z tego zbioru jest zgodna oraz nie istnieje żaden inny zbiór elementów zgodnych V’, zawierający V. Maksymalne zbiory zgodne są odpowiednikiem klik w grafie prostym.

Z powyższego wynika, że w celu obliczania klik metodą maksymalnych klas zgodności należy:

Zapisać pary SPRZECZNE (v_i, v_j), (v_k, v_l), (v_p, v_q), w postaci koniunkcji dwuskładnikowych sum (v_i + v_j)(v_k + + v_l)(v_p, + v_q) ¼
Koniunkcję dwuskładnikowych sum przekształcić do minimalnego wyrażenia boolowskiego typu suma iloczynów v_iv_jv_k + v_pv_qv_rv_s +…

Wtedy MKZ są uzupełnieniami zbiorów reprezentowanych przez składniki iloczynowe tego wyrażenia.

Dla grafu z rys.1.2 pary zgodne są: (v₁, v₆), (v₂, v₃), (v₂, v₄), (v₂, v₅), (v₂, v₆), (v₃, v₄), (v₃, v₆), (v₅, v₆). Zatem pary sprzeczne będą:

E = {(v1, v2), (v1, v3), (v1, v4), (v1, v5), (v3, v5), (v4, v5), (v4, v6)}

Obliczamy wyrażenie boolowskie typu „koniunkcja sum”:

(v₁ + v₂)(v₁ + v₃)(v₁+ v₄)(v₁ + v₅)(v₃ + v₅)(v₄ + v₅)(v₄ +v₆) =

= (v₁ + v₂)(v₁ + v₃)(v₁+ v₄)(v₁ + v₅)(v₄ + v₅)(v₄ +v₆)(v₃ + v₅) =

(stosujemy zasadę (a + b)(a + c) = a + bc)

= (v₁ + v₂v₃v₄v₅)(v₄ + v₅v₆)(v₃ + v₅) =

(wymnażamy i redukujemy zbędne składniki)

= (v₁v₄ + v₁v₅v₆ + v₂v₃v₄v₅ + v~~₂v₃v₄v₅v₆~~)(v₃ + v₅) =

= (v₁v₄ + v₁v₅v₆ + v₂v₃v₄v₅)(v₃ + v₅) =

= v₁v₃v₄ + v~~₁v₃v₅v₆~~ + v₂v₃v₄v₅ + v₁v₄v₅ + v₁v₅v₆ + v~~₂v₃v₄v₅~~ =

= v₁v₃v₄ + v₁v₄v₅ + v₁v₅v₆ + v₂v₃v₄v₅

Odejmując od zbioru {v1, ¼, v6} zbiory reprezentowane przez poszczególne składniki uzyskanego wyrażenia obliczamy wszystkie maksymalne klasy zgodne, czyli kliki:

{v1, ¼, v6} – {v1, v3, v4} = {v2, v5, v6}

{v1, ¼, v6} – {v1, v4, v5} = {v2, v3, v6}

{v1, ¼, v6} – {v1, v5, v6} = {v2, v3, v4}

{v1, ¼, v6} – {v2, v3, v4, v5} = {v1, v6}

W podobny sposób możemy sformułować algorytm obliczania Maksymalnych Zbiorów Niezależnych (MZN).

Zapisać pary zgodne (v_i, v_j), (v_k, v_l), (v_p, v_q), ¼w postaci koniunkcji dwuskładnikowych sum (v_i, + v_j)(v_k, + v_l)(v_p, + v_q) ¼
Koniunkcję dwuskładnikowych sum przekształcić do minimalnego wyrażenia boolowskiego typu suma iloczynów v_iv_jv_k + v_pv_qv_rv_s +…

Wtedy MZN są uzupełnieniami zbiorów reprezentowanych przez składniki iloczynowe tego wyrażenia.

Obliczmy wszystkie MZN dla grafu z rys. 1.2.

E = {(v1, v6), (v2, v3), (v2, v4), (v2, v5), (v2, v6), (v3, v4), (v3, v6), (v5, v6)}

Obliczamy wyrażenie boolowskie typu „koniunkcja sum”:

(v₁ + v₆)(v₂ + v₃)(v₂+ v₄)(v₂ + v₅)(v₂ + v₆)(v₃ + v₄)(v₃ + v₆)(v₅ + v₆) =

= (v₂ + v₃)(v₂ + v₄)(v₂ + v₅)(v₂ + v₆)(v₆ + v₁)(v₆ + v₃)(v₆ + v₅)(v₃ + v₄) =

= (v₂ + v₃v₄v₅v₆)(v₆ + v₁v₃v₅)(v₃ + v₄) =

= (v₂v₆ + v₁v₂v₃v₅ + v₃v₄v₅v₆ + v~~₁v₃v₄v₅v₆~~)(v₃ + v₄) =

= v₂v₃v₆ + v₁v₂v₃v₅ + v₃v₄v₅v₆ + v₂v₄v₆ + v~~₁v₂v₃v₄v₅~~ + v~~₃v₄v₅v₆~~ =

= v₂v₃v₆ + v₁v₂v₃v₅ + v₃v₄v₅v₆ + v₂v₄v₆ =

= v₂v₃v₆ + v₂v₄v₆ + v₁v₂v₃v₅ + v₃v₄v₅v₆

Stąd maksymalne zbiory niezależne MZN: {v1, v4, v5}, {v1, v3, v5}, {v4, v6}, {v1, v2}.

2.4. Kolorowanie grafu

Kolorowaniem grafu nazywamy przyporządkowanie kolorów do wierzchołków grafu w taki sposób, aby żadna para wierzchołków sąsiednich nie miała takiego samego koloru. Przykład prawidłowo pokolorowanego grafu pokazany jest na rys. 1.4.

Rys. 1.4. kolorowanie grafu

Podstawowym problemem jest zadanie obliczenia najmniejszej liczby kolorów zapewniających prawidłowe pokolorowanie grafu. Jest to tzw. liczba chromatyczna grafu. Korzystając z pojęcia maksymalnych zbiorów niezależnych można algorytm kolorowania grafu sprowadzić do wykonania następujących obliczeń:

1. Obliczyć wszystkie maksymalne zbiory niezależne MZN. Uzyskujemy Rodzinę Maksymalnych Zbiorów Niezależnych (RMZN).

2. Obliczyć pokrycie zbioru wierzchołków V minimalną liczbą maksymalnych zbiorów niezależnych (tzw. minimalne pokrycie). Minimalne pokrycie reprezentuje minimalny zbiór kolorów.

3. W uzyskanym pokryciu usunąć elementy powtarzające się.

E = {(v₁, v₆), (v₂, v₃), (v₂, v₄), (v₂, v₅), (v₂, v₆), (v₃, v₄), (v₃, v₆), (v₅, v₆)}

Rys2

Rys. 1.5. Graf i jego kolorowanie

Dla grafu z rys. 1.5a należy wyznaczyć kolorowanie z minimalną liczbą kolorów. W tym celu najpierw obliczamy maksymalne zbiory niezależne: {v₁, v₄, v₅}, {v₁, v₃, v₅}, {v₄, v₆}, {v₁, v₂}. Następnie tworzymy minimalną podrodzinę pokrywającą zbiór V = {v₁, ¼, v₆}: {v₁, v₃, v₅}, {v₄, v₆}, {v₁, v₂}. Wreszcie po usunięciu wierzchołków powtarzających się uzyskujemy zbiory rozłączne reprezentują kolorowanie: {v₁, v₃, v₅}, {v₄, v₆}, {v₂}, co przedstawiono na rys. 1.5b.

Na zakończenie podamy jeszcze jedną – wygodną do stosowania w praktyce – metodę obliczania maksymalnych klas zgodności.

Metoda wg par zgodnych

Niech E będzie relacją na zbiorze V = {v₁, ..., v_n}, tzn. zbiorem par zgodnych (sąsiednich) v_i, v_j: i,j Î {1, ..., n} oraz i ¹ j. Obliczenie (maksymalnych) klas zgodności w zbiorze V przy danej E sprowadza się do wykonania następujących czynności.

1. Zapisujemy elementy v w rodzinach S_j zgodnie z zasadą v_i Î S_j tylko wtedy, gdy v_j, v_i jest parą zgodną oraz i < j.

2. Jeżeli RKZ_k jest rodziną klas zgodności uzyskaną w k-tym kroku algorytmu, to rodzinę RKZ_k₊₁ uzyskujemy, obliczając przecięcie każdej KZ Î RKZ_k ze zbiorem S_k₊₁. Wyróżniamy przy tym następujące przypadki:

a) S_k₊₁ = f i wtedy RKZ_k₊₁ jest powiększana o klasę KZ = {k+1},

b) KZ Ç S_k₊₁ = f wtedy klasa KZ nie ulega zmianie,

c) KZ Ç S_k₊₁ ¹ f wtedy powstaje nowa klasa KZ’ = KZ Ç S_k₊₁ È {k+1}.

W przykładzie obliczymy maksymalne klasy zgodności algorytmem korzystającym z par zgodnych. Następujące pary są zgodne: (v₁, v₂), (v₁, v₃), (v₁, v₅), (v₂, v₃), (v₂, v₅), (v₃, v₄), (v₃, v₅), (v₃, v₇), (v₄, v₆), (v₄, v₇), (v₅, v₆), (v₆, v₇). Na tej podstawie wyznaczamy zbiory S_j i tworzymy kolejne listy (rodziny RKZ_k) klas zgodnych, które dla uproszczenia zapisów podawać będziemy w postaci zbiorów indeksów:

S₁ = f	{1}
S₂ = {1}	{1, 2}
S₃ = {1, 2}	{1, 2, 3}
S₄ = {3}	{3, 4}, {1, 2, 3}
S₅ = {1, 2, 3}	~~{3, 5}~~, {1, 2, 3, 5}, {3, 4}
S₆ = {4, 5}	{5, 6}, {4, 6}, {1, 2, 3, 5}, {3, 4}
S₇ = {3, 4, 6}	~~{6, 7}~~, {4, 6, 7}, ~~{3, 7}~~, {3, 4, 7}, {5, 6}, {1, 2, 3, 5}

Dla relacji R, w której zbiór par zgodnych jest E = {(e₁,e₂), (e₁,e₃), (e₁,e₄), (e₁,e₅), (e₁,e₆), (e₁,e₇), (e₂,e₃), (e₂,e₅), (e₂,e₆), (e₂,e₇), (e₃,e₄), (e₃,e₅), (e₃,e₆), (e₃,e₈), (e₄,e₆), (e₄,e₇), (e₄,e₈), (e₅,e₆), (e₅,e₇), (e₅,e₈), (e₆,e₇), (e₆,e₈), (e₇,e₈)} obliczyć maksymalne klasy zgodności:

metodą wg par zgodnych,
metodą wg par sprzecznych.

Rozwiązanie a)

S₁= Æ	e₁
S₂= e₁	e₁, e₂
S₃= e₁, e₂	e₁, e₂, e₃
S₄= e₁, e₃	e₁, e₃, e₄/e₁, e₂, e₃¹⁾
S₅= e₁, e₂, e₃	e₁~~, e₃, e₅~~/e₁, e₂, e₃, e₅/e₁, e₃, e₄
S₆= e₁, e₂, e₃, e₄, e₅	e₁, e₂, e₃, e₅, e₆/e₁, e₃, e₄, e₆/e~~₁, e₃, e₄~~
S₇= e₁, e₂, e₄, e₅, e₆	e₁, e₂, e₅, e₆, e₇/e₁, e₄, e₆, e₇/e₁, e₂, e₃, e₅, e₆/e₁, e₃, e₄, e₆
S₈= e₃, e₄, e₅, e₆, e₇	e₅, e₆, e₇, e₈/e₄, e₆, e₇, e₈/e₃, e₅, e₆, e₈/e₃, e₄, e₆, e₈/e₁, e₂, e₅, e₆, e₇/e₁, e₄, e₆, e₇/e₁, e₂, e₃, e₅, e₆/e₁, e₃, e₄, e₆

Rozwiązanie b)

Pary sprzeczne: (e₁, e₈) (e₂, e₄) (e₂, e₈) (e₃, e₇) (e₄, e₅)

(e₈ + e₁) (e₈ + e₂) (e₄ + e₂) (e₄ + e₅) (e₃ + e₇) = = (e₈ + e₁e₂) (e₄ + e₂e₅)(e₃ + e₇) =

= (e₄e₈ + e₂e₅e₈ + e₁e₂e₄ + e₁e₂e₅)(e₃ + e₇) = e₃e₄e₈ + e₂e₃e₅e₈ + e₁e₂e₃e₄ + e₁e₂e₃e₅ + e₄e₇e₈ + + e₂e₅e₇e₈ + e₁e₂e₄e₇ + e₁e₂e₅e₇

W obu przypadkach maksymalne klasy zgodności są następujące:

{e₁, e₂, e₅, e₆, e₇} { e₁, e₂, e₃, e₅, e₆}

{e₁, e₄, e₆, e₇} {e₅, e₆, e₇, e₈}

{ e₄, e₆, e₇, e₈} { e₁, e₂, e₃, e₅, e₆}

{e₁, e₃, e₄, e₆} {e₃, e₅, e₆, e₈}

{e₃, e₄, e₆, e₈}

¹⁾ Do rozdzielenia klas zgodności użyto znaku „/” (zamiast nawiasów „{” i „}”

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:

4. Przykładowe zadania

Przykładowe zadania do samodzielnego rozwiązania

4.1. Zadanie 1

W zbiorze S = {1, 2, 3, 4, 5, 6, 7, 8} następujące pary są zgodne: (1,3), (1,7), (2,5), (2,8), (3,4), (3,5), (3,6), (4,5), (4,6), (5,7), (5,8), (6,7), (6,8). Obliczyć (sensowną metodą) wszystkie maksymalne klasy zgodności.

4.2. Zadanie 2

Dla grafu G = (V,E), w którym V = {1,2,3,4,5,6,7,8}, E = {(1,8), (2,4), (2,8), (3,7), (4,5)} obliczyć maksymalne kliki metodą: a) zbiorów niezależnych, b) maksymalnych klas zgodności.

4.3. Zadanie 3

Dla relacji R, w której zbiór par zgodnych jest E = {(B₁,B₂), (B₁,B₃), (B₁,B₆), (B₁,B₇), (B₂,B₃), (B₂,B₅), (B₂,B₆), (B₂,B₇), (B₃,B₄), (B₃,B₅), (B₃,B₆), (B₄,B₆), (B₄,B₇), (B₄,B₈), (B₅,B₆), (B₅,B₈), (B₆,B₇), (B₆,B₈)} obliczyć maksymalne klasy zgodności.

4.4. Zadanie 4

Dla podziałów П₁, П₂, П₃ określonych na zbiorze {a, b, c, d, e, f, g, h, i, j, k}:

$\Pi_1=\left(\overline{a,b,c};\overline{d,e};\overline{g,h,i};\overline{j,k}\right)$

$\Pi_2=\left(\overline{a,b};\overline{c,g,h};\overline{d,e,f};\overline{i,j,k}\right)$

$\Pi_3=\left(\overline{a,b,c,f};\overline{d,e};\overline{g,h,i,j,k}\right)$

należy wyznaczyć:

P₁ + P₂ oraz P₁ · P₂,
P₁ + P₃ oraz P₁ · P₃.