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

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

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

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

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

Метод дозволяє отримувати скорочену ДНФ булевої функції 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.

Див. також

Це незавершена стаття про алгоритми.
Ви можете проєкту, виправивши або дописавши її.