Мінімізація булевих функцій методом Квайна–Мак-Класкі

МІНІСТЕРСТВО ОСВІТИ І НАУКИ УКРАЇНИ

НАЦІОНАЛЬНИЙ ТЕХНІЧНИЙ УНІВЕРСИТЕТ УКРАЇНИ «КИЇВСЬКИЙ ПОЛІТЕХНІЧНИЙ ІНСТИТУТ імені ІГОРЯ СІКОРСЬКОГО»

Факультет програмної інженерії та комп’ютерних наук

Кафедра інженерії програмного забезпечення

РОЗРАХУНКОВА РОБОТА

з курсу «Комп’ютерна дискретна математика »

на тему: «Мінімізація булевих функцій методом Квайна–Мак-Класкі»

Виконав студент 1 курсу групи № 412п

Спеціальності 121 - інженерія програмного забезпечення

Прокопенко І.І.
Прийняв старший викладач Самойлова А.М.

_____________________________________

Національна шкала ____________

Кількість балів: ___________

Київ – 2022

ЗМІСТ

1

Постановка завдання        3

2 Метод Квайна – Мак-Класкі        4

3 Мінімізація булевої функції        5

4 Результат мінімізації булевої функції        7

5 ВИСНОВОК        8

Розрахункова робота

МІНІМІЗАЦІЯ БУЛЕВИХ ФУНКЦІЙ ЕТОДОМ

КВАЙНА–МАК-КЛАСКІ

Мета роботи – навчитися мінімізувати булеві функції (БФ) за допомогою методу Квайна – Мак-класкі.

Постановка завдання

Для БФ, поданої у вигляді досконалої диз'юнктивної нормальної форми (ДДНФ), знайти мінімальну диз'юнктивної нормальної форми (МДНФ) за допомогою методу Квайна – Мак-Класкі.

[pic 1]

[pic 2]

Метод Квайна – Мак-Класкі

Метод Квайна – Мак-Класкі – табличний метод мінімізації булевих функцій, запропонований Уиллардом Квайном і вдосконалений Едвардом Мак-Класкі, який є спробою позбавитися від недоліків методу Квайна. Незважаючи на деякі переваги перед картами Карно, метод Квайна – Мак-Класкі також обмежений: час роботи методу збільшується експоненціально зі зростанням вхідних даних. Тому для функцій з великою кількістю змінних використовують евристичні алгоритми.

Метод Квайна оснований на справедливості твердження, якщо в досконалій диз’юнктивній нормальній формі формули алгебри логіки (ФАЛ) виконати неповне склеювання

( x ∧ F ) ∨ (∧ F ) = ( x ∧ F ) ∨ (  ∧ F ) ∨ F = F,[pic 3][pic 4]

а потім – всі можливі поглинання (F ∧ Х) ∨ F = F, то виходить скорочена диз’юнктивна нормальна форма (СкДНФ) ФАЛ, з якої отримують мінімальну диз’юнктивну нормальну форму шляхом виключення деяких імплікант.

Ідея методу реалізується у формі алгоритму.

Алгоритм методу

1. Записати булеву функцію у вигляді ДДНФ.

2. Виконати всі можливі операції склеювання.

3. Отримати диз'юнкцію всіх можливих імплікант (ЕК – елементарні кон’юнкцї) булевої функції.

4. Виконати всі можливі операції поглинання. Отримати скорочену СкДНФ.

5. Скласти імплікантну таблицю і знайти диз'юнктивне ядро – опорне рішення.

6. Спростити імплікантну таблицю: видалити з неї рядки, що відповідають опорному рішенню, і стовпці, які покриваються імплікантами ядра.

7. Знайти всі тупикові диз’юнктивні нормальні форми (ТДНФ).

8. Вибрати МДНФ.

Мінімізація булевої функції

[pic 5]

[pic 6]

Таблиця 1 – Таблиця пронумерованих елементарних кон’юнкцій ДДНФ за їх двійковими номерами та десятковими еквівалентами.