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

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

Способи мінімізації булевих функцій

• метод Блейка-Порецького;
• метод Нельсона;
• метод Дужкових форм;
• метод карт Карно.

Метод Блейка-Порецького

Метод дозволяє отримувати скорочену ДНФ булевої функції f з її довільної ДНФ. Базується на застосуванні методу загального склеювання Ax v Bẍ = Ax v Bẍ v AB, правильність якого легко доводиться: Ax = Ax v ABx; Bẍ = Bẍ v ABẍ. З цього слідує: Ах v Вẍ = Ах v АВх v Вẍ v АВẍ = Ах V Вẍ V АВ. В основу методу покладено наступне твердження: якщо в випадковій ДНФ булевій функції f зробити всі можливі узагальнені склеювання, а потім виконати всі поглинання, то в результаті вийде скорочена ДНФ функція f.

Приклад: Булева функція f задана випадковою ДНФ: f = ẍ1ẍ2 v x1ẍ2ẍ3 v x1x2. Знайти методом Блейка — Порецкого скорочену ДНФ функції f. Проводимо узагальнені склеювання. Легко бачити, що перший і другий елемент заданої ДНФ допускають узагальнене склеювання по змінній х1. В результаті склеювання маємо:

ẍ1ẍ2 v x1ẍ2ẍ3 = ẍ1ẍ2 v x1ẍ2ẍ3 v ẍ2ẍ3

Перший і третій елемент вихідної ДНФ допускають узагальнене склеювання як по змінній х1, так і по х2. Після склеювання по x1 маємо:

ẍ1ẍ2 v x1x2 = ẍ1ẍ2 v x1x2 v ẍ2x2 = ẍ1ẍ2 v x1x2

Після склеювання по x2 маємо:

ẍ1ẍ2 v x1x2 = ẍ1ẍ2 v x1x2 v ẍ1x1 = ẍ1ẍ2 v x1x2

Другий і третій елемент ДНФ допускають узагальнене склеювання по змінній х2 . Після склеювання отримуємо:

x1ẍ2ẍ3 v x1x2 = x1ẍ2ẍ3 v x1x2 v x1x3

Виконавши останнє узагальнене склеювання, приходимо до ДНФ:

f = ẍ1ẍ2 v x1ẍ2ẍ3 v ẍ2ẍ3 v x1x2 v x1ẍ3

Після виконання поглинань отримуємо:

f = ẍ1ẍ2 v ẍ2ẍ3 v x1x2 v x1ẍ3

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

Метод Нельсона

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

Приклад:

f = (x1 v ẍ2)(ẍ1 v x3)(x1 v x2 v ẍ3)

f = (x1x3 v ẍ1ẍ2 v ẍ2x3)((x1 v x2 v ẍ3))

Знайдемо скорочену ДНФ

f = x1x3 v x1x2x3 v ẍ1ẍ2ẍ3 v x1ẍ2x3

Зробимо поглинання

f = x1x3 v ẍ1ẍ2ẍ3

і виходить скорочена ДНФ.

Література

• «Прикладна теорія цифрових автоматів» Київ, «Вища Школа» 1987, К. Г. Самофалов, А. М. Романкевич, В. Н. Валуйський, Ю. С. Каневский, М. М. Пиневич, С.201—202.

Див. також

• Нормальна форма формули у логіці предикатів
• Диз'юнктивна нормальна форма (ДНФ)
• Кон'юнктивна нормальна форма (КНФ)
• Досконала диз'юнктивна нормальна форма (ДДНФ)
• Досконала кон'юнктивна нормальна форма (ДКНФ)
• Карта Карно