Мінімізація булевих функцій методом Квайна–Мак-Класкі
Автор: ananim_007 • Январь 7, 2023 • Практическая работа • 511 Слов (3 Страниц) • 210 Просмотры
МІНІСТЕРСТВО ОСВІТИ І НАУКИ УКРАЇНИ
НАЦІОНАЛЬНИЙ ТЕХНІЧНИЙ УНІВЕРСИТЕТ УКРАЇНИ «КИЇВСЬКИЙ ПОЛІТЕХНІЧНИЙ ІНСТИТУТ імені ІГОРЯ СІКОРСЬКОГО»
Факультет програмної інженерії та комп’ютерних наук
Кафедра інженерії програмного забезпечення
РОЗРАХУНКОВА РОБОТА
з курсу «Комп’ютерна дискретна математика »
на тему: «Мінімізація булевих функцій методом Квайна–Мак-Класкі»
Виконав студент 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 – Таблиця пронумерованих елементарних кон’юнкцій ДДНФ за їх двійковими номерами та десятковими еквівалентами.
Десятковий номер | Елементарні кон’юнкції | Двійковий номер |
15 | [pic 7] | 1111 |
7 | [pic 8] | 0111 |
8 | [pic 9] | 1000 |
10 | [pic 10] | 1010 |
6 | [pic 11] | 0110 |
5 | [pic 12] | 0101 |
2 | [pic 13] | 0010 |
12 | [pic 14] | 1100 |
1 | [pic 15] | 0001 |
6 | [pic 16] | 0110 |
...