Системи булевих функцій (стр. 3 из 5)
Викреслюючи рядка, у яких перебувають істотні імпліканти, і стовпці, що покриваються цими імплікантами, одержуємо матрицю менших розмірів Якщо в ній є стовпці, що містять по однієї 1, то операцію виділення істотних імплікант варто повторити.
2 Стиск по стовпцях або рядкам. З матриці викреслюється той стовпець, у який повністю входить який-небудь інший стовпець і той рядок, що повністю покривається інший.
Після виконання всіх зазначених дій у матриці залишаться тільки ті прості імпліканти, які входять у мінімальне покриття функції. З'єднавши ці імпліканти й знайдені раніше істотні імпліканти знаками диз'юнкцій, одержимо мінімальну ДНФ заданої функції.
Приклад 7 Мінімізувати булеву функцію
.Рішення. Функція задана в ДНФ, тому займемося відразу відшуканням простих імплікант, проводячи операцію склеювання. Для цього представимо кожну елементарну кон'юнкцію двійковим набором, ставлячи на k-ом місці 0, якщо Хk входить із запереченням, 1 - якщо без заперечення й знак "-", якщо ця змінна не входить у кон'юнкцію Тоді функція прийме вид:
.Розіб'ємо ці набори на класи, у кожному з яких утримуються набори з однаковим числом одиниць і розташуємо їху порядку зростання суми всіх чисел набору (рис 2 а)
Для виключення змінних за правилом склеювання зрівняємо всі набори всіх суміжних класів. Якщо при цьому яка-небудь змінна виключається, то в розряд, що відповідає цієї змінної, записуємо прочерк. Наприклад, двійкові набори 0100 і 0101 утворять набір 010-. Всі отримані набори знову розбиваємо на класи. Поєднуємо знову набори із двох суміжних класів, причому порівнянню підлягають тільки ті, у яких прочерк перебуває в тому самому розряді, одержуємо новий набір імплікант (мал.2 в). Неважко переконатися, що подальше об'єднання наборів неможливо, отже, всі отримані імпліканти - прості.
Побудуємо матрицю (табл.3 а). Виділяючи стовпці, що містять по одній одиниці, знаходимо істотні імпліканти, що утворять ядро Квайна: 0-0 - 0-0. При цьому перша з них є істотною для 0000, 0001, 0100, 0101, а друга - для 0000, 0010, 1000, 1010. Викреслюючи стовпці із цими й рядка з істотними імплікантами, одержимо табл.3 б. У цій таблиці немає стовпців, що містять тільки одну одиницю, отже істотних імплікант у цій таблиці немає і ядро Квайна складається із двох імплікант, знайдених вище: 0-0 - і - 0-0.
Переходимо до операцій стисла по рядках і стовпцям. Другий рядок табл.3 б поглинає першу, а четверта - третю, тому першу й третю рядки можна викреслити (табл.3 в).
У табл.3 у перший стовпець повністю входить у четвертий, а другий - у третій, Після викреслювання четвертого й третього стовпців таблиця приймає вид 3 р. Із цієї таблиці видно, що імпліканта 111 - є зайвої, тому що не містить одиниць у жодному стовпці, а дві інші входять у мінімальне покриття. Таким чином, задана функція має чотири простих імпліканти: 0-0-, - 0-0, 1-і0 і - 111. Поєднуючи їхнім знаком диз'юнкції, одержуємо мінімальну ДНФ у вигляді
.Алгоритм Квайна дозволяє одержувати мінімальні диз'юнктивні нормальні форми заданих функцій Однак у ряді випадків мінімальні нормальні вираження виявляються "менше" диз'юнктивних, тому при рішенні задач мінімізації бажано одержати не тільки диз'юнктивні, але й нормальні формули й вибрати з них найменше. Методи одержання мінімальних виражень двоїсті розглянутим вище методам і ми не будемо на них зупинятися.
4. Геометричне подання логічних функцій
Позначимо через Еn множину всіх наборів (α1,., αη), що складаються із чисел нуль і одиниця. Множина Еn називається n-мірним кубом, а набір (α1,., αη) - вершинами куба.
Нехай σ1,., σr - фіксований набір чисел з 0 і 1. Множина всіх вершин (α1,., αη) куба Еn таких, що αi1 = σ1, αi2 = σ2,., αir = σr, 1 < i1 < i2 <.< ir, називається (n - r) - мірною гранню. Очевидно, що (n - r) - мірна грань є (n - r) - підкубом куба Еn.
Наприклад, у тривимірному кубі Е3 набори (0,0,1) і (0,0,0) утворять одномірну (n = 3, r = 2) грань (ребро), а набори (1,0,0), (1,0,1), (1,1,0), (1,1,1) - двомірну грань.
Нехай f (X1,X2,…,Xn) - довільна булева функція. Їй зіставляється у відповідність підмножина Νf вершин куба Еn, таких що (α1,., αη)
Nf тоді й тільки тоді, коли f (α1,., αη) = l Очевидно, що по підмножині Nf вихідна функція f (X1, X2.,., Χn) відновлюється однозначно. У такий спосіб геометричний спосіб завдання булевої функції полягає в завданні множини вершин n-мірного куба Еn, у яких дана функція щира.Приклад 8. Нехай функція f (X1, X2, Х3) задана табл.4. Скласти для неї множина Nf.
Таблиця 4
| X1 | X2 | X3 | f (X1, X2, Х3) |
| 0 | 0 | 0 | 1 |
| 0 | 0 | 1 | 0 |
| 0 | 1 | 0 | 0 |
| 1 | 0 | 0 | 1 |
| 0 | 1 | 1 | 0 |
| 1 | 0 | 1 | 1 |
| 1 | 1 | 0 | 1 |
| 1 | 1 | 1 | 1 |
Рішення. Очевидно, що Nf = { (0,0,0), (1,0,0), (1,0,1), (1,1,0), (1,1,1) }. Множина Nf зображена на мал.3.
Мал.3
Нагадаємо [1], що для будь-який булевої функції існує її подання в СДНФ. Причому в алгоритмі побудови СДНФ використовуються тільки ті набори значень, при яких функція дорівнює одиниці [3]. Це дозволяє проінтерпретувати геометричне подання функції в такий спосіб. Розглянемо тривимірний куб і занумеруємо вершини так, як показано на мал.4.
 |  |
 |  |
 |  |
