Розв’язок

З таблиці 4.6 видно, що кожне значення булевої функції є запереченням симетричного йому значення, наприклад: булева функція на інтерпретації дорівнює нулю, тобто , симетричне значення цієї функції на інтерпретації дорівнює одиниці, тобто .

Отже, функція є самодвоїстою.

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

Отже, функція не є самодвоїстою.

 

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. Записати диз’юнктивне розкладання функції за змінними .