АКСИОМАТИЧЕСКОЕ ПРЕДСТАВЛЕНИЕ УЗКОГО ИСЧИСЛЕНИЯ ПРЕДИКАТОВ
В исчислении высказываний проблема разрешимости состояла в решении вопроса, является ли данная сложная функция высказывания, представляемая формулой исчисления высказываний, тождественно истинной, выполнимой или тождественно ложной. В этом исчислении метод таблиц и метод приведения к совершенным нормальным формам давал эффективный способ решения этого вопроса. И это потому, что каждому атомарному высказыванию приписывалось лишь два значения.
В узком исчислении предикатов проблема разрешимости состоит в постановке аналогичного вопроса: является ли сложная, функция, которая представляется формулой исчисления предикатов тождественно истинной при любых значениях переменных и любых предикатах, выполнимой, или тождественно ложной. Воспользоваться методом таблиц в узком исчислении предикатов уже нельзя. Например, по определению высказывание" хР(х) эквивалентно конъюнкции высказываний Р(а) Ù Р(в) Ù Р(с) Ù … Эта конъюнкция истинна, если и только если истинны все высказывания Р(а), Р(в), … Однако в тех случаях, когда переменная х в Р(х) пробегает бесконечную предметную область, установить истинное значение каждого из высказываний Р(а), Р(в) и т.д. не всегда удается. А это значит, что вопрос об истинностном значении формулы " хР(х) или формулы, содержащей " хР(х) может оставаться открытым.
Итак, проблема разрешимости в исчислении предикатов представляет собой очень трудную и в целом отнюдь не решенную проблему. И даже можно считать безнадежными попытки дать ее полное решение. Но в виду центрального значения проблемы большой интерес представляют попытки дать ее решение хотя бы для возможно более широких классов формул. Один из таких классов представляется аксиоматическим представлением исчисления предикатов.
|
|
|
Существуют разные эквивалентные системы аксиом узкого исчисления предикатов. Одна из них, предложенная Гильбертом в качестве аксиом содержит четыре аксиомы исчисления высказываний:
a) р Ú р ® р
b) р ® рÚq
c) рÚq ®qÚ р
d) (р ® q) ®( rÚ р® rÚq)
К этим аксиомам присоединяются еще две аксиомы для кванторов " и $
e) "х F(х) ®F(у)
f) F(у) ®$х F(х)
Первая из этих аксиом читается так: «Если предикат F выполняется для всех х, то он выполняется также для любого у». Вторая аксиома читается так: «Если предикат F выполняется для какого-то у, то существует х, для которого выполняется F».
Для получения новых формул из аксиом, равно как уже из выведенных формул используются правила и формулы исчисления высказываний, а также следующие правила.
a) Правило подстановки.
a1) В формуле переменную, обозначающую высказывание, можно заменить любой формулой при условии, что эта замена происходит одновременно во всех местах, в которых встречается данная переменная, обозначающая высказывание, и что при этом вообще снова получается формула. Замена допустима лишь в том случае, если подставляемая формула не содержит предметной переменной, встречающейся в исходной формуле в связанном виде.
|
|
|
a2) Свободная предметная переменная может быть заменена другой предметной переменной при условии, что замена происходит одновременно во всех местах в которых встречается эта свободная переменная. Подставляемая переменная не должна, кроме того, встречаться где-либо связанной в первоначальной формуле.
a3) В формуле j ( F) содержащей переменный предикат F от n предметных переменных он может быть заменен формулой y содержащей по меньшей мере n свободных предметных переменных если свободные предметные переменные в y не встречаются в j в связанном виде и если в результате получается формула.
b) Схема заключения
Из формул вида j и j ® y , получаем новую формулу y.
g)Схема для кванторов
g1) Пусть формула j ® y такова, что j не содержит предметную переменную х, а формула y содержит ее. Тогда, если формула j ® y выводима, то выводима и формула j ® " х y (х).
|
|
|
g2) При тех же самых условиях относительно вида формул 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(х).
Дата добавления: 2019-07-15; просмотров: 158; Мы поможем в написании вашей работы! |
Мы поможем в написании ваших работ!