Задачка что ни на есть крепкая, особенно для первокурсника. Прошу помочь её решить. И можете дать примерные рекомендации по решению подобных задач, множества из замкнутых классов можно разные составлять?

Условие: Найти мощность множества $%A=L \setminus (T_{0} \bigtriangleup T_{1})(n)$%. Выписать явно все функции из $%A$% при $%n=6$%, входящие в $%(M \wedge S)$%

задан 8 Июн '14 14:34

изменен 8 Июн '14 14:35

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

Рассмотрим линейную функцию от $%n$% переменных. Она имеет вид $%f(x_1,\ldots,x_n)=a_0+a_1x_1+\cdots+a_nx_n$%. Нас интересуют те функции, которые не принадлежат симметрической разности классов $%T_0$% и $%T_1$%. Это в точности функции, которые либо принадлежат обоим этим классам, либо обоим не принадлежат.

Если $%f\in T_0$%, то $%a_0=0$% (и наоборот). При этом $%f(1,\ldots,1)=a_1+\cdots+a_n=1$% при условии, что $%f\in T_1$%.

Если $%f\notin T_0$%, то $%a_0=1$%. В этом случае $%f(1,\ldots,1)=1+a_1+\cdots+a_n=0$% при условии, что $%f\notin T_1$%. Это снова означает, что $%a_1+\cdots+a_n=1$%.

Таким образом, коэффициенты $%a_0$%, ... , $%a_{n-1}$% выбираются произвольно, а последний коэффициент задаётся формулой $%a_n=1+a_1+\cdots+a_{n-1}$%. Ясно, что при $%n\ge1$% таких функций будет в точности $%2^n$%, так как они определяются $%n$% независимыми параметрами, каждый из которых выбирается двумя способами. (Заметим, что в "вырожденном" случае, когда $%n=0$%, имеются только две константы $%0$% и $%1$%, ни одна из которых нам не подходит.)

Все рассмотренные нами функции являются самодвойственными, так как $%f(x_1+1,\ldots,x_n+1)=a_0+a_1(x_1+1)+\cdots+a_n(x_n+1)=f(x_1,\ldots,x_n)+1$% за счёт равенства $%a_1+\cdots+a_n=1$% (на противоположных наборах функция принимает противоположные значения).

Далее, для монотонности функции необходимо, чтобы не нашлось двух коэффициентов при переменных $%x_1,\ldots,x_n$%, равных единице. Это следует из того, что ни одна из функций $%x_i+x_j$%, $%1+x_i+x_j$% (где $%i < j$%) не монотонна. Таким образом, остаются только функции вида $%a_0+x_i$%, и тогда ясно, что $%a_0=0$%, поскольку отрицание не монотонно. Итогом будет 6 тождественных функций: $%x_1$%, ... , $%x_6$%.

Применения определения классов здесь вполне достаточно; никаких дополнительных сведений не нужно. Конечно, надо также знать правило суммы и правило произведения из комбинаторики, но это просто.

ссылка

отвечен 8 Июн '14 15:01

Спасибо, очень интересное решение.

(9 Июн '14 9:34) XAegis

@falcao, а не посоветуете хороший задачник (исключая Сапоженко и Гаврилова)

(9 Июн '14 18:36) XAegis
1

@XAegis: я не очень хорошо знаю издаваемую литературу, потому что сейчас очень много всего появляется, и за всем не уследишь. И сам "охват" материала может быть разным. Но мне известна книжка: С.Г.Гиндикин, "Алгебра логики в задачах". Её имеет смысл посмотреть на предмет того, подойдёт ли она Вам. Вот ссылка.

(9 Июн '14 18:50) falcao
10|600 символов нужно символов осталось
Ваш ответ

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

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

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

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

отмечен:

×1,699

задан
8 Июн '14 14:34

показан
1168 раз

обновлен
9 Июн '14 18:50

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

по почте:

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

по RSS:

Ответы

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

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