Контрольная работа: Исчисления предикатов и их применение в логическом умозаключении
Вместо " х Р(х ) пишут просто` " х Р(х);
Вместо $ х Р(х) пишут просто ` $ х Р(х).
Из самого смысла знаков общности и существования получаются следующие эквивалентности:
$ х Р(х) º ` " х ` Р(х) (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(х)