Умные вопросы
Войти
Регистрация
Добрый день. Почему число симметричных булевых функций равно 2^n . Объясните подробне.
Почему число симметричных булевых функций равно 2^n . Объясните подробне.
11 года
назад
от
irusik
1 ответ
▲
▼
0
голосов
Симметричность означает, что значение функции не зависит от порядка аргументов, а только от количества единичных значений среди них, т. к. мы всегда можем переставить аргументы таким образом, чтобы сначала шли только единичные аргументы, а потом нулевые. Например, для трёх аргументов 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 - число различных значений в степени, равной числу различных входных данных.
11 года
назад
от
Дима
Связанные вопросы
3
ответов
Как думаете, долго ещё будут к нам приходить АГлицкие словечки? Панкейки, бренды, креативщики и прочие менеджеры. ) +
7 года
назад
от
Muhammed_Shefi
2
ответов
Могут ли существовать газовые гиганты размером с Солнце, но при этом не быть термоядерной реакции?
12 года
назад
от
John Cena
1
ответ
Подскажите интересные книги по физике.
8 года
назад
от
турмалин