Полнота и замкнутость
Покажем, что To – замкнутый класс. Так как Toсодержит тождественную функцию, то для обоснования его замкнутости достаточно показать, что функция
Ф = f( f1, … , fm ) принадлежит To, если f1, … , fm принадлежат To. Последнее соотношение вытекает из следующей цепочки равенств:
Ф( 0, … , 0 ) = f( f1( 0, … , 0 ), …, fm( 0, … , 0 ) ) = f ( 0, … , 0 ) = 0.
T1 – класс всех логических функций f ( x1, …, xn ), сохраняющих единицу, т.е.для которых выполняется равенство:
f( 1, …, 1 ) = 1.
Легко видеть, что функции 1, x, x & y, x 
y принадлежат данному классу, а
функции 0, 
не принадлежат ему. Класс T1 так же содержит
/
2 функций n переменных.
Доказательство того, что класс T1 является замкнутым классом, проводится аналогично.
Определение. Функция f*( x1, … , xn ) называется двойственной функцией к функции f( x1, … , xn ), если она определяется равенством
. f*(
x1, … , xn ) = 
(
1, …, n).
Очевидно, что таблица для двойственной функции получается из таблицы функции f( x1, … , xn ) инвертированием ( т.е. заменой 0 на 1 и 1 на 0 ) столбца зна-чений функции и его переворачиванием. Это видно из следующей таблицы:
предыдущаяследующая