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

Функция g(x₁,...,x_n) = ¬f(¬x₁,...,¬x_n) называется двойственной функцией к функции f и обозначается f^* .

Пример (x & y)^* = ¬(¬x & ¬y) = x Ú y.

Теорема:Функция, двойственная к двойственной функции f равна самой функции f.

Доказательство. f^*(x₁,...,x_n)^* = (¬f(¬x₁,...,¬x_n))^* = ¬¬f(¬¬x₁,...,¬¬x_n) = f(x₁,...,x_n)

 

Рассмотрим, что происходит с таблицей двойственной функции. Замена набора (x₁,...,x_n) на (¬x₁,...,¬x_n) соответствует ``переворачиванию'' таблицы. Действительно, наборы (x₁,...,x_n) и (¬x₁,..., ¬x_n) расположены симметрично относительно середины таблицы. Теперь остаётся применить операцию ¬ к результату функции, т.е. поменять 0 на 1 и 1 на 0. Т.о. вектор значений функции, двойственной к исходной, получается из вектора исходной функции переворачиванием и заменой 0 на 1, а 1 на 0.

Функции x & y и x Ú y, задаваемые векторами значений (0,0,0,1) и (0,1,1,1) двойственны друг к другу. Также двойственными являются x Å y и x º y, задаваемые векторами (0,1,1,0) и (1,0,0,1). Каждая из функций x и ¬x (векторы (0,1) и (1,0) соответственно) двойственна сама себе.