Исчисление предикатов

Исчисления высказываний заведомо недостаточно для того, чтобы в его рамки уложить "всю" математику. Чего нам не хватает? Мы часто используем такие обороты как "через любые две различные точки можно провести единственную прямую". Здесь задействованы такие языковые средства, как обороты "для любого" ("для любых", "для всех") и "существует" (в неявной форме). Эти фундаментальные средства присутствуют при рассмотрении логики предикатов. То есть сейчас помимо логических связок мы будем использоватьлогические кванторы, а именно квантор всеобщности, обозначаемый далее через A (за неимением опять-таки подходящих шрифтов) и квантор существования, обозначаемый далее черезE. Эти обозначения происходят от английских слов "All" и "Exists"; обычно их записывают в перевёрнутом виде (букву "A" располагают "вверх ногами", букву "E" разворачивают "зубчиками" влево).

По сравнению с исчислением высказываний, мы сейчас отказываемся от символов для высказывательных переменных. Высказывания у нас появятся, но в ином облике. Это будут некоторые высказывания об изучаемых объектах, в роли которых может выступать что угодно -- числа, точки, прямые, множества. Для того, чтобы говорить об объектах, нам будут нужны переменные другого сорта. Они называются предметными переменными и содержательно могут обозначать какие угодно предметы, но с формальной точки зрения они суть некие символы. Мы их будем обозначать в привычной форме: чаще всего -- буквами из конца латинского алфавита вроде x, y, z (возможно, с индексами).

Далее, изучаемые нами объекты могут обладать некоторыми свойствами. Например, число может быть или не быть простым, множество может быть или не быть пустым. Для обозначения свойств вводятся специальные символы (заглавные буквы, также с индексами или без). Например, тот факт, что предмет x обладает свойством P, будет обозначаться в виде P(x). Помимо свойств отдельных объектов, в математике возникают свойства пар объектов. Например, прямая a может быть параллельна прямой b; число x может быть больше числа y, и так далее. Такого рода свойства будут записываться в форме Q(a,b), R(x,y) и так далее. Запись вида E(x,y), может, например, обозначать тот факт, что объекты x и y равны. Отдельными объектами и парами объектов дело не ограничивается. Допустим, мы хотим сказать, что сумма двух чисел равна третьему. Для этого мы вводим свойство S для тройки объектов. Запись S(x,y,z) будет при этом выражать собой тот факт, что x+y=z. Аналогично можно записывать в виде П(x,y,z) тот факт, что xy=z. При этом высказывания S(2,3,5) и П(2,3,6) становятся истинными, а высказывания S(2,3,6) и П(2,3,5) -- ложными.

Заглавные буквы, которые мы использовали выше, называются предикатными символами, потому что они служат обозначениями неких свойств (предикатов). Каждый предикатный символ имеет свою специфику в зависимости от числа идущих вслед за ним переменных. В примерах выше P будет считаться одноместным предикатом, Q, R, E -- двуместными, а S и П --трёхместными предикатными символами. Ограничений на количество мест, вообще говоря, нет. Можно рассматривать n-местные предикатные символы для любого целого положительного n, причём считать также, что запас таких символов для каждого n в принципе ничем не ограничен.

Часто при изложении этого материала привлекают так называемые функциональные символы, то есть специальные буквы для выражения математических операций. Скажем, через f(x,y) можно обозначить сумму чисел x+y. Функциональные символы отличаются от предикатных тем, что значением выражения f(x,y) является предмет (число, множество и т.д.), а двуместный предикат P(x,y) на данных объектах x, y будет принимать (при фиксированной интерпретации) значение "истина" или "ложь". Мы намеренно отказываемся от функциональных символов, так как вместо рассмотрения двуместного символа f достаточно привлечь трёхместный предикатный символ S, для которого S(x,y,z) означает, что f(x,y)=z. Такой подход сильно упрощает дело, так как становится ненужным давать длинное определение математических выражений (термов). Помимо этого, мы отказываемся также и от часто используемых предметных констант, служащих для обозначения фиксированных объектов. Предметные константы можно считать нульместными функциональными символами, поэтому вместо них рассматриваются одноместные предикатные символы. Скажем, можно ввести предметную константу 0 для обозначения нуля, но можно ввести предикатный символ Z и писать Z(x), если мы хотим выразить ту мысль, что объект x представляет собой не что иное как ноль.

