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

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

Розглянемо розв'язання цієї задачі на прикладі. Дана функція $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}) \lor (\overline{x} \land y \land z) \lor (x \land \overline{y} \land \overline{z}) \lor (x \land \overline{y} \land z)

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

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

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

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

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

Дивись також

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

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

Дивись також

Навігаційне меню

Пошук