Здравствуйте! Необходимо найти, сколько функций от $%n$% переменных содержит множество $%L \cap S$% ($%L$% - линейные функции, $%S$% - самодвойственные функции), а также необходимо найти базис.

задан 24 Сен '15 21:46

изменен 25 Сен '15 10:02

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

Линейная функция от $%n$% переменных имеет вид $%f(x_1,\ldots,x_n)=a+a_1x_1+\cdots+a_nx_n$%. Чтобы она была самодвойственной, необходимо и достаточно, чтобы на противоположных наборах функция принимала противоположные значения. Понятно, что $%f(x_1+1,\ldots,x_n+1)=a+a_1x_1+\cdots+a_nx_n+(a_1+\cdots+a_n)$%. Таким образом, $%a_1+\cdots+a_n=1$%. При $%n=0$% таких функций нет (константы не самодвойственны). При $%n\ge1$% функций будет $%2^n$%, то есть половина от общего количества линейных. Значения для $%a$%, $%a_1$%, ... , $%a_{n-1}$% выбираются свободно; $%a_n=1+a_1+\cdots+a_{n-1}$%.

Базисом класса $%L\cap S$% будет система функций $%\{\bar{x},x+y+z\}$%. Обе они принадлежат пересечению классов. Первая функция не выражается через вторую, так как вторая сохраняет ноль, а первая не сохраняет. Вторая функция не выражается через отрицание, так как класс функций, выражающихся через отрицание, состоит из отрицания и тождественной функции. Значит, эта система базисная.

Далее, любая функция из $%L\cap S$% через указанные две выражается. Для тождественной функции это очевидно. Далее по индукции показываем, что сумма нечётного числа переменных в количестве $%\ge3$% выражается. База очевидна; шаг состоит в подстановке в $%x+y+z$% предыдущей функции вместо $%x$% с новыми переменными $%y$%, $%z$%. Это даёт все функции с $%a=0$%. Добавляя отрицание, охватываем случай $%a=1$%.

ссылка

отвечен 24 Сен '15 22:04

@falcao: Я что-то не совсем поняла доказательство, что любая функция из $%L \cap S$% выражается через этот базис - а случай четного числа переменных?

(25 Сен '15 17:38) Math_2012

@falcao: Число функций будет равно $%2^n$% и для четного, и для нечетного $%n$%?

(25 Сен '15 18:59) Math_2012

@falcao: Почему в базисе именно $%x + y + z$%, а не $%x + y$%? Нужна такая, чтобы сохраняла $%0$%?

(25 Сен '15 19:06) Math_2012

@Anna_2012: мы описываем линейные самодвойственные функции. У меня в начале написано, что для самодвойственности необходимо условие $%a_1+\cdots+a_n=1$%, которое в точности означает, что число переменных, входящих в запись полинома, нечётно. Функция $%x+y$% не рассматривается, так как она не самодвойственна. Сохранение нуля как раз не требуется, потому что $%1+x+y+z$% будет самодвойственной, как и $%x+y+z$%.

Число функций от $%n$% переменных в $%L\cap S$% равно $%2^n$% для всех $%n$% (как чётных, так и нечётных) кроме случая $%n=0$%, когда таких функций нет.

(25 Сен '15 20:51) falcao
10|600 символов нужно символов осталось
Ваш ответ

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

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

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

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

отмечен:

×1,333
×234
×150

задан
24 Сен '15 21:46

показан
787 раз

обновлен
25 Сен '15 20:51

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

по почте:

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

по RSS:

Ответы

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

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