Полнота и замкнутость
3. Система Поста: { 
, max ( x,y
) } является полной.
4. Система: { V
(x,y) } – полная. Вопрос о ее полноте может быть легко све-
ден к полноте системы 3.
В k – значных логиках исследование произвольной системы функций на полно-ту сопряжено с большими техническими трудностями: использование критерия полно-
ты, основанного на рассмотрении всех предполных классов в P, даже при k = 3 и 4
требует проверки весьма значительного числа условий т.к. в P
существует ровно 18,
а в P
– ровно 82 предполных классов. Доказательство полноты конкретных
систем
в P проводится обычно методом сведения к заведомо полным системам.
С понятием полноты связано понятие замыкания и замкнутого класса, определе-ния которых аналогичны соответственным определениям для двузначной логики.
Приведем примеры замкнутых классов.
1. Класс P
, очевидно,
является замкнутым.
2. Пусть e 
E. Обозначим через T
множество всех функций
f (x
, …, x
)