ПЕРВОГО ПОРЯДКА ДЛЯ ПРЕДСТАВЛЕНИЯ ЗНАНИЙ

ИСПОЛЬЗОВАНИЕ ЛОГИКИ ПРЕДИКАТОВ

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

В логике предикатов расширенно понятие атома. При символическом описании атома разрешено использование символов констант a, b, c, … , возможно с индексами; символов переменных x, y, z, …, возможно с индексами; функциональных символов f, g, h, …, возможно с индексами; предикатных символов P, Q, R, …, возможно с индексами.

Кроме этого для определения атома вводится понятие терма:

1. Константа есть терм.

2. Переменная есть терм.

3. Если f есть N – местный функциональный символ и t₁, t₂, …, t_N – термы, то f(t₁, t₂, …, t_N) – терм.

4. Никаких других термов нет.

Тогда если P есть N – местный предикатный символ и t₁, t₂, …, t_N – термы, то P(t₁, t₂, …, t_N) – атом.

В логике предикатов логические формулы определяются следующим образом:

1. Атом есть логическая формула;

2. Если G – логическая формула, то (~G) также является логической формулой;

3. Если G и H – логические формулы, то (G Ù H), (G Ú H), (G → H) и (G ↔ H) также являются логическими формулами;

4. Если G – логическая формула, а x – свободная переменная в G, то ("x) G и ($x) G – логические формулы.

5. Логические формулы порождаются только конечным числом применений п.п. 1 – 4.

Символы и называются соответственно кванторами всеобщности и существования. Запись вида читается как «Для всех x», а запись вида - как «Существует x». Как и логические связки в логике высказываний, кванторы имеют ранг и этот ранг – наименьший.

Вхождение переменной x в формулу называется связанным, если оно совпадает с вхождением в кванторный комплекс или или находится в области действия этого комплекса, иначе вхождение называется свободным. Если хотя бы одно из вхождений переменной в формулу свободно, то переменная называется свободной в этой формуле. Если хотя бы одно из вхождений переменной в формулу связанно, то переменная называется связанной.

Интерпретация формулы F логики предикатов состоит из непустой предметной области D и указания значения всех констант, функциональных символов и предикатных символов, встречающихся в F. При этом:

1. Каждой константе ставится в соответствие некоторый элемент из D.

2. Каждому N–местному функциональному символу ставится в соответствие отображение из D^N в D.

3. Каждому N– местному предикатному символу ставится в соответствие отображение D^N в {И, Л}.

Для каждой интерпретации формулы из области D формула может получить значение И или Л согласно следующим правилам:

1. Если заданы значения формул G и H, то истинностные значения формул (~G), (G H), (G H), (G→H) и (G↔H) получаются с помощью таблицы 1.

2. G получает значение И, если G получает значение И для каждого x из D, в противном случае она получает значение Л.

3. G получает значение И, если G получает значение И хотя бы для одного x из D, в противном случае она получает значение Л.

4. Формула, содержащая свободные переменные, не может получить истинностное значение.

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

Основные законы логики высказываний являются таковыми и для логики предикатов. Кроме них в логике предикатов применяются законы, приведенные в таблице 2.1.

Таблица 2.1

С помощью законов логики предикатов можно любую формулу преобразовать в формулу вида (Q₁x₁)(Q₂x₂)…(Q_Nx_N) M, где каждое (Q_i x_i), i = 1, 2, …, N, есть или , а M есть формула, не содержащая кванторов. Формула такого вида называется формулой в предваренной нормальной форме. Последовательность (Q₁x₁)(Q₂x₂)…(Q_Nx_N) называется префиксом, а M - матрицей формулы в предваренной нормальной форме.

Если формула находится в предваренной нормальной форме и при этом из префикса удалены все кванторы существования, переменные, находившиеся под действием этих кванторов, заменены в матрице символами констант или функциональными символами, а сама матрица находится в КНФ, то говорят, что она представлена в сколемовской стандартной форме. Удаление кванторов существования и замена переменных производится согласно следующему правилу:

1).если левее удаляемого квантора существования нет ни одного квантора всеобщности, то переменная, относящаяся к этому квантору, заменяется на символ константы, отличный от символов констант, имеющихся в матрице;

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

Например, формула ($x) ("y) ("z) ($u) P(x,y,z,u) в сколемовской стандартной форме имеет вид ("y) ("z) P(a,y,z,f(y,z)), т. е. кванторы существования удалены, а символы переменных x и u заменены на символ константы a и функциональный символ f(y,z). Символы констант и функциональные символы, которые используются для замены переменных, называются сколемовскими константами и функциями.

Сколемовские стандартные формы применяются при решении задач методом резолюций. Центральным понятием, используемым в этом методе, является понятие резольвенты. Резольвента есть результат применения правила резолюций, которое выглядит следующим образом: для любых двух дизъюнктов C₁ и C₂, если существует литера L₁ в C₁, которая есть отрицание некоторой литеры L₂ в C₂, то вычеркнув L₁ и L₂ из C₁ и C₂ соответственно, построим дизъюнкцию оставшихся дизъюнктов. Построенный дизъюнкт есть резольвента C₁ и C₂. Например, если C₁ = P Ú ~Q, C₂ = R Ú Q, то L₁ = ~Q, L₂ = Q, а дизъюнкт P Ú R - резольвента дизъюнктов C₁ и C₂.

Интерпретация называется моделью для множества формул, если любая формула из этого множества истинна в этой интерпретации.

Пример 2. Описать на языке логики предикатов следующие утверждения:

1. Накопитель деталей пуст. Если накопитель деталей пуст, то станок простаивает.

2. Станок простаивает. Если станок простаивает, то накопитель деталей пуст.

3. Накопитель деталей станка пуст. Если станок простаивает, то необходимо принять меры по наполнению накопителя.

Введем предметную область D - множество станков и накопителей станков и следующие предикаты:

1. P (x) = «x пуст».

2. Q (x) = «x – это станок».

3. R (x, y) = «x – это накопитель деталей станка y».

4. S (x) = «x простаивает».

5. T (x) = «необходимо принять меры по наполнению накопителя

станка x».

Тогда вышеперечисленные утверждения можно записать таким образом:

1. ($x)($y)(R (x, y) P (x)).

($x)($y)(R (x, y) P (x) → Q (y) S (y)).

2. ($x) (Q (x) S (x)).

($x)(Q (x) S (x) → ($y)(R (y, x) P (y))).

3. ($x)($y)(R (x, y) P (x)).

($x)(Q (x) S (x) → ($y)(R (y, x) P (y) T (y))).

Контрольные вопросы

1. Как определяется атом в логике предикатов первого порядка?

2. Как определяется формула в логике предикатов первого порядка?

3. Как проводится интерпретация в логике предикатов первого порядка?

4. Каковы правила записи логических выражений при представлении знаний с использованием предикатов первого порядка?

5. Как найти резольвенту?

6. Назовите этапы получения сколемоской формы.

7. Как преобразовать логическое выражение, чтобы привести его к форме дизъюнктов?

8. Запишите законы логики предикатов?