5 Нормальні форми зображення булевих функцій

5.1 Мета заняття

Ознайомлення на практичних прикладах з поняттям «нормальна форма» булевої функції. Вивчення способів зображення формул у вигляді диз’юнктивних і кон’юнктивних нормальних форм (ДНФ і КНФ). Вивчення алгоритмів переходу від таблиць істинності булевих функцій і від довільних формул до досконалої диз’юнктивної і досконалої кон’юнктивної нормальних форм (ДДНФ і ДКНФ).

5.2 Методичні вказівки з організації самостійної роботи студентів

Під час підготовки до практичного заняття необхідно повторити лекційний матеріал, розділи літератури [1-10] з таких питань: основні поняття і визначення, які пов’язані з «нормальною формою» булевої функції; ДДНФ і ДКНФ булевої функції; теореми про диз’юнктивне і кон’юнктивне розкладання булевої функції за змінними; правила переходу від таблиць істинності булевої функції до ДДНФ і ДКНФ булевої функції; правила переходу від довільних формул булевої функції до ДДНФ і ДКНФ.

Підготовка і виконання практичного заняття проводиться у два етапи. Перший етап пов’язаний з вивченням на практичних прикладах наступних основних понять і визначень: елементарна кон’юнкція; елементарна диз’юнкція; ДНФ; конституента одиниці (мінтерм -го рангу); ДДНФ; КНФ; конституента нуля (макстерм-го рангу); ДКНФ.

При виконанні першого етапу практичного заняття студент повинен запропонувати і записати індивідуальний приклад для кожного з розглянутих вище понять і визначень. Другий етап виконання практичного заняття пов’язаний з розв’язанням практичних завдань, які представлено у підрозділі 5.3, на основі запропонованих типових прикладів (див. підрозділ 5.4).

5.3 Контрольні запитання і завдання

5.3.1 Контрольні запитання

1. На прикладі булевих функцій опишіть поняття «нормальна форма» функції.

2. Що являє собою елементарна кон’юнкція, елементарна диз’юнкція?

3. Яка формула називається диз’юнктивною нормальною формою, кон’юнктивною нормальною формою булевої функції?

4. Дайте визначення поняттям мінтерм, макстерм, конституента одиниці, конституента нуля.

5. Що таке досконала нормальна форма і які властивості в неї є?

6. Скільки є різних конституент одиниці та нуля для функції змінних?

7. Скільки ДНФ і скільки СДНФ може мати булева функція?

8. Запишіть формули диз’юнктивного розкладання булевих функцій від змінних зазмінними, за всімазмінними, за однією змінною.

9. Запишіть формули кон’юнктивного розкладання булевих функцій від змінних зазмінними, за всімазмінними, за однією змінною.

10. Опишіть алгоритми переходу від таблиці істинності булевої функції до ДДНФ і ДКНФ.

11. Сформулюйте правила перетворення довільної формули алгебри логіки в нормальну форму з використанням законів булевої алгебри.

5.3.2 Контрольні завдання

Завдання 1. Знайти диз’юнктивне розкладання наступних булевих функцій за змінними :

а) ;

б) ;

в) .

Завдання 2. Знайти кон’юнктивне розкладання наступних булевих функцій за змінними :

а) ;

б) ;

в) .

Завдання 3. Записати диз’юнктивне розкладання булевої функції за змінною .

Завдання 4. Записати конституенти нуля та одиниці булевої функції, що відповідають інтерпретаціям функції чотирьох змінних.

Завдання 5. За допомогою еквівалентних перетворень привести до ДНФ наступні формули: а) ; б) .

Завдання 6. Представити у вигляді ДДНФ і ДКНФ наступні функції:

а) , де стовпець значень функції з таблиці істинності; б) ; в); г); д); е).

Завдання 7. Скласти алгоритм переходу від таблиці істинності булевої функції до ДДНФ даної функції.

Завдання 8. За допомогою перетворень виду перейти від заданої ДНФдоДДНФ.

Завдання 9. Записати ДДНФ для функції , що має нульові значення на всіх непарних двійкових наборах.

