Список літератури. 1. Сигорский В.П. Математический аппарат инженера

Основна

1. Сигорский В.П. Математический аппарат инженера. – К.: Техника, 1975. - С.550-564.

2. Новоселов В.Г., Скатков А.В. Прикладная математика для инженеров-системотехников. Дискретная математика в задачах и примерах. – К.: Учебно-методический кабинет высшего образования, 1992. - С.146-161.

3. Горбатов В.А. Основы дискретной математики. – М.: Высш.шк., 1986. - С.50-55.

Додаткова

4. Яблонский С.В. Введение в дискретную математику. – М.: Наука, 1979. - С.215-220.

5. Новиков Ф.А. Дискретная математика для программистов. – СПб.: Питер, 2001. - С.91-92.

Для практичних занять

6. Методичні вказівки і завдання до контрольних робіт з дисципліни «Основи дискретної математики» для студентів очної та заочної форм навчання фахів 6.0804, 6.0915 / О.М. Мартинюк. – Одеса: ОНПУ, 2001. – С.35-38.

7. Гаврилов Г.П., Сапоженко А.А. Сборник задач по дискретной математике. – М.: Наука, 1973. - С.38-44.

Лекція 27. Аналітична мінімізація. Базові методи

Вступ

Лекція має за мету навести базові поняття та методи аналітичної мінімізації булевих функцій. Розглянути поняття комплексів кубів, постановка задачі мінімізації, метод Квайна, таблиці покриття та алгебраїчний метод. Основну увагу звернено до дій з комплексом кубів, побудови та роботи з таблицею покриття та скороченою таблицею покриття.

У лекції присутні три підрозділи:

27.1. Аналітичні методи мінімізації

27.2. Метод Квайна

27.3. Алгебраїчний метод одержання мінімального покриття (алгоритм Петрика)

27.1. Аналітичні методи мінімізації

27.1.1. Комплекс кубів

Аналітичні методи мінімізації використовують спеціальні методи представлення булевих функцій. Деякі з цих методів використовують комплекс кубів.

Визначення. Комплекс кубів К(у) функції y=f(x₁, x₂,..., x_n) - це об'єднання множин Кs(y) усіх s-кубів, де 0£s£n-1, причому деякі з Кs(y) можуть бути порожніми:

К(у)=È Кs(y)

Кожен s-куб відображає визначений мінтерм. Для запису s-кубів і відповідних їм мінтермів функції від «n» змінних використовують слова довжини «n». Вхідні в мінтерм змінні називаються зв'язаними і являються одиницею для x_i або нулем для `хі. Не вхідні в мінтерм (відсутні) змінні називаються вільними і позначаються через «´» (хрест), або через «~» (тильда).

Приклад. n=5 `x₁`x₂x₃x₄`x₅Þ 00110 - 0-куб

x₁`x₃x₄Þ 1´01´ - 2-куб

`x₁x₂`x₅Þ 01´´0 - 2-куб

