Сколько существует нелинейных булевых функций четырех переменных, имеющих нулевой коэффициент при xyzu? Является ли это множество классом замкнутости?

задан 10 Янв 23:39

Выпишем все 16 одночленов Жегалкина. При xyzw выберем коэффициент 1. Функция заведомо будет нелинейной. Остальные коэффициенты выбираются произвольно. Получается 2^{15} функций.

Конечные системы функций почти никогда не замкнуты. В данном случае функция 1+xyzw принадлежит системе. Через неё выразим штрих Шеффера 1+xy, а через него -- все функции.

Выражение "класс замкнутости" (уже не первый раз вижу) -- чей-то очень неудачный языковой "креатив". Это звучит примерно так же противоестественно, как "треугольник прямоугольности". Приличное название -- (функционально) замкнутый класс.

(12 Янв 13:15) falcao

Прошу пояснить, почему перед xyzw был выбран коэффициент 1, если в задании указано, что при xyzw должен быть нулевой коэффициент? Это было сделано, чтобы можно было утверждать он нелинейности функции, так если бы коэффициент был равен 0, то нелинейность не была бы очевидна?

(12 Янв 23:41) Lampero

@Lampero: это я невнимательно прочитал условие. Сейчас отвечу на тот вопрос, который был задан.

(13 Янв 0:02) falcao
10|600 символов нужно символов осталось
1

Булевых функций вида f(x,y,z,u) с нулевым коэффициентом при xyzu имеется ровно столько же, сколько и с коэффициентом 1, то есть 2^{15}. Понятно, что у всех линейных функций это так, то есть их количество нужно вычесть. А линейных функций от n переменных имеется в точности 2^{n+1} (коэффициенты выбираются при 1, x1, ... , xn). Значит, ответом здесь будет 2^{15}-2^5.

Рассматриваемому классу функций принадлежит штрих Шеффера 1+xy. Поэтому замыканием системы будет класс всех функций алгебры логики.

ссылка

отвечен 13 Янв 0:06

10|600 символов нужно символов осталось
Ваш ответ

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

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

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

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

отмечен:

×56

задан
10 Янв 23:39

показан
148 раз

обновлен
13 Янв 0:06

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

по почте:

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

по RSS:

Ответы

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

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