Исчисления предикатов и их применение в логическом умозаключении (стр. 2 из 3)
$х Р(х) º`"х`Р(х) (33)
$х`Р(х) º`"х Р(х) (34)
`$х Р(х) º"х`Р(х) (35)
`$х`Р(х) º"х Р(х) (36)
На основании этих содержательных соотношений можно заменять квантор существования квантором общности и наоборот, а значит, при построении исчисления предикатов обойтись лишь одним квантором.
Проиллюстрируем представления в символической форме высказываний. Предполагая, что переменные пробегают множество людей, применим следующие соглашения
М(х): х есть мужчина;
V (х): х есть женщина;
J (х,у): х моложе, чем у;
R (х,у): х есть ребенок у;
G (х,у): х состоит в браке с у;
K (х): х живет в Киеве;
L (х): х живет в Луганске.
Представим в символической форме следующее высказывание: «Каждый человек имеет отца и мать». Оно будет иметь вид:
("х ($у (М(у) Ù R (х,у)) Ù$z (V (z) Ù R (х, z)))).
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. НАТУРАЛЬНОЕ УЗКОЕ ИСЧИСЛЕНИЕ ПРЕДИКАТОВ
В натуральном узком исчислении предикатов определение формулы исчисления предикатов такое же, как и в аксиоматическом представлении узкого исчисления предикатов.
Основными правилами вывода в натуральном исчислении предикатов являются:
1. Все основные правила вывода исчисления высказываний.
2. Правила введения и удаления кванторов общности и существования.
Для записи схем правил введения и удаления кванторов общности и существования можно пользоваться символом j (х/w), обозначающем выражение, полученное изj подстановкой вместо именной переменной х выражения w при выполнении следующих условий:
1) В выражении j замена переменной х производится лишь в тех местах, где она свободна. Если х входит в j несколько раз, то столько же раз она заменяется выражением w.
2) Если в j переменная х находится в области действия квантора, связывающую предметную переменную z, то вместо х не подставляется выражение содержащее z в качестве свободной переменной. Короче говоря, подстановку следует производить так, чтобы свободные переменные подставляемого выражения не оказались связанными в выражении, полученном в результате подстановки.
Если это правило нарушается, то можно получить ложное высказывание. Так, в выражении $m (m>n) переменная m связана, а переменная n свободна. Если мы вместо n подставим m+1, то получим ложное выражение: $m (m> m+1).
Правило удаление квантора общности:
У" 
.
Примером рассуждения по правилу У":
.
Правило введения квантора общности:
В" 
применяется лишь при условии, что переменная х не входит в качестве свободной в допущение косвенного доказательства.
Примером рассуждения по правилу
В": 
.
Правило введение квантора существования :
В$ 
.
Примером рассуждения по правилу В$:
2 – четное и простое число
$х (х – четное и простое).Правило удаления квантора существования:
У$ 
,
где у1, …уn- все свободные именные переменные выражения j, отличные от переменной х, а выражение j(х/σ у1, …уn) – результат подстановки в выражение j постоянной σ, отмеченной индексами у1, …уnвместо х. Заметим, что переменные у1, …уn, входящие в выражение σу1, …уn рассматриваются в качестве свободных. Поэтому выражение σу1, …уn можно подставлять в выражение j вместо переменной х тогда, и только тогда, когда эта переменная не находится в области действия квантора, связывающего переменные у1, …уп.