Полнота логических функций. Теорема дедукции. Свойства формальных теорий (логических систем). Равносильные формулы логики предикатов, страница 6

4.1) Правило отделения (modus pones)

                                                           ├а, ├ав

├в

4.2) Правило подстановки

├а

                                                           ├а)

4.3) Правило сложной подстановки

├а

├а)

            4.4)                                               ├а

├а^’

4.5) Правило введения квантора всеобщности

                                                                    ├ва()

├в а()

4.6)  Правило введения квантора существования

в не содержит .

                                   ├а()в

├а()в^’

Опр.

Часть формулы И.П. называется её подформулой, если :

а) Если а – элементарная формула, тогда а – её подформула (она же сама)

б)  а(),  а()           - формула   а(),  а(),а() – подформула + подформула а.

в) а , а&в , ав , ав  - формулы И.П.  они сами и а и в – подформулы и  подформулы а и в.

Замечание 1.

Если предметную переменную заменить везде на , то формула а() даст а^’().

Замечание 2.

В формуле И.П. свободные переменные отличаются от связанных переменных (это противоречии пункту 2.4)).

Замечание 3.

Если один квантор стоит в поле действия другого квантора, то переменные, которые они связывают различны.

 по Замечанию 1. всё равно получим формулу И.П.

Определим операцию подстановки в И.П. :

1)

2)

3) , где   не совпадают с (.

4)

5) Если определена подстановка :

, где а и в формулы не содержащие одинаковые переменные.

 - пропозициональная переменная, то

 а())а())

6) а)а())=а())

7) а()),в)а&в)= а)& в).

            8)а)= а)

9) а), в) а&в)= а)& в)

10) а)= в)

Причём обязательно должно выполняться :

а)  Не существует переменной в):

 - свободная в а и связанная в в и наоборот.

б) А и Р(…) стоит в поле действия некоторого квантора в формуле а, то эта связанная     переменная этого квантора не содержится в в.

в)  - не содержатся в а, а содержатся только в в,  соответствует переменной, стоящей на i- м месте в предикате.

Пр.

1)       

Тогда :

2)  - формула.

Можно заменить х на z частично :

 - формула.

3)  -формула.

Если заменить х на z, то нужно заменить везде, где встречается х.

 - не формула, т.к. в поле действия квантора  она связана квантором . (не может переменная находиться в поле действия самой себя)

4)  - не формула, т.к. одна переменная в формуле связанная и свободная.

5) Подстановка :

Пусть

Мы хотим

в –должна содержать 2 свободные переменные.

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

Опр.

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

<> , такое что

1)  Х – алфавит, состоит из следующих переменных :

1.1) Предметные константы : а, в, …

1.2) Предметные переменные : x, y, z,…

1.3) Предикаты : …

1.4) Функторы : …              , где n, m – местность.

1.5) Логические связки : &,…

1.6) “ ( “, “ ) “, “ , “ – дополнительные символы.

2) Ф – множество формул.

Терм – а) либо константа, либо предметная переменная.

б)  - термы - терм (функция, где n – местность)

2.1) Элементарные формулы  , где  - предикат,  - термы.

2.2) а – формула, содержащая свободную переменную х, то а, а – формулы, где х – свободная переменная.

2.3) а,в – формулыа , а&в , ав , ав  - тоже формулы.

3) А – множество аксиом.

3.1)- 3.11)

3.12) , где t – терм.

3.13)

4) R – множество правил вывода.

4.1)                   в, ва

 М.П.  :    а

4.2)                    в а()

 :    в а()

4.3)                 а()в

                                    :      а()в

I.  Теория равенств

Выведем предикат =

х=у

            =(х,у)            

)   (

)  

     II.        Теория частичного порядка

Выведем предикат

                                             

Свойство рефлексивности :

                       

Свойство транзитивности :

        III. Теория Пеано (формальной арифметики)

Выделяют особенно : 0

Вводят 3 функтора : ‘ , “ , “’

’ 0)

x’=y’)

 x’=y’)

0=x)

y’=(x+y)’)

0=0)

            ’