Самодвойственная функция
булева функция, двойственная сама к себе / Материал из Википедии — свободной encyclopedia
Самодвойственная функция — булева функция, двойственная сама к себе. Более развёрнуто, булева функция называется самодвойственной, если для любых значений верно
Другими словами самодвойственная функция на противоположных друг другу наборах значений аргументов принимает противоположные значения. Примеры самодвойственных функций: , , , [1]. Самодвойственных функций с двумя существенными переменными нет[2].
Каждую самодвойственную функцию арности можно представить в виде
- ,
для некоторой арности , причём определяется однозначно. Обратно, для любой функции арности функция , определяемая указанным выше соотношением, самодвойственна. Самодвойственных функций арности нет. Таким образом, между любыми булевыми функциями арности и самодвойственными функциями арности есть взаимо-однозначное соответствие. Поэтому, количество самодвойственных функций арности равно количеству всех булевых функций арности , которое в свою очередь равно [3].
Аналогичное представление получится, если выносить не переменную , а любую другую.