Логика предикатов
Логика высказываний обладает довольно слабыми выразительными возможностями. В ней нельзя выразить даже очень простые с математической точки зрения рассуждения. Рассмотрим, например, следующее умозаключение. «Всякое целое число является рациональным. Число 2 – целое. Следовательно, 2 – рациональное число». Все эти утверждения с точки зрения логики высказываний являются атомарными. Средствами логики высказываний нельзя вскрыть внутреннюю структуру и поэтому нельзя доказать логичность этого рассуждения в рамках логики высказываний. Мы рассмотрим расширение логики высказываний, которое называется логика предикатов первого порядка или логика первого порядка.
Предикаты и операции над ними
Введем основное понятие темы.
Определение. Пусть М – непустое множество. Тогда 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) истинно.