Найти замыкание множества $%A=\{xy, x \sim y\}$%. Ответ обосновать.

задан 29 Май '15 14:39

изменен 29 Май '15 17:12

%D0%92%D0%B8%D1%82%D0%B0%D0%BB%D0%B8%D0%BD%D0%B0's gravatar image


9917

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

Обе функции сохраняют 1, поэтому они принадлежат классу $%T_1$%, а он замкнут. Достаточно показать, что любая функция этого класса выражается через наши две: тогда окажется, что замыканием является в точности $%T_1$%.

Заметим, что $%(x\sim y)=x+y+1$% (сложение по модулю 2). Функцию $%f(x_1,\ldots,x_n)\in T_1$% представим полиномом Жегалкина. Окажется, что либо свободный член равен нулю, а одночленов нечётное количество, либо свободный член равен единице, а одночленов чётное количество. Одночлен, равный 1, выразим через эквиваленцию в виде $%x\sim x$%. Сумму нечётного числа одночленов вида $%w_1+w_2+\cdots+w_{2k}+w_{2k+1}$% можно выразить при помощи эквиваленции: $%(\ldots((w_1\sim w_2)\sim w_3)\sim\cdots)\sim w_{2k+1})$% есть в точности сумма одночленов с учётом указанного выше тождества, так как 1 прибавляется здесь $%2k$% раз. Аналогично, сумму чётного числа одночленов и единицы можно выразить как $%1+w_1+w_2+\cdots+w_{2k}=(\ldots((w_1\sim w_2)\sim w_3)\sim\cdots)\sim w_{2k})$%, то есть любая функция из $%T_1$% выразима.

ссылка

отвечен 29 Май '15 15:05

изменен 29 Май '15 17:16

1

@falcao разве эквиваленция сохраняет 0?

(29 Май '15 16:49) mathhunter

@mathhunter: конечно, не сохраняет! Я писал в перерыве между лекциями, и второпях написал не то. Сейчас исправлю текст -- ответ там другой, но доказательство похожее.

(29 Май '15 17:11) falcao

@mathhunter: для полноты картины можно ещё отметить следующее. Функции $%xy$% и $%x+y+z$% сохраняют и 0, и 1. Про них можно доказать, что любая функция из $%T_0\cap T_1$% через них выразима. Действительно, мономы кроме 1 выражаются через конъюнкцию, а потом берём один моном и прибавляем к нему по два при помощи второй функции. Получаются суммы нечётного числа одночленов без свободного члена.

(29 Май '15 18:24) falcao
10|600 символов нужно символов осталось
Ваш ответ

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

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

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

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

отмечен:

×1,071

задан
29 Май '15 14:39

показан
329 раз

обновлен
29 Май '15 18:24

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

по почте:

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

по RSS:

Ответы

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

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