Cтраница 1
Теорема Поста показывает, что перечислимое неразрешимое множество ( которое мы еще построим) обязательно имеет неперечисли-мое дополнение. [1]
По теореме Поста теория Т разрешима. [2]
В теореме Поста содержатся условия на систему функций, необходимые и достаточные для того, чтобы суперпозициями входящих в нее функций были представимы все функции алгебры логики. Основной материал содержится в задачах 6.1 - 6.21; в задачах 6.22 - 6.27 содержится дополнительный материал. Основным является понятие функционально замкнутого класса ( определение 6.2) - класса функций, замкнутого относительно суперпозиции. [3]
Ясно, что теорема Поста позволяет выяснить вопрос о том, является ли полная система базисом. Это опять-таки удобно делать при помощи таблиц Поста. [4]
Этот факт называют теоремой Поста. [5]
Как это вытекает из теорем Поста и Жегалкина, в алгебре логики мы имеем следующие ответы на поставленные вопросы. [6]
Теперь обсудим вопрос о существенности условий теоремы Поста. Все рассмотренные в этой задаче системы не полны, так как для каждой из них в таблице имеется столбец, состоящий сплошь из плюсов. Заметим, что для каждой системы имеется ровно по одному такому столбцу, причем для разных систем эти столбцы разные. Отсюда следует, что в условии теоремы Поста нельзя отбросить ни одного из пяти классов. Действительно, для каждого из классов можно указать систему содержащихся в нем функций ( а значит, не полную), в которой для каждого из остальных четырех классов имеется функция, ему не принадлежащая. [7]
Пусть система т булевых функций удовлетворяет условиям теоремы Поста. [8]
Сейчас мы сделаем некоторые общие замечания о базисах, следующие из теоремы Поста. [9]
Отождествляя переменные, упростить функции изФ с тем, чтобы они по-прежнему удовлетворяли условиям теоремы Поста. [10]
Следовательно, к функции / достаточно присоединить не более трех булевых функций, чтобы выполнить условия теоремы Поста о функциональной полноте. [11]
Предположим, что существует базис JF, состоящий более чем из четырех функций. По теореме Поста тогда получаем, что Т, состоит ровно из пяти функций, каждая из которых не принадлежит ровно одному классу Поста. Это означает, что / не является самодвойственной функцией, что противоречит предположению. [12]
Если некоторый функционально замкнутый класс Т не содержится ни в одном из указанных пяти классов, то для каждого из них в Т найдется функция, ему не принадлежащая. Но тогда по теореме Поста Т содержит все функции алгебры логики. [13]
Из сказанного выше ясно, что система Л, V, - i является полной. Ответ на вопрос о полноте произвольной системы Т дает теорема Поста, формулируемая ниже. [14]
В § 12 дается краткий обзор логики предикатов. В упражнениях фигурирует несколько задач, решавшихся при доказательстве теоремы Поста ( их можно опустить) и некоторые примеры из анализа. Этот параграф занимает особое место. Все предыдущие рассмотрения так или иначе связаны с понятием логической операции, и соответственно высказывания рассматриваются при фиксированной ситуации; в § 12 исследуется зависимость высказывания от ситуации. [15]