Сколько существует булевых функций, сохраняющих ноль и единицу?

Сколько существует различных самодвойственных булевых функций от n переменных (часть переменных может быть фиктивна)?

задан 7 Янв '15 16:59

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

Всего имеется $%2^{2^n}$% булевых функций от $%n$% переменных. Классу $%T_0$% функций, сохраняющих ноль, принадлежит половина из них, то есть $%2^{2^n-1}$%. Это связано с тем, что в строке из нулей значение функции равно нулю, а в остальных $%2^n-1$% строках можно независимо выбирать одно из двух значений. Классу $%T_1$% функций, сохраняющих единицу, принадлежит столько же элементов.

Если речь идёт о функциях, сохраняющих то и другое, то есть о пересечении классов $%T_0\cap T_1$%, то при $%n\ge1$% количество таких функций будет равно одной четверти от числа всех функций, то есть $%2^{2^n-2}$%. Строка из нулей и строка из единиц различны, на них значения заданы. На остальных $%2^n-2$% строках выбираются любые значения.

Надо заметить, что при $%n=0$%, то есть для случая констант 0 и 1, пересечение двух этих классов пусто.

У самодвойственных функций вторая половина таблицы истинности строится однозначно по первой половине: на противоположных наборах выбираются противоположные значения (по определению). Первая же половина, в которой $%2^{n-1}$% строка, заполняется произвольно. Это даёт ответ $%2^{2^{n-1}}$% при $%n\ge1$% (корень квадратный от общего числа функций, или общее количество функций от $%n-1$% переменной). В вырожденном случае $%n=0$% самодвойственных функций нет (константы двойственны друг другу).

ссылка

отвечен 7 Янв '15 17:49

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

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

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

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

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

отмечен:

×1,094

задан
7 Янв '15 16:59

показан
2005 раз

обновлен
7 Янв '15 17:49

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

по почте:

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

по RSS:

Ответы

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

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