Здравствуйте! Необходимо доказать, что всякая функция $%f$% из множества $%S \setminus (T_0 \cup T_1 \cup M \cup L)$% образует базис в $%S$%.

задан 12 Окт '15 1:32

10|600 символов нужно символов осталось
0

По условию, $%f(0,...,0)=1$% и $%f(1,...,1)=0$% (здесь можно заметить, что оба этих условия равносильны, так как $%f$% самодвойственна). Очевидно, что $%f(x,...,x)=\bar{x}$%, то есть отрицание выразимо. Поэтому достаточно выразить через $%f$% функцию $%xy+xz+yz$%, так как она вместе с отрицанием образует базис класса $%S$% (это было в одной из предыдущих задач).

Для начала покажем, что через $%f$% можно выразить нелинейную функцию от трёх переменных. Поскольку $%f$% имеет нелинейный член, в него входит какая-то переменная, которую можно обозначить через $%x_1$%. Разложим полином Жегалкина по этой переменной: $%f(x_1,...,x_n)=x_1g(x_2,...,x_n)+h(x_2,...,x_n)$%. Заметим, что полином $%g(x_2,...,x_n)$% не является константой. В частности, найдётся такой набор, на котором функция $%g$% принимает значение, отличное от значения функции на наборе из нулей: $%g(\sigma_2,...,\sigma_n)\ne g(0,...,0)$%. Заменим теперь переменную $%x_1$% на $%x$%, а при $%2\le i\le n$% заменяем $%x_i$% на $%y$%, если $%\sigma_i=0$%, и на $%z$%, если $%\sigma_i=1$%. Получится некоторая функция $%\psi(x,y,z)$%, выразимая через $%f$%.

По построению, $%\psi(x,y,z)=xg_1(y,z)+h_1(y,z)$%, где $%g_1(0,0)=g(0,...,0)\ne g(\sigma_2,...,\sigma_n)=g_1(0,1)$%. Тем самым, $%g_1$% не является константой, и её полином Жегалкина имеет степень не ниже $%1$%, откуда следует, что $%\psi$% нелинейна. Поскольку всё происходит в пределах $%S$%, эта функция самодвойственна.

Запишем $%\psi$% в виде полинома Жегалкина: $%\psi(x,y,z)=axyz+b_1yz+b_2xz+b_3xy+c_1x+c_2y+c_3z+d$%. Двойственная функция равна $%\psi(x+1,y+1,z+1)+1$%, и она совпадает с $%\psi$%. Следовательно, $%\psi(x,y,z)$% равна $%a(x+1)(y+1)(z+1)+b_1(y+1)(z+1)+\cdots$%, где член $%yz$% далее уже не присутствует. Из сравнения коэффициентов при $%yz$% следует, что $%a=0$%. Таким образом $%\psi(x,y,z)=b_1(y+1)(z+1)+b_2(x+1)(z+1)+b_3(x+1)(y+1)+c_1(x+1)+\cdots$%, где $%x$% далее не встречается.Сравнивая коэффициенты при $%x$%, видим, что $%b_2=b_3$%. Из соображений симметрии, все $%b_i$% попарно равны. Они не могут быть равны нулю ввиду нелинейности функции, поэтому все они равны единице.

Мы получили, что $%\psi(x,y,z)=xy+xz+yz+c_1x+c_2y+c_3z+d$%. Сравнивая значения на нулях и на единицах, приходим к выводу, что $%c_1+c_2+c_3=0$%. Если все три коэффициента нулевые, то мы имеем дело либо с $%xy+xz+yz$%, либо с её отрицанием. В последнем случае функцию надо подставить в отрицание. Если же один коэффициент равен нулю, а два другие равны единице, то с точностью до симметрии $%\psi(x,y,z)=xy+xz+yz+x+y+d$%. Заменяя $%z$% её отрицанием, выражаем $%\psi(x,y,z+1)=xy+xz+x+yz+y+x+y+d=xy+xz+yz+d$%, и всё сводится к предыдущему случаю.

ссылка

отвечен 12 Окт '15 12:20

10|600 символов нужно символов осталось
Ваш ответ

Если вы не нашли ответ, задайте вопрос.

Здравствуйте

Математика - это совместно редактируемый форум вопросов и ответов для начинающих и опытных математиков, с особенным акцентом на компьютерные науки.

Присоединяйтесь!

отмечен:

×1,249
×146

задан
12 Окт '15 1:32

показан
367 раз

обновлен
12 Окт '15 12:20

Отслеживать вопрос

по почте:

Зарегистрировавшись, вы сможете подписаться на любые обновления

по RSS:

Ответы

Ответы и Комментарии

Дизайн сайта/логотип © «Сеть Знаний». Контент распространяется под лицензией cc by-sa 3.0 с обязательным указанием авторства.
Рейтинг@Mail.ru