Отметим также, что мы рассматриваем здесь так называемое чистое исчисление предикатов, то есть не используем знака равенства в качестве символа языка. Это удобно, например, при помещении в данный контекст формальной теории множеств, где за основу берётся всего один двуместный предикатный символ P для отношения принадлежности, и при этом запись P(x,y) содержательно означает, что объект x принадлежит множеству y. Равенство множеств стандартным образом определяется через принадлежность.

Нелишне также при этом добавить, что все известные содержательные математические теории (алгебра, топология, арифметика, анализ, теория вероятностей и др.) можно излагать на теоретико-множественном материале. То есть в этом смысле в теорию множеств как бы "укладывается" вся современная математика.

Таким образом, мы выбираем как бы "минимальную" версию, то есть привлекаем минимум "строительного материала", достаточного для формального выражения тех или иных утверждений самого разного вида из самых разных областей математики.

Дадим теперь определение формулы исчисления предикатов. Прежде всего, атомарной формулой будет называться любая запись вида P(x_1,...,x_n), где P есть n-местный предикатный символ, а x_1,...,x_n -- предметные переменные, не обязательно различные. Скажем, можно писать E(x,x), S(x,y,z), П(x,x,y). (Последняя запись содержательно выражает тот факт, что y -- это x "в квадрате".) Атомарные формулы играют ту же роль, что в исчислении высказываний играли высказывательные переменные p, q, r и им подобные. Из уже имеющихся формул разрешается строить новые при помощи логических связок и кванторов. С логическими связками дело обстоит точно так же, как и раньше. То есть для любой формулы Ф можно рассмотреть её отрицание (Ф), а для любых формул Ф1 и Ф2 можно рассмотреть формулу (Ф1 * Ф2), где * есть конъюнкция, дизъюнкция, импликация или эквиваленция (точнее, символ, её обозначающий). С кванторами дело обстоит очень просто. Если Ф -- произвольная формула, а x -- произвольная предметная переменная, то разрешается, как это принято говорить, "навешивать" на формулу Ф любой из двух кванторов по переменной x. Это приводит к одной из двух формул: (Ax)Ф и (Ex)Ф. Первая содержательно означает, что при любом значении x выполняется условие Ф (как правило, как-то зависящее от x), а вторая -- что существует некоторое значение x такое, что выполнено Ф.

Правила образования более сложных формул из более простых можно применять последовательно и в любом порядке конечное число раз. Всякая формула строится в соответствии с этими правилами. Сейчас мы приведём пример формулы, содержательно выражающей справедливость сочетательного закона сложения, то есть равенства (x+y)+z=x+(y+z), справедливого для любых чисел x, y, z. Нам здесь потребуется только трёхместный предикатный символ S(x,y,z), выражающий отношение x+y=z, а символ для отношения равенства даже не потребуется.

Нам будут нужны дополнительные обозначения: u для x+y, v для y+z и w для общего результата (т.е. для x+y+z в обоих вариантах). Содержательно мы имеем равенства x+y=u, y+z=v, u+z=w, x+v=w. Таким образом, сочетательный закон утверждает, что для любых x,y,z найдутся такие u,v,w, что будут выполняться одновременно четыре равенства, выписанные выше. Это приводит к такой формуле: (Ax)(Ay)(Az)(Eu)(Ev)(Ew)(S(x,y,u)&S(y,z,v)&S(u,z,w)&S(x,v,w)).

