Двої́ста бу́лева фу́нкція до булевої функції — функція , яка визначається співвідношенням
Поняття «двоїстої функції» дуже важливе в теорії булевих функцій і широко в ній використовується:
за допомогою поняття двоїстої функції визначається принцип двоїстості для булевих функцій; за допомогою поняття двоїстої функції визначається клас самодвоїстих функцій, одним із п'яти передповних класів булевих функцій.
Функція, двоїста до двоїстої, збігається з початковою функцією, тобто . Функцію, двоїста до якої збігається з нею самою, називають самодвоїстою.
Приклади
Константи двоїсті одна до одної:
Тотожна функція самодвоїста:
Заперечення самодвоїсте:
Диз'юнкція двоїста до кон'юнкції:
Виключне або двоїсте до еквівалентності:
Імплікація двоїста до оберненої неімплікації:
Зворотна імплікація двоїста до коімплікації:
Штрих Шефера двоїстий до стрілки Пірса :
Мажоритарна функція самодвоїста:
Принцип двоїстості Введемо поняття двоїстої булевої формули. Нехай — булева формула. Двоїста до неї формула індуктивно визначається так:
Якщо має вигляд , де — змінна, то
Якщо має вигляд , де — функція арності , — деякі формули, то
Принцип двоїстості: якщо формула задає відносно набору змінних функцію , то формула задає відносно набору змінних функцію .
З принципу двоїстості випливає таке: якщо виконується деяка тотожність , то двоїста до неї тотожність теж правильна. Це дає змогу виводити нові тотожності з відомих, просто замінивши всі функції в тотожності на двоїсті. Приклад:
Візьмемо істинну тотожність . Замінивши ліву та праву формули на двоїсті, отримаємо — теж істинна тотожність.
Таку тотожність називають двоїстою тотожністю.
Для різних нормальних форм можна отримувати двоїсті до них форми. Наприклад, кожну функцію можна подати у вигляді диз'юнктивної нормальної форми. Подамо в ДНФ двоїсту до неї функцію , а потім за принципом двоїстості отримаємо подання . Ми отримали другу нормальну форму, перейшовши до двоїстої формули. Таку нормальну форму називають двоїстою нормальною формою до початкової нормальної форми. Двоїста нормальна форма до ДНФ — кон'юнктивна нормальна форма. Аналогічно можна отримати, наприклад, двоїсту форму до полінома Жегалкіна, яка також виглядатиме як многочлен, але роль множення в ній відіграватиме диз'юнкція, а роль додавання — еквівалентність. Таку нормальну форму називають кополіномом Жегалкіна.
Двоїсті системи функцій Поняття двоїстості поширюється на системи функцій. Нехай — система булевих функцій. Двоїста система визначається так:
Прикладом двоїстих систем є, наприклад, клас функцій, що зберігають , та клас функцій, що зберігають . Класи лінійних, самодвоїстих, монотонних і всіх булевих функцій — самодвоїсті.
Для операції дуалізації систем істинні такі співвідношення:
якщо , то якщо , то
З третього співвідношення безпосередньо випливає, що
двоїста система до замкнутого класу — замкнутий клас; якщо система повна в замкнутому класі , то й повна в замкнутому класі ; якщо система базис у замкнутому класі , то й базис у замкнутому класі .
Тому для самодвоїстих замкнутих класів двоїста до базису система також є базисом. Приклади двоїстих базисів у :
и ; і ; и ;
Примітки
Література