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

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

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

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

Легко убедиться, что (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. О двойственной функции

Пусть функция Ф(x₁,x₂,…,x_n) является суперпозицией функций f₁(x₁₁,x₁₂,…,x_1p1), f₂(x₂₁,x₂₂,…,x_2p2),…, f_s(x_s1,x_s2,…,x_sps), т.е. Ф(x₁,x₂,…,x_n)=f(f₁(x₁₁,x₁₂,…,x_1p1), f₂(x₂₁,x₂₂,…,x_2p2),…, f_s(x_s1,x_s2,…,x_sps)), где x₁,x₂,…,x_n – это все различные символы имен переменных из наборов (x₁₁,x₁₂,…,x_1p1), (x₂₁,x₂₂,…,x_2p2), …,(x_s1,x_s2,…,x_sps), тогда Ф^*(x₁,x₂,…,x_n)=f^*(f^*₁(x₁₁,x₁₂,…,x_1p1), f^*₂(x₂₁,x₂₂,…,x_2p2),…, f^*_s(x_s1,x_s2,…,x_sps)).

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

По определению двойственной функции Ф^*(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 означает структуру формулы. Заметим, что структура формулы, определяемая порядком выполняемых действий, остается неизменной.

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

Примеры:

U₁(x,y) = x & y  U₁^*(x,y) = x  y;

U₂(x,y) = x & y    U₂^*(x,y) = (x  y) &;

U₃(x,y) = (x  y) & ()  U₃^*(x,y) = x & y  .