Контрольная работа: Исчисления предикатов и их применение в логическом умозаключении

Для получения новых формул из аксиом, равно как уже из выведенных формул используются правила и формулы исчисления высказываний, а также следующие правила.

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

a₁ ) В формуле переменную, обозначающую высказывание, можно заменить любой формулой при условии, что эта замена происходит одновременно во всех местах, в которых встречается данная переменная, обозначающая высказывание, и что при этом вообще снова получается формула. Замена допустима лишь в том случае, если подставляемая формула не содержит предметной переменной, встречающейся в исходной формуле в связанном виде.

a₂ ) Свободная предметная переменная может быть заменена другой предметной переменной при условии, что замена происходит одновременно во всех местах в которых встречается эта свободная переменная. Подставляемая переменная не должна, кроме того, встречаться где-либо связанной в первоначальной формуле.

a₃ ) В формуле j ( F) содержащей переменный предикат F от n предметных переменных он может быть заменен формулой y содержащей по меньшей мере n свободных предметных переменных если свободные предметные переменные в y не встречаются в j в связанном виде и если в результате получается формула.

b) Схема заключения

Из формул вида j и j ® y , получаем новую формулу y .

g)Схема для кванторов

g₁ ) Пусть формула j ® y такова, что j не содержит предметную переменную х , а формула y содержит ее. Тогда, если формула j ® y выводима, то выводима и формула j ® " х y (х).

g₂ ) При тех же самых условиях относительно вида формул j и y получаем из y (х) ® j новую формулу $ х y (х) ® j .

d) Правила переименования связанных переменных

Связанную предметную переменную, встречающуюся в формуле, можно заменить другой связанной переменной. Эту замену следует производить во всех местах области действия и в соответствующем знаке общности и существования. При этом предполагается, что после такой замены вообще снова получается формула. Если переменная, которая должна быть заменена, встречается одновременно в нескольких кванторах (с различными областями действия), то замену следует производить только относительно одной области.

Рассмотрим теперь несколько примеров вывода формул из аксиом a), b), c), d), e), f) .

Докажем формулу p→ " x(p Ú F(x))

Доказательство:

р ® рÚq (аксиома в)

р ® рÚ F(х) (посредством подстановки)

р ®"х (рÚ F(х)) (по правилу g)

Докажем формулу:

" х F(х) ® $ х F(х)

Доказательство:

"х F(х) ® F(у) (аксиома e)

F(у) ®$х F(х) (аксиома f)

Подставим теперь в формулу (29) (р ® q) ® ((r ® р) ® ( r ® q)) вместо р выражение F(у), вместо q выражение$ х F(х), вместо r выражение " х F(х). Получаем: (F(у) ® $ х F(х)) ® ( " х F(х) ® F(у)) ® ( " х F(х) ® $ х F(х)).

Применяя, правило 5 с учетом этой формулы и двух приведенных выше формул получаем: " х F(х) ® $ х F(х).

4. НАТУРАЛЬНОЕ УЗКОЕ ИСЧИСЛЕНИЕ ПРЕДИКАТОВ

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

Основными правилами вывода в натуральном исчислении предикатов являются:

1. Все основные правила вывода исчисления высказываний.