Розглянемо розв'язання цієї задачі на прикладі. Дана функція
f
(
x
,
y
,
z
)
=
(
00111100
)
{\displaystyle f(x,y,z)=(00111100)}
таблицю істинності , а значення функції підставляємо в тому ж порядку, в я кому вона і дана.
x
y
z
f
0
0
0
0
0
0
1
0
0
1
0
1
(
x
¯
∧
y
∧
z
¯
)
{\displaystyle ({\overline {x}}\land y\land {\overline {z}})}
0
1
1
1
(
x
¯
∧
y
∧
z
)
{\displaystyle ({\overline {x}}\land y\land z)}
1
0
0
1
(
x
∧
y
¯
∧
z
¯
)
{\displaystyle (\ x\land {\overline {y}}\land {\overline {z}})}
1
0
1
1
(
x
∧
y
¯
∧
z
)
{\displaystyle (\ x\land {\overline {y}}\land z)}
1
1
0
0
1
1
1
0
Для того щоб створити диз'юнктивну нормальну форму потрібно дивитися лише на ті значення функції які дорівнюють "1". Наступний крок — зробити так, щоб змінні при кон'юнкції між собою давали стовідсоткову 1 (Приклад у таблиці). Тобто диз'юнктивна нормальна форма матиме такий вигляд:
f
(
x
,
y
,
z
)
=
(
x
¯
∧
y
∧
z
¯
)
∨
(
x
¯
∧
y
∧
z
)
∨
(
x
∧
y
¯
∧
z
¯
)
∨
(
x
∧
y
¯
∧
z
)
{\displaystyle f(x,y,z)=({\overline {x}}\land y\land {\overline {z}})\vee ({\overline {x}}\land y\land z)\vee (\ x\land {\overline {y}}\land {\overline {z}})\vee (\ x\land {\overline {y}}\land z)}
Для створення кон'юнктивної нормальної форми скористаємося тими значення, де вона дорівнює "0". Робимо все по аналогії, але тепер диз'юнкція між змінними повинна дорівнювати "0".
x
y
z
f
0
0
0
0
(
x
∨
y
∨
z
)
{\displaystyle (x\vee y\vee z)}
0
0
1
0
(
x
∨
y
∨
z
¯
)
{\displaystyle (x\vee y\vee {\overline {z}})}
0
1
0
1
0
1
1
1
1
0
0
1
1
0
1
1
1
1
0
0
(
x
¯
∨
y
¯
∨
z
)
{\displaystyle ({\overline {x}}\vee {\overline {y}}\vee z)}
1
1
1
0
(
x
¯
∨
y
¯
∨
z
¯
)
{\displaystyle ({\overline {x}}\vee {\overline {y}}\vee {\overline {z}})}
Тепер ми можемо створити кон'юнктивну нормальну форму , яка буде виглядати наступним чином:
f
(
x
,
y
,
z
)
=
(
x
∨
y
∨
z
)
∧
(
x
∨
y
∨
z
)
∧
(
x
¯
∨
y
¯
∨
z
)
∧
(
x
¯
∨
y
¯
∨
z
)
{\displaystyle f(x,y,z)=(x\vee y\vee z)\land (x\vee y\vee z)\land ({\overline {x}}\vee {\overline {y}}\vee z)\land ({\overline {x}}\vee {\overline {y}}\vee z)}
Розглянемо приклад функції, яка залежить від чотирьох змінних
f
(
x
,
y
,
z
,
g
)
=
(
1110001000001111
)
{\displaystyle f(x,y,z,g)=(1110001000001111)}
x
y
z
g
f
0
0
0
0
1
(
x
¯
∧
y
¯
∧
z
¯
∧
g
¯
)
{\displaystyle ({\overline {x}}\land {\overline {y}}\land {\overline {z}}\land {\overline {g}})}
0
0
0
1
1
(
x
¯
∧
y
¯
∧
z
¯
∧
g
)
{\displaystyle ({\overline {x}}\land {\overline {y}}\land {\overline {z}}\land g)}
0
0
1
0
1
(
x
¯
∧
y
¯
∧
z
∧
g
¯
)
{\displaystyle ({\overline {x}}\land {\overline {y}}\land z\land {\overline {g}})}
0
0
1
1
0
0
1
0
0
0
0
1
0
1
0
0
1
1
0
1
(
x
¯
∧
y
∧
z
∧
g
¯
)
{\displaystyle ({\overline {x}}\land y\land z\land {\overline {g}})}
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
(
x
∧
y
∧
z
¯
∧
g
¯
)
{\displaystyle (\ x\land y\land {\overline {z}}\land {\overline {g}})}
1
1
0
1
1
(
x
∧
y
∧
z
¯
∧
g
)
{\displaystyle (\ x\land y\land {\overline {z}}\land g)}
1
1
1
0
1
(
x
∧
y
∧
z
∧
g
¯
)
{\displaystyle (\ x\land y\land z\land {\overline {g}})}
1
1
1
1
1
(
x
∧
y
∧
z
∧
g
)
{\displaystyle (\ x\land y\land z\land g)}
Схема розв'язння функції з чотирма змінними така ж сама. Отже, ДНФ має такий вигляд:
f
(
x
,
y
,
z
,
g
)
=
(
x
¯
∧
y
¯
∧
z
¯
∧
g
¯
)
∨
(
x
¯
∧
y
¯
∧
z
¯
∧
g
)
∨
(
x
¯
∧
y
¯
∧
z
∧
g
¯
)
∨
(
x
¯
∧
y
∧
z
∧
g
¯
)
∨
(
x
∧
y
∧
z
¯
∧
g
¯
)
∨
(
x
∧
y
∧
z
¯
∧
g
)
∨
(
x
∧
y
∧
z
∧
g
¯
)
∨
(
x
∧
y
∧
z
∧
g
)
{\displaystyle f(x,y,z,g)=({\overline {x}}\land {\overline {y}}\land {\overline {z}}\land {\overline {g}})\vee ({\overline {x}}\land {\overline {y}}\land {\overline {z}}\land g)\vee ({\overline {x}}\land {\overline {y}}\land z\land {\overline {g}})\vee ({\overline {x}}\land y\land z\land {\overline {g}})\vee (\ x\land y\land {\overline {z}}\land {\overline {g}})\vee (\ x\land y\land {\overline {z}}\land g)\vee (\ x\land y\land z\land {\overline {g}})\vee (\ x\land y\land z\land g)}
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
(
x
∨
y
∨
z
¯
∨
g
¯
)
{\displaystyle (\ x\vee y\vee {\overline {z}}\vee {\overline {g}})}
0
1
0
0
0
(
x
∨
y
¯
∨
z
∨
g
¯
)
{\displaystyle (\ x\vee {\overline {y}}\vee z\vee {\overline {g}})}
0
1
0
1
0
(
x
∨
y
¯
∨
z
∨
g
¯
)
{\displaystyle (\ x\vee {\overline {y}}\vee z\vee {\overline {g}})}
0
1
1
0
1
0
1
1
1
0
(
x
∨
y
¯
∨
z
¯
∨
g
¯
)
{\displaystyle (\ x\vee {\overline {y}}\vee {\overline {z}}\vee {\overline {g}})}
1
0
0
0
0
(
x
¯
∨
y
∨
z
∨
g
)
{\displaystyle ({\overline {x}}\vee y\vee z\vee g)}
1
0
0
1
0
(
x
¯
∨
y
∨
z
∨
g
¯
)
{\displaystyle ({\overline {x}}\vee y\vee z\vee {\overline {g}})}
1
0
1
0
0
(
x
¯
∨
y
∨
z
¯
∨
g
)
{\displaystyle ({\overline {x}}\vee y\vee {\overline {z}}\vee g)}
1
0
1
1
0
(
x
¯
∨
y
∨
z
¯
∨
g
¯
)
{\displaystyle ({\overline {x}}\vee y\vee {\overline {z}}\vee {\overline {g}})}
1
1
0
0
1
1
1
0
1
1
1
1
1
0
1
1
1
1
1
1
За аналогією створюємо КНФ:
f
(
x
,
y
,
z
,
g
)
=
(
x
∨
y
∨
z
¯
∨
g
¯
)
∧
(
x
∨
y
¯
∨
z
∨
g
¯
)
∧
(
x
∨
y
¯
∨
z
∨
g
¯
)
∧
(
x
∨
y
¯
∨
z
¯
∨
g
¯
)
∧
(
x
¯
∨
y
∨
z
∨
g
)
∧
(
x
¯
∨
y
∨
z
∨
g
¯
)
∧
(
x
¯
∨
y
∨
z
¯
∨
g
)
∧
(
x
¯
∨
y
∨
z
¯
∨
g
¯
)
{\displaystyle f(x,y,z,g)=(\ x\vee y\vee {\overline {z}}\vee {\overline {g}})\land (\ x\vee {\overline {y}}\vee z\vee {\overline {g}})\land (\ x\vee {\overline {y}}\vee z\vee {\overline {g}})\land (\ x\vee {\overline {y}}\vee {\overline {z}}\vee {\overline {g}})\land ({\overline {x}}\vee y\vee z\vee g)\land ({\overline {x}}\vee y\vee z\vee {\overline {g}})\land ({\overline {x}}\vee y\vee {\overline {z}}\vee g)\land ({\overline {x}}\vee y\vee {\overline {z}}\vee {\overline {g}})}
Спростити отримані вирази можна за допомогою карт Карно .
Дивись також
ред.