x₃`x₅Þ ´´1´0 - 3-куб

Нуль-куби (0-куби) відповідають конституентам одиниці, або конституентам нуля. Сукупність усіх s-кубів записується як множина слів у алфавіті {0, 1, ´}, або {0, 1, ~}, що відповідають кубам визначеної розмірності відповідно зв'язаним та вільним змінним.

Приклад. y = x₁`x₂`x₃ Ú x₁`x₂x₃ Ú`x₁`x₂x₃ Ú`x₁x₂x₃ Ú`x₁x₂`x₃Ú x₁x₂x₃. К(y) = К°ÈК¹ÈК²,

де K° = 1 0 0 K¹ = {1 0 ´ K² = {´ ´ 1}

1 0 1 ´ 0 1

0 0 1 0 ´ 1

0 1 1 ´ 1 1

0 1 0 1 ´ 1

1 1 1} 0 1 ´}

Комплекс кубів утворює максимальне покриття функції. Крім того, виключаючи із нього всі ті S-куби, що покриваються кубами вищої розмірності, одержуємо скорочене покриття. Скорочене покриття дозволяє сполучити множину тупикових покрить. На множині тупикових покрить визначаються мінімальні.

Якщо використати куби для позначення макстермів, точно в такий же спосіб можна одержувати тупикові і мінімальні покриття для КНФ.

27.1.2. Постановка задачі

Мінімізація схем у булевому базисі зводиться до пошуку мінімальної ДНФ, якій відповідає мінімальне покриття. Для оцінки складності булевої функції використовується критерій Квайна, що формулюється таким чином:

Твердження: Мінімальній функції відповідає мінімальна ціна за Квайном, обумовлена як С=åq_s(n-s), де q_s - число S-кубів, що утворюють покриття даної функції від n змінних, s - розмірність кубів.

Мінімальне покриття характеризується мінімальною ціною.

Приклад. y=x₁`x₃x₄Úx₁x₂Ú`x₁x₃ n=4

C=1×(4-1)+2×(4-2)=3+4=7.

Задача мінімізації здійснюється в два кроки.

На першому кроці знаходиться скорочене покриття, що містить всі S-куби максимальної розмірності і не утримує жодного куба, що покривається Якім-небудь кубом цього покриття.

Відповідну скороченому покриттю ДНФ називають скороченою ДНФ, а її мінтерми - простими імплікантами. Для будь-Якій булевої функції скорочене покриття є єдиним, але воно може бути надлишковим унаслідок того, що деякі з кубів покриваються сукупностями інших кубів.

На другому кроці здійснюється перехід від скороченої ДНФ до тупикової ДНФ, утвореної зі скороченої ДНФ виключенням усіх надлишкових кубів, без яких сукупність кубів, що залишилася, ще утворить покриття даної булевої функції, але при подальшому виключенні кожного з кубів одержувана сукупність кубів вже не покриває задану функцію, тобто перестає бути покриттям.

Куб скороченого покриття, що покриває вершини даної булевої функції, які не покриваються ніЯкіми іншими кубами скороченого покриття, не може виявитися надлишковим і завжди увійде в мінімальне покриття. Такий куб, як і відповідна йому імпліканта, називається екстремаллю чи істотною імплікантою, а вершини, що покриваються ними, - відзначеними вершинами. Множина екстремалей утворює ядро покриття.

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

СДНФ Þ СкДНФ Þ {ТДНФ} Þ {МДНФ}

Приклад. y =`x₁ x₂`x₃Ú`x₁ x₂ x₃ Ú x₁`x₂`x₃ Ú x₁`x₂ x₃ Ú x₁ x₂ x₃

K₀ = 0 1 0 K₁ = 0 1 ´ K₂ = Æ

0 1 1 ´ 1 1

1 0 0 1 0 ´

1 0 1 1 ´ 1

1 1 1

CкДНФ =К₁ТДНФ₁ = 0 1 ´ ТДНФ₂ = 0 1 ´

1 0 ´ ´ 1 1

1 ´ 1 ` 1 0 ´

МДНФ₁ = 0 1 ´ МДНФ₂ = 0 1 ´

1 0 ´ ´ 1 1

1 ´ 1 1 0 ´.

27.2. Метод Квайна

Як вихідну форму булевої функції для мінімізації методом Квайна використовують СДНФ чи таблицю істинності. Приведення до скороченого ДНФ здійснюється застосуванням властивостей доповнення (операції склеювання).

