Практичне заняття 12

Вправа 1. Перевірити, що суперпозиція функцій з класу Поста функцій, що зберігають 0, також належить цьому класу.

16. Мінімізація булевих функцій

16.1 Постановка задачі. Основні поняття

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

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

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

При цьому використовується термінологія: одиниця функції g покриває одиницю функції f на визначеному слові.

Приклад 1. Важливими прикладами імплікант є конституенти одиниці, які входять до складу ДДНФ, елементарні кон’юнкції, що входять до складу ДНФ функції.

Множина S імплікант функції f називається покриттям (або повною системою імплікант) функції f, якщо кожна одиниця функції f покривається одиницею хоча б однієї імплікант множини S.

Приклад 2. Множина імплікант, складових ДНФ функції, є її покриттям. Множина всіх конституент одиниці функції, що входять до її ДДНФ, є покриттям цієї функції.

Будь-яку елементарну кон’юнкцію А, що входить до складу елементарної кон’юнкції В і містить менше змінних, ніж кон’юнкція В, називають власною частиною кон’юнкції В і вважають, що кон’юнкція А покриває кон’юнкцію В.

Приклад 3. Елементарна кон’юнкція входить до складу елементарної кон’юнкції і є власною частиною кон’юнкції В. Елементарна кон’юнкція не входить до складу В і тому не є власною частиною В.

Простою імплікантою функції f називається така кон’юнкція (імпліканта), що ніякі її власні частини не є імплікантою даної функції.

Множини всіх простих імплікант становить покриття даної функції.

Диз’юнкція всіх простих імплікант функції є її скороченою ДНФ.

Диз’юнктивним ядром булевої функції f називається множина її простих імплікант, яка є покриттям f, але після видалення будь-якої імпліканти втрачає цю властивість, тобто перестає бути повною системою імплікант.

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

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

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

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

• неповного диз’юнктивного склеювання

; (1)

• диз’юнктивного поглинання

; (2)

• повного диз’юнктивного склеювання

. (3)

Тут А - деяка елементарна кон’юнкція змінних, х – булева змінна.

Приклад 4. Нехай булева функція задана ДДНФ:

Виконаємо операції повного склеювання двома шляхами:

а)

Насамперед, є імплікантами функції f. Щоб переконатися в цьому побудуємо таблицю істинності.

З цієї таблиці видно:

1) на словах 011, 111. На цих самих словах і дана функція . Отже є імплікантою функції f на словах 011, 111; Одиниці імпліканти покривають одиниці функції на цих словах.;

2) на словах 001 та 011. На цих самих словах і дана функція . Отже і є імплікантою функції . Одиниці імпліканти покривають одиниці функції на цих словах.;

3) на словах 000 та 001. На цих словах і . Одиниці імпліканти покривають одиниці функції на словах 000 та 001.

Всі вони є простими імплікантами. Наприклад власні частини і z імпліканти не є імплікантами функції ( на слові 100, а на цьому слові). Аналогічно для імплікант та .

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

– множині слів на яких функція приймає значення 1.

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

б) Виконаємо операції склеювання іншим способом:

.

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

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

• операція неповного кон’юнктивного склеювання

; (4)

• операція кон’юнктивного поглинання

; (5)

• операція повного кон′юнктивного склеювання

. (6)