Розв'язник вправ по дискретній математиці. Побудова ДНФ та КНФ Розглянемо розв'язання цієї задачі на прикладі. Дана функція . Спочатку будуємо таблицю істинності, а значення функції підставляємо в тому ж порядку, в я кому вона і дана. 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 За аналогією створюємо КНФ:
Спростити отримані вирази можна за допомогою карт Карно.
Дивись також Досконала диз'юнктивна нормальна форма Досконала кон'юнктивна нормальна форма Карта Карно