2.4.4. Критерий полноты

Теорема (Поста). Для того чтобы система функций была полна, необходимо и достаточно, чтобы множество не являлось подмножеством ни одного из классов Поста.

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

Функции	Классы Поста
…	…	…	…	…	…

В ячейках таблицы ставится знак «+» или «–», в зависимости от того, входит функция, стоящая в данной строке, в класс, стоящий в данном столбце, или не входит. В силу теоремы Поста для полноты системы необходимо и достаточно, чтобы в каждом столбце стоял хотя бы один минус.

Таблицу Поста лучше заполнять по столбцам. Вначале рассматриваем класс . Если окажется подмножеством (первый столбец таблицы заполнен только плюсами), то система неполна. В противном случае переходим к классу и т.д.

Упражнение 2.42. Используя критерий полноты, выяснить, полна ли система :

а) ; б) ;

в) ; г) .

◄ а) Для удобства рассуждений зададим функции системы таблично.

0	0	0	0	0
0	0	1	0	1
0	1	0	0	0
0	1	1	0	1
1	0	0	0	0
1	0	1	0	1
1	1	0	1	1
1	1	1	1	1

0	0	1	0
0	1	0	0
1	0	0	1
1	1	1	0

Класс : ; .

Класс : ; ;

.

Класс : .

Класс : перебрав все пары сравнимых векторов, убеждаемся, что условие монотонности для функции не нарушается, следовательно ; , а , следовательно, .

Класс : .

Функции	Классы Поста
	+	+	–	+	–
	–	+		–
		–

Таким образом, не является подмножеством ни одного из классов Поста, следовательно, - полная система.

б) Класс : .

Класс : ; .

Класс : .

Класс : , а , следовательно, .

Класс : ; .

Функции	Классы Поста
	–	+	–	–	+
		–			+

Таким образом, - подмножество , следовательно, система неполна.

в) и г) решите самостоятельно. ►

Определение. Система функций называется базисом, если:

1. -полна;

2. любое собственное подмножество неполно.

Упражнение 2.43. Укажите подмножества , являющиеся базисами:

а) ; б) ;

в) ; г) .

◄ а) Мы уже рассматривали систему в упражнении 2.42. Чтобы выделить из этой полной системы базисы, заполним таблицу Поста до конца.

Функции	Классы Поста
	+	+	–	+	–
	–	+	–	–	+
	+	–	–	–	–

Из таблицы видно, что сама система базисом не является, так как имеет собственное полное подмножество . Это полное подмножество является базисом, поскольку не имеет собственных полных подмножеств. Остальные собственные подмножества базисами не являются ( неполно, так как лежит в ; неполно, так как лежит в ; очевидно, что неполны и подмножества, содержащие по одной функции).

б) Заполним таблицу Поста:

Функции	Классы Поста
	+	+	–	+	–
	+	+	–	+	–
	–	–	+	–	+

По этой таблице легко установить, что система полна, но базисом не является, так как имеет два полных собственных подмножества и . Оба эти полные подмножества являются базисами, так как их собственные подмножества, состоящие каждое из одной функции, полными не являются ( , , ).

в) и г) решите самостоятельно. ►