Этот и два следующих параграфа посвящены рассмотрению трех конкретных классов функций: самодвойственных, монотонных и линейных.

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

g(x₁,…,x_n)=n[f(n(x₁),…,n(x_n)]].

Например, x×y двойственна xÚy, и наоборот. Это следует из равенств x×y=n(n(x)Ún(y) и xÚy=n(n(x)×n(y)), которые мы уже приводили. Функция x®y двойственна функции n(x)&y, поскольку n(n(x)®n(y)=n[n(n(x))Ún(y)]=n(xÚn(y)) =n(x)&y. Отметим, что первое равенство выполняется на основании закона 20, второе 19 и третье 18 и 19.

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

f(x₁,…,x_n)=n[f(n(x₁),…,n(x_n)]. (1)

Другими словами, функция самодвойственна, если она совпадает со своей двойственной.

Приведем примеры. Легко видеть, что самодвойственными функциями являются тождественная функция и отрицание: n[e(n(x))]=n[n(x)]=x=e(x), n[n(n(x))]=n(x). В то же время, произведение x×y самодвойственной не является, поскольку двойственно дизъюнкции xÚy и x×y¹xÚy. Можно показать, что никакая функция от двух переменных, существенно зависящая от каждого аргумента, самодвойственной не является. В качестве еще одного примера самодвойственной функции приведем функцию

f(x₁,x₂,x₃)=(x₁×x₂)Ú(x₁×x₃)Ú (x₁×x₃).

Последнее равенство выполняется на основании закона поглощения.

Отметим, что равенство (1) из определения самодвойственности равносильно равенству n(f(x₁,…,x_n))=f(n(x₁),…,n(x_n)). (2)

Класс всех самодвойственных функций обозначим буквой S. Убедимся в том, что S – замкнутый класс. Как уже отмечалось, S содержит e(x). Пусть f(x₁,…,x_n)ÎS и y₁,…,y_n – новый набор переменных. Тогда поскольку равенство f(x₁,…,x_n)=n[f(n(x₁),…,n(x_n)] выполняется для всех значений переменных x₁,…,x_n, то n[f(n(y₁),…,n(y_n)]=f(y₁,…,y_n). Следовательно, f(y₁,…,y_n)ÎS и S – замкнут относительно переименования аргументов. Возьмем теперь функции f(x₁,…,x_k), g₁(x₁,…,x_n),…, g_k(x₁,…,x_n) из S. Поскольку эти функции принадлежат S, то, используя равенство (2), получаем, что

n(f(x₁,…,x_k))=f(n(x₁),…,n(x_n)),

n(g₁(x₁,…,x_n))=g₁(n(x₁),…,n(x_n)),

· · ·

n(g_k(x₁,…,x_n))=g_k(n(x₁),…,n(x_n)).

В силу равенства (2), h(x₁,…,x_n) – самодвойственная функция. Следовательно, класс S замкнут относительно суперпозиции.

Следующее утверждение называется леммой о несамодвойственной функции.

Лемма. Пусть f(x₁,…,x_n) – несамодвойственная функция. Тогда замыкание класса K={f(x₁,…,x_n), n(x)} содержит константы q(x) и i(x).

Доказательство. Поскольку f(x₁,…,x_n) – несамодвойственная функция, то существуют a₁,…,a_nÎB такие, что

n[f(a₁,…,a_n)]¹f(n(a₁),…,n(a_n)).

Множество B содержит только два элемента. Поэтому из этого неравенства следует равенство

f(a₁,…,a_n)=f(n(a₁),…,n(a_n)).

Для удобства обозначений предположим, что a₁,…,a_k=0, a_k+1,…, a_n=1. Тогда последнее равенство можно записать так:

f(0,…,0;1,…,1)=f(1,…,1;0,…,0),

где точка с запятой отделяет k-ый аргумент от (k+1)-го.

Рассмотрим функцию

g(x)=f(x,…,x;n(x),…,n(x)).

Заметим, что g(x) принадлежит [K]. Имеем равенства

g(0)=f(0,…,0; n(0),…,n(0))=f(0,…,0;1,…,1)=

=f(1,…,1;0,…,0)=f(1,…,1; n(1),…,n(1))=g(1).

Следовательно, g(x) – одна из констант, принадлежащая [K]. Поскольку K содержит отрицание, то и другая константа принадлежит [K].

Лемма доказана.

В заключение параграфа рассмотрим пример решения задачи на распознавание самодвойственности: определить, будет ли функция f(x₁,x₂)=x₂×(x₂®x₁) самодвойственной? (Впрочем, мы уже знаем, что f(x₁,x₂) несамодвойственна, но надо это доказать). Для получения ответа на вопрос составим таблицу, задающую функции f(x₁,x₂) и n(f(n(x₁),n(x₂)). (см. таблицу 2.4)

Таблица 2.4

Мы видим, что f(x₁,x₂)¹n(f(n(x₁),n(x₂)), например при x₁=0, x₂=1. Следовательно, функция f(x₁,x₂) самодвойственной не является. (Для того, чтобы сделать заключение о несамодвойственности, можно было, конечно, прервать составление таблицы на второй строке.