Изменения

Перейти к: навигация, поиск

КНФ

3600 байт добавлено, 17:50, 24 декабря 2017
Исправлена СКНФ для медианы от 5 аргументов
== Пример построения СКНФ для медианы==
=== Построение СКНФ для медианы от трех аргументов ===
1. В таблице истинности отмечаем те наборы переменных, на которых значение функции равно <tex>0</tex>.
<tex> \langle x,y,z \rangle = ( x \lor y \lor z) \land (\neg{x} \lor y \lor z) \land (x \lor \neg{y} \lor z) \land ( x \lor y \lor \neg{z})</tex>
 
=== Построение СКНФ для медианы от пяти аргументов ===
 
{| class="wikitable" style="width:16cm" border=1
|+
|-align="center" bgcolor=#EEEEFF
|<tex> x_1 </tex>||<tex> x_2 </tex>||<tex> x_3 </tex>||<tex>x_4</tex>||<tex> x_5 </tex>||<tex> \langle x_1, x_2, x_3, x_4, x_5 \rangle </tex> ||
|-align="center" bgcolor=#FFFFFF
! 0 || 0 || 0 || 0 || 0 || 0 || <tex>(x_1 \lor x_2 \lor x_3 \lor x_4 \lor x_5)</tex>
|-align="center" bgcolor=#FFFFFF
! 0 || 0 || 0 || 0 || 1 || 0 || <tex>(x_1 \lor x_2 \lor x_3 \lor x_4 \lor \neg {x_5})</tex>
|-align="center" bgcolor=#FFFFFF
! 0 || 0 || 0 || 1 || 0 || 0 || <tex>(x_1 \lor x_2 \lor x_3 \lor \neg {x_4} \lor x_5)</tex>
|-align="center" bgcolor=#FFFFFF
! 0 || 0 || 0 || 1 || 1 || 0 || <tex>(x_1 \lor x_2 \lor x_3 \lor \neg {x_4} \lor \neg {x_5})</tex>
|-align="center" bgcolor=#FFFFFF
! 0 || 0 || 1 || 0 || 0 || 0 || <tex>(x_1 \lor x_2 \lor \neg {x_3} \lor x_4 \lor x_5)</tex>
|-align="center" bgcolor=#FFFFFF
! 0 || 0 || 1 || 0 || 1 || 0 || <tex>(x_1 \lor x_2 \lor \neg {x_3} \lor x_4 \lor \neg {x_5})</tex>
|-align="center" bgcolor=#FFFFFF
! 0 || 0 || 1 || 1 || 0 || 0 || <tex>(x_1 \lor x_2 \lor \neg {x_3} \lor \neg {x_4} \lor x_5)</tex>
|-align="center" bgcolor=#FFFFFF
| 0 || 0 || 1 || 1 || 1 || 1 ||
|-align="center" bgcolor=#FFFFFF
! 0 || 1 || 0 || 0 || 0 || 0 || <tex>(x_1 \lor \neg {x_2} \lor x_3 \lor x_4 \lor x_5)</tex>
|-align="center" bgcolor=#FFFFFF
! 0 || 1 || 0 || 0 || 1 || 0 || <tex>(x_1 \lor \neg {x_2} \lor x_3 \lor x_4 \lor \neg {x_5})</tex>
|-align="center" bgcolor=#FFFFFF
! 0 || 1 || 0 || 1 || 0 || 0 || <tex>(x_1 \lor \neg {x_2} \lor x_3 \lor \neg {x_4} \lor x_5)</tex>
|-align="center" bgcolor=#FFFFFF
| 0 || 1 || 0 || 1 || 1 || 1 ||
|-align="center" bgcolor=#FFFFFF
! 0 || 1 || 1 || 0 || 0 || 0 || <tex>(x_1 \lor \neg {x_2} \lor \neg {x_3} \lor x_4 \lor x_5)</tex>
|-align="center" bgcolor=#FFFFFF
| 0 || 1 || 1 || 0 || 1 || 1 ||
|-align="center" bgcolor=#FFFFFF
| 0 || 1 || 1 || 1 || 0 || 1 ||
|-align="center" bgcolor=#FFFFFF
| 0 || 1 || 1 || 1 || 1 || 1 ||
|-align="center" bgcolor=#FFFFFF
! 1 || 0 || 0 || 0 || 0 || 0 || <tex>(\neg {x_1} \lor x_2 \lor x_3 \lor x_4 \lor x_5)</tex>
|-align="center" bgcolor=#FFFFFF
! 1 || 0 || 0 || 0 || 1 || 0 || <tex>(\neg {x_1} \lor x_2 \lor x_3 \lor x_4 \lor \neg {x_5})</tex>
|-align="center" bgcolor=#FFFFFF
! 1 || 0 || 0 || 1 || 0 || 0 || <tex>(\neg {x_1} \lor x_2 \lor x_3 \lor \neg {x_4} \lor x_5)</tex>
|-align="center" bgcolor=#FFFFFF
| 1 || 0 || 0 || 1 || 1 || 1 ||
|-align="center" bgcolor=#FFFFFF
! 1 || 0 || 1 || 0 || 0 || 0 || <tex>(\neg {x_1} \lor x_2 \lor \neg {x_3} \lor x_4 \lor x_5)</tex>
|-align="center" bgcolor=#FFFFFF
| 1 || 0 || 1 || 0 || 1 || 1 ||
|-align="center" bgcolor=#FFFFFF
| 1 || 0 || 1 || 1 || 0 || 1 ||
|-align="center" bgcolor=#FFFFFF
| 1 || 0 || 1 || 1 || 1 || 1 ||
|-align="center" bgcolor=#FFFFFF
! 1 || 1 || 0 || 0 || 0 || 0 || <tex>(\neg {x_1} \lor \neg {x_2} \lor x_3 \lor x_4 \lor x_5)</tex>
|-align="center" bgcolor=#FFFFFF
| 1 || 1 || 0 || 0 || 1 || 1 ||
|-align="center" bgcolor=#FFFFFF
| 1 || 1 || 0 || 1 || 0 || 1 ||
|-align="center" bgcolor=#FFFFFF
| 1 || 1 || 0 || 1 || 1 || 1 ||
|-align="center" bgcolor=#FFFFFF
| 1 || 1 || 1 || 0 || 0 || 1 ||
|-align="center" bgcolor=#FFFFFF
| 1 || 1 || 1 || 0 || 1 || 1 ||
|-align="center" bgcolor=#FFFFFF
| 1 || 1 || 1 || 1 || 0 || 1 ||
|-align="center" bgcolor=#FFFFFF
| 1 || 1 || 1 || 1 || 1 || 1 ||
|}
 