Говоря о формулах, мы должны определить очень важное понятие, которое сейчас будет рассмотрено на примере. Пусть Ф есть формула (Ax)P(x,y) -> (Ez)S(y,z,w). В смысл написанной формулы вдумываться не надо, но надо обратить внимание на разную роль переменных. Мы видим, что в данном случае переменные x и z находятся под кванторами, а переменные y,w -- не находятся. Мы говорим об x, z как о связанных переменных, а об y, w как о свободных переменных для данной формулы. При этом можно сказать, что формула Ф выражает некоторое свойство предметов y и w, но она ничего не говорит ни об x, ни о z. Связанные переменные можно без ущерба для смысла как угодно переименовать, заменив их, допустим, на мягкий и твёрдый знак соответственно. Получится формула (Aь)P(ь,y) -> (Eъ)S(y,ъ,w), отличающаяся от Ф как формальный объект, но при этом выражающая ровно ту же мысль. Часто говорят, что Ф зависит от y и w (и не зависит от других переменных); в этом случае допустима запись вида Ф(y,w), подчёркивающая упомянутую зависимость.

Здесь следует оговорить, что в принципе допустима такая формула: (Ax)P(x) -> (Ey)П(x,y,z). Данная ситуация несколько сложнее. Ясно, что y -- переменная связанная, а z -- свободная. Однако переменная x фигурирует здесь и в той, и в другой роли. Поэтому точнее говорить о связанных или свободных вхождениях переменных. Однако описанной ситуации можно избежать, не используя одну и ту же переменную в двух разных ролях. Связанные вхождения переменной x здесь можно заменить на вхождения какой-то другой переменной u, что приводит к формуле (Au)P(u) -> (Ey)П(x,y,z) со свободными переменными x и z безо всяких коллизий.

Если формула Ф не имеет свободных переменных вообще, то она просто выражает некоторую законченную мысль. Такая формула называется замкнутой. При фиксации смысла входящих в неё символов, она превращается в высказывание, то есть становится истинной или ложной.

5. Интерпретации и модели. Заметим, что любая формула исчисления предикатов вообще-то является просто некой последовательностью символов, не имеющей никакого фиксированного смысла. Для того, чтобы она приобрела некий смысл (который может быть ей придан совершенно разными способами), нужна такая вещь как интерпретация. Только после этого можно говорить об истинности или ложности той или иной формулы. При этом одна и та же формула может быть истинной в одной интерпретации и ложной в какой-то другой. Например, формула, выписанная в конце предыдущего раздела, будет истинной, если переменные -- это числа, а S интерпретируется как и выше. То же самое будет, если под S(x,y,z) мы понимаем xy=z. Однако если S(x,y,z) понимать как x-y=z, то формула станет ложной ввиду того, что для операции вычитания сочетательный закон не справедлив.

Существуют, однако, формулы, истинные при любой интерпретации, и они также называются тавтологиями, но уже как формулы исчисления предикатов. Можно привести следующие примеры тавтологий на базе использования одного двуместного предикатного символа P.
a) (Ax)(Ay)P(x,y) -> (Ay)(Ax)P(x,y)
b) (Ex)(Ey)P(x,y) -> (Ey)(Ex)P(x,y)
c) (Ex)(Ay)P(x,y) -> (Ay)(Ex)P(x,y)

Первые два утверждения говорят о том, что однотипные кванторы (вместе со следующими за ними переменными) можно менять местами. Третье утверждение говорит о том, что если некий объект x "подходит" для всех y, то для каждого y найдётся хотя бы один "подходящий" x, что довольно легко осознать. Однако нижеследующее утверждение

d) (Ax)(Ey)P(x,y) -> (Ey)(Ax)P(x,y)

