Как найти число шефферовых функций от n переменных? (от трех переменных)

Что для этого нужно?

задан 11 Дек '15 22:38

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

Найти количество шефферовых функций от $%n$% переменных нетрудно, если быть знакомым с теорией булевых функций в рамках теоремы Поста о предполных классах.

Система из одной функции $%f$% полна в $%P_2$% (то есть все булевы функции выразимы через $%f$%, и тем самым $%f$% является шефферовой) тогда и только тогда, когда $%f$% не принадлежит ни одному из пяти предполных классов двузначной логики: $%T_0$%, $%T_1$%, $%L$%, $%M$%, $%S$%. Первые два условия означают, что $%f(0,...,0)=1$% и $%f(1,...,1)=0$%. Таких функций от $%n\ge1$% переменных имеется ровно $%2^{2^n-2}$%, то есть в точности $%\frac14$% от числа всех функций $%n$% переменных. Если эти условия выполнены, то $%f\notin M$%, то есть $%f$% не монотонна. Далее, если линейная функция удовлетворяет этим двум условиям, то её полином Жегалкина имеет вид $%1+x_{i_1}+\cdots+x_{i_k}$%, где $%k$% нечётно. Достаточно очевидно, что такая функция самодвойственна. Поэтому, если учесть последнее условие $%f\notin S$%, то мы автоматически получим, что $%f$% не линейна, то есть $%f\notin L$%.

Таким образом, условие шефферовости функции в точности означает, что $%f\notin T_0\cup T_1\cup S$%. Для подсчёта количества нам остаётся вычесть из указанного выше числа, количество самодвойственных функций, которые удовлетворяют первым двум условиям.

Самодвойственная функция произвольным образом задаётся на первой (верхней) половине таблицы истинности. На остальных наборах она однозначно определяется предыдущими значениями. У нас при этом есть только одно ограничение: $%f(0,...,0)=1$%, а на всех остальных $%2^{n-1}-1$% наборах верхней половины таблицы мы задаём значения функции как угодно. И таких функций из $%S$%, которые не принадлежат $%T_0\cup T_1$%, получается ровно $%2^{2^{n-1}-1}$%.

Итоговый ответ: шефферовых функций от $%n$% переменных имеется в точности $$2^{2^n-2}-2^{2^{n-1}-1}.$$

При $%n=2$% получается две функции (собственно штрих Шеффера, а также стрелка Пирса). При $%n=3$% формула даёт значение $%2^6-2^3=56$%.

При $%n\gg1$% примерно каждая четвёртая функция от $%n$% переменных будет шефферовой.

ссылка

отвечен 12 Дек '15 4:24

изменен 12 Дек '15 4:25

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

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

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

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

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

отмечен:

×1,074
×497

задан
11 Дек '15 22:38

показан
2458 раз

обновлен
19 Май 21:48

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

по почте:

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

по RSS:

Ответы

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

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