Т. А. Сливина математическая логика и теория алгоритмов

2. Проблема полноты.
Определение 1. Теория Т называется абсолютно полной, если для любого высказывания S этой теории или S или есть теорема.
Это определение учитывает то обстоятельство, что любое высказывание S теории Т будучи интерпретированной в некоторой модели оказывается или истинным, или ложным. Но тогда или S, или должно быть теоремой в теории Т.
Теория, являющаяся одновременно непротиворечивой и полной, будет максимальной в отношении непротиворечивости – в том смысле, что добавление к такой теории в качестве аксиомы любого предложения, которое можно сформулировать в этой теории, но не являющегося ее теоремой, приводит к противоречивой теории.
Отметим, что для многих математических теорий наличие одновременно обоих качеств (непротиворечивости и полноты) не имеет места.
Определение 2. Аксиоматическая теория называется полной в узком смысле если добавление к ее аксиомам любого недоказуемого в ней утверждения с сохранением в ней всех правил вывода приводит к противоречивой теории. Всякая абсолютно полная теория будет полна и в узком смысле. Действительно, пусть некоторая абсолютно полная теория не полна в узком смысле. Тогда найдется такое утверждение U этой теории, недоказуемое в ней, что новая теория, построенная на основе прежних аксиом и утверждения U в качестве новой аксиомы, непротиворечива. Тогда U принадлежит новой теории. Кроме того, в связи с абсолютной полнотой исходной теории и недоказуемостью в ней утверждения U будет доказуемо утверждение . Таким образом, в новой теории оказались доказуемыми U и , т.е. получили противоречие.
3. Проблема разрешимости.
Проблема разрешимости является алгоритмической проблемой, в которой для заданного множества А требуется построить алгоритм, разрешающий А относительно другого множества В, включающего А(АВ)\, т.е. такой алгоритм U, который применим ко всякому элементу из В, причем U(x) = 1, если х  А и U(x) = 0, если х В\А. Простейшим примером проблемы разрешимости является проблема разрешимости алгебры логики, в которой она состоит в отыскании алгоритма, позволяющего для каждой формулы алгебры логики установить, является ли она или тождественно истинной, или тождественно ложной, или выполнимой. Важным классом алгоритмических проблем является проблема разрешимости для формальных теорий, то есть проблема разрешимости для множества всех доказуемых (выводимых) в теории формул (множество А) относительно множества всех формул теории (множество В). Выше она была рассмотрена для аксиоматической теории исчисления высказываний


Глава 5
АЛГОРИТМЫ

С появлением ЭВМ стала актуальной теория алгоритмов. Теорию алгоритмов можно понимать как науку пограничную между математикой и информатикой. В этой главе рассматриваются определения алгоритма, его свойства, представлены две формальные модели алгоритмов: машина Тьюринга и рекурсивные функции, примеры позволят студентам и всем интересующимся лицам овладеть определенным кругозором теоретических знаний и практических навыков.