Теории первого порядка (К)

Символы.

Счетное множество переменных.

Конечное или счетное множество функциональных букв.

Конечное или счетное (но непустое) множество предикатных букв.

Логические аксиомы:

(К1).

(К2).

(К3).

(К4). , где есть формула теории, а - терм теории, свободный для в . В частности, если совпадает с ,

(К5). , если формула не содержит свободных вхождений .

Два правила вывода: МП и Gen

Generalization: правило обобщения: из следует .

В каждой частной теории могут быть собственные аксиомы.

Пример вывода в теории К:

(1). - гипотеза

(2). - (К4)

(3). - 1,2 - МП

(4). - (К4)

(5). - 3,4 - МП

(6). - Gen

(7). - Gen

Некоторые свойства теорий первого порядка:

1. Если формула теории К есть частный случай тавтологии, то она является теоремой теории и может быть выведена из (1)-(3) с использованием лишь МП.

2. Всякое исчисление предикатов первого порядка (К) непротиворечиво.

3. Теорема Дедукции неверна, например: , однако не всегда.

4. Если и существует вывод, построенный без применения правила обобщения к свободным переменным формулы , то - аналог теоремы дедукции.

5. Если замкнута и , то - частный случай аналога теоремы дедукции.

6. Всякая теорема теории К логически общезначима.

7. Во всяком исчислении предикатов первого порядка теоремами являются все те и только те формулы, которые логически общезначимы (Теорема Геделя о полноте).

В качестве примера:

Дата добавления: 2013-12-13; Просмотров: 339; Нарушение авторских прав?; Мы поможем в написании вашей работы!