Исчисления предикатов и их применение в логическом умозаключении (стр. 1 из 3)
ПЛАН
1. Предикаты и кванторы.
Понятие формулы исчисления предикатов.
2. Аксиоматическое представление узкого исчисления предикатов.
3. Натуральное узкое исчисление предикатов.
4. Погружение аристотелевской силлогистики в узкое исчисление предикатов.
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. ПОНЯТИЕ ФОРМУЛЫ ИСЧИСЛЕНИЯ ПРЕДИКАТОВ
Как уже говорилось, запись предиката можно рассматривать как множество высказываний. Из предикатов получаются высказывания при замене (подстановке) переменных постоянными или посредством связывания их кванторами. Так что предикаты можно соединять между собой и с высказываниями теми же связками «¯», «Ù», «Ú», «®», «º», которые приняты в исчислении высказываний, получая формулы исчисления предикатов. Более точно понятие формулы исчисления предикатов (коротко формулы) определяется следующим образом:
1. Переменное высказывание есть формула.
2. Предикаты являются формулами.
3.
Если j есть формула, то j - формула.4. Если j и y какие-то формулы, причем одна и та же переменная не встречается связной внутри одной формулы и свободной, внутри другой, то jÙy, jÚy, j®y, jºy суть формулы.
5. Если j (х) означает какую-то формулу, в которой переменная х выступает в качестве свободной переменной, то "хj (х) и $хj (х) суть формулы. То же самое справедливо для других свободных переменных.
Значит, согласно пункту 5. Одна и та же переменная не встречается в формуле одновременно в свободной и связанной форме.
Для экономии скобок вводятся следующие соглашения: знаки Ù, Ú, ®, º разделяют выражение сильнее, чем знаки общности и существования. Например, выражение "х F(х) Ù р, является более простым способом записи выражения ("х F(х)) Ù р. Прежнее соглашение, что знак Ù связывает теснее, чем знаки Ú, ®,º, знак Ú - связывает теснее, чем знаки ®иº, знак ® теснее, чем º остается в силе.
Далее, ко всякому встречающемуся в формуле знаку общности или существования принадлежит часть формулы, к которой он относится. Эту часть формулы заключают в скобки, помещая перед ними соответствующий знак. Так, в формуле "х (F(х) ®$у G(у)) область действия знака" простирается до конца формулы. В формуле "х F(х) ®$у G(у) – лишь до знака ®.
Дальнейшее уменьшение количества скобок достигается с помощью следующего правила: если несколько знаков общности или существования следуют непосредственно друг за другом, не будучи разделенными скобками, то это всегда нужно понимать так, что, их область действия простирается до одного и того же места. Например, выражение:
"х$у"z (Р(х,у,z) Ù Q(у,z))Ù R(u) есть более простая запись выражения
"х ($у ("z (Р(х,у,z) Ù Q(у,z))))Ù R(u).
Для удобства обозначений формул принимаются еще и следующие соглашения:
Вместо Р(х) пишут просто `Р(х); 
Вместо "х Р(х) пишут просто`"х Р(х); 
Вместо $х Р(х) пишут просто `$х Р(х).Из самого смысла знаков общности и существования получаются следующие эквивалентности: