2.5. Полнота и замкнутость

Определение полноты системы функций в k- значной логике аналогично соот-

ветствующему определению в двузначной логике.

Определение. Система функций f , …, f из P называется (функционально)

полной, если любая функция из P может быть записана в виде формулы через функ-ции этой системы.

Для обоснования полноты системы функций в k – значной логике можно так же

использовать принцип сведения задачи о полноте других систем, применяемый п.1.7.

Приведем некоторые примеры полных систем в k – значной логике.

1. Множество всех функций из P является полной системой.

2.Система Россера-Туркетта:

{0, 1, …, k-1, J (x),…, J (x), min(x,y), max(x,y)}

– полная система в P .

Действительно, для произвольной функции из P справедливо равенство (2.4),

правая часть которого состоит из функций данной системы, т.е. любая функция из P

выражается через эти функции.

3. Система Поста: { , max ( x,y ) } является полной.

3. Система: { V (x,y) } – полная. Вопрос о ее полноте может быть легко све-

ден к полноте системы 3.

В k – значных логиках исследование произвольной системы функций на полно-ту сопряжено с большими техническими трудностями: использование критерия полно-

ты, основанного на рассмотрении всех предполных классов в P , даже при k = 3 и 4

требует проверки весьма значительного числа условий т.к. в P существует ровно 18,

а в P – ровно 82 предполных классов. Доказательство полноты конкретных систем

в P проводится обычно методом сведения к заведомо полным системам.

С понятием полноты связано понятие замыкания и замкнутого класса, определе-ния которых аналогичны соответственным определениям для двузначной логики.

Приведем примеры замкнутых классов.

1. Класс P , очевидно, является замкнутым.

2. Пусть e E . Обозначим через T множество всех функций f (x , …, x )

из P сохраняющих e, т.е. таких, что f (a , …, a ) e, если a e, ( i = 1, …, n). Класс T очевидно, является замкнутым.

3. Множество всех линейных функций из P образует замкнутый класс линей-

ных функций, который обозначается через L ( или L ). Этот класс отличен от P при любом k > 2.

4. Множество всех функций из P , представимых полиномами по модулю k,

является замкнутым классом в P .

Понятие замкнутого класса может быть приложено к решению вопроса об обос-новании неполноты некоторых систем.

Пример. Доказать, что система M = { ~x, max (x,y) } не является полной.

Пусть e = { 0, (k-1) }. Так как обе функции системы сохраняют e, то [M] T . Поскольку при k > 2, e ≠ E , то T не содержит, например константу 1. Значит при

k > 2 M не будет полной системой.

На этом примере видно, что хотя данная система и является обобщением полной

cистемы { , x y } булевых функций, она не является полной.

Предыдущий материал показывает, что во многом k – значные логики похожи на двузначную логику. В них сохраняются многие результаты, имеющие место в дву-

значной логике. Однако есть и существенные отличия в этих логиках. Приведем некоторые из них.

Для двузначной логики имеем:

1. Каждый замкнутый класс имеет конечный базис.

2. Мощность множества всех замкнутых классов в P счетная.

3. Всякая логическая функция в P может быть записана в виде полинома по модулю 2.

Для k – значной логики имеем:

1. Существуют в P замкнутые классы не имеющие конечного базиса.

2. Мощность множества всех замкнутых классов в P равна континууму.

3. Всякая логическая функция в P может быть записана в виде полинома по

модулю k в том и только в том случае, когда k – простое число.