Системи булевих функцій (стр. 4 из 5)
Мал.7
Відзначимо очевидні властивості уведеної відповідності між булевої функцією f і підмножиною Nf.
Якщо
, то 
.Зокрема, якщо f (X1, Χ2, X3) володіє ДНФ, тобто
, те 
й 
тобто ДНФ функції f відповідає покриття множини Ν, гранями 
.Приклад 12. Розглянемо представлену в СДНФ функцію
.модель куба, для якої побудована на мал.3. За допомогою таблиці істинності може бути показано, що дана функція представимо також ДНФ
.ДНФ відповідають два покриття множини Nf:
, 
,де Nk1={2}, Nk2={6}, Nk3={3}, Nk4={8}, Nk5={4}, Nk10={2,6,8,4}, Nk20={4,3}. Одне із цих покриттів - крапкове, друге складається з ребра й двовимірної грані.
Нехай ri - ранг гpани Νki (він дорівнює рангу кон'юнкції ki). Число r, певне формулою
,називається рангом покриття. Тoгда задача про мінімізацію булевої функції приймає наступну геометричну постановку: для даної множини Nf, знайти таке покриття гранями, що належать Nf,
, щоб його ранг був найменшим.Приведемо також визначення скороченої й тупикової ДНФ c геометричної точки зору.
Грань Nk, що втримується в Nf, називається максимальної відносно Nf, якщо не існує грані
, такий, що1)
2) розмірність грані
більше розмірності грані Nk.Приклад 13. Нехай f (X1, Х2, X3) - функція, задана табл.4 і
Тоді грані Νk1 і Nk3 є максимальними, a Nk2 не максимальна для Nf, тому що 
й розмірність Nk3 більше розмірності Nk2.Кон'юнкція К, що відповідає максимальної грані Nk, називається простою імплікантою функції f.
ДНФ, що є диз'юнкцією всіх простих імплікант функції f, називається скороченої ДНФ.
Покриття множини Nf, що складає з максимальних відносно Nf граней, називається що не приводиться, якщо сукупність граней, що виходить із вихідної шляхом викидання будь-якої грані, не буде покриттям Nf.
множини Nf називається тупикової в геометричному змісті.
Теорема. Поняття тупикової ДНФ і тупикової ДНФ у геометричному змісті еквівалентні.
Алгоритм мінімізації функцій, що залежать від трьох змінних, складається в наступних чотирьох кроках:
Нанести множина Nf, на тривимірний куб. Використовувати або табличне завдання функції, відзначивши вершини, у яких f (X1, Χ2, Χ3) = 1, або СДНФ функції й тоді кожному що складається СДНФ поставити у відповідність вершину (див. розділ 5).
Якщо відзначеними виявляться всі вершини куба, то дана функція тотожно щира. Якщо відзначені всі вершини якої-небудь грані, то для побудови мінімальної форми замінити всі чотири вершини одною змінної - назвою грані.
Якщо відзначені вершини якого-небудь ребра, то в мінімізованій формі їм відповідає кон'юнкція - назва ребра.
Щоб одержати мінімізовану форму, треба вибирати ребра, що покривають вершини, так, щоб меншим числом ребер покрити всі відзначені вершини.
Приклад 14. Мінімізувати функцію f (X1, X2, Х3), задану табл.4.
Рішення. Множина Nf для зазначеної функції зображене на мал.3. Тому що вершини 2, 4, 6, 8 належать одній грані Χ1,вершини 7 і 8 належать ребру
, те мінімізована форма функції f має вигляд 
.Приклад 15. Мінімізувати записану в СДНФ функцію
.Рішення. Відзначимо на моделі куба елементарні кон'юнкції: першої кон'юнкції відповідає вершина 6, другий - вершина 5, третьої - вершина 8, четвертої - вершина 2 (рис 8). Таким чином, множина Nf - побудовано. Жодна грань не відзначена повністю, тому переходимо до кроку 4 алгоритми.
Мал.8
Вершини 5 і 6 належать одному ребру
, вершини 6 і 8 - ребру 
, отже, мінімізована форма має вигляд: 
.Приклад 16. Мінімізувати функцію f (X1,X2,X3), задану табл.5.
Таблиця 5
| Х1 | 1 | 1 | 1 | 0 | 1 | 0 | 0 | 0 |
| Х2 | 1 | 1 | 0 | 1 | 0 | 1 | 0 | 0 |
| Х3 | 1 | 0 | 1 | 1 | 0 | 0 | 1 | 0 |
| f (X1,X2,X3) | 1 | 1 | 1 | 1 | 1 | 1 | 0 | 0 |
Рішення. Побудуємо модель куба, що відповідає цієї функції (мал.9).
Мал.9
Грані (1, 2, 3,4) відповідає X2, грані (2, 4, 6,8) - Х1, отже, мінімізована форма має вигляд
.Відзначимо, що при n = 3 геометричний метод мінімізації булевих функцій аналогічний мінімізації за допомогою прямокутної таблиці, названої, картою (картою Карно).
6. Мінімізація булевої функції за допомогою карти Карно
Карта Карно являє собою таблицю для завдання логічних функцій у СДНФ. Наприклад, для функції, заданої табл.5, карта Карно представлена в табл.6.
Розташування кліток у таблиці дозволяє легко визначити члени, що склеюються між собою, тому що кожній клітці карти Карно відповідає вершина куба. Помітимо, що сусідніми вважаються не тільки поруч варті осередки, але й осередку, що перебувають на протилежних кінцях будь-якого стовпця й будь-якого рядка.
Таблиця 6
Так, склеюючи констітуенти, розташовані в другому й третьому рядках табл.6, одержуємо імпліканту - X2, а констітуентам двох останніх рядків відповідає імпліканта Х1 - . Отже, мінімальна форма заданої булевої функції має вигляд (див. приклад 16)
.Приклад 17. Мінімізувати за допомогою карти Карно функцію f (X1, Х2, Χ3), задану табл.4.
Рішення. Побудуємо для
карту (табл.7)Таблиця 7
Об'єднаємо сусідні клітки, що відповідають одиничним значенням функції f, у максимальні інтервали, як показано в табл.7. Зіставимо кожному максимальному інтервалу імпліканти Χ1 і
. Отже, мінімальна форма має вигляд: .Приклад 18. Мінімізувати булеву функцію
.Рішення. Використовуючи таблиці істинності, побудуємо для заданої функції f карту Карно (табл.8).
Об'єднаємо сусідні клітки, що відповідають одиничному значенню функції, у максимальні інтервали, як показано в табл.8. Отже, мінімальна форма даної функції має вигляд
Таблиця 8
.Якщо булева функція f залежить від чотирьох аргументів, то за допомогою карти можна знаходити скорочену ДНФ.
Приклад 19. Нехай функція f (X1, X2, Х3, Х4) задана та6л.9. Побудувати скорочену ДНФ.
Рішення. Максимальні інтервали, що з'єднують клітки, що відповідають одиничним значенням функції f, вибираються так, як показано в табл.9. Зіставляючи їм прості імпліканти, одержимо скорочену Д??.
Таблиця 9
