Проблема разрешимости для логики предикатов - Контрольная работа

бесплатно 0
4.5 82
Доказательство теоремы, позволяющей решить проблему разрешимости (выполнимости) для формул исчисления высказываний, содержащих предикаты, зависящие от одного переменного. Представление равносильности в виде тождественно истинной формулы для любого поля.


Аннотация к работе
Проблема разрешимости - эта проблема ставится для формул исчисления предикатов, лишенных символов постоянных предметов и символов индивидуальных предикатов. Если такая формула истинна для некоторого поля 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. Практика по решению проблемы разрешимости формул, содержащих предикаты от одного переменного

Литература
Заказать написание новой работы



Дисциплины научных работ



Хотите, перезвоним вам?