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

Функция называется двойственной к функции f (x ₁, x ₂,…, x_n). Для обозначения двойственной функции используется запись: [ f (x ₁, x ₂,…, x_n)]^* или f ^*(x ₁, x ₂,…, x_n) или f ^*.

Для получения столбца значений двойственной функции, как следует из определения, необходимо инвертировать значения функции f, т.е. заменить все единицы на нули, а нули – на единицы, а затем «перевернуть» полученный столбец, т.е. переписать его, начиная с конца, – что соответствует инвертированию значений переменных.

В таблице 5 процесс получения двойственной функции показан по шагам.

x	y	z	f (x, y, z)







				Таблица 5

Легко убедиться, что (0)^*=1, (1)^*=0, (х)^*= х, ()^*= , (x & y)^*= x Ú y, (x Ú y)^*= x & y, (x ® y)^*= , ()^*= y ® x, (x Å y)^*= x º y, (x º y)^*= x Å y, (x ¯ y)^*= x ½ y, (x ½ y)^*= x ¯ y.

Из определения двойственности следует, что f ^**=(f ^*)^*= f, т.е. f двойственна f ^*, – это так называемое свойство взаимности.

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

пусть формула U = S [ f ₁, f ₂,…, f_p ] реализует функцию f (x ₁, x ₂,…, x_n), тогда формула S [ f ₁^*, f ₂^*,…, f_p ^*], полученная из формулы U заменой функций f ₁, f ₂,…, f_p двойственными функциями f ₁^*, f ₂^*,…, f_p ^* соответственно, реализует функцию f ^*(x ₁, x ₂,…, x_n), двойственную f. Эта формула называется двойственной к формуле U и обозначается U ^*. Таким образом, U ^*= S [ f ₁^*, f ₂^*,…, f_p ^*], где S означает структуру формулы. Заметим, что структура формулы, определяемая порядком выполняемых действий, остается неизменной.

На практике наиболее часто принцип двойственности применяется к формулам, сконструированным из таких функций, как константы ноль и единица, тождественной функции, отрицания, конъюнкции и дизъюнкции. В таких случаях для получения двойственной формулы необходимо ноль заменить на единицу, а единицу на ноль везде, где они встречаются, знак «&» заменить знаком «Ú», а знак «Ú» – на «&». При этом следует учесть порядок выполняемых действий в исходной формуле и, если он не был задан явно скобками, а задавался только приоритетом операций, то, возможно, придется расставить скобки в двойственной формуле. Тогда установить их надо на тех же местах, где они неявно присутствовали в исходной формуле. В других случаях, ввиду того же старшинства операций, в двойственной формуле скобки, возможно, и не понадобятся.

Примеры:

1) U ₁(x, y) = x & y Þ U ₁^*(x, y) = x Ú y;