Двойственная булева функция

Материал из Википедии — свободной энциклопедии
Перейти к навигации Перейти к поиску

Двойственная булева функция к булевой функции — функция , определяемая соотношением

[1]

Понятие «двойственной функции» является очень важным в теории булевых функций и широко используется в ней:

  • при помощи понятия двойственной функции определяется принцип двойственности для булевых функций;
  • при помощи понятия двойственной функции определяется класс самодвойственных функций, который является одним из пяти предполных классов булевых функций.

Функция, двойственная к двойственной, совпадает с исходной функцией, то есть .[2] Функция, двойственная к которой совпадает с ней собой, называется самодвойственной.[3]

[2]
[4]
[5]
[6]

Принцип двойственности

[править | править код]

Введём понятие двойственной булевой формулы. Пусть булева формула. Двойственная к ней формула индуктивно определяется следующим образом:

  • Если имеет вид , где — переменная, то
;
  • Если имеет вид , где — функция арности , — некоторые формулы, то

Принцип двойственности: если формула задаёт относительно набора переменных функцию , то формула задаёт относительно набора переменных функцию .[7]

Из принципа двойственности следует следующее: если верно некоторое тождество , то двойственное к нему тождество тоже верно. Это позволяет выводить новые тождества из известных, просто заменив все функции в тождестве на двойственные. Пример:

  • Возьмём верное тождество . Заменив левую и правую формулы на двойственные получим — тоже верное тождество.[8]

Такое тождество называют двойственным тождеством.

Для различных нормальных форм можно получать двойственные к ним формы. Например, каждая функция представляется в виде дизъюнктивной нормальной формы. Представим в ДНФ двойственную к ней функцию , а затем по принципу двойственности получим представление . Мы получили другую нормальную форму, перейдя к двойственной формуле. Такая нормальная форма называется двойственной нормальной формой к исходной нормальной форме. Двойственная нормальная форма к ДНФ — конъюнктивная нормальная форма. Аналогично можно получить, например, двойственную форму к полиному Жегалкина, которая также будет выглядеть как многочлен, но роль умножения в ней будет играть дизъюнкция, а роль сложения — эквиваленция. Такая нормальная форма называется кополином Жегалкина.[9]

Двойственные системы функций

[править | править код]

Понятие двойственности распространяется на системы функций. Пусть — система булевых функций. Двойственная система определяется следующим образом:

Примером двойственных систем является, например, класс функций, сохраняющих , и класс функций, сохраняющих .[5] Классы линейных, самодвойственных, монотонных и всех булевых функций — самодвойственны.

Для операции дуализации систем верны следующие соотношения:

  • если , то
  • если , то

Из третьего соотношения непосредственно следует, что

  • двойственная система к замкнутому классу — замкнутый класс;
  • если система полна в замкнутом классе , то и полна в замкнутом классе ;
  • если система базис в замкнутом классе , то и базис в замкнутом классе .

Поэтому для самодвойственных замкнутых классов двойственная к базису система тоже является базисом. Примеры двойственных базисов в :

  • и ;
  • и ;
  • и ;

Примечания

[править | править код]

Литература

[править | править код]
  • Яблонский С. В. Введение в дискретную математику. — М.: Наука, 1986. — 384 с.
  • Математическая логика и теория алгоритмов. Лекции 2–4: пропозициональные формулы и булевы функции. https://old.mipt.ru/education/chairs/dm/. Дата обращения: 4 мая 2024.
  • Колпаков Р. М, Кочергин В. В. Теория дискретных функций. https://teach-in.ru/. Дата обращения: 4 мая 2024.
  • Подколзин А. С. 2 лекция курса «Теория дискретных функций». http://intsys.msu.ru. Дата обращения: 4 мая 2024.
  • Рагимханов В. Р. Дискретная математика. Часть IV. Булевы функции.. — Махачкала: ДГУ, 2019. — 102 с.