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

Определение:

Пусть $f(x_1,...,x_n)\in P_2$. Двойственной функцией к функции $f$ называется $f^*(x_1,...,x_n) = \overline f(\overline x_1, ..., \overline x_n)$.

Пример

Пусть $f(x,y,z) = \overline{xy\vee z}$. Тогда [math]\displaystyle{ f^*(x,y,z) = \overline{\overline{\overline x\cdot \overline y\vee \overline z} } = \overline x\cdot \overline y \vee \overline z }[/math].

Пример

Пусть функция $f(x,y,z)$ задана таблицей.

Тогда, чтобы получить двойственную функцию, нужно перевернуть и инвертировать столбец значений:

[math]\displaystyle{ \begin{array}{ccc|cc} x & y & z & f(x,y,z) & f^*(x,y,z)\\ \hline \begin{array}{c} 0\\ 0\\ 0\\ 0\\ 1\\ 1\\ 1\\ 1\\ \end{array} & \begin{array}{c} 0\\ 0\\ 1\\ 1\\ 0\\ 0\\ 1\\ 1\\ \end{array} & \begin{array}{c} 0\\ 1\\ 0\\ 1\\ 0\\ 1\\ 0\\ 1\\ \end{array} & \begin{array}{c} 1\\ 1\\ 1\\ 0\\ 1\\ 0\\ 0\\ 1\\ \end{array} & \begin{array}{c} 0\\ 1\\ 1\\ 0\\ 1\\ 0\\ 0\\ 0\\ \end{array} \end{array} }[/math]

Рис. 1. Двойственная функция получается в два шага: столбец значений читается снизу вверх (инверсия аргументов), затем инвертируется. Сравните строки [math]\displaystyle{ 000 }[/math] и [math]\displaystyle{ 111 }[/math]: [math]\displaystyle{ f(0,0,0)=1 }[/math] переходит в [math]\displaystyle{ f^*(1,1,1)=0 }[/math].

Конспект: Дискретная математика