Мінімізація булевих функційМінімізація булевих функцій — спрощення булевих виразів. Оскільки логічні функції реалізують за допомогою певного набору пристроїв, то, спрощуючи вираз, зменшуємо кількість елементів. Способи мінімізації булевих функцій
Метод Блейка-ПорецькогоМетод дозволяє отримувати скорочену ДНФ булевої функції 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 з її випадкової КНФ. Якщо у довільній КНФ булевої функції розкрити всі дужки і провести всі поглинання, то в результаті буде отримана скорочена ДНФ булевої функції. Приклад:
Знайдемо скорочену ДНФ
Зробимо поглинання
і виходить скорочена ДНФ. Література
Див. також
|
Portal di Ensiklopedia Dunia