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

[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 с.