Доказательство теоремы, позволяющей решить проблему разрешимости (выполнимости) для формул исчисления высказываний, содержащих предикаты, зависящие от одного переменного. Представление равносильности в виде тождественно истинной формулы для любого поля.
Аннотация к работе
Проблема разрешимости - эта проблема ставится для формул исчисления предикатов, лишенных символов постоянных предметов и символов индивидуальных предикатов. Если такая формула истинна для некоторого поля M и некоторых предикатов, на нем определенных, мы будем называть ее выполнимой. Если формула истинна для данного поля M и для всех предикатов, определенных на M, мы будем называть ее тождественно истинной для поля M. Если формула истинна для всякого поля M и для всяких предикатов, будем называть ее тождественно истинной или просто истинной. Легко показать, что если формула U тождественно истинна, то формула ложна, и наоборот.P(a) обозначает высказывание о предмете a, Q(b) - высказывание о предмете b, R(c, d) - высказывание о предметах c и d и т.д. Формулы, в которых из операций алгебры высказываний имеются только операции , и , а знаки отрицания относятся только к элементарным предикатам и высказываниям, будем называть приведенными формулами. Если две формулы U и B, отнесенные к некоторому полю M, при всех замещениях переменных предикатов, переменных высказываний и свободных предметных переменных соответственно индивидуальными предикатами, определенными на M, индивидуальными высказываниями и индивидуальными предметами из M, принимают одинаковые значения И или Л, то мы будем говорить, что эти формулы равносильны на поле M. Покажем, что если для некоторого поля M существуют индивидуальные предикаты ,..., , для которых формула U( ,..., ) истинна, то эта формула истинна и на некотором подмножестве этого поля, содержащем не более элементов, так как иначе наше утверждение тривиально. Множество всех этих элементов обозначим .докажем, что если формула U( , ..., ) истинна на поле M, то она истинна и на поле (так как - часть поля M, то предикаты определены на ). каждому элементу x поля M поставим в соответствие элемент из , принадлежащий тому же классу, что и х.
План
Содержание
Введение
1. Основные понятия
2. Логика предикатов с одним переменным
3. Практика по решению проблемы разрешимости формул, содержащих предикаты от одного переменного