<tex> \langle x_1, x_2, x_3, x_4, x_5 \rangle = (x_1 \lor x_2 \lor x_3 \lor x_4 \lor x_5) \land (x_1 \lor x_2 \lor x_3 \lor x_4 \lor \overline {x_5}) \land \\ (x_1 \lor x_2 \lor x_3 \lor \overline {x_4} \lor x_5) \land (x_1 \lor x_2 \lor x_3 \lor \overline {x_4} \lor \overline {x_5}) \land (x_1 \lor x_2 \lor \overline {x_3} \lor x_4 \lor x_5) \land \\ (x_1 \lor x_2 \lor \overline {x_3} \lor x_4 \lor \overline {x_5}) \land (x_1 \lor x_2 \lor \overline {x_3} \lor \overline {x_4} \lor x_5) \land (x_1 \lor \overline {x_2} \lor x_3 \lor x_4 \lor x_5) \land \\ (x_1 \lor \overline {x_2} \lor x_3 \lor x_4 \lor \overline {x_5}) \land (x_1 \lor \overline {x_2} \lor x_3 \lor \overline {x_4} \lor x_5) \land (x_1 \lor \overline {x_2} \lor \overline {x_3} \lor x_4 \lor x_5) \land (\overline {x_1} \lor x_2 \lor x_3 \lor x_4 \lor x_5) \land (\overline {x_1} \lor x_2 \lor x_3 \lor x_4 \lor \overline {x_5}) \land (\overline {x_1} \lor x_2 \lor x_3 \lor \overline {x_4} \lor x_5) \land (\overline {x_1} \lor x_2 \lor \overline {x_3} \lor x_4 \lor x_5) \land (\overline {x_1} \lor \overline {x_2} \lor x_3 \lor x_4 \lor x_5) </tex>
==Примеры СКНФ для некоторых функций==
Исключающее или: <tex> x \oplus y \oplus z = (\neg {x} \lor \neg {y} \lor z) \land (\neg {x} \lor y \lor \neg {z}) \land (x \lor \neg {y} \lor \neg {z}) \land (x \lor y \lor z)</tex>
Медиана 5 аргументов:== См. также == * [[Специальные формы КНФ]]* [[ДНФ]]
<tex> \langle x_1, x_2, x_3, x_4, x_5 \rangle = (x_1 \lor x_2 \lor x_3 \lor x_4 \lor x_5) \land (\overline{x_1} \lor x_2 \lor x_3 \lor x_4 \lor x_5) \land \\ (x_1 \lor \overline{x_2} \lor x_3 \lor x_4 \lor x_5) \land (\overline{x_1} \lor \overline{x_2} \lor x_3 \lor x_4 \lor x_5) \land (x_1 \lor x_2 \lor \overline{x_3} \lor x_4 \lor x_5) \land \\ (\overline{x_1} \lor x_2 \lor \overline{x_3} \lor x_4 \lor x_5) \land (x_1 \lor \overline{x_2} \lor \overline{x_3} \lor x_4 \lor x_5) \land (x_1 \lor x_2 \lor x_3 \lor \overline{x_4} \lor x_5) \land \\ (\overline{x_1} \lor x_2 \lor x_3 \lor \overline{x_4} \lor x_5) \land (x_1 \lor \overline{x_2} \lor x_3 \lor \overline{x_4} \lor x_5) \land (x_1 \lor x_2 \lor \overline{x_3} \lor \overline{x_4} \lor x_5) \land (x_1 \lor x_2 \lor x_3 \lor x_4 \lor \overline{x_5}) \land (\overline{x_1} \lor x_2 \lor x_3 \lor x_4 \lor \overline{x_5}) \land (x_1 \lor \overline{x_2} \lor x_3 \lor x_4 \lor \overline{x_5}) \land (x_1 \lor x_2 \lor \overline{x_3} \lor x_4 \lor \overline{x_5}) \land (x_1 \lor x_2 \lor x_3 \lor \overline{x_4} \lor \overline{x_5}) </tex>
== Источники информации ==
* [http://ru.wikipedia.org/wiki/%D0%A1%D0%9A%D0%9D%D0%A4 Википедия {{---}} СКНФ]
Haposiwe
17
правок
Источник — «http://neerc.ifmo.ru/wiki/index.php?title=Служебная:Сравнение_версий/62910...62997»

Навигация