Критерий полноты { формулировка } . Лемма о нелинейной функции
Формулировка. Система булевых функций $F$ является полной тогда и только тогда, когда она целиком не принадлежит ни одному из замкнутых классов $~S,M,L,T_0,T_1$.
- монотонные функции { функция монотонно не убывает по каждому из своих аргументов } ;
- функции, сохраняющие нуль { функция от нуля даёт ноль } ;
- функции, сохраняющие единицу { функция от единицы даёт единицу } ;
- линейные функции { функция представима многочленом, в котором каждый член состоит из одной переменной } ;
- самодвойственные функции { функция двойственна сама себе } .
Лемма: Суперпозицией нелинейной функции, отрицания и константы $1$ можно получить конъюнкцию.
Доказательство: Пусть $f(x_1, x_2 , ..., x_n)$ — нелинейная функция, тогда полином Жигалкина для нее содержит слагаемое, в котором присутствует произведение каких-то переменных $x_i*x_j$. Пусть для простоты это будет произведение $x_1x_2$. Произведя группировку слагаемых в полиноме Жегалкина для $f$ относительно $x_1x_2, x_1, x_2$, функцию $f$ представим в виде $f(x_1,..., x_n)=x_1*x_2*h_0(x_3,...,x_n)+$ { собрали все слагаемые с $x_1*x_2$ и вынесли $x_1*x_2$ за скобки. В скобках осталась сумма $h_0(x_3,...,x_n)$, в которой переменных $x_1, x_2$ нет } $+ x_1h_1(x_3,..., x_n) + x_2h_2(x_3,..., x_n) + h_3(x_3,..., x_n)$
Функция $h_0(x_3,..., x_n) \neq 0$, в противном случае многочлен Жигалкина слагаемых с произведением $x_1x_2$ не имеет, тогда существует набор $(a_3,..., a_n)$ из $0$ и $1$, для которого $h_0(a_3,..., a_n) = 1$. Пусть на этом наборе $h_1(a_3,..., a_n)=a; h_2(a_3,..., a_n)=b; h_3(a_3,..., a_n)=c$. Тогда функция $g(x_1,x_2)= f(x_1,x_2,a_3,..., a_n)=x_1*x_2+a*x_1+b*x_2+c$. Построим функцию $h(x_1,x_2) = g(x_1+bx_2+a) =(x_1+b)$ $(x_2+a)+a(x_1+b)+b(x_2+a)+c = x_1*x_2+a*x_1+b*x_2+a*b+a*x_1+a*b+b*x_2+a*b+c$ $=_1*x_2+a*b+c=x_1*x_2+d, d=a*b+c$ Если $d=0$, то $h(x_1,x_2)=x_1*x_2$, конъюнкция получена. Если $d=1$, то $h(x_1,x_2)=x_1*x_2+1 \Rightarrow x_1*x_2=\bar { h } (x_1,x_2)$, что и требовалось доказать.
Далее:
СКНФ. Теорема о представлении в виде СКНФ. Построение СКНФ по таблице
Односторонние и двусторонние поверхности. Ориентация поверхности
Определение двойного интеграла
Свойства потока векторного поля
Класс $T_1$. Теорема о замкнутости класса $T_1$
Замыкание. Свойства замыкания. Теорема о сведении к заведомо полной системе
Условия независимости криволинейного интеграла от пути интегрирования
Поверхностный интеграл второго рода и его свойства
Определение криволинейного интеграла второго рода
Специальные векторные поля
Класс Te . Теорема о замкнутости Te
Вычисление криволинейного интеграла второго рода. Примеры.
Вычисление тройного интеграла. Теорема о переходе от тройного интеграла к повторному
Скалярное поле, производная по направлению, градиент
Класс $L$. Теорема о замкнyтости класса $L$
Огравление $\Rightarrow $
Комментарии ()