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

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

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

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

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

Ця стаття потребує додаткових посилань на джерела для поліпшення її перевірності. Будь ласка, допоможіть удосконалити цю статтю, додавши посилання на надійні (авторитетні) джерела. Зверніться на сторінку обговорення за поясненнями та допоможіть виправити недоліки. Матеріал без джерел може бути піддано сумніву та вилучено. (березень 2017)

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