Самодвойственная функция
Самодвойственная функция — булева функция, двойственная сама к себе. Более развёрнуто, булева функция называется самодвойственной, если для любых значений верно
Другими словами самодвойственная функция на противоположных друг другу наборах значений аргументов принимает противоположные значения. Примеры самодвойственных функций: , , , [1]. Самодвойственных функций с двумя существенными переменными нет[2].
Каждую самодвойственную функцию арности можно представить в виде
- ,
для некоторой арности , причём определяется однозначно. Обратно, для любой функции арности функция , определяемая указанным выше соотношением, самодвойственна. Самодвойственных функций арности нет. Таким образом, между любыми булевыми функциями арности и самодвойственными функциями арности есть взаимо-однозначное соответствие. Поэтому, количество самодвойственных функций арности равно количеству всех булевых функций арности , которое в свою очередь равно [3].
Аналогичное представление получится, если выносить не переменную , а любую другую.
Класс самодвойственных функций
[править | править код]![](http://chped.net/https/upload.wikimedia.org/wikipedia/commons/thumb/2/21/%D0%A0%D0%B5%D1%88%D1%91%D1%82%D0%BA%D0%B0_%D0%B7%D0%B0%D0%BC%D0%BA%D0%BD%D1%83%D1%82%D1%8B%D1%85_%D0%BA%D0%BB%D0%B0%D1%81%D1%81%D0%BE%D0%B2_%D1%81%D0%B0%D0%BC%D0%BE%D0%B4%D0%B2%D0%BE%D0%B9%D1%81%D1%82%D0%B2%D0%B5%D0%BD%D0%BD%D1%8B%D1%85_%D1%84%D1%83%D0%BD%D0%BA%D1%86%D0%B8%D0%B9.svg/220px-%D0%A0%D0%B5%D1%88%D1%91%D1%82%D0%BA%D0%B0_%D0%B7%D0%B0%D0%BC%D0%BA%D0%BD%D1%83%D1%82%D1%8B%D1%85_%D0%BA%D0%BB%D0%B0%D1%81%D1%81%D0%BE%D0%B2_%D1%81%D0%B0%D0%BC%D0%BE%D0%B4%D0%B2%D0%BE%D0%B9%D1%81%D1%82%D0%B2%D0%B5%D0%BD%D0%BD%D1%8B%D1%85_%D1%84%D1%83%D0%BD%D0%BA%D1%86%D0%B8%D0%B9.svg.png)
Класс всех самодвойственных функций является замкнутым классом, предполным в . Класс самодвойственных функций обозначается символом [4] или [1] (обозначение Поста). Базисами класса самодвойственных функций являются, например: , , .[5] Порядок класса самодвойственных функций равен [2].
Самодвойственные функции, сохраняющие , будут сохранять и ; обратное тоже верно. Таким образом, (где ). Монотонная самодвойственная функция всегда сохраняет константы, при этом есть немонотонные сохраняющие константы самодвойственные функции ().
Даже если не требовать в определении замкнутого класса, чтобы он обязательно содержал функцию , любой замкнутый класс самодвойственных функций всё равно будет её содержать. Любой замкнутый класс самодвойственных функций можно расширить до предполного в . Предполными в являются следующие два класса: (класс самодвойственных линейных функций) и (класс самодвойственных функций, сохраняющих константы)[6]. Верен аналог малой теоремы Поста: система самодвойственных функций полна в тогда и только тогда, когда она содержит нелинейную и не сохраняющую константы функцию.
Примечания
[править | править код]- ↑ 1 2 Яблонский, Гаврилов, Кудрявцев, 1966, с. 22.
- ↑ 1 2 Яблонский, Гаврилов, Кудрявцев, 1966, с. 25.
- ↑ Яблонский, Гаврилов, Кудрявцев, 1966, с. 23.
- ↑ Яблонский, 1986, с. 34.
- ↑ Яблонский, Гаврилов, Кудрявцев, 1966, с. 24.
- ↑ Яблонский, Гаврилов, Кудрявцев, 1966, с. 112.
Литература
[править | править код]- Яблонский С. В. Введение в дискретную математику. — М.: Наука, 1986. — 384 с.
- Яблонский С. В., Гаврилов Г. П., Кудрявцев В. Б. Функции алгебры логики и классы Поста. — М.: Наука, 1966. — 120 с.
- Марченков С.С. Замкнутые классы булевых функций. — М.: Физматлит. - 2000