Rotation of„

168

Indeks	Ko1umna 1	Kolumna 2	Kolumna 3
1	4 V	4.12(8) *	12,13.14,15(1.2) *
2	9 V 10 V 12 V	9.13(4) * 10,14(4) * 12,13(1) V 12,14(2) V 7.15(8) * 13,15(2) V 14.15(1) V
3	7 V 13    V 14    V
4	15 V

Rys.3.16. Generowanie prostych implikantów (przykład 3.10)

Uzyskano następujące proste implikanty:

4.12(8);    9.13(4);    10,14(4);    7,15(8);    12. 13.14.15(1,2).

Aby zapisać je w postaci elementarnych iloczynów zmiennych ; binarnych Xj.X2.X2.X4, należy zamienić pierwszÄ… liczbÄ™ każdego implikantu na liczbÄ™ binarnÄ… i skreÅ›lić bity, których wagi odpowiadajÄ… liczbom podanym w nawiasach. Zatem;

4,12(8)

J

0100

J

9.13(4)

>

1001

10,14(4)

\

1010

7,15(8)

^X2^X3^X4

>

^x1X3X4

^X1^X3^X4

J

il

J

^X2^X3^X4

12,13,14,15(1,2)

J

1100    (3.54)

J

^xl^x2

Zbiór wszystkich prostych implikantów wygenerowanych w Etapie I metody jest punktem wyjÅ›cia do Etapu II. Przypomnijmy, że celem tego ostatniego etapu jest okreÅ›lenie minimalnego liczebnie zestawu implikantów nakrywajÄ…cych wszystkie jedynki funkcji. Etap II najwygodniej jest przeprowadzić posÅ‚ugujÄ…c siÄ™ tzw. tablicÄ… Quine’a (np. tablica z rys. 3.17 dla przykÅ‚adu 3.6). Wiersze tej tablicy odpowiadajÄ… prostym impiikantom, a kolumny zespoÅ‚om wartoÅ›ci zmiennych, dla których funkcja jest równa 1 - a wiÄ™c jedynkom funkcji.

Warto tu zauważyć, że w Etapie I metody rozpatrywany jest zarówno zbiór jedynek F jak i zbiór “kresek" F funkcji. Zbiór “kresek"

jest uwzglÄ™dniany po to, aby uzyskać możliwie proste postaci implikantów funkcji. Natomiast w Etapie II rozważane sÄ… wyÅ‚Ä…cznie jedynki funkcji - zbiór F*. gdyż wszystkie jedynki funkcji muszÄ… być objete przez koÅ„cowÄ… postać funkcji; “kreski" sÄ… tu nieistotne.

Ogólny algorytm dla Etapu II realizowanego z pomocÄ… tablicy Quine’a jest nastÄ™pujÄ…cy: ze zbioru wszystkich prostych implikantów (wierszy tablicy Quine’a), należy wybrać te, które sÄ… niezbÄ™dne do nakrycia wszystkich jedynek funkcji (a wiÄ™c kolumn tej tablicy).

Przykład 3.11 (cd(l) Przykładu 3.10)

Proste ^V\F^1implikanty	4	7	9	10	12	13	14	15
4.12(8)	V				V				•
9.13(4)			V			V			â–
10,14(4)				V			V		«
7,15(8)		V						V	•
12.13,14,15(1,2)					V	V	V	V
					*	*

Rys. 3.17. Tablica Quine’a (przykład 3.11)

Znaki V w tablicy pokazujÄ…, które jedynki funkcji zostaÅ‚y nakryte przez dany implikant. Zatem, znaki V należy postawić na przeciÄ™ciu tych wierszy i kolumn, dla Których liczba opisujÄ…ca kolumnÄ™ wchodzi do wyrażenia opisujÄ…cego wiersz - nie uwzglÄ™dnia siÄ™ tu, rzecz jasna, tej części opisu wiersza, która jest umieszczona w nawiasie.

JeÅ›li w którejÅ› z kolumn znajduje siÄ™ tylko jeden znak V - to odpowiadajÄ…cy mu implikant jest niezbÄ™dny (jest to tzw. zasadniczy Prosty implikant). W tablicy na rys. 3.17 np. w kolumnie opisanej przez 4 jest tylko jeden znak V. Oznacza to, że jedynka 4 jest nakrywana wyÅ‚Ä…cznie przez prosty implikant 4,12(8). Nie można wiÄ™c tego Â°statniego usunąć z zestawu prostych implikantów wchodzÄ…cych w skÅ‚ad Minimalnej postaci funkcji.

A zatem, należy przejrzeć wszystkie kolumny tablicy Quine’a (np. z