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

Розв'язник вправ по дискретній математиці. Побудова ДНФ та КНФРедагувати

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

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

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

 

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

Дивись такожРедагувати