Cтраница 2
В клетках таблицы Поста ставится плюс или минус, в зависимости от того, входит функция, стоящая в данной строке, в класс, стоящий в данном столбце, или не входит. Для полноты системы функций необходимо и достаточно ( в силу теоремы Поста), чтобы в каждом столбце стоял бы хотя один минус. [16]
Небольшой по объему, но очень важный § 3 посвящен закону двойственности в алгебре логики. Задачи 3.10 и 3.11 имеют вспомогательный характер: они понадобятся в § 6 при доказательстве теоремы Поста. [17]
В силу ( а), предикат Pf рекурсивен относительно F, л х, следовательно, ввиду рекурсивности а. F и, наконец, относительно F0, который выразим, в экзистенциальной однокванторной форме. Поэтому, 6 силу одной теоремы Поста ( теорема XI § 58), Pf выразим в обеих двукванторных формах теоремы V, что и требовалось доказать. [18]
Теперь обсудим вопрос о существенности условий теоремы Поста. Все рассмотренные в этой задаче системы не полны, так как для каждой из них в таблице имеется столбец, состоящий сплошь из плюсов. Заметим, что для каждой системы имеется ровно по одному такому столбцу, причем для разных систем эти столбцы разные. Отсюда следует, что в условии теоремы Поста нельзя отбросить ни одного из пяти классов. Действительно, для каждого из классов можно указать систему содержащихся в нем функций ( а значит, не полную), в которой для каждого из остальных четырех классов имеется функция, ему не принадлежащая. [19]
В связи с этим сужается класс схем, реализующих функции алгебры логики. Одновременно приходится применять элементы нового типа - элементы задержки, необходимые для выравнивания времени прихода сигналов на входы функциональных элементов. Всюду в дальнейшем делается предположение о том, что время срабатывания одно и то же для всех основных элементов. Это довольно обременительное ограничение сильно упрощает наши рассмотрения. При учете времени срабатывания элементов теорема Поста уже не дает ответа на вопрос об условиях полноты системы функциональных элементов. Решение этой проблемы при указанных выше предположениях дается в задачах 8.7 - 8.11. Отметим, что в ответе фигурируют множества, уже не являющиеся функционально замкнутыми классами относительно обычной суперпозиции. [20]