Критерий полноты { теорема Поста о функциональной полноте }
Теорема Поста: система функций из $P_2$ функционально полна $\Longleftrightarrow$ система содержит:
- Функцию, не сохраняющую константу $0$.
- Функцию, не сохраняющую константу $1$.
- Несамодвойственную функцию
- Немонотонную функцию
- Нелинейную функцию
Доказательство $\Rightarrow$ { прямое } : Пусть система функций $F$ из $P_2$ полна { в $P_2$), допустим, что в системе $F$ нет одной из указанных функций, например немонотонной. Тогда все функции в $F$ монотонны, т.к. класс монотонных функций замкнут относительно суперпозиции, то мы не можем получить ни одной немонотонной функции. Потому система $F$ полной в $P_2$ не является. Противоречие с полнотой $F$. Следовательно, система $F$ содержит все $5$ указанных функций.
Доказательство $\Leftarrow$ { обратное } : Пусть $F$ содержит все $5$ функций: $f_1(x_1, x_2,...,x_n)$ – не сохраняет константу $0$, $f_2(x_1, x_2,...,x_n)$ – не сохраняет константу $1$, $f_3(x_1, x_2,...,x_n)$ – несамодвойственная функция, $f_4(x_1, x_2,...,x_n)$ – немонотонная функция, $f_5(x_1, x_2,...,x_n)$ – нелинейная функция.
Покажем, что суперпозицией функций системы $F$ можно получить полную систему $G { xy,\bar { x } } $
-
Пусть $g(x) = f_1(x_1, x_2,...,x_n)$, тогда $g(0) = f(0,...,0) = 1$ далее возможны два случая: А } $g(1) = 1 \Rightarrow g(x) \equiv 1$. Функция $h(x) = f_2(g_1(x),g_2(x),...,g_n(x)) = f_2(1,..,1) = 0$. Т.е. $h(x) \equiv 0$ получили константы $0$ и $1$. Б } $g(1) =0 \Rightarrow g(x) = \bar { x } $. По лемме о несамодвойственной функции суперпозицией над $\ { f_3,\bar { x } \ } $ можно получить одну из констант, например $0$. $f_1(0,...,0) = 1$ есть другая константа. В обоих случаях получили обе константы.
-
По лемме о немонотонной функции суперпозицией над $\ { f_4,0,1\ } $ можно получить отрицание $х$.
-
По лемме о нелинейной функции суперпозицией над $\ { f_5,1,\bar { x } \ } $ можно получить конъюнкцию.
Функции системы $G$ найдены $\ { x\wedge y, \bar { x } \ } $ суперпозицией функций над системой $F$. Следовательно, $F$ – есть полная система в $P_2$. чтд.
Далее:
Механические приложения двойного интеграла
Механические и физические приложения поверхностного интеграла первого рода
Класс $L$. Теорема о замкнyтости класса $L$
Класс Te . Теорема о замкнутости Te
Замена переменных в двойном интеграле. Двойной интеграл в полярных координатах
Дифференциальные характеристики векторного поля
Замыкание. Свойства замыкания. Теорема о сведении к заведомо полной системе
Вычисление криволинейного интеграла второго рода. Примеры.
Булевы функции от $n$ переменных
Логические операции над высказываниями
Замена переменных в тройном интеграле
Вычисление площади поверхности
Критерий полноты {формулировка}. Лемма о несамодвойственной функции
Инвариантное определение дивергенции
Условия независимости криволинейного интеграла от пути интегрирования
Огравление $\Rightarrow $
Комментарии ()