тавтологией уже не будет -- скажем, она будет ложной, если в качестве значений переменных брать числа, а P(x,y) понимать как равенство. Тогда посылка импликации, очевидно, истинна, так как для любого числа существует равное ему (оно само). В то же время, заключение импликации ложно, так как нет такого числа, которое было бы равно всем числам сразу! То есть квантор всеобщности и квантор существования нельзя менять местами. Может, правда, так оказаться, что формула из пункта d) при каких-то интерпретациях будет истинна (например, это будет так, если P(x,y) считать верным всегда), но тавтологией она при этом не будет.

Итак, дадим определение интерпретации. Прежде всего надо зафиксировать некоторое непустое множество M -- так называемую предметную область. Наши предметные переменные тем самым будут принимать значения из этой области в рамках рассматриваемой интерпретации. Далее для каждого n-местного предикатного символа P нужно задать его интерпретацию, то есть придать ему смысл. Это означает, что символу P мы сопоставляем конкретное n-местное (или ещё говорят "n-арное") отношение на множестве M, которое мы будем обозначать в виде P^M (то есть P с индексом M вверху при нормальном изображении). Это значит, что для каждого набора m_1,...,m_n элементов множества M (среди элементов могут быть одинаковые) мы задаём правило, согласно которому высказывание P^M(m_1,...,m_n) будет считаться истинным или ложным.

Например, мы можем в качестве предметной области взять множество натуральных (целых неотрицательных) чисел, а двуместный предикатный символ P интерпретировать как отношение "меньше", то есть считать высказывание P^M(m_1,m_2) истинным тогда и только тогда, когда число m_1 меньше числа m_2. Высказывания P^M(3,2) и P^(4,4) будут при этом ложны, а P^M(2,7) будет истинным высказыванием. Нужно чётко понимать, что сам по себе символ P никакого смысла не имеет вообще. Проинтерпретировать же его мы имеем право на любой предметной области как душа пожелает.

После того, как интерпретация (то есть задание предметной области и задание n-арного отношения для каждого n-местного предикатного символа) указана, можно говорить об истинности тех или иных формул исчисления предикатов. Само по себе понятие истинности формулы без интерпретации лишено смысла, так как формула есть лишь набор знаков. Скажем, когда мы выписывали формулу для содержательного выражения сочетательного закона сложения чисел, мы писали некое формальное выражение, которое после надлежащей интерпретации выражало нужную нам мысль.

Если дана формула вида Ф(x_1,...,x_n), где x_1,...,x_n -- набор свободных переменных, от которых зависит Ф, то имеет смысл говорить об истинности этой формулы в выбранной интерпретации при заданных значениях свободных переменных. При n=0, когда свободных переменных нет, то есть Ф ни от чего не зависит, говорят об истинности или ложности формулы Ф (в заданной интерпретации). Формальное определение истинности формул очень длинное, и в нём нет необходимости. Просто надо содержательно понимать все входящие в формулы связки и кванторы.

В качестве простого примера рассмотрим замкнутую формулу (Ax)(Ey)P(x,y), где в качестве предметной области возьмём множество натуральных чисел, а символ P интерпретируем как отношение "меньше". Формула станет истинной, так как для любого x существует большее число y -- например, y=x+1. Неравенство "x меньше y" при этом выполняется. Если P интерпретировать как отношение "больше", то формула станет ложной, так как не для любого натурального числа есть меньшее. А если предметная область -- это множество целых чисел, то формула будет истинна для обеих интерпретаций символа P.

Этот простой пример показывает, что истинность формулы может сильно зависеть от выбора как предметной области, так и интерпретации предикатных символов. Нас далее будут интересовать прежде всего тавтологии, то есть замкнутые формулы, истинные всегда (в любой интерпретации).

