дискретная-математика - Сколько функций от n переменных содержит множество? (Дискретная Математика)

В принципе, как-то так и надо делать. Подсчёты здесь несложные. Надо только исправить формулу для числа самодвойственных функций: там должно быть $%2^{2^{n-1}}$%.

Общий вид линейной функции нам известен: $%f(x_1,...,x_n)=a+a_1x_1+\cdots+a_nx_n$%. При замене каждой из переменных на её отрицание, должно получаться отрицание функции. Это равносильно тому, что $%a_1+\cdots+a_n=1$%. Такое возможно при $%n\ge1$%, и ровно в половине случаев значение этой суммы равно 1, а в половине оно равно 0. Значит, $%L\bar{S}$% даёт $%2^n$% функций при $%n\ge1$%. Сразу же отметим, что половина только что учтённых функций принадлежит $%T_0$%, а половина нет. Поэтому учёт $%LT_0\bar{S}$% даёт нам $%2^n-2^{n-1}=2^{n-1}$%.

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

Итоговый ответ: $%2^{2^n-1}-2^{2^{n-1}-1}+2^{n-1}$% (при $%n\ge1$%). При $%n=0$% получится одна функция (константа 0).