Двойственные функции и принцип двойственности

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

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

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

Таблица 13

x	y	z	f (x, y, z)

Легко убедиться, что (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 реализует функцию f (x ₁, x ₂,…, x_n). Найдем формулу, реализующую двойственную функцию f ^*(x ₁, x ₂,…, x_n).

Теорема 1.8.1. О двойственной функции.

Пусть функция Ф(x ₁, x ₂,…, x_n) является суперпозицией функций f ₁(x ₁₁, x ₁₂,…, x _{1 p 1}), f ₂(x ₂₁, x ₂₂,…, x _{2 p 2}),…, f _s(x _s1, x _s2,…, x _{s p s}), т.е. Ф(x ₁, x ₂,…, x_n)= f (f ₁(x ₁₁, x ₁₂,…, x _{1 p 1}), f ₂(x ₂₁, x ₂₂,…, x _{2 p 2}),…, f _s(x _s1, x _s2,…, x _{s p s})), где x ₁, x ₂,…, x_n – это все различные символы имен переменных из наборов (x ₁₁, x ₁₂,…, x _{1 p 1}), (x ₂₁, x ₂₂,…, x _{2 p 2}), …,(x _s1, x _s2,…, x _{s p s}), тогда Ф^*(x ₁, x ₂,…, x_n)= f ^*(f ^*₁(x ₁₁, x ₁₂,…, x _{1 p 1}), f ^*₂(x ₂₁, x ₂₂,…, x _{2 p 2}),…, f ^*_s(x _s1, x _s2,…, x _{s p s})).

Доказательство:

По определению двойственной функции Ф^*(x ₁, x ₂,…, x_n)==

Из этой теоремы следует так называемый принцип двойственности:

Пусть формула 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;

2) U ₂(x, y) = x & y Ú Þ U ₂^*(x, y) = (x Ú y) &;

3) U ₃(x, y) = (x Ú y) & () Þ U ₃^*(x, y) = x & y Ú .

Дата добавления: 2014-01-07