2014 dxdy logo

Научный форум dxdy

Математика, Физика, Computer Science, Machine Learning, LaTeX, Механика и Техника, Химия,
Биология и Медицина, Экономика и Финансовая Математика, Гуманитарные науки




 
 Является ли булева функция - шефферовой
Сообщение22.05.2007, 18:26 
Помогите пожалуйста!
Мне надо определить является ли некая функция шефферовой, для этого удобно сначало решить вспомогательную задачу: Для того, чтобы функция являлась базисом в \[P_2\] (шефферовой) достаточно проверить, что она не принадлежит только классам \[T_0,T_1,S\], а не всем т.е. \[T_0,T_1,S,L,M\]
Предлагается следующее доказательство в коспекте лекций:
1) Дествительно, если \[f \notin T_0,f \notin T_1,f \notin S \] тогда \[f(0, \ldots ,0) = 1,f(1, \ldots ,1) = 0, \Rightarrow f \notin M\].
2) Предположим теперь, что \[f \in L\] . Тогда из того, что \[f(0, \ldots ,0) = 1\]следует, что полином функции \[f\] содержит свободный член
3) из того, что \[f(1, \ldots ,1) = 0\] следует, что полином функции \[f\]содержит нечетное число переменных.
4) Из 2) и 3) следует, что для любого набора\[\left( {x_1 ,...,x_n } \right)\]выполнено \[\overline {f\left( {x_1 ,...,x_n } \right)}  = f\left( {\overline {x_1 } ,...,\overline {x_n } } \right)\], т.е.\[f \in S\] получили противоречие.

Я никак не могу понять пункт 3) и 4).

 
 
 
 
Сообщение22.05.2007, 20:25 
Аватара пользователя
Городецкий Павел писал(а):
2) Предположим теперь, что \[f \in L\] . Тогда из того, что \[f(0, \ldots ,0) = 1\]следует, что полином функции \[f\] содержит свободный член
в п. 2) установлено (и Вы понимаете это), что полином Жегалкина имеет ровно одно слагаемое 1, а остальные
его слагаемые - это переменные, но, если складывать единицы по модулю 2, то сумма будет равна нулю только для четного числа 1, поэтому, с учетом этой приблудной 1, самих переменных должно быть нечетное число.
Городецкий Павел писал(а):
4) Из 2) и 3) следует, что для любого набора\[\left( {x_1 ,...,x_n } \right)\]выполнено \[\overline {f\left( {x_1 ,...,x_n } \right)} = f\left( {\overline {x_1 } ,...,\overline {x_n } } \right)\], т.е.\[f \in S\] получили противоречие.
если теперь обратить в полиноме все переменные, то можно обращать их не все сразу, а по одной штуке, тогда каждое обращение обратит и функцию, а, так как переменных - нечетное число, то в результате всех обращений значение функции заменится на противоположное, если его еще раз обратить, то все встанет на место, поэтому получается самодвойственная ф-ция. Все.

 
 
 
 
Сообщение22.05.2007, 22:33 
Понял :) оказалось просто
СПАСИБО

 
 
 [ Сообщений: 3 ] 


Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group