2.2. Логика предикатов первого порядка

2.2.1. Основные определения.

Как показывает практика, возможностей логики высказываний явно недостаточно для представления знаний. Напомним основные понятия более сложной логики предикатов первого порядка (ЛППП).

Предикат – это логическая функция одного или нескольких переменных. Результатом этой функции является 1 – истина или 0 – ложь.

Примеры. СТУДЕНТ (Вася), ПРОЖИВАНИЕ (x, Томск).

Терм – это константа, переменная или некоторая n-местная функция (функтор f(x₁,…,x_n))

Примеры. а , x, f(x, y).

Если P – n-местный предикат и t₁…t_n – термы, то P(t₁,…,t_n) – атом.

Примеры. P(x), P(x,y), P(a, x), P(x, y, f(x, y)).

В формулах используются логические связки (операции):, , , ,  и кванторы:, .

Рекуррентное определение формулы:

1. Атом – есть формула

2. Если F – формула, то F – формула.

3. Если F, G – формулы, то FG, FG, FG, FG – формулы.

4. Если F – формула, в которой есть переменная x, то x F(x), x F(x) – формулы (при этом переменная x называется связанной квантором всеобщности или существования).

5. Все переменные в формуле связаны кванторами.

Пример. Формализуем утверждение: «для любого натурального числа существует единственное натуральное число, непосредственно следующее за ним».

Введем предикаты E(x, y) – x=y, N(x) – x – натуральное число и функтор f(x) – следующее число (x+1).

x [N(x)y [E(f(x), y)z [E(f(x), z)E(y, z)]]].

Интерпретация формул производится следующим образом:

А) Считаем, что для каждой формулы определено множество объектов, о которых может идти речь, это множество называется областью определения формулы (обозначается D).

2. Каждой константе ставим в соответствие один элемент из D.

3. Определяем значения функций для всех возможных наборов аргументов.

4. Определяем истинностное значение каждого предиката.

5. Устанавливаем истинностное значение формулы по таблицам истинности (это можно сделать только в случае, если все переменные в формуле связаны кванторами – иначе, формула бессмысленна)

Пример.

//пример на интерпретацию (1)

x [P(x)→Q(x,f(x))]

A) D = {1, 2} – область определения

B) Константы отсутствуют

С) f (1) = 2 f (2) = 1

D) P (1) = 1 P (2) = 0

Q (1, 1) = 1 Q (1, 2) = 0 Q (2, 1) = 0 Q (2, 2) = 1

E) Вычисляем значение матрицы

x = 1

P (x) → Q (x, f (x)) = P (1) → Q (1, f(1)) = P(1) → Q (1, 2) =1 → 0 = 0

Таким образом:

x [P(x) → Q (x, f(x))] = 0 в данной интерпретации.

В этой же интерпретации формула

x [P(x) → Q (x, f(x))] = 1,

т.к.

при x = 2

P(x) → Q (x, f(x) = P(2) → Q (2, f (2)) = 0 → 0 = 1

Определения общезначимости, противоречивости и логического следствия точно соответствуют аналогичным понятиям в логике высказываний. Имеют место те же теоремы дедукции. Справедливыми остаются и эквивалентные преобразования.

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

А) Избавляются от операций ,  с помощью соответствующих правил (см. 2.1.1).

B) Добиваются, чтобы  стояло только перед атомом (используем законы Де Моргана см. 2.1.1)

С) Переносят кванторы в начало формулы, чтобы она имела вид:

//формула (2)

₁ x_{1 2} x₂ ….. _n x _n M [x₁, … , x_n]

В этом случае говорят, что формула представлена в ПНФ (предваренной норм форме). M[x₁,…,x_n] называется матрицей формулы.

Используются следующие эквивалентные преобразования:

//формулы (3)

x F(x) G = x [F(x) G]

в случае, если G не содержит переменную x:

₁ x F (x) ₂x G(x) = ₁ x ₂ y [F₁(x) G₂(y)],

т.е. в случае необходимости производим замену переменных.

В двух частных случаях можно избежать переименования переменной:

//формулы (4)

x F (x)  x G(x) = x [F(x)  G(x)]

 x F(x)   x G (x) =  x [F(x)  G(x)]

D) Добиваются, чтобы матрица была представлена в КНФ.

E) Избавляются от  путем замены связанных им переменных на константы.

//формула (5)

F = x₁ … x_i-1  x_i x_i+1 … x_n M [x₁ …, x_i-1, x_i ; x_i+1; x_n]

G = x₁ … x_i-1 … x_i+1 … x_n M [x₁, …, x_i-1, a, x_i+1, … x_n],

где :

а – некоторая константа.

Таким образом, заменяем переменные под  на константы.

Это преобразование не является эквивалентным, однако оно сохраняет противоречивость, т.е. F- противоречива, тогда и только тогда, когда противоречива G. Этого достаточно, если мы пользуемся 2-й теоремой дедукции.