Самодвої́ста фу́нкція — булева функція, двоїста сама до себе. Більш розгорнуто, булева функція називається самодвоїстою, якщо для будь-яких значень виконується
Тобто, самодвоїста функція на протилежних один до одного наборах значень аргументів набуває протилежних значень. Приклади самодвоїстих функцій: , , , мажоритарна функція, заперечення мажоритарної функції. Самодвоїстих функцій, які суттєво залежать від двох змінних, немає.
Кожну самодвоїсту функцію арності можна подати у вигляді
,
для деякої арності , причому визначається однозначно як (а відповідно дорівнює ). І навпаки, для будь-якої функції арності функція , що визначається зазначеним вище співвідношенням, самодвоїста. Самодвоїстих функцій арності немає. отже, між будь-якими булевими функціями арності і самодвоїстими функціями арності є взаємно-однозначна відповідність. Тому кількість самодвоїстих функцій арності дорівнює кількості всіх булевих функцій арності , яка, в свою чергу, дорівнює .
Аналогічне подання вийде, якщо виносити не змінну , а будь-яку іншу.
Клас самодвоїстих функцій
Клас усіх самодвоїстих функцій є замкнутим класом, передповним у . Клас самодвоїстих функцій позначають символом або (позначення Поста). Базисами класу самодвоїстих функцій є, наприклад:
— заперечення і мажоритарна функція; — заперечення мажоритарної функції.
Порядок класу самодвоїстих функцій дорівнює .
Самодвоїсті функції, що зберігають , будуть зберігати й ; зворотне теж правильне. отже, (де ). Монотонна самодвоїста функція завжди зберігає константи, при цьому є немонотонні самодвоїсті функції, що зберігають константи ().
Навіть якщо не вимагати у визначенні замкнутого класу, щоб він обов'язково містив функцію , будь-який замкнутий клас самодвоїстих функцій все одно її міститиме. Будь-який замкнутий клас самодвоїстих функцій можна розширити до передповного в . Передповними в є такі два класи: () та (). Істинний аналог малої теореми Поста: система самодвоїстих функцій повна в тоді і лише тоді, коли вона містить нелінійну функцію, яка не зберігає константи.
Лемма про несамодвоїсту функцію
З несамодвоїстої функції підстановкою та можна отримати константу.
Ця лема використовується в одному з доведень малої теореми Поста.
Є також загальніша властивість, використовувана в доведеннях різних властивостей класів :
З несамодвоїстої функції можна отримати несамодвоїсту функцію двох змінних таку, що .
Узагальнення Функцію k-значної логіки називають самодвоїстою відносно перестановки , якщо для будь-яких значень виконується
.
Звичайна самодвоїстість булевих функцій відповідає самодвоїстості відносно перестановки . Клас усіх самодвоїстих відносно перестановки функцій є повним у тоді й лише тоді, коли перестановка розкладається в добуток незалежних циклів однакової простої довжини.
Див. також Ґратка Поста Замкнений клас функцій алгебри логіки Симетричні функції алгебри логіки Монотонні функції алгебри логіки Лінійні функції алгебри логіки Передповний клас функцій алгебри логіки
Примітки
Література