Завдання 10. Записати ДКНФ для функції від 4-х змінних, яка має одиничні значення на нульовому наборі та всіх парних двійкових наборах.

Завдання 11. Нехай функція задана таким чином: , якщоабо, а інакше. За допомогою таблиці істинності функції записатимножину таку, що і записати ДКНФ і ДДНФ даної функції.

5.4 Приклади аудиторних і домашніх завдань

Завдання 1. Записати диз’юнктивне розкладання функції за змінними.

Розв’язок.

Скористаємося теоремою про розкладання булевих функцій за змінними:

.

Обчислимо:

;

;

;

.

Підставимо значення ,,,у формулу диз’юнктивного розкладання за змінним:

Завдання 2. Записати кон’юнктивне розкладання функції за змінною.

Розв’язок.

Скористаємося теоремою про кон’юнктивне розкладання булевої функції (за однією змінною):

.

Завдання 3. Представити у вигляді досконалої дизюнктивної нормальної форми і досконалої кон’юнктивної нормальної форми функцію .

Розв’язок.

Побудуємо таблицю істинності даної функції (табл. 5.4).

Таблиця 5.4 – Таблиця істинності функції

0	0	0	0	0	1
0	0	1	0	0	1
0	1	0	1	0	0
0	1	1	1	1	1
1	0	0	1	0	0
1	0	1	1	0	0
1	1	0	0	0	1
1	1	1	0	1	1

ДДНФ () побудуємо на одиничних значеннях функції:

.

ДКНФ () побудуємо на нульових значеннях функції:

.

Завдання 4.

Записати конституенти нуля та одиниці, що відповідають інтерпретаціям булевої функції трьох змінних.

Розв’язок.

Конституента нуля і конституента одиниці булевої функції однозначно визначаються номерами відповідних їм інтерпретацій. Конституента нуля функції являє собою елементарну диз’юнкцію. Інтерпретація, що обертає в нуль дану елементарну диз’юнкцію, перетворює в нуль і функцію. Конституента одиниці функціїявляє собою елементарну кон’юнкцію. Інтерпретація, що обертає в одиницю дану елементарну кон’юнкцію, перетворює в одиницю і функцію.

Конституенти нуля і конституенти одиниці для функцій трьох змінних наведені в табл. 5.4.

Таблиця 5.4 – Конституенти нуля і конституенти одиниці для функцій трьох змінних

Номер інтерпре-таціїи	Інтерпретація			Конституента одиниці	Конституента нуля
0	0	0	0
1	0	0	1
2	0	1	0
3	0	1	1
4	1	0	0
5	1	0	1
6	1	1	0
7	1	1	1

Завдання 5.

За допомогою еквівалентних перетворень привести до ДНФ формулу .

Розв’язок.

.

Завдання 6. Побудувати ДДНФ функції , використовуючи правила перетворення довільної формули алгебри логіки до ДДНФ.

Розв’язок.

Скористаємося правилами перетворення довільної формули алгебри логіки до ДДНФ.

Опускаємо заперечення на змінні, використовуючи закон де Моргана: .

Побудуємо диз’юнктивну нормальну форму, використовуючи дистрибутивний закон, закони ідемпотентності й протиріччя:

.

Булева функція залежить від трьох змінних, тому в елементарні кон’юнкції необхідно ввести відсутні змінні, використовуючи закон виключеного третього:

.

Використовуючи дистрибутивний закон, розкриємо дужки і зведемо подібні для одержання ДДНФ:

.

Одержана досконала диз’юнктивна нормальна форма заданої булевої функції: .

Завдання 7. Скласти алгоритм переходу від таблиці істинності булевої функції до ДКНФ.

Розв’язок.

Для переходу від таблиці істинності булевої функції до ДКНФ можна скористатися наступним алгоритмом:

а) виділити в таблиці істинності булевої функції всі інтерпретації, на яких значення функції дорівнює нулю;

б) записати конституенти нуля, що відповідають відзначеним інтерпретаціям;

в) одержати ДКНФ функції за допомогою з’єднання операцією кон’юнкції записаних конституент нуля.