Добрый день. Почему число симметричных булевых функций равно 2^n+1 . Объясните подробнее.

Симметричность означает, что значение функции не зависит от порядка аргументов, а только от количества единичных значений среди них, т. к. мы всегда можем переставить аргументы таким образом, чтобы сначала шли только единичные аргументы, а потом нулевые. Например, для трёх аргументов F(1,0,1) = F(0,1,1) = F(1,1,0).

То есть для симметричной функции от n аргументов существует ровно n+1 неэквивалентных исходных данных (0 единиц в аргументах, 1 единица, 2... и так до n). Например, для 3-х аргументов это 4 различных варианта входных данных: (0,0,0), (1,0,0), (1,1,0), (1,1,1). Все остальные варианты, в силу симметрии, сводятся к этим.

Для каждого конкретного набора значений аргументов булева функция может принимать 2 значения (0 или 1). Т. е. функции, одна из которых при конкретном числе 1 на входе принимает значение 0, а другая при том же числе 1 на входе принимает значение 1 - различны. Вот и получается, что всего различных симметричных булевых функций 2^(n+1) - число различных значений в степени, равной числу различных входных данных.