Визначення безлічі мінімальних покриттів

На цьому етапі з безлічі максимальних кубів не належать ядру покриття, виділяються такі мінімальні підмножини, за допомогою кожного з яких покриваються вершини, що залишилися (не покриті ядром). Реалізацію цього етапу доцільно виконувати з використанням спрощеної таблиці покриттів (табл. 6). У ній викреслено всі куби, що належать ядру, і вершини, що покриваються ядром.

Для вирішення завдання третього етапу можна використовувати один із трьох методів або їх комбінацію:

1) метод простого перебору;

2) метод Петрика;

3) подальше спрощення таблиці покриттів.

Спрощена таблиця покриттів

Максимальні куби	Істотні вершини
A	000X	´	´
B	X000	´
C	0X01	´	´
D	01X1	´	´
E	X111	´	´
F	111X	´
a	b	c	d	e

На даному етапі доцільно ввести позначення максимальних кубів та суттєвих вершин.

Максимальні куби позначені у табл. 6 великими літерамиA, . F, а суттєві вершини малими літерамиa, . e.

Метод доцільно застосовувати для спрощеної таблиці невеликого обсягу. Він не дає гарантії отримання максимальних покриттів.

Для прикладу всі куби, що входять у спрощену таблицю покриттів, мають одну розмірність, тобто. необхідно вибрати мінімальну кількість цих кубів для покриття всіх істотних вершин, що залишилися.

З табл. 6 видно, що мінімальна кількість кубів дорівнює трьом. До можливих варіантів мінімальних покриттіввідносяться:

p align="justify"> Метод Петрика заснований на складанні булева виразу, що визначає умову покриття всіх істотних вершин булевої функції зі спрощеної імплікантної таблиці. Булеве вираз являє собою кон'юнкцію диз'юнктивних термів, кожен з яких включає сукупність всіх простих імплікант, що покривають одну істотну вершину функції. Отримане вираз перетворюється на диз'юнктивну форму і мінімізується з використанням законів поглинання та тавтології. Кожен кон'юктивний терм диз'юнктивної форми відповідає одному з варіантів покриття, з яких вибирається мінімальне.

Гідність методу Петрика – отримання всіх мінімальних покриттів.

Для прикладу, що розглядається, булеве вираз, що визначає умову покриття всіх істотних вершин відповідно до табл. 6 матиме вигляд:

Цей вираз представлений у кон'юктивній формі. Для його перетворення на диз'юктивну форму виконується попарне логічне множення диз'єїтивних термів.

Зауваження.З метою максимального спрощення етапу перетворення виразуYперемножуються терми, що містять по можливості максимальну кількість літер.

Після логічного множення двох перших пар диз'юктивних термів отримаємо вираз:

Y = (AAÚACÚABÚ BC)(CDÚCEÚDDÚDE)(EUF),

яке після застосування законів тавтології та поглинання наводиться до вигляду:

Після логічного множення останніх двох дужок та подальшого спрощення отримаємо:

Логічно помноживши пару дужок, отримаємо виразYв диз'юкнівній формі:

Y =ADEU ADFÚ ACEÚBCDEÚ BCDFÚ BCCE=

=ADEÚ ADFÚ ACEÚBCEÚ BCDF.

Кожен із п'яти кон'юнктивних термів відповідають покриттю булевої функції (з урахуванням доповненняядром), кожному з яких можна поставити у відповідність тупикову ДНФ.

Останній терм не відповідає мінімальному покриттю, тобто дана функція має чотири мінімальні покриття.

Для всіх мінімальних покриттівS a =11; S b = 15.

Мінімальні ДНФ, що відповідають цим покриттям:

МДНФ1:

МДНФ2:

МДНФ3:

МДНФ4:

Подальше спрощення таблиці покриттів полягає у застосуванні двох операцій:

а) викреслення "зайвих" рядків;

б) викреслення "зайвих" стовпців.

Операції викреслення рядків та стовпців базуються на таких правилах:

§ якщо безліч мітокi-го рядка є підмножиною мітокj-го рядка і кубiмає не більшу розмірність, ніж кубj, то з таблиці можна викреслитиi-й рядок, так як суттєві вершини покриваютьсяi-м кубом будуть з гарантією покритіj-м кубом;

§ якщо безліч мітокk–го стовпця таблиці покриттів є підмножиною мітокl-го стовпця, то з таблиці покриттів можна викреслитиl–ий стовпець, оскільки суттєва вершинаlбуде напевно покрита за рахунок одного з кубів, що покривають суттєву вершинуk.

Застосуємо метод подальшого спрощення таблиці покриттів щодо табл. 6. За допомогою операції викреслення "зайвих" рядків з неї можна видалити два рядкиB іF, безліч міток у яких є підмножиною міток у рядкахA таE відповідно. Процес видалення "зайвих" рядків показаний у табл. 7.

Після видалення рядківB таF, відповідних максимальним кубам Х000 і 111Х отримаємо нову спрощену таблицю покриттів представлену у вигляді табл. 8. На відмінувід табл. 6 (спрощена таблиця покриттів нульового порядку) називатимемо табл. 8 спрощеною таблицею покриттів першого порядку.

У табл. 8 можна виділити нове ядро ​​покриттяT 1 (f)=яке називатимемо ядром покриття першого порядку на відміну від ядраТ(f)(ядра покриття нульового порядку),виділеного за вихідною таблицею покриттів (табл. 5).

Викреслення "зайвих" рядків

Максимальні куби	Істотні вершини
A	000X	*	*
B	X000	*
C	0X01	*	*
D	01X1	*	*
E	X111	*	*
F	111X	*
a	b	c	d	e

Спрощена таблиця покриттів першого порядку

Максимальні куби	Істотні вершини
0000	0001	0111	1111
A	000X	Ä	*
C	0X01	*	*
D	01X1	*	*
E	X111	*	Ä
a	b	c	d	e

Після викреслення кубів ядраT 1 (f)(рядкиA іE ), а також суттєвих вершин , що покриваються кубами ядра (стовпціa, b, d, e ) отримаємо спрощену таблицю покриттів другого порядку (табл. 9).

Спрощена таблиця покриттів другого порядку

Максимальні куби	Істотні вершини
C	0X01	*
D	01X1	*

З табл. 9 визначаємо двамінімальних покриття у вигляді двох можливих варіантів доповнення кубів ядер покриття нульовогоT(f)і першого порядкуT 1 (f)кубамиC іD відповідно.

Таким чином за допомогою методу спрощення таблиці покриттів отримано лише два мінімальні покриття:

тоді як з допомогою методу Петрика знайдено чотири мінімальних покриття, тобто. усі можливі варіанти.

---