Навигация
АКСИОМАТИЧЕСКОЕ ПРЕДСТАВЛЕНИЕ УЗКОГО ИСЧИСЛЕНИЯ ПРЕДИКАТОВ
23161
знак
0
таблиц
0
изображений
3. АКСИОМАТИЧЕСКОЕ ПРЕДСТАВЛЕНИЕ УЗКОГО ИСЧИСЛЕНИЯ ПРЕДИКАТОВ
В исчислении высказываний проблема разрешимости состояла в решении вопроса, является ли данная сложная функция высказывания, представляемая формулой исчисления высказываний, тождественно истинной, выполнимой или тождественно ложной. В этом исчислении метод таблиц и метод приведения к совершенным нормальным формам давал эффективный способ решения этого вопроса. И это потому, что каждому атомарному высказыванию приписывалось лишь два значения.
В узком исчислении предикатов проблема разрешимости состоит в постановке аналогичного вопроса: является ли сложная, функция, которая представляется формулой исчисления предикатов тождественно истинной при любых значениях переменных и любых предикатах, выполнимой, или тождественно ложной. Воспользоваться методом таблиц в узком исчислении предикатов уже нельзя. Например, по определению высказывание"хР(х) эквивалентно конъюнкции высказываний Р(а) Ù Р(в) Ù Р(с) Ù… Эта конъюнкция истинна, если и только если истинны все высказывания Р(а), Р(в), … Однако в тех случаях, когда переменная х в Р(х) пробегает бесконечную предметную область, установить истинное значение каждого из высказываний Р(а), Р(в) и т.д. не всегда удается. А это значит, что вопрос об истинностном значении формулы "хР(х) или формулы, содержащей "хР(х) может оставаться открытым.
Итак, проблема разрешимости в исчислении предикатов представляет собой очень трудную и в целом отнюдь не решенную проблему. И даже можно считать безнадежными попытки дать ее полное решение. Но в виду центрального значения проблемы большой интерес представляют попытки дать ее решение хотя бы для возможно более широких классов формул. Один из таких классов представляется аксиоматическим представлением исчисления предикатов.
Существуют разные эквивалентные системы аксиом узкого исчисления предикатов. Одна из них, предложенная Гильбертом в качестве аксиом содержит четыре аксиомы исчисления высказываний:
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(х).
4. НАТУРАЛЬНОЕ УЗКОЕ ИСЧИСЛЕНИЕ ПРЕДИКАТОВ
В натуральном узком исчислении предикатов определение формулы исчисления предикатов такое же, как и в аксиоматическом представлении узкого исчисления предикатов.
Основными правилами вывода в натуральном исчислении предикатов являются:
Похожие работы
типов формул, однако, проблема разрешимости решается. Мы рассмотрим наиболее важный тип формул, для которых решение проблемы разрешимости может быть осуществлено, это формулы логики предикатов, зависящие от одного переменного. Основные понятия Пусть M - некоторое множество предметов и a, b, c, d - какие-то определённые предметы из этого множества. Тогда высказывания об этих предметах мы ...
... что предмету не присуще некоторое свойство. Объединенная классификация простых категорических суждений по количеству и качеству. В каждом суждении имеется количественная и качественная характеристика. Поэтому в логике применяется объединенная классификация суждений по количеству и качеству, на основе которой выделяются следующие 4 типа суждений: 1. суждение А общеутвердительное. Его ...
... названием "Prolog", а внутри него ярлык на файл "Prolog.exe" с названием "Prolog with databases", ярлык на help-файл и на файл "readme.txt". 3.3 Руководство пользователя программы интерпретатора языка Пролог 3.3.1 Запуск программы Запуск программы можно произвести несколькими способами. Нажать кнопку "Пуск", выбрать в меню пункт "Программы", выбрать пункт "Prolog". После того, как ...
... , искусственным формализованным языкам. В логике правильным способом рассуждения является такой, который никогда не приводит от истинных предпосылок к ложным заключениям. Это требование вводит в соприкосновение логику как теорию вывода с семантикой. Вывод считается корректным тогда и только тогда, когда условия истинности его предпосылок составляют подмножество условий истинности его заключений. ...
0 комментариев