Цей і два наступних параграфа присвячені розгляду трьох конкретних класів функцій: самодвоїстих, монотонних і лінійних.
Визначення. Функція g (x1, ..., xn) називається двойственнойk f (x1, ..., xn), якщо виконується рівність
Наприклад, 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 (x1, ..., xn) називається самодвоїстих. якщо виконується рівність
Іншими словами, функція самодвоїстих, якщо вона збігається зі своєю двоїстої.
Наведемо приклади. Легко бачити, що самодвоїстих функціями є тотожна функція і заперечення: n [e (n (x))] = n [n (x)] = x = e (x), n [n (n (x))] = n (x). У той же час, твір x × y самодвоїстих не є, оскільки двояко диз'юнкції x Ú y і x × y ¹ x Ú y. Можна показати, що ніяка функція від двох змінних, істотно залежить від кожного аргументу, самодвоїстих не є. В якості ще одного прикладу самодвоїстих функції наведемо функцію
В силу рівності (2), h (x1, ..., xn) - самодвоїстих функція. Отже, клас S замкнутий щодо суперпозиції.
Наступне твердження називається леммой про несамодвойственной функції.
Лемма. Нехай f (x1, ..., xn) - несамодвойственная функція. Тоді замикання класу K = 1, ..., xn), n (x)> містить константи q (x) і i (x).
Доведення. Оскільки f (x1, ..., xn) - несамодвойственная функція, то існують a1, ..., an Î B такі, що
Безліч B містить тільки два елементи. Тому з цієї нерівності випливає рівність
Для зручності позначень припустимо, що a1, ..., ak = 0, ak + 1, ..., an = 1. Тоді остання рівність можна записати так:
де крапка з комою відокремлює k-ий аргумент від (k + 1) -го.
Зауважимо, що g (x) належить [K]. маємо рівності
Отже, g (x) - одна з констант, що належить [K]. Оскільки K містить заперечення, то й інша константа належить [K].
На закінчення параграфа розглянемо приклад рішення задачі на розпізнавання самодвоїстих: визначити, чи буде функція f (x1, x2) = x2 × (x2 ® x1) самодвоїстих? (Втім, ми вже знаємо, що f (x1, x2) несамодвойственна, але треба це довести). Для отримання відповіді на питання складемо таблицю, що задає функції f (x1, x2) і n (f (n (x1), n (x2)). (Див. Таблицю 2.4)