Практичне заняття 6

Вправа 1. Побудувати ДДНФ логічної функції .

Виконання. За номером функції будуємо її таблицю істинності

Вибираємо слова, на яких задана функція набуває значення 1 і виписуємо відповідні конституенти одиниці.

000

011

110

111

Об’єднуємо одержані конституанти одиниці операцією диз’юнкції і одержуємо ДДНФ заданої функції:

.

Вправа 2. Записати ДДНФ функції

Виконання Перетворюємо логічну формулу до формули булевої алгебри:

.

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

Отже, ДДНФ функції

.

Варіанти для самостійної роботи

Варіант	Вправа 1.	Вправа 2.
1	124
2	149
3	137
4	123
5	175
6	157
7	187
8	136
9	201
10	147
11	188
12	158
13	173
14	112
15	138
16	150
17	125

10. Кон’юнктивні нормальні форми (кнф) булевих функцій

Елементарною диз’юнкцією називається диз’юнкція будь-якого числа булевих змінних, із запереченням або без нього, в якій кожна змінна зустрічається не більше одного разу. Константу 0 – елементарна диз’юнкція, що містить нуль змінних.

Приклад 1. Приклади елементарних диз’юнкцій , , ,.

Кон’юнктивною нормальною формою (КНФ) називається формула, що зображена у вигляді диз’юнкції елементарних кон’юнкцій.

Приклад 2. Формула є кон’юнктивною нормальною формою (КНФ).

Теорема. Будь-яка булева функція може бути представлена кон’юнктивним розкладом

(1)

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

Приклад 3. Записати кон’юнктивний розклад функції по змінним x і t.

Виконання. За формулою (1)

.

Обчислимо:

;

;

:

.

Отже

Приклад 4. Одержати кон’юнктивний розклад функції по змінній .

Виконання. За формулою (1)

,

,

.

Отже,

Практичне заняття 7.

11. Досконала кон’юнктивна нормальна форма булевих функцій

Елементарна диз’юнкція називається конституентою нуля (макстермом) функції , якщо .

Конституента нуля має такі властивості.

1. Конституента нуля дорівнює нулю тільки на одному відповідному слові.

2. Конституента нуля однозначно визначається номером відповідного їй слова.

3. Диз’юнкція будь-якого числа різних конституент нуля функції дорівнює одиниці.

Приклад. Елементарна диз’юнкція є конституантою нуля функції на слові 01, оскільки

Елементарна диз’юнкція є конституентою нуля функції на слові 000, оскільки

Елементарна диз’юнкція є конституантою нуля функції на слові 101, оскільки

Диз’юнкція .

Досконалою кон’юктивною нормальною формою (ДКНФ) називають кон’юнкція конституент нуля.

Кожна булева функція, крім константи 1, може бути подана єдиною ДКНФ, яка є результатом кон’юнктивного розкладу (1) булевої функції по всім змінним:

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

1. Вибрати всі слова, на яких задана функція приймає значення 0.

2. Побудувати конституенти нуля на цих вибраних словах.

3. Об’єднати одержані конституенти нуля операцією кон’юнкції.

Приклад. Булева функція задана таблицею істинності

Побудувати ДКНФ для цієї функції.

Виконання. Вибираємо слова, на яких задана функція набуває значення 0 і виписуємо відповідні конституенти нуля.

000

001

011

110

111

Об’єднуємо одержані конституанти одиниці операцією диз’юнкції і одержуємо ДКНФ заданої функції:

.

Якщо булева функція задана формулою булевої алгебри, то для побудови ДКНФ здійснюється за таким алгоритмом.

1. Виключити константи. Для цього скористатися законами дій з константами: ; ; ; .

2. Опустити знаки заперечення на змінні. Для цього скористатися законами де Моргана : ; .

3. Побудувати КНФ булевої функції. Для цього розкрити дужки використовуючи дистрибутивний закон диз’юнкції відносно кон’юнкції, звести подібні, застосовуючи закони ідемпотентності та і закони дій із запереченням ; .

4. Побудувати конституенти нуля функції. Для цього ввести в кожну елементарну диз’юнкцію відсутні змінні використовуючи рівність ;

5. Побудувати ДКНФ булевої функції. Для цього необхідно розкрити дужки та звести подібні.

Приклад. Побудувати ДКНФ функції .

Виконання. Константи у формулу не входять і тому починаємо з 2 кроку.

2 крок. Опускаємо заперечення на змінні:

.

3 крок. Розкриваємо дужки:

(КНФ)

4 крок: Задана функція залежить від трьох змінних, тому до елементарних кон’юнкцій вводимо відсутні змінні:

.

5 крок: Розкриваємо дужки і зводимо подібні члени

.

Отже, ДКНФ заданої функції.