Розв'язник вправ по дискретній математиці/Булева алгебра/Диз'юнктивна та кон'юнктивна нормальні форми

Матеріал з Вікіпідручника
Перейти до навігації Перейти до пошуку

Побудова ДНФ та КНФ[ред.]

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

x y z f
0 0 0 0
0 0 1 0
0 1 0 1 - дає 1
0 1 1 1 - дає 1
1 0 0 1 - дає 1
1 0 1 1 - дає 1
1 1 0 0
1 1 1 0

Для того щоб створити диз'юнктивну нормальну форму потрібно дивитися лише на ті значення функції які дорівнюють "1". Наступний крок — зробити так, щоб змінні при кон'юнкції між собою давали стовідсоткову 1 (Приклад у таблиці). Тобто диз'юнктивна нормальна форма матиме такий вигляд:


Для створення кон'юнктивної нормальної форми скористаємося тими значення, де вона дорівнює "0". Робимо все по аналогії, але тепер диз'юнкція між змінними повинна дорівнювати "0".

x y z f
0 0 0 0 - дає 0
0 0 1 0 - дає 0
0 1 0 1
0 1 1 1
1 0 0 1
1 0 1 1
1 1 0 0 - дає 0
1 1 1 0 - дає 0

Тепер ми можемо створити кон'юнктивну нормальну форму, я ка буде виглядати натсупним чином:

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

x y z g f
0 0 0 0 1 - дає 1
0 0 0 1 1 - дає 1
0 0 1 0 1 - дає 1
0 0 1 1 0
0 1 0 0 0
0 1 0 1 0
0 1 1 0 1 - дає 1
0 1 1 1 0
1 0 0 0 0
1 0 0 1 0
1 0 1 0 0
1 0 1 1 0
1 1 0 0 1 - дає 1
1 1 0 1 1 - дає 1
1 1 1 0 1 - дає 1
1 1 1 1 1 - дає 1

Схема розв'язння функції з чотирма змінними така ж сама. Отже, ДНФ має такий вигляд:

x y z g f
0 0 0 0 1
0 0 0 1 1
0 0 1 0 1
0 0 1 1 0 - дає 0
0 1 0 0 0 - дає 0
0 1 0 1 0 - дає 0
0 1 1 0 1
0 1 1 1 0 - дає 0
1 0 0 0 0 - дає 0
1 0 0 1 0 - дає 0
1 0 1 0 0 - дає 0
1 0 1 1 0 - дає 0
1 1 0 0 1
1 1 0 1 1
1 1 1 0 1
1 1 1 1 1

За аналогією створюємо КНФ:

Спростити отримані вирази можна за допомогою карт Карно.

Дивись також[ред.]