Самодвойственная функция — булева функция, двойственная сама к себе. Более развёрнуто, булева функция называется самодвойственной, если для любых значений верно
Другими словами самодвойственная функция на противоположных друг другу наборах значений аргументов принимает противоположные значения. Примеры самодвойственных функций: , , , функция голосования, отрицание функции голосования. Самодвойственных функций с двумя существенными переменными нет.
Каждую самодвойственную функцию арности можно представить в виде , для некоторой арности , причём определяется однозначно как (а соответственно равно ). Обратно, для любой функции арности функция , определяемая указанным выше соотношением, самодвойственна. Самодвойственных функций арности нет. Таким образом, между любыми булевыми функциями арности и самодвойственными функциями арности есть взаимо-однозначное соответствие. Поэтому, количество самодвойственных функций арности равно количеству всех булевых функций арности , которое в свою очередь равно .
Аналогичное представление получится, если выносить не переменную , а любую другую.
Класс самодвойственных функций
Класс всех самодвойственных функций является замкнутым классом, предполным в . Класс самодвойственных функций обозначается символом или (обозначение Поста). Базисами класса самодвойственных функций являются, например: ; — отрицание и функция голосования; — отрицание функции голосования. Порядок класса самодвойственных функций равен .
Самодвойственные функции, сохраняющие , будут сохранять и ; обратное тоже верно. Таким образом, (где ). Монотонная самодвойственная функция всегда сохраняет константы, при этом есть немонотонные сохраняющие константы самодвойственные функции ().
Даже если не требовать в определении замкнутого класса, чтобы он обязательно содержал функцию , любой замкнутый класс самодвойственных функций всё равно будет её содержать. Любой замкнутый класс самодвойственных функций можно расширить до предполного в . Предполными в являются следующие два класса: (класс самодвойственных линейных функций) и (класс самодвойственных функций, сохраняющих константы). Верен аналог малой теоремы Поста: система самодвойственных функций полна в тогда и только тогда, когда она содержит нелинейную и не сохраняющую константы функцию.
Лемма о несамодвойственной функции Лемма о несамодвойственной функции: Из несамодвойственной функции и отрицание при помощи суперпозиции можно получить константу. Данная лемма используется в одном из доказательств малой теоремы Поста.
Есть также более общее свойство, используемое в доказательствах различных свойств классов в : Из несамодвойственной функции можно получить несамодвойственную функцию от двух переменных такую, что .
Обобщения Функция k-значной логики называется самодвойственной относительно перестановки , если для любых значений выполнено . Обычная самодвойственность булевых функций соответствует самодвойственности относительно перестановки . Класс всех самодвойственных относительно перестановки функций является предполным в тогда и только тогда, когда перестановка разлагается в произведение независимых циклов одной и той же простой длины.
Примечания
Литература
Марченков С.С. Замкнутые классы булевых функций. — М.: Физматлит. - 2000
Категория:Булева алгебра Категория:Математическая логика Категория:Теория дискретных функций