Задачка по дискретке на замкнутость класса

[Turegg]

Помогите доказать задачку по дискретке.

Пусть $K=\{f: f(a_1,a_2,...,a_n)=0, \text {если} \ a_1+a_2+...+a_n=0 \ (\bmod\ 2) \}$
Докажите, что класс $K$ замкнут.

Если судить по букве класса, то, возможно, это класс конъюнкций $K$ (написано в Википедии).
Если же пробовать подбирать один из других классов ($T_0,T_1, L,S,M$), то ни один из них не подходит. Или же я ошибаюсь? Для этих классов доказать замкнутость могу. Не могу понять, что этот класс $K$ из себя представляет.

[provincialka]

Надо так понимать, что для остальных наборов аргументов значение функции равно 1? Тогда это просто сумма по модулю 2. Т.е. остаток от деления суммы на 2. (обозначим его через $res$

Подставим значение функции в $f$ в качестве аргумента. Получим:
$f(f(b_1,...,b_k),a_2,..., a_n)=res(res (b_1+...+b_k)+a_2+...+a_n) = res(b_1+ ... +b_k+a_2+...+a_n) $

[Turegg]

На счет остальных наборов аргументов я не знаю. Об этом ничего не сказано.
Может лучше стоит под эти определения как-то этот класс свести?

Класс булевых функций K называется замкнутым, если K

1. содержит тождественную функцию;
2. замкнут относительно переименования аргументов;
3. замкнут относительно суперпозиции.

[nikvic]

Turegg в сообщении #718217 писал(а):

Не могу понять, что этот класс из себя представляет.

Запишите исходную импликацию в обычном порядке, ""если-то.
Получите множество всех функций, не превосходящих сумму по модулю двух. А дальше - вперёд, боритесь с композицией

[Turegg]

А может лучше воспользоваться замкнутостью относительно переименования аргументов?
Ну то есть возьмем какие-нибудь другие аргументы, н-р $b_1,b_2,...,b_n$, сумма которых по модулю 2 была бы такой же, и получим замкнутость. Или не прокатит?

[nikvic]

Turegg в сообщении #718341 писал(а):

Или не прокатит?

А как же нумер три из определения?

[Turegg]

Если честно, то я чайник в этих вопросах. Я препода уговорил экзаменационный билет домой дать. Вот сижу, думаю...

[provincialka]

Turegg в сообщении #718330 писал(а):

На счет остальных наборов аргументов я не знаю. Об этом ничего не сказано.

Остальные значения не должны быть фиксированными, иначе получится не "класс", а только одна функция.

(Оффтоп)

мое рассуждение в этом смысле бесполезно

А число аргументов у функции произвольно? Наверное, да, иначе откуда взять тождественную функцию. Правда, в вики про тождественную функцию ничего не сказано - только про суперпозицию. Вернее, про произвольную формулу, которую можно получить из данных. Но тождественная функция не входит автоматически в число "формул".

-- 01.05.2013, 19:01 --

Все-таки условие задачи не очень понятно. Рассмотрим две функции. Функция $f(x,y)$ на парах $(0;0), (0;1), (1;0), (1;1)$ принимает значения $0,1,1,0$. Функция $g(x,y)$ на тех же парах принимает значения $0,1,0,0$. Обе функции принадлежат классу $K$. Рассмотрим композицию $h(x,y,z)=f(g(x,y),z)$. Имеем $h(1,0,1)=f(0,1) =1$, в то время как $1+0+1=0\pmod 2$

Где ошибка?

[Turegg]

Условие действительно странное. В остальных билетах были доказательства обычных классов. Видимо, мне не повезло.

[nikvic]

Turegg в сообщении #718395 писал(а):

Видимо, мне не повезло

Обратите в победу, воспользовавшись контрпримером provincialka

[Turegg]

Другого выбора все равно нету. Спасибо огромное

[Turegg]

В общем, я понял, что это за функция. Это - исключающее "или" (сложение по модулю 2). Теперь осталось узнать к какому из основных классов ее можно отнести.

[nikvic]

Как насчёт функции, тождественно равной нулю?

[Turegg]

Можно немножко по-подробней?

[nikvic]

Гм, функция-константа (пусть от одного переменного) со значением ноль.