Предикаты и операции над ними

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

Исчисления предикатов, в которых под знаком квантора не могут находится символы предикатов называется исчисление предикатов 1 порядка.

Предикат (высказывательная функция) - логическое сказуемое.

Предикат – специальный знак, отражающий определенное отношение между конечным множеством сущностей-аргументов.

Пусть М - непустое множество (предметное множество).

Тогда n -местным предикатом, заданным на М, называется выражение, содержащее n переменных и образующееся в высказывание при замене этих переменных элементами множества М.

Пример: Пусть М есть множество натуральных чисел N, тогда выражения «Х -простое число», «X -четное число», «Х -больше 10» являются одноместными предикатами.

При подстановке вместо X натуральных чисел получаются высказывания «2-простое число», «5 больше 10» и так далее.

Выражение «x больше y», «x + y =10» является двухместным предикатом.

Выражение «x лежит между y и z» является трехместным предикатом.

Высказывание - нульместный предикат, или предикат, в котором нет переменных для замены.

Предикат с заменяемыми переменными x 1,.., xn будет обычно указываться заглавной буквой латинской буквой, после которой в скобках указываются эти переменные.

Пример: P (x 1, x 2)

Среди переменных в скобках могут быть и фиктивные

Пример: На множестве имен индивидов, университета и специальностей заданы высказывательные функции (предикаты).

Р 1(Х)= «х -студент».

Р 2(Х,БГТУ)= «студент х университета БГТУ».

Р 3(x, y,САПР)= «студент х университета y обучается по специальности САПР».

X, Y - предметные переменные.

БГТУ и САПР – постоянные

На совокупности всех предикатов, заданных на множестве М, вводятся операции конъюнкции, дизъюнкции, отрицания, импликации, эквиваленции.

В логике предикатов I порядка вводится 2 новые операции:

- квантор общности ;

- квантор существования ().

Предикат W (x 1,.., xn) называется конъюнкцией предикатов U (x 1,.., xn) и V (x 1,.., xn), заданных на множестве М, если для любых a 1,.., an из М высказываний W (a 1,.., an) есть конъюнкция высказываний U (a 1,.., an) и V (a 1,.., an).

Пример: «Существует х такой, что x + y =10» На множестве натуральных чисел это предположение определяется одноместным предикатом P (y). Так Р (2) и Р (9) истинные высказывания, Р (11) ложное.

Если обозначить «x + y =10» через S (x,y) то Р (y) «существует x такой, что S (x,y)». Предикат Р (у) получаем из S (x,y) навешиванием квантора существования на x и пишут P (Y)=( x) S (x,y).

Пусть P (x 1,…, xn) – предикаты, заданные на множестве М, у переменная.

Тогда:

-выражение «для каждого у выполняется Р (х 1,…, xn)» - предикат, полученный из Р навешиванием квантора общности на переменную у.

-выражение «существует у такой, что выполняется Р (х 1,…, xn)» - предикат полученный из Р навешиванием квантора существования на переменную y.

Высказывание xP (x) означает, что область истинности предиката P (x) совпадает с областью значение переменой х. Высказывание ( x) Р (х) означает, что область истинности предиката Р (х) не пустая.