Покриття булевих функцій
Конспект лекцій з дискретної математики
Геометричним чином 3-куба вважатимуться 3-х мірний куб. Так як він може бути утворений трьома способами як пара паралельних граней, то при склеюванні він виходить у трьох екземплярах.
Покриття булевих функцій.
Між кубами різної розмірності, що входять до кубічного комплексу K(f), є відношення включення або покриття. Прийнято говорити, що куб А меншої розмірності покривається кубом Б більшої розмірності, якщо куб А входить у куб Б. Це означає, що з освіті куба Б хоча у одному склеюванні бере участь куб А.
Відношення включення (покриття) між кубами прийнято позначати АІБ. Теоретично множин відношення включення пов'язує між собою деяка безліч і його підмножини.
Для розглянутого прикладу відношення включення мають місце між 001?001; 011×11×1x . будь-який 1-куб покриває 2 0-куби, 2-куб - 4 0-куби і 2 1-куби, 3-куби покриває 8 0-кубів, 12 1-кубів і 6 2-кубів.
Покриттям булевої функції f називається таке підмножина кубів із кубічного комплексу K(f), яке покриває всі суттєві вершини функції.
У зв'язку з тим, що будь-якому кубу комплексу K(f) можна поставити у відповідність кон'юнктивний терм, для будь-якого покриття можна уявити певну ДНФ булевої функції.
Окремим випадком покриття булевої функції є кубічний комплекс K0(f), покриття c0(f)=K0(f). Цьому покриттю відповідає КДНФ.
Для прикладу покриттям є також
цьому покриттю відповідає ДНФ виду
_ _ _ _ _ _ _ _ _ _
f=x1x3vx1x2vx2x3vx2x3vx1x2 наведена ДНФ не є мінімальною.
Як мінімальне ще одне покриття можна використовувати безліч максимальних кубів
Справді, куб 0х1покриває суттєві вершини 0х1É(001, 011), а куб x1xÉ(010, 011, 110, 111).
Безліч максимальних кубів булевої функції завжди є її покриттям.
Покриття c2(f) відповідає ДНФ виду х1х3vx2. Ця ДНФ є мінімальною. Покриття булевої функції, яке відповідає мінімальній ДНФ, називається мінімальним покриттям.
Мінімальне покриття має складатися лише з максимальних кубів.
В окремому випадку вся безліч максимальних кубів є мінімальним покриттям. Це слушно для нашого прикладу. У загальному випадку безліч максимальних кубів є надлишковим і для отримання мінімального покриття достатньо взяти його підмножину.
K0(f)=100 (3) K1(f)=1x0 (3-4)
Для цього прикладу безліч максимальних кубів збігаються з комплексом K1(f). Z(f)=K1(f)
Мінімальними покриттями є
З аналізу покриття суттєвих вершин максимальними кубами з комплексу K1(f) випливає:
1) Куб 00х повинен обов'язково включатися в покриття, тому що тільки він покриває суттєву вершину 001, аналогічно 11х покриває 111.
Безліч максимальних кубів без яких не може бути утворено покриття булевої функції називається ядром покриття T(f)=00x
2) Так як ядром покриття крім істотних вершин 001 і 111 покриваються також суттєві вершини 000 і 110, то не покритою ядром залишається тільки суттєва вершина 100. Для її покриття достатньо взяти 1 з максимальних, що залишилися кубів (х00 або 1х0).
Завдання отримання мінімальної ДНФ зводиться до отримання мінімального покриття.
Отримання мінімального покриття реалізується в такому порядку: а) Знаходиться безліч максимальних кубів; б) Виділяється ядро покриття; в) З максимальних кубів, що не ввійшли в ядро,вибирається таке мінімальне підмножина, що покриває суттєві вершини, не вкриті ядром.
Ціна r-куба є кількістю незв'язаних координат. Sr=n*r
Для оцінки якості покриття використовують два види ціни покриття:
1) Sa = SrNr, де Nr - кількість r-кубів, що входять в по-
криття, m – максимальна розмірність куба. Ціна Sa є сумою цін кубів, що входять у покриття.
2) Sb = Sa + k, де k - кількість кубів, що входять до покриття
Sa = (n-r) Nr ; Sb=å(n-r)(Nr+1)
Під мінімальним покриттям розуміють покриття, що має мінімальну ціну Sa в порівнянні з будь-яким іншим покриттям цієї функції.
Можна показати, що покриття, що має мінімальну ціну Sa має також і мінімальну ціну Sb.
C0(f)=K0(f); Sa = 5 * 3 = 15; Sb = Sa + 5 = 20
C1(f)=K1(f); Sa = 4 * 2 = 8; Sb = Sa + 4 = 12
Cmin (f): Sa = 3 * 2 = 6; Sb=9
Ціна покриття Sa являє собою кількість букв, що входять до ДНФ, що відповідає даному покриттю.
Ціна Sb представляє для ДНФ суму кількості літер та кількості термів.
Ціна покриття добре узгоджується з ціною схеми за Квайном, яка будується за нормальною формою, що відповідає цьому покриттю.
Для наведеної схеми ціна Квайну SQ=9=Sb (9-число входів).
В принципі, між SQ і цінами Sa і Sb існує співвідношення Sa £ SQ £ Sb Ця нерівність має місце при наступних припущеннях за комбінаційною схемою:
1) Схема будується за нормальною формою (ДНФ чи КНФ).
2) Схема будується на елементах булевого базису (І, АБО).
3) На входи схеми можна подавати як прямі, і інверсні значення вхідних змінних, що є значення аргументів булевої функції (схема з парафазними входами). Елементи НЕ(Інвертора у схемі відсутні.
Нульове покриття булевої функції та отримання мінімальної КНФ.
Вище було розглянуто покриття булевої функції на наборах аргументів, для яких функція дорівнює одиниці.
Такі покриття можна назвати одиничними. Поряд із одиничними покриттями існують і нульові, для яких покриваються набори аргументів, на яких функція дорівнює нулю, тобто покриття реалізується для суттєвих вершин, але не самої функції, а її заперечення (інверсії).
Нульове покриття будується як і одиничне, але тільки заперечення вихідної функції.
C0 (f) = K0 (f) Sa = 9 Sb = 12
K1(f)=01x Z(f)=Cmin(f)=01x Sa=5 Sb=7
Ціна мінімального нульового покриття виявилася меншою за ціну мінімального одиничного покриття.
Так як заздалегідь передбачити неможливо, яке з мінімальних покриттів даної функції, одиничне або нульове, матиме меншу ціну, то для побудови схеми, що має мінімальну ціну за Квайном, доцільно вирішувати задачу мінімізації щодо обох покриттів.