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

Функция называется двойственной к функции 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;

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

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