Введем основное
понятие темы.
Определение. Пусть М – непустое
множество. Тогда n-местным предикатом, заданным на М, называется
выражение, содержащее n
переменных и обращающееся в высказывание при замене этих переменных элементами
множества М.
Рассмотрим
примеры. Пусть М есть множество натуральных чисел N. Тогда
выражения «x – простое
число», «x – четное
число», «x – больше 10»
являются одноместными предикатами. При подстановке вместо x натуральных чисел получаются
высказывания: «2 – простое число», «6 – простое число», «3 – четное число», «5
больше 10» и т.д. Выражения «x
больше y», «x делит y нацело», «x плюс y равно 10» являются двухместными
предикатами. (Конечно, последнее выражение можно было записать и так: «x+y=10»). Примеры трехместных
предикатов, заданных на множестве натуральных чисел: число z лежит между «x и y», «x
плюс y равно z», «|x-y|£z».
Будем считать,
что высказывание – нульместный предикат, то
есть предикат, в котором нет переменных для замены.
Надо отметить,
что местность предикатов не всегда равна числу всех переменных, содержащихся в выражении. Например, выражение
«существует число x
такое, что y=2x» на множестве натуральных
чисел определяет одноместный предикат. По смыслу этого выражение в нем можно
заменять только переменную y.
Например, замена y на 6
дает истинное высказывание: «существует число x такое, что 6=2x», а замена y на 7 дает ложное (на множестве N) высказывание «существует число x такое, что 7=2x».
Предикат с
заменяемыми переменными x1,…,xn будет обычно
обозначаться заглавной латинской буквой. После которой в скобках указаны эти
переменные. Например, P(x1,x2), Q(x2,x3), R(x1). Среди переменных в скобках могут быть и
фиктивные.
На совокупности
всех предикатов, заданных на множестве М, вводятся знакомые операции конъюнкция, дизъюнкция, отрицание,
импликация и эквиваленция. Эти
операции вводятся довольно очевидным образом. Приведем в качестве примера
определение конъюнкции предикатов.
Определение. Предикат W(x1,…,xn)
называется конъюнкцией предикатов U(x1,…,xn) и V(x1,…,xn), заданных на множестве М,
если для любых а1,…,аn из М высказывание W(а1,…,аn) есть конъюнкция высказываний U(а1,…,аn) и V(а1,…,аn).
Легко по
аналогии привести определения и других упомянутых выше операций.
В логике
предикатов первого порядка вводятся и две новые операции. Называются они
квантором общности и квантором существования. Эти операции рассмотрим вначале
на примерах. Пусть дано выражение «существует х такой, что x+y=10». На множестве натуральных чисел это предложение определяет
одноместный предикат P(y), так Р(2) и Р(9) –
истинные высказывания, Р(11) – ложное. Если обозначить предикат «x+y=10» через S(x,y) (а
это предикат двухместный), то P(y) можно записать так:
«существует х такой, что S(x,y)». В этом случае говорят, что предикат
P(y) получен из предиката S(x,y) навешиванием квантора существования на x и пишут P(y)=($x)S(x,y). Рассмотрим другой пример. Выражение «для всех х справедливо,
что y³-х2»
определяет на множестве целых чисел одноместный предикат Q(y). Если предикат «y³-х2» обозначить через T(x,y), то Q(y) можно записать так: «для всех x справедливо T(x,y)». В таком случае говорят, что предикат Q(y) получен из предиката T(x,y) навешиванием квантора
общности на х и пишут Q(y)=("x)T(x,y).
После этих
примеров нетрудно дать определение в общем виде.
Определение. Пусть P(x1,…,xn)
– предикат, заданный на множестве M, y –
переменная. Тогда выражение «для всякого y выполняется P(x1,…,xn)» – предикат,
полученный из P навешиванием квантора
общности на переменную y, а выражение
«существует y такой,
что выполняется P(x1,…,xn)» – предикат,
полученный из P навешиванием квантора
существования на переменную y.
Обозначения
операций были введены выше.
Заметим, что в
определении не требуется, чтобы y
была одна из переменных x1,…,xn, хотя в
содержательных примерах, которые будут ниже, квантор навешивается на одну из
переменных x1,…,xn. Указанное
требование не накладывается, чтобы избежать усложнения определения формулы
логики предикатов. Если y
– одна из переменных x1,…,xn, то после
навешивания квантора на y
новый предикат является (n-1)-местным,
если yÏ{
x1,…,xn}, то местность
нового предиката равна n.
Если предикат W(x1,…,xn) получен из предикатов U(x1,…,xn) и V(x1,…,xn)
с помощью связок, то истинность высказывания W(a1,…,an) определяется
таблицами истинности этих связок. Пусть W(x1,…,xn)=("y)U(x1,…,xn,y). Тогда высказывание W(a1,…,an) истинно тогда и только
тогда, когда для любого bÎM истинно высказывание U(a1,…,an,b). Если же W(x1,…,xn)=($y)U(x1,…,xn,y), то высказывание W(a1,…,an) истинно в том и только в
том случае, когда найдется bÎM, для которого высказывание U(a1,…,an) истинно.
Понятие
предиката – весьма широкое понятие. Это видно уже из приведенных выше примеров.
Тем не менее мы это еще раз подчеркнем, показав, что n-местная функция может рассматриваться
как (n+1)-местный
предикат. Действительно, функции y=f(x1,…,xn), заданной на
множестве М можно поставить в соответствие выражение «y равно f(x1,…,xn)».
Это выражение есть некоторый предикат P(x1,…,xn,y). При этом если элемент b есть значение функции в
точке (a1,…,an), то
высказывание P(a1,…,an,b) истинно, и обратно.
(Подобное «превращение» функции в предикат мы уже делали выше для сложения
натуральных чисел.)
На предикаты
можно смотреть и более формально, причем с двух точек зрения.
Во-первых,
предикат можно представить отношением следующим образом. Пусть предикат P(x1,…,xn) задан на множестве M. Рассмотрим прямую степень
этого множества Mn=MxMx…xM и подмножество Dp множества Mn, определяемое
равенством:
Dp={(a1,…,an)ÎMn½высказывание P(a1,…,an)
истинно}.
Отношение Dp можно назвать областью
истинности предиката P.
Во многих случаях предикат P
можно отождествить с отношением Dp.
При этом, правда возникают некоторые трудности при определении операций над
отношениями, аналогичными операциям над предикатами.
Во-вторых,
предикат P(x1,…,xn), заданный на M, можно отождествить с
функцией fp:Mn®{0,1},
определяемой равенством
Мы, в основном,
будем понимать термин «предикат» в смысле исходного определения, т.е. как
языковое выражение. Связано это с тем, что одной из главный целей, как уже
отмечалось во введении, является изучение выразительных возможностей логики
первого порядка, возможности представления средствами этой логики информации,
выраженного на естественном (скажем, русском) языке.
|