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

Question

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

Answer 1

Симметричность означает, что значение функции не зависит от порядка аргументов, а только от количества единичных значений среди них, т. к. мы всегда можем переставить аргументы таким образом, чтобы сначала шли только единичные аргументы, а потом нулевые. Например, для трёх аргументов F (1, 0, 1) = F (0, 1, 1) = F (1, 1, 0) .
 
То есть для симметричной функции от n аргументов существует ровно n неэквивалентных исходных данных (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 - число различных значений в степени, равной числу различных входных данных.