(ах_і)Ú (a`x_i)=a

Множині конституент «1» відповідає сукупність 0-кубів К₀, операції склеювання відповідає об'єднання двох 0-кубів, що відрізняються тільки однією координатою. Результатом такого об'єднання є 1-куб, у якому різні координати вихідних 0-кубів заміщені символом ´.

Приклад. 0-куби: 1010 Þ 1-куб: 10´0.

Якщо порівняти попарно всі 0-куби, одержуємо множину 1-кубів К₁. Застосовуючи таким же способом до множини К₁ операцію склеювання, знаходимо множину 2-кубів К₂ і т.д. Процес продовжується доти, поки отримана з множини К_S чергова множина К_S+1 не виявиться порожньою (чи не буде отриманий n-куб, що представляє функцію – константу «1»). У результаті є комплекс кубів, що складається з множин К_S:

К={К₀, К₁,..., К_S}, де s£n-1.

Для виділення з К₀ множини простих імплікант ZÌK при кожній операції склеювання тим чи іншим способом відзначаються ті куби, що поєднуються в куби вищої розмірності. Очевидно, що невідмічені куби й утворять множину простих імплікант Z, іменовану скороченою ДНФ.

На наступному кроці при витягу екстремалей використовується таблиця покрить. Її рядки відповідають простим імплікантам, а стовпці - конституентам «1» (0-кубам) даної функції. У клітці таблиці ставиться мітка, якщо проста імпліканта, що відповідає даному рядку, покриває вершину, яка відповідає даному стовпцю клітки. Екстремалям відповідають ті рядки таблиці, що містять єдину мітку в якому-небудь стовпці. Видаляючи рядки екстремалей і всі стовпці, в яких дані рядки мають мітки, одержуємо скорочену таблицю покрить.

Зі скороченої таблиці покрить тим чи іншим способом вибираються прості імпліканти, що доповнюють виділену множину екстремалей до тупикових покрить. Метод Квайна не формалізує цей крок у вигляді якої-небудь процедури. На множини всіх тупикових покрить визначаються мінімальні покриття, яких може бути кілька.

Приклад. Задана функція y=Ú¹(0, 1, 2, 5, 6, 7). Комплекс кубів містить три множини, з яких К₁дорівнює скороченої ДНФ,
табл. 17.1 ілюструє покриття простими імплікантами зі СкДНФ конституент 1.

К = 000 К₁ = 00´ К₂ = Æ

001 0´0 СкДНФ = К₁

010 ´01

101 ´10

110 1´1

111 11´

Таблиця 27.1

	000	001	010	101	110	111
00´	Ú	Ú					A
0´0	Ú		Ú				В
´01		Ú		Ú			С
´10			Ú		Ú		D
1´1				Ú		Ú	E
11´					Ú	Ú	F
	AÚB	AÚC	BÚD	CÚE	DÚF	EÚF

У прикладі екстремалі відсутні (Екстремалі з'являться у наступному прикладі лекції 18). Тупикові ДНФ мають вид:

ТДНФ₁= 00´ ТДНФ₂= 00´ ТДНФ₃= 0´0

0´0 ´10 ´01

1´1 1´1 11´.

11´

Мінімальні ДНФ і їхньої ціни по Квайну мають вид:

МДНФ₁=ТДНФ₂,

Смднф₁=3(n-1)=6, y_min1=`x₂`x₃Ú`x₁ x₂Ú x₁ x₃,

МДНФ₂=ТДНФ₃,

Смднф₂=3(n-1)=6, y_min2=`x₁`x₃Ú x₁`x₂Úx₂x₃.

27.3. Алгебраїчний метод одержання мінімального покриття (алгоритм Петрика)

Вибір мінімального покриття на заключному етапі формалізується за допомогою алгебраїчного методу, що запропонований Петриком. Вихідна форма для алгоритму – таблиця покрить. Прості імпліканти позначаються Якіми-небудь символами, наприклад, літерами латинського алфавіту. У кожнім стовпці таблиці записується диз'юнкція простих імплікант, що покривають відповідний 0-куб. Покриттю функції відповідає кон'юнкція всіх записаних диз'юнкцій векторів.

Якщо спростити отримане вираження за допомогою тотожностей булевої алгебри, одержуємо деяку ДНФ, кожен член якої відповідає деякому тупиковому покриттю. Вибір тих з них, що містять мінімальну кількість букв або мінімальну ціну за Квайном, дає можливість знайти мінімальні покриття.

Приклад. З попередньої таблиці і ряду спрощень при розкритті дужок випливає таке:

Множина ТДНФ: (АÚВ)(АÚС)(ВÚD)(CÚE)(DÚF)(EÚF)=…=

= ADE ÚABEFÚBCDEÚBCEFÚACDFÚABCFÚBCDFÚ BCF...

Підкреслені кон'юнкції, що мають найменшу ціну і відповідають доповненням ядра до МДНФ. Тому що ядро (множина екстремалей) порожнє, самі підкреслені кон'юнкції й утворюють множину МДНФ.

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

Результатом перетворень є множини простих імплікант, що доповнюють сукупність екстремалей до тупикових покрить. Мінімальне з цих доповнень разом з ядром утворить мінімальне покриття функції.

Контрольні запитання

1. Що є комплексом кубів К(у) та як його побудувати?

2. Які змінні називаються зв'язаними, а Які вільними, як позначають у кубі зв'язані та вільні змінні?

3. Чи є комплекс кубів мінімальним покриттям?

4. Що є тупиковим покриттям, а що мінімальним?

5. Чи можна використовувати комплекс кубів для КНФ?

6. Що є ціною за Квайном та як вона обчислюється?

7. Які кроки звичайно використовує задача мінімізації?

8. Що є скороченим покриттям, що є простими імплікантами?

9. Що є екстремаллю, або істотною імплікантою та ядром покриття?

10. Які кроки треба виконати при переході від скороченого покриття до мінімального?

11. Що є методом Квайна та яку роль відіграє у ньому таблиця покриття?