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

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

Рассмотрим вначале некоторые примеры:

1) «x - простое число». Это выражение не является высказыванием, пока мы не заменим переменную x на какое-либо определенное число. При x = 1 получим истинное высказывание, при x = 6 - ложное. Таким образом, выражение «x - простое число» есть некоторая функция P (x), зависящая от переменной x. Область определения P (x) - множество чисел, область значений P (x) - высказывания;

2) «x больше y». Это выражение можно рассматривать как функцию Q (x, y), зависящую от переменных x и y. Она становится высказыванием после того, как x и y заменим их значениями.

В общем случае под предикатом от n переменных понимается выражение P(x₁, x₂,.., x_n), которое становится высказыванием после подстановки вместо переменных x₁, x₂,.., x_n их значений из множеств

M₁, M₂,..., M_n соответственно. Элементы этих множеств называются предметами, а переменные x₁, x₂,.., x_n - предметными переменными. Множество M₁ ´ M₂ ´…´ M_n (декартово произведение) упорядоченных наборов длины n называется полем предиката P (x₁, x₂,.., x_n). Если число предметных переменных равно нулю, то предикат есть высказывание.

Будем обозначать:

x, y, z,.., x₁, x₂, x₃,... (малые буквы конца латинского алфавита) - предметные переменные;

a, b, c,.., a₁, a₂, a₃,... (малые буквы начала латинского алфавита) - предметы из множеств M₁, M₂,.., M_n;

A (x, x), B, F (x, y), P (x₁, x₂,.., x_n) - предикаты. Символы 0,1,как и прежде, обозначают истину и ложь.

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

Пусть, например, «х = у» - предикат A (х, у), а «х < у» - предикат В (х, у). Тогда

A (x, y) ٧ B (x, y)

- новый предикат, полученный применением операции дизъюнкции.

Помимо операций алгебры высказываний в логике предикатов есть две специфические операции, связанные с природой предикатов.

Пусть дан предикат P (x), зависящий от одной переменной и определенный на поле М.

Выражение "x P (x) («для всякого х, Р (х)») означает высказывание, истинное только в том случае, когда предикат Р (х) истинен для всех предметов из поля М. Здесь символ " - квантор общности.

Выражение $x P (x) («существует х, что Р (х)») означает высказывание, истинное только в том случае, когда предикат Р (х) истинен хотя бы для одного предмета из поля М; символ $ - квантор существования.

Эти две операции называются операциями квантирования. Рассмотрим примеры применения операций квантирования. Пусть даны предикаты над по лем натуральных чисел:

1) x² = xx, тогда "x (x² = xx) - истинное высказывание;

2) x + 2 = 7, тогда "x (x + 2 = 7) - ложное;

$x (x + 2 = 7) - истинное;

3) x + 2 = x, тогда $x (x + 2 = x) - ложное.

Операции квантирования легко обобщаются на случай, когда предикат зависит от n переменных. Пусть G (x₁, x₂,.., x_n) - предикат от переменных x₁, x₂,.., x_n над полем М = M₁ ´ M₂ ´..´ M_n. Подставим вместо переменных x₁,.., x_i-1, x_i+1,.., x_n предметы a₁,.., a_i-1, a_i+1,.., a_n из множеств M₁,.., M_i-1, M_i+1,.., M_n. Получим предикат G (a₁,.., a_i-1, a_i+1,.., a_n), зависящий только от одной переменной x_i. Следовательно, выражение

"x_i G (a₁,.., a_i-1, x_i, a_i+1,.., a_n)

есть высказывание. Отсюда выражение

"x_i G(x₁,.., x_i-1, x_i, x_i+1,.., x_n)

есть предикат от n-1 переменной. Он не зависит от x_i. Значение его для данного набора (a₁,.., a_i-1, a_i+1,.., a_n) равно истине, если предикат G (a₁,.., a_i-1, x_i, a_i+1,.., a_n) истинен для всякого предмета x_i из поля М.

Аналогичные рассуждения можно провести для квантора $. С помощью операций конъюнкции, дизъюнкции, импликации, эквивалентности, отрицания, а также операций квантирования можно получать более сложные предикаты. При этом предметные переменные, по отношению к которым применялись операции квантирования, называются связанными а остальные - свободными.

Например, в предикате

"x (A (x, y) ٧ $z B (z, v))

переменные x, z- связанные, y, v- свободные.

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

X, Y,.., X₁, X₂,.., W(x₁, x₂,.., x_n), V(x₁, x₂,.., x_n), …

Переменный предикат от нуля переменных есть переменное высказывание. Применяя к переменным предикатам операции ٧, ٨, ®, ‾, ~, $, ", получим формулы логики предикатов. Так, выражение

"x W (x, y) ٧ x ® U (z)

– пример формулы логики предикатов.