Исчисления предикатов ИП (ИПС)




Определим исчисление предикатов гильбертовского типа ИП. Это исчисление является расширением исчисления высказываний ИВ.

В алфавит ИВ добавим строчные латинские буквы для обозначения предметных переменных и символы кванторов " и $. Язык исчисления составляют формулы, определяемые также, как в алгебре предикатов.

Аксиоматика исчисления дополняется двумя схемами аксиом:

11.

12. ,

где - произвольная формула, содержащая свободные вхождения переменной x, причем ни одно из них не находится в области действия квантора по переменной y, а получена из заменой свободных вхождений x на y.

К правилу заключения ИВ добавляются два правила, связанные с кванторами. Пусть и – формулы, которые содержат и не содержат свободные вхождения переменной x соответственно.

2. Правило обобщения (введения ")

.

3. Правило введения $

.

Правила естественного вывода дополняются 4-мя правилами. Пусть

14. Правило введения квантора ".

Если T |- U (x), то T |- " x U (x).

15. Правило удаления квантора ".

Если T |- " x U (x), то T |- U (y).

16. Правило введения квантора $.

Если T |- U (y), то T |- $ x U (x).

17. Правило удаления квантора $.

Если T, U (x) |- V, то T, $ x U (x) |- V.

Рассмотрим пример вывода в ИП.

Доказать, что в ИП |-

1. |-  
2. |- 15 (1)
3. |- 14 (2)

Исчисление предикатов генценовского типа ИПС строится расширением исчисления ИП.

Прикладные исчисления предикатов

Прикладные исчисления предикатов строятся добавлением к исчислению предикатов своих собственных аксиом. Причем, в прикладных исчислениях предикатов вводится понятие терма. Термами являются:

1) предметные переменные и константы;

2) предметные функции.

В аксиомах прикладных исчислений предикатов наряду с предметными переменными могут использоваться произвольные термы, так аксиомы 11, 12 в них имеют вид:

11')

12') ,

где t – произвольный терм.

Всюду далее будут рассматриваться прикладные исчисления предикатов первого порядка, т. е. исчисления, в которых кванторами связываются только предметные переменные, а не предикаты и функции.

Исчисление с равенством.

В данном исчислении вводится предикат =, а к аксиомам ИП добавляются аксиомы равенства.

E1.

E2.

Здесь Е1 является аксиомой, а Е2 – схемой аксиомы, где – произвольная формула, а – формула, полученная из заменой некоторых вхождений x на y.

Теорема 6.1. В любой теории с равенством:

1) |- для любого терма t;

2) |- ;

3) |- .

Доказательство. 1) Данное утверждение непосредственно следует из аксиом 11’ и Е1, где .

Для свойств 2), 3) построим формальные выводы формул.

2)

1. |- Е2
2. |- 6 (1)
3. |- Е1
4. |- 3 (2, 3)
5. |- 5 (4)

3)

1. |- Е2
2. |- 1, где ,
3. |- 6 (2)
4. |- Теорема исчисления с равенством
5. |- 4 (4, 3)
6. |- 5 (5)

Строгий частичный порядок.

Предикатом строгого частичного порядка является предикат <, а дополнительными – следующие аксиомы.

NE1.

NE2.


Формальная арифметика.

Формальная арифметика определяется как исчисление с равенством на предметном множестве ô, в котором вводятся предметная константа 0 и предметные функции +, ×, ¢, задаваемые аксиомами.

A1.

A2.

A3.

A4.

A5.

A6.

A7.

A8.

Здесь А1-А7 – аксиомы, а А8 – схема аксиомы, определяющая доказательство по индукции.



Поделиться:




Поиск по сайту

©2015-2024 poisk-ru.ru
Все права принадлежать их авторам. Данный сайт не претендует на авторства, а предоставляет бесплатное использование.
Дата создания страницы: 2017-03-31 Нарушение авторских прав и Нарушение персональных данных


Поиск по сайту: