Принцип двойственности. Определение. Функция f*(x1, , xn) называется двойственной к функции f(x1, , xn), если f*(x1

Определение. Функция f*(x₁,..., x_n) называется двойственной к функции f(x₁,..., x_n), если f*(x₁,..., x_n) = ( ₁,..., _n).

Пример 8. Покажем с помощью таблицы истинности (табл. 13), что константа 0 двойственна к 1.

Таблица 13

Функции f (x) = x и g (x) = двойственны сами себе (табл. 14).

Таблица 14

Определение. Если f*(x₁,..., x_n) = f(x₁,..., x_n), то f(x₁,..., x_n) называется самодвойственной.

Если f *– самодвойственна, то ( ₁,..., _n) = f (x ₁,..., x_n), т.е. на противоположных наборах функция принимает противоположные значения.

Пример 9. Покажем, что f (x ₁, x ₂, x ₃)= x ₁Å x ₂Å x ₃ – самодвойственна (табл. 15).

Таблица 15

Пример 10. Покажем, что функция x₁&x₂ двойственна к х₁Úх₂, функция х₁ х₂ двойственна к функции x₁|x₂ (табл. 16).

Таблица 16

x 1 x 2	f = х 1Ú х 2	f *	g = x 1| x 2	g *= x 1 x 2
0 0 0 1 1 0 1 1

Теорема о двойственных функциях.

Если f * двойственна к f, то f двойственна к f *.

Доказательство. f *(x ₁,..., x_n) = ( ₁,..., _n). Найдем двойственную функцию к f *, т.е. (f *(x ₁,..., x_n))* = ( ( ₁,..., _n))* =

= ( ₁,..., _n) = f (x ₁,.., x_n).

Предположим, что функция задана формулой. Можно ли найти по этой формуле двойственную функцию? Ответ на этот вопрос дает следующая теорема.