Полнота и замкнутость
.
Определение. Минимальная полная система функций ( т.е. такая полная сис-тема функций, удаление из которой любой функции делает систему не полной ) называ-ется базисом.
Базисами будут следующие полные системы функций:
{ xy, x
y, 1 }, { x “
y }, { x y
}, { x 
y , x y , 1 },
{ x y
z , xy, 0, 1 }, {
x ’ y, 
}, { x ’ y, 0
}.
Замечание. Можно показать, что базис не может содержать более четырех функций.
Таким образом, для задания логических функций формулами можно исполь-зовать разные языки – разные полные системы функций. Какой именно из языков является более удобным, зависит от характера рассматриваемой задачи.
С понятием полноты тесно связано понятие замыкания и замкнутого класса.
Определение. Множество логических функций называется замкнутым классом, если любая суперпозиция функций из этого множества снова принадлежит ему.
Рассмотрим основные замкнутые классы логических функций:
Тo – класс всех логических функций f( x1,…, xn ), сохраняющих ноль, т.е. для которых выполняется равенство:
f( 0, …, 0 ) = 0.
Легко видеть, что функции 0, x, x
& y, x 
y, x 
y принадлежат классу To, а функции 1,
не
принадлежат ему. В таблице задания функции из класса Toзначение функции равно 0 для первой строки. Из таблицы 1.2
видно, что таких функций двух переменных ровно половина. Следовательно, логических функций
от n переменных принадлежащих этому классу будет
/
2.