Ребрами даного куба (одномірними підкубами) будуть, наприклад,
, і т.д.Приклад 9. Побудувати модель куба, що відповідає функції:
.Рішення. Першому доданку відповідає вершина 2, другому - вершина 6, третьому - вершина 3, четвертому - вершина 8, п'ятому - вершина 4 (мал.5).
Мал.5
Приклад 10. Дано модель куба з позначеними вершинами (мал.6). Скласти СДНФ для даної булевої функції
Рішення. Вершині 1 відповідає кон'юнкція
, вершинам 3 і 4 кон'юнкція 
й 
відповідно; вершинам 5 і 6 - кон'юнкції 
й 
. Отже, шукана СДНФ має вигляд 
.Помітимо, що для функцій, що залежать від чотирьох і більше змінних, геометричне подання застосовується дуже рідко, тому що важко побудувати наочну модель n-мірного куба при n > 3. Тому в цьому й наступному параграфах ми будемо розглядати тільки булеві функції трьох аргументів, хоча все викладене справедливо для інших функцій, що залежать від великої кількості аргументів.
Перейдемо тепер до геометричної постановки задачі мінімізації булевих функцій.
5. Геометричний метод мінімізації булевої функції
Розглянемо елементарну кон'юнкцію рангу r (тобто утримуючу r змінних)
де ε = 0,1;
. Очевидно, що множина Nk, що відповідає кон'юнкції К, є (3 - r) - мірна грань. Число r називається рангом цієї грані.Приклад 11.
, 
, 
відповідають грані (мал.7 а, б, в), Nk1={7,8}, Nk2={8,6}, Nk3={6,2,4,8}, що мають ранги 2, 2, і 1. Перші дві грані є одномірною гранню (ребром), а третя - двовимірною гранню.