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

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

Розглянемо розв'язання цієї задачі на прикладі. Дана функція $f(x,y,z)=(00111100)$. Спочатку будуємо таблицю істинності, а значення функції підставляємо в тому ж порядку, в я кому вона і дана.

x	y	z	f
0	0	0	0
0	0	1	0
0	1	0	1 $({\overline {x}}\land y\land {\overline {z}})$ - дає 1
0	1	1	1 $({\overline {x}}\land y\land z)$ - дає 1
1	0	0	1 $(\ x\land {\overline {y}}\land {\overline {z}})$ - дає 1
1	0	1	1 $(\ x\land {\overline {y}}\land z)$ - дає 1
1	1	0	0
1	1	1	0

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

$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\vee y\vee z)$ - дає 0
0	0	1	0 $(x\vee y\vee {\overline {z}})$ - дає 0
0	1	0	1
0	1	1	1
1	0	0	1
1	0	1	1
1	1	0	0 $({\overline {x}}\vee {\overline {y}}\vee z)$ - дає 0
1	1	1	0 $({\overline {x}}\vee {\overline {y}}\vee {\overline {z}})$ - дає 0

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

$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)$. Будуємо таблицю істинності.

x	y	z	g	f
0	0	0	0	1 $({\overline {x}}\land {\overline {y}}\land {\overline {z}}\land {\overline {g}})$ - дає 1
0	0	0	1	1 $({\overline {x}}\land {\overline {y}}\land {\overline {z}}\land g)$ - дає 1
0	0	1	0	1 $({\overline {x}}\land {\overline {y}}\land z\land {\overline {g}})$ - дає 1
0	0	1	1	0
0	1	0	0	0
0	1	0	1	0
0	1	1	0	1 $({\overline {x}}\land y\land z\land {\overline {g}})$ - дає 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 $(\ x\land y\land {\overline {z}}\land {\overline {g}})$ - дає 1
1	1	0	1	1 $(\ x\land y\land {\overline {z}}\land g)$ - дає 1
1	1	1	0	1 $(\ x\land y\land z\land {\overline {g}})$ - дає 1
1	1	1	1	1 $(\ x\land y\land z\land g)$ - дає 1

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

$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\vee y\vee {\overline {z}}\vee {\overline {g}})$ - дає 0
0	1	0	0	0 $(\ x\vee {\overline {y}}\vee z\vee {\overline {g}})$ - дає 0
0	1	0	1	0 $(\ x\vee {\overline {y}}\vee z\vee {\overline {g}})$ - дає 0
0	1	1	0	1
0	1	1	1	0 $(\ x\vee {\overline {y}}\vee {\overline {z}}\vee {\overline {g}})$ - дає 0
1	0	0	0	0 $({\overline {x}}\vee y\vee z\vee g)$ - дає 0
1	0	0	1	0 $({\overline {x}}\vee y\vee z\vee {\overline {g}})$ - дає 0
1	0	1	0	0 $({\overline {x}}\vee y\vee {\overline {z}}\vee g)$ - дає 0
1	0	1	1	0 $({\overline {x}}\vee y\vee {\overline {z}}\vee {\overline {g}})$ - дає 0
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\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}})$

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

Дивись також

• Досконала диз'юнктивна нормальна форма
• Досконала кон'юнктивна нормальна форма
• Карта Карно