Дискретная математика

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

• Часть 1
• | 2
• | 3
• | 4

            Определение полноты системы функций в 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

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

предыдущаяследующая