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

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

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

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

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

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

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

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

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

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

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

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

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

Приклад:

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

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

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

Література ред.

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

Див. також ред.

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