Описание систем основных операций

Будем понимать под системой основных операций такие системы операций, что все остальные операции через них выражаются. У нас уже имеется несколько примеров систем основных операций. Кроме того, в предыдущих двух пунктах мы доказали, что наборы , нельзя принять за системы основных операций. При этом мы получили необходимые условия на такие системы; они обязательно должны содержать нелинейные и немонотонные операции. Замечательно, что в таких же терминах можно дать необходимые и достаточные условия. Мы сделаем это не в самой общей ситуации. Будем говорить, что для системы операций выполняется предположение 0I, если эта система содержит 0 и I.

Теорема Поста. Систему операций, удовлетворяющую предположению 0I, можно принять за систему основных операций тогда и только тогда, когда она содержит немонотонную и нелинейную операции.

Имеется общая формулировка теоремы Поста для любых систем (без предположения 0I); при этом число условий возрастает.

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

Достаточность будет следовать из двух приводимых ниже задач.

Задача 1. Докажите, что в предположении 0I из всякой немонотонной операции можно получить операцию дополнения.

Пусть — немонотонная операция и в входит долька, отвечающая , а долька, отвечающая , не входит. Тогда, если на j-м месте и в и стоит 0, то вместо подставляем пустое множество, если же и тут и там стоит 1, то подставляем универсальное множество . На остальных местах, поскольку , в стоит 0, а в . Подставим вместо этих одно и то же множество . Тогда долька, отвечающая , превратится в , а долька, отвечающая , - в . Операция , которая получится в результате, будет совпадать с , так как содержит и не содержит .

Задача 2. Докажите, что в предположении 0I через всякую нелинейную операцию и дополнение можно выразить пересечение.

Основные понятия комбинаторики