Изменения

КНФ

4872 байта добавлено, 17:50, 24 декабря 2017

Исправлена СКНФ для медианы от 5 аргументов

{{Определение

|definition =

'''Простой дизъюнкцией ''' (англ. ''inclusive disjunction'') или '''дизъюнктом ''' (англ. ''disjunct'') называется дизъюнкция одной или нескольких переменных или их отрицаний, причём каждая переменная встречается не более одного раза.

}}

Простая дизъюнкция

}}

Пример КНФ:

== СКНФ ==

|proof =

Поскольку инверсия функции <tex>\neg{f}(\vec x)</tex> равна единице на тех наборах, на которых <tex>f(\vec x)</tex> равна нулю, то СДНФ для <tex>\neg{f}(\vec x)</tex> можно записать следующим образом:

<tex>\neg{f}(\vec x) = \bigvee\limits_{f(x^{\sigma_{1}}, x^{\sigma_{2}}, ~~...~~ \ldots ,x^{\sigma_{n}}) = 0} (x_{1}^{\sigma_{1}} \wedge x_{2}^{\sigma_{2}} \wedge ~~...~~ \ldots \wedge x_{n}^{\sigma_{n}}) </tex>, где <tex> \sigma_{i} </tex> обозначает наличие или отсутствие отрицание при <tex> x_{i} </tex>

Найдём инверсию левой и правой части выражения:

<tex> f(\vec x) = \neg ({\bigvee\limits_{f(x^{\sigma_{1}}, x^{\sigma_{2}}, ~~...~~ \ldots ,x^{\sigma_{n}}) = 0} (x_{1}^{\sigma_{1}} \wedge x_{2}^{\sigma_{2}} \wedge ~~...~~ \ldots \wedge x_{n}^{\sigma_{n}})}) </tex>

Применяя дважды к полученному в правой части выражению правило де Моргана, получаем:

<tex> f(\vec x) = \bigwedge\limits_{f(x^{\sigma_{1}}, x^{\sigma_{2}}, ~~...~~ \ldots ,x^{\sigma_{n}}) = 0} (\neg{x_{1}^{\sigma_{1}}} \vee \neg{x_{2}^{\sigma_{2}}} \vee ~~...~~ \ldots \vee \neg{x_{n}^{\sigma_{n}}} ) </tex>

Последнее выражение и является СКНФ. Так как СКНФ получена из СДНФ, которая может быть посторена для любой функции, не равной тождественному нулю, то теорема доказана.

== Пример построения СКНФ для медианы==

=== Построение СКНФ для медианы от трех аргументов ===

1. В таблице истинности отмечаем те наборы переменных, на которых значение функции равно <tex>0</tex>.

|+

|-align="center" bgcolor=#EEEEFF

| '''x ''' || '''y ''' || '''z ''' || <tex> \langle x,y,z \rangle </tex>

|-align="center" bgcolor=#F0F0F0

! 0 || 0 || 0 || 0

|+

|-align="center" bgcolor=#EEEEFF

| '''x ''' || '''y ''' || '''z ''' || <tex> \langle x,y,z \rangle </tex> ||

|-align="center" bgcolor=#F0F0F0

! 0 || 0 || 0 || 0 || <tex>( x \lor y \lor z)</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> ||