6. Правила доказательства в исчислении предикатов. Мы сейчас добавим к правилам доказательства в исчислении высказываний два новых очень простых и понятных правила, при этом сделав одну маленькую оговорку насчёт условных рассуждений. При этом мы по-прежнему следуем принципу "минимализма", стараясь обойтись минимумом не только логических связок, но и кванторов. Дело в том, что оба квантора выражаются друг через друга при помощи отрицания, поэтому от одного из кванторов можно отказаться. Действительно, пусть имеется формула (Ax)Ф, где Ф -- некоторая формула. Будем сейчас воспринимать эту формулу как некое содержательное утверждение; при этом вместо Ф для наглядности можно писать Ф(x). Что представляет собой отрицание выписанной формулы на содержательном уровне? Сама формула говорит, что Ф(x) верно всегда, при любом x. Говоря, что Ф(x) верно не всегда, мы имеем в виду, что существует опровергающий пример, то есть такое x, для которого выполнено условие Ф(x). То есть отрицанием формулы выше будет (Ex)Ф(x). Таким образом, формулы (Ax)Ф (не для любого x верно Ф) и (Ex)Ф (при некотором x неверно Ф) имеют один и тот же смысл. То есть в качестве мнемонических правил, можно заменять сочетание (Ax) на (Ex) и наоборот; то же касается сочетаний (Ex) и (Ax).

Таким образом, мы сейчас откажемся от использования кванторов существования, поскольку формула (Ex)Ф содержательно выражает ту же мысль, что и (Ax)Ф.

Вот какие правила доказательства мы добавляем.

4) Правило обобщения Пусть утверждение Ф(x) доказано для произвольного x. Тогда можно считать доказанным утверждение (Ax)Ф(x).

5) Правило перехода к частному случаю Пусть доказано утверждение (Ax)Ф(x). Тогда можно считать доказанным утверждение Ф(y) для любой переменной y.

Оба правила в некотором смысле обратны друг другу. Смысл их понятен, в силу содержательного толкования квантора всеобщности. Обозначать эти правила мы будем как Gen и Partсоответственно (первое из обозначений общепринято, второе -- нет). По поводу пятого правила заметим, что y может быть любой из переменных, в том числе x. Также следует сказать, что в нашей версии мы не имеем дела с термами -- выражениями наподобие арифметических, вроде (x+y)z+x-1, и потому нам не нужно определять правила подстановки термов в формулы, что осложнило бы пятое правило.

Oсталось сделать оговорку, касающуюся условных рассуждений. В исчислении предикатов принятое временно условие A может зависеть от некоторых переменных. Когда мы принимаем A, мы содержательно принимем его как бы для данных значений переменных, но не для всех. Скажем, я могу сказать: "пусть f(x)=3". Я под этом понимаю, что в какой-то конкретной точке x значение функции равно трём. Я вовсе не подразумеваю, что функция постоянна, то есть равна трём при всех x. Поэтому правило обобщения Gen в рамках условного рассуждения не должно применяться к переменной x. В общем виде дело обстоит так: если мы принимаем условие вида A(x_1,...,x_n), где A -- формула с данным списком свободных переменных, то правило обобщения Gen мы не можем применять ни к одной из переменных x_1,...,x_n, пока предположение не будет снято. Иными словами, мы рассуждаем с учётом указанного ограничения и в итоге приходим к доказательству некой формулы B (которая сама может от чего-то зависеть). После чего мы можем снять предположение, считая, что мы доказали импликацию A -> B уже безусловно. Здесь A=A(x_1,...,x_n) -- прежняя формула.

В рамках исчисления высказываний такой проблемы у нас не было, так как не было предметных переменных. Заметим, что если A есть замкнутая формула, то она не имеет свободных переменных, и никаких ограничений не накладывается. Итак, сформулируем модифицированное правило условного рассуждения, которое будет обозначаться CondP.

2P) Правило "условного рассуждения" для исчисления предикатов Пусть требуется доказать утверждение вида A -> B. Тогда достаточно принять утверждение A (в качестве предположения) и доказать утверждение B, не применяя при этом правило обобщения ни к одной из свободных переменных формулы A.

Дата добавления: 2015-07-15