Essays.club - Получите бесплатные рефераты, курсовые работы и научные статьи
Поиск

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

Автор:   •  Январь 7, 2023  •  Практическая работа  •  511 Слов (3 Страниц)  •  216 Просмотры

Страница 1 из 3

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

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

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

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

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

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

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

Виконав студент 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

...

Скачать:   txt (8.3 Kb)   pdf (106.7 Kb)   docx (558.9 Kb)  
Продолжить читать еще 2 страниц(ы) »
Доступно только на Essays.club