Полнота и замкнутость
Пример. Доказать полноту системы { 
, x1 
x2 }.
Доказательство проводится аналогично предыдущему примеру, учитывая, что:
x1 & x2 =
.
Замечания:
1). С точки зрения функциональной полноты систему функций первого примера можно считать
избыточной, т.е. она сохраняет свойство полноты и при удалении из нее операции &
или .
2). Однако за не избыточностью полученных при этом систем приходится платить избыточностью формул.
Пример. Доказать полноту систем F1 = { x1 / x2 } и F2 = { x1“ x2}.
Данные системы будут полные, т.к. отрицание, дизъюнкция и конъюнкция выражаются через функции этих систем следующим образом:
= x /
x = x “
x, x1 x2 =
= (
x1 “ x2 ) “ (
x1 “ x2 ),
x1 &
x2 = 
= ( x1 / x2 ) / ( x1 / x2 ).
Пример. Доказать полноту системы {
x & y, x
y, 1 }.
Так как = x1 получим, что функции полной
системы {, x & y }
выражаются через функции данной системы. Следовательно, эта система так же полная