Вікіпідручник

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

Інтерактивний перегляд історії
Наступне редагування →
Вилучено вміст Додано вміст
ВізуальнийВікірозмітка
Створена сторінка: Роздивимося розв'язання цієї задачі на прикладі. Дана функція f(x,y,z)=(00111100). Спочатку бу...
 
Vlasenko D (обговорення | внесок)
118 редагувань
оформлення
Рядок 1:
РоздивимосяРозглянемо розв'язання цієї задачі на прикладі. Дана функція <math>f(x,y,z)=(00111100)</math>. Спочатку будуємо таблицю істинності, а значення функції підставляємо в том ж порядку, в я кому вона і дана (знак (-) означає функцію "ні").
{| class="wikitable"
|-
Рядок 8:
| 0 || 0 || 1 || 0
|-
| 0 || 1 || 0 || 1 <math>(-\overline x ʌ\land y ʌ\land \overline -z)</math> - дає 1
|-
| 0 || 1 || 1 || 1 (-x ʌ y ʌ z) - дає 1
Рядок 20:
| 1 || 1 || 1 || 0
|}
Для того щоб створити диз'юнктивну нормальну форму потрібно дивитися лише на ті значення функції які дорівнюють "1". Наступний крок - зробити так, щоб змінні при кон'нкціїюнкції між собойсобою давали стовідсоткову 1 (Приклад у таблиці). Тобто диз'юнктивна нормальна форма матиме такий вигляд:
f(x,y,z)=(-x ʌ y ʌ -z)v(-x ʌ y ʌ z)v(x ʌ -y ʌ -z)v(x ʌ -y ʌ z).
 
Для створення кон'юнктивної нормальної форми скористаємося тими значення, де вона дорівнює "0". Робимо все по аналогії, але тепер диз'юнкіяюнкція між змінними повинна дорівнювати "0".
{| class="wikitable"
|-
! x !! y !! z !! f
|-
| 0 || 0 || 0 || 0 <math>(x v\vee y v \vee z)</math> дає 0
|-
| 0 || 0 || 1 || 0 (x v y v -z) дає 0
Рядок 43 ⟶ 44:
| 1 || 1 || 1 || 0 (-x v -y v -z) дає 0
|}
 
Тепер ми можемо створити кон'юнктивну нормальну форму, я ка буде виглядати натсупним чином:
f(x,y,z)=(x v y v z)ʌ(x v y v -z)ʌ(-x v -y v z)ʌ(-x v -y v -z).▼
 
▲ :f(x,y,z)=(x v y v z)ʌ(x v y v -z)ʌ(-x v -y v z)ʌ(-x v -y v -z).
Отримано з https://uk.wikibooks.org/wiki/Розв%27язник_вправ_по_дискретній_математиці/Булева_алгебра/Диз%27юнктивна_та_кон%27юнктивна_нормальні_форми