Исчисления предикатов и их применение в логическом умозаключении
ПЛАН
Предикаты и кванторы.
Понятие формулы исчисления предикатов.
Аксиоматическое представление узкого исчисления предикатов.
Натуральное узкое исчисление предикатов.
Погружение аристотелевской силлогистики в узкое исчисление предикатов.
5. Расширенное исчисление предикатов.
Литература
1. ПРЕДИКАТЫ И КВАНТОРЫ
Исчисление высказываний образует основную часть математической логики. Но оно не составляет достаточного базиса для анализа всех правил рассуждений, потому что оставляет в стороне внутреннюю структуру высказываний. Исчисление предикатов преследует цель расширить наши представления о правилах правильных рассуждений на основании учета внутренней структуры высказываний.
Анализ содержания высказываний таких как «Роза-растение», «ав», «Точка А лежит между точками В и С» и др. позволяет сделать вывод, что в высказываниях речь идет о том, что предметы, указанные в высказываниях, обладают какими-то свойствами или находятся в каких-то отношениях. Ту часть высказывания, в которой говорится о свойствах или отношениях принято считать предикатом, если имена предметов, которые обладают этими свойствами или отношениями, заменены переменными, принимающими значения из множества самого общего вида. Так что предикат зависит не только от того, о каких свойствах или отношениях идет речь, но и от переменных. Например, из высказывания «Роза растение» получается предикат «х - растение», из высказывания «ав» - предикат «ху», а из высказывания «Точка А лежит между точками В и С» - предикат «Точка Х лежит между точками Y и Z».
Если обозначить ту часть высказываний, в которой говорится о свойствах или отношениях большими латинскими буквами Р, Q, R, … с индексами или без них, а переменные – традиционно малыми латинскими буквами х, y, z ,… с индексами или без них, то обозначение предиката примет вид Р (х), Q(х,у), L(х,y,z) и т.д. Число n переменных или аргументов, от которых зависит предикат называется n -местностью предиката, так что можно говорить об одноместном предикате, двухместном и т.д.
Запись предиката Р (х), Q(х,у) и т.д. ничем не отличается от записи математической функции. Но это не только случайное совпадение. Если подставлять в предикаты имена предметов, эти имена традиционно обозначаются малыми латинскими буквами а, в, с, d,… с индексами или без них, то предикаты превращаются в высказывания истинные или ложные. Так если Р (х) считать записью предиката «х - растение», то, подставляя вместо х имена «Роза», «Лилия» получаем истинное высказывание «Роза - растение», «Лилия - растение». Если же вместо х подставить имена «камень», «железо» - то ложное высказывание «камень -растение», «железо - растение». Обозначив через «0» «ложь», а через «1» «истину», получаем из предиката Р (х>1>, х>2>, …, х>п>) двухзначную функцию, аргументы которой принимает значение из множества самого общего вида.
При подстановке в предикат, вместо переменных имен предикатов он превращается в высказывание. Так что предикат, скажем предикат Р(х), можно рассматривать записью некоторого множества высказываний, мощность которого равна мощности множества значений аргумента.
В логике наряду с подстановкой, превращающей предикат в высказывание, используются и другая операция, делающая это. Эта операция заключается в связывании переменных, входящих в предикат, кванторами. Применяются кванторы двух видов: квантор общности, его обычно обозначают символом , и читается он «для всех», «для любого», «все», и квантор существования, он обозначается и читается «существует такое». Высказывание (х) Р(х) читается : «Для всех х Р(х)» или «Для любого х Р(х)». Высказывание х Р(х) читается: «Существует такое х, что Р(х)» или «Для некоторых х Р(х)».
Следует еще раз подчеркнуть, что заменять в предикате переменную, к которой относится квантор, на имена предметов, чтобы превратить предикат в высказывание, не имеет смысла. Такая переменная считается связанной. Переменные предикаты, не связанные кванторами, называются свободными.
Если Р (х>1>, х>2>, …, х>п>) – n-местный предикат и m его переменных (m n) связываются кванторами, то он превращается в (n-m) местный предикат.
Кванторы общности и существования могут употребляться комбинировано. Порядок употребления кванторов в многоместных предикатов играет существенную роль. Например для двухместного предиката Р(х,у) мы имеем следующие простейшие формы составления: >х >>у >Р(х,у) – читать эту формулу следует так: «Для всех х и для всех у имеет место отношение Р(х,у)».
>х >>у >Р(х,у) «Существует некоторое х и некоторое у, для которых имеет место Р(х,у)».
>х>>у >Р(х,у) – «Существует такое х, которое к каждому у находится в отношении Р(х,у)».
>х>>у >Р(х,у) – «Для каждого х существует некоторое у, такое, что имеет место Р(х,у)».
В выражении >х >>у >Р(х,у) знаки общности могут быть переставлены без изменения смысла высказывания. То же самое имеет место в выражении >х >>у >Р(х,у).
Напротив, в выражении >х>>у >Р(х,у) порядок следования знаков>х>> >и >у>> >играет существенную роль. Например, высказывание >х>>у >(х<у) – «Для каждого числа х существует число у такое, что х меньше у – истинно». Но если мы переставим в этом высказывании знаки >х>> >и >у>, то получим высказывание >у >>х >(х<у) – «Существует число у, которое больше любого числа х», - которое ложно. Так что порядок следования в комбинациях кванторов общности и существования, и обратно, перед предикатом играет важную роль.
2. ПОНЯТИЕ ФОРМУЛЫ ИСЧИСЛЕНИЯ ПРЕДИКАТОВ
Как уже говорилось, запись предиката можно рассматривать как множество высказываний. Из предикатов получаются высказывания при замене (подстановке) переменных постоянными или посредством связывания их кванторами. Так что предикаты можно соединять между собой и с высказываниями теми же связками «¯», «», «», «», «», которые приняты в исчислении высказываний, получая формулы исчисления предикатов. Более точно понятие формулы исчисления предикатов (коротко формулы) определяется следующим образом:
Переменное высказывание есть формула.
Предикаты являются формулами.
Е
сли
есть формула,
то - формула.
Если и какие-то формулы, причем одна и та же переменная не встречается связной внутри одной формулы и свободной, внутри другой, то , , , суть формулы.
Если (х) означает какую-то формулу, в которой переменная х выступает в качестве свободной переменной, то >х> (х) и >х> (х) суть формулы. То же самое справедливо для других свободных переменных.
Значит, согласно пункту 5. Одна и та же переменная не встречается в формуле одновременно в свободной и связанной форме.
Для экономии скобок вводятся следующие соглашения: знаки , , , разделяют выражение сильнее, чем знаки общности и существования. Например, выражение >х> F(х) р, является более простым способом записи выражения (>х> F(х)) р. Прежнее соглашение, что знак связывает теснее, чем знаки , , , знак - связывает теснее, чем знаки и , знак теснее, чем остается в силе.
Далее, ко всякому встречающемуся в формуле знаку общности или существования принадлежит часть формулы, к которой он относится. Эту часть формулы заключают в скобки, помещая перед ними соответствующий знак. Так, в формуле >х> (F(х) >у >G(у)) область действия знака простирается до конца формулы. В формуле >х> F(х) >у >G(у) – лишь до знака .
Дальнейшее уменьшение количества скобок достигается с помощью следующего правила: если несколько знаков общности или существования следуют непосредственно друг за другом, не будучи разделенными скобками, то это всегда нужно понимать так, что, их область действия простирается до одного и того же места. Например, выражение:
>х>>у>>z >(Р(х,у,z) Q(у,z)) R(u) есть более простая запись выражения
>х> (>у> (>z >(Р(х,у,z) Q(у,z)))) R(u).
Для удобства обозначений формул принимаются еще и следующие соглашения:
В
место Р(х)
пишут просто Р(х);
В
место >х>
Р(х) пишут просто>х>
Р(х);
Вместо >х>
Р(х) пишут просто >х>
Р(х).
Из самого смысла знаков общности и существования получаются следующие эквивалентности:
>х> Р(х) >х>Р(х) (33)
>х>Р(х) >х> Р(х) (34)
>х> Р(х) >х>Р(х) (35)
>х>Р(х) >х> Р(х) (36)
На основании этих содержательных соотношений можно заменять квантор существования квантором общности и наоборот, а значит, при построении исчисления предикатов обойтись лишь одним квантором.
Проиллюстрируем представления в символической форме высказываний. Предполагая, что переменные пробегают множество людей, применим следующие соглашения
М(х): х есть мужчина;
V (х): х есть женщина;
J (х,у): х моложе, чем у;
R (х,у): х есть ребенок у;
G (х,у): х состоит в браке с у;
K (х): х живет в Киеве;
L (х): х живет в Луганске.
Представим в символической форме следующее высказывание: «Каждый человек имеет отца и мать». Оно будет иметь вид:
(>х >(>у> (М(у) R (х,у)) >z> (V (z) R (х, z)))).
3. АКСИОМАТИЧЕСКОЕ ПРЕДСТАВЛЕНИЕ УЗКОГО ИСЧИСЛЕНИЯ ПРЕДИКАТОВ
В исчислении высказываний проблема разрешимости состояла в решении вопроса, является ли данная сложная функция высказывания, представляемая формулой исчисления высказываний, тождественно истинной, выполнимой или тождественно ложной. В этом исчислении метод таблиц и метод приведения к совершенным нормальным формам давал эффективный способ решения этого вопроса. И это потому, что каждому атомарному высказыванию приписывалось лишь два значения.
В узком исчислении предикатов проблема разрешимости состоит в постановке аналогичного вопроса: является ли сложная, функция, которая представляется формулой исчисления предикатов тождественно истинной при любых значениях переменных и любых предикатах, выполнимой, или тождественно ложной. Воспользоваться методом таблиц в узком исчислении предикатов уже нельзя. Например, по определению высказываниехР(х) эквивалентно конъюнкции высказываний Р(а) Р(в) Р(с) … Эта конъюнкция истинна, если и только если истинны все высказывания Р(а), Р(в), … Однако в тех случаях, когда переменная х в Р(х) пробегает бесконечную предметную область, установить истинное значение каждого из высказываний Р(а), Р(в) и т.д. не всегда удается. А это значит, что вопрос об истинностном значении формулы хР(х) или формулы, содержащей хР(х) может оставаться открытым.
Итак, проблема разрешимости в исчислении предикатов представляет собой очень трудную и в целом отнюдь не решенную проблему. И даже можно считать безнадежными попытки дать ее полное решение. Но в виду центрального значения проблемы большой интерес представляют попытки дать ее решение хотя бы для возможно более широких классов формул. Один из таких классов представляется аксиоматическим представлением исчисления предикатов.
Существуют разные эквивалентные системы аксиом узкого исчисления предикатов. Одна из них, предложенная Гильбертом в качестве аксиом содержит четыре аксиомы исчисления высказываний:
р р р
р рq
рq q р
(р q) ( r р rq)
К этим аксиомам присоединяются еще две аксиомы для кванторов и
х F(х) F(у)
F(у) х F(х)
Первая из этих аксиом читается так: «Если предикат F выполняется для всех х, то он выполняется также для любого у». Вторая аксиома читается так: «Если предикат F выполняется для какого-то у, то существует х, для которого выполняется F».
Для получения новых формул из аксиом, равно как уже из выведенных формул используются правила и формулы исчисления высказываний, а также следующие правила.
Правило подстановки.
>1> В формуле переменную, обозначающую высказывание, можно заменить любой формулой при условии, что эта замена происходит одновременно во всех местах, в которых встречается данная переменная, обозначающая высказывание, и что при этом вообще снова получается формула. Замена допустима лишь в том случае, если подставляемая формула не содержит предметной переменной, встречающейся в исходной формуле в связанном виде.
>2> Свободная предметная переменная может быть заменена другой предметной переменной при условии, что замена происходит одновременно во всех местах в которых встречается эта свободная переменная. Подставляемая переменная не должна, кроме того, встречаться где-либо связанной в первоначальной формуле.
>3> В формуле F) содержащей переменный предикат F от n предметных переменных он может быть заменен формулой содержащей по меньшей мере n свободных предметных переменных если свободные предметные переменные в не встречаются в в связанном виде и если в результате получается формула.
) Схема заключения
Из формул вида и , получаем новую формулу .
)Схема для кванторов
>1>) Пусть формула такова, что не содержит предметную переменную х, а формула содержит ее. Тогда, если формула выводима, то выводима и формула х (х).
>2>) При тех же самых условиях относительно вида формул и получаем из (х) новую формулу х (х) .
) Правила переименования связанных переменных
Связанную предметную переменную, встречающуюся в формуле, можно заменить другой связанной переменной. Эту замену следует производить во всех местах области действия и в соответствующем знаке общности и существования. При этом предполагается, что после такой замены вообще снова получается формула. Если переменная, которая должна быть заменена, встречается одновременно в нескольких кванторах (с различными областями действия), то замену следует производить только относительно одной области.
Рассмотрим теперь несколько примеров вывода формул из аксиом a), b), c), d), e), f).
Докажем формулу p→x(pF(x))
Доказательство:
р рq (аксиома в)
р р F(х) (посредством подстановки)
р х (р F(х)) (по правилу )
Докажем формулу:
х F(х) х F(х)
Доказательство:
х F(х) F(у) (аксиома e)
F(у) х F(х) (аксиома f)
Подставим теперь в формулу (29) (р q) ((rр) ( rq)) вместо р выражение F(у), вместо q выражениех F(х), вместо r выражение х F(х). Получаем: (F(у) х F(х)) (х F(х) F(у)) (х F(х) х F(х)).
Применяя, правило 5 с учетом этой формулы и двух приведенных выше формул получаем: х F(х) х F(х).
НАТУРАЛЬНОЕ УЗКОЕ ИСЧИСЛЕНИЕ ПРЕДИКАТОВ
В натуральном узком исчислении предикатов определение формулы исчисления предикатов такое же, как и в аксиоматическом представлении узкого исчисления предикатов.
Основными правилами вывода в натуральном исчислении предикатов являются:
Все основные правила вывода исчисления высказываний.
Правила введения и удаления кванторов общности и существования.
Для записи схем правил введения и удаления кванторов общности и существования можно пользоваться символом (х/), обозначающем выражение, полученное из подстановкой вместо именной переменной х выражения при выполнении следующих условий:
В выражении замена переменной х производится лишь в тех местах, где она свободна. Если х входит в несколько раз, то столько же раз она заменяется выражением .
Если в переменная х находится в области действия квантора, связывающую предметную переменную z, то вместо х не подставляется выражение содержащее z в качестве свободной переменной. Короче говоря, подстановку следует производить так, чтобы свободные переменные подставляемого выражения не оказались связанными в выражении, полученном в результате подстановки.
Если это правило нарушается, то можно получить ложное высказывание. Так, в выражении m (m>n) переменная m связана, а переменная n свободна. Если мы вместо n подставим m+1, то получим ложное выражение: m (m> m+1).
Правило удаление квантора общности:
У
.
Примером рассуждения по правилу У:
.
Правило введения квантора общности:
В
применяется лишь при условии, что
переменная х не входит в качестве
свободной в допущение косвенного
доказательства.
Примером рассуждения по правилу
В:
.
Правило введение квантора существования :
В
.
Примером рассуждения по правилу В:
2 – четное и простое число
х (х –
четное и простое).
Правило удаления квантора существования:
У
,
где у>1>, …у>n>> >- все свободные именные переменные выражения , отличные от переменной х, а выражение (х/σ у>1>, …у>n>) – результат подстановки в выражение постоянной σ, отмеченной индексами у>1>, …у>n>> >вместо х. Заметим, что переменные у>1>, …у>n>, входящие в выражение σ у>1>, …у>n> рассматриваются в качестве свободных. Поэтому выражение σ у>1>, …у>n> можно подставлять в выражение вместо переменной х тогда, и только тогда, когда эта переменная не находится в области действия квантора, связывающего переменные у>1>, …у>п>>.>
В качестве примеров вывода формул в натуральном узком исчислении предикатов рассмотрим вывод аксиом e),f), а также формул (37), (38).
е) х F(х) F(у)
Доказательство:
х F(х) Допущение
F(у) У: 1
f) F(у) х F(х)
Доказательство:
F(у) Допущение
х F(х) В: 1
Докажем формулу (37):
рх (р F(х))
Доказательство:
р Допущение
р F(х) ВД: 1
х р F(х) В: 2
Докажем теперь формулу (38):
х F(х) х F(х)
Доказательство:
х F(х) Допущение
2) F(у) У: 1
х F(х) В: 2
5. ПОГРУЖЕНИЕ АРИСТОТЕЛЕВСКОЙ СИЛЛОГИСТИКИ В УЗКОЕ ИСЧИСЛЕНИЕ ПРЕДИКАТОВ
В логике Аристотеля и его последователей вплоть до конца ХІХ столетия основная роль приписывалась четырем видам суждений, называемым категорическими А, Е, I, О. Символические суждение А «Все S суть Р» записывается так:
х (S(х) Р(х)) (39)
Суждение Е «Никакое S не есть Р» :
х (S(х) Р(х)) (40) или по другому х (S(х) (х)) (401 )
Суждение I «Некоторые S суть Р»:
х (S(х) Р(х)) (41)
Суждение О «Некоторые S не суть Р»:
х (S(х) (х)) (42)
Докажем некоторые модусы непосредственных умозаключений.
Модус АSР ISР, пользуясь (39)-(42) запишем так:
х (S(х) Р(х)) х (S(х) Р(х)) (43)
Доказательство:
х (S(х) Р(х)) Допущение
S(у) Р(у) У: 1
S(у) Допущение
Р(у) ПО: 2,3
S(у) Р(у) ВК: 3,4
х (S(х) Р(х)) В: 5
Модус ЕSРОSР опять-таки с помощью (39-42) записываем так:
х (S(х) (х)) х (S(х) (х)) (44)
Доказательство:
х (Sх (х)) Допущение
х (S(х) (х)) (S(у) (у)) подстановка в аксиому е)
S(у) (у) ПО: 1,2
S(у) Допущение
(у) ПО: 3,4
S(у) (у) ВК: 4,5
х S(х) (х) В: 6
Модус АSР IРS записываем в виде:
х (Sх (х)) х (S(х) (х)) (45)
Доказательство:
х (S(х) (х)) Допущение
х (S(х) (х)) (S(у) (у)) подстановка в аксиому е)
S(у) (у) ПО: 1,2
S(у) Допущение
(у) ПО: 3,4
S(у) (у) ВК: 4,5
х S(х) (х) В: 6
Аналогично записываются и доказываются остальные модусы непосредственных умозаключений.
Докажем теперь справедливость некоторых модусов силлогизмов.
Используя (39)-(42), записываем первый модус первой фигуры силлогизма АМРАSМАSР так:
х (М(х)Р(х)) х (S(х) → М(х)) →х(S(х) →Р(х)) (46)
Доказательство:
х (М(х)Р(х)) х (S(х) → М(х)) Допущение
х (М(х)Р(х)) УК: 1
х (S(х) → М(х)) УК: 1
М(у)Р(у) У: 2
S(у) М(у) У: 3
S(у) Р(у) (29): 4,5
х(S(х) →Р(х)) В: 6
Докажем справедливость первого модуса второй фигуры силлогизма
ЕРМ АSМ→ЕSР.
Используя (39)-(42), записываем его в виде:
х (Р(х) М(х)) х (S(х) → М(х)) →х(S(х) →Р(х)) (47)
Доказательство:
х (Р(х) М(х)) х (S(х) → М(х)) Допущение
х (Р(х) М(х)) УК: 1
х (S(х) → М(х)) УК: 1
Р(у)М(у) У: 2
S_ (у) М(у) У: 3
М(у)Р(у) (30): 4
М(у)Р(у) (9): 6
S (у)Р(у) (29): 5,7
х(S(х) →Р(х)) В: 8
Наконец, докажем первый модус третьей фигуры силлогизма
АМРАSМ→ІSР.
Используя (39)-(42), записываем его в виде:
х (М(х)Р(х)) х (М(х)→S(х)) →х(S(х) Р(х))
Доказательство:
х (М(х)Р(х)) х (М(х)→S(х)) Допущение
х (М(х)Р(х)) УК: 1
х (М(х)→S(х)) УК: 1
М(у) Р(у) У: 2
М(у) S (у) У: 3
М(у) Допущение
S (у) ПО: 5,6
Р(у) ПО: 4,5
S (у) Р(у) ВК: 7,8
х(S(х) Р(х)) В: 9
6. РАСШИРЕННОЕ ИСЧИСЛЕНИЕ ПРЕДИКАТОВ
В узком исчислении предикатов переменные являются пропозициональные переменные, именные переменные и переменные представляющие предикаты. В формулах этого исчисления кванторы связывают только именные переменные. Это исчисление явно не завершено. Например, формула х (Р(х)Р(х)) выполняется для любого предиката Р. значит, мы должны располагать квантором общности для предиката. С другой стороны формула хF(х) явно не общезначима. Но она выполняется для некоторых F. Чтобы выразить это мы должны располагать и кванторами существования для предиката, и выполнимость этой формулы записать так: F хF(х).
Исчисление предикатов, получаемое посредством применения квантора общности и квантора существования не только к предметным переменным, но и к переменным предикатам, принято называть расширенным исчислением предикатов. Очевидно, что все правила узкого исчисления предикатов распространяются как на расширенное исчисление предикатов, так и на любую систему, получаемую присоединением к расширенному исчислению предикатов каких угодно аксиом и новых правил образования истинных формул. Справедливость этого ясна, так как все аксиомы и правила вывода исчисления предикатов, на основании которых выведены производные правила, во всех случаях сохраняются.
Смешение символов для разных формул не может произойти, так как из контекста, обычно, видно, в каком формализме выводится та или иная формула.
Расширенное исчисление предикатов и полученные из него некоторые системы посредством добавления к его аксиомам аксиом специальной структуры дали возможность получить очень важные результаты в теории множеств, геометрии, арифметике, теории алгоритмов и во многих других областях. Однако как показали К. Гедель и др., проблема разрешимости в таких системах становится очень запутанной. И все дело в том, что, формализуя словесный оборот «все» с помощью квантора мы пытаемся заключить бесконечное в конечные рамки. Но при этом мы можем рассчитывать лишь на частный успех.
Алгоритмическая неразрешимость расширенного исчисления предикатов, формализованной теории множеств, формализованной арифметики и других формальных систем лишний раз доказывает, что математика не является нанизыванием силлогизмов в направлении, избранном наугад. Алгоритмическая неразрешимость показывает, что математическое исследование включает в себя интуицию, догадку, воображение и другие элементы творчества!
Литература
Логическое суждение. Руфулаев О.Н. К. – 2005 г.
Логика – исскуство мышления. Тимирязев А.К.– К. 2000 г.
Философия и жизнь – журнал- К. 2004 г.
История логики и мышления – Касинов В.И. 1999.
Логика и человек – М. 2000.
Философия жизни. Матюшенко В.М. – Москва – 2003 г.
Философия бытия. Марикова А.В. – К. 2000 г.