Формальные логические модели

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

В основе логических моделей лежит понятие формальной теории, задаваемой четверкой [54, 64]:

S = < В, F, A, R>;.

Здесь В - счетное множество базовых символов (алфавит) теории S. Конечные последовательности базовых символов называются выражениями теории S. F - подмножество выражений теории S, называемых формулами теории. Обычно имеется эффективная процедура построения выражений, являющихся формулами. Можно эту процедуру рассматривать как множество синтаксических правил, позволяющих строить из В синтаксически правильные выражения, т.е. формулы. А - выделенное множество формул, называемых аксиомами, теории S, т. е. множество априорно истинных формул; R - конечное множество отношений { r₁,..., r_n } между формулами, называемых правилами вывода. Для каждого r_i существует целое положительное число j такое, что для каждого множества, состоящего из j формул, и для каждой формулы f эффективно решается вопрос о том, находятся ли данные j формул в отношении r_i с формулой f. Если отношение r_i выполняется, то f называется непосредственным следствием данных f_n формул по правилу r_i. Следствием (выводом) формулы f_n в теории S называется всякая последовательность f₁,..., f_n формул такая, что для любого i формула f_i есть либо аксиома теории S, либо непосредственное следствие каких-либо предыдущих формул по одному из правил вывода. Правила вывода позволяют расширять множество формул, которые считаются истинными в рамках данной теории. Формальная теория называется разрешимой, если существует единая эффективная процедура, позволяющая узнать для любой данной формулы, существует ли ее вывод в S. Формальная система S называется непротиворечивой, если не существует формулы А такой, что А и Ø А выводимы в S.

Наиболее распространенной формальной системой, используемой для представления знаний, является исчисление предикатов. Алфавит исчисления предикатов состоит из следующего набора символов:

1) знаков пунктуации { (,).};

2) пропозициональных связок{Ø, V, L, É};

3) знаков кванторов {", $};

4) символов переменных x_k, k = 1,2,...;

5) n - местных функциональных букв: f_kⁿ, k ³ 1, n ³ 0(f_k⁰ называют константными буквами);

6) n-местных предикатных букв (символов): p_kⁿ, k ³ 1, n ³ 1.

В дальнейшем в примерах для упрощения будем вместо x_k писать u, v, x, y, z,...; вместо f_k⁰ - a, b, c, d,...; вместо f_n^k (n ¹ 0) - f, g, h,...; вместо p_kⁿ - P, Q, R, S, T, V, W,...

Из символов алфавита можно строить различные выражения. Выделяют термы, элементарные формулы (атомы) и правильно построенные формулы (или просто формулы). Всякий символ переменной или константной буквы есть терм. Если t₁,...,t_n (n ³ 1)- термы, то и f_kⁿ(t₁,..., t_n) является термом.

Если p_kⁿ - предикатная буква, а t₁,..., t_n - термы, то p_kⁿ (t₁,..., t_n) - элементарная формула (атом). Атом является правильно построенной формулой. Если А и В - правильно построенные формулы (п.п.ф.), то Ø A, A V B, A L B, A É Bесть правильно построенные формулы. Если А - п.п.ф и х - переменная в А, то (" x) A и ($ x) A - правильно построенные формулы. Выражение является п.п.ф., только если оно получено с соблюдением перечисленных выше правил.

В выражениях (" x)(A)и ($ x)(A) A называются областью действия квантора всеобщности (общности) и квантора существования соответственно. При этом переменная х называется связанной, если она находится в области действия квантора, примененного к этой переменной. Переменная свободна, если она не связана. Примером формулы является следующее выражение: " x (Q(x, y) É R(x)). В этой формуле переменная х связана, а переменная yсвободна. Формула называется замкнутой, если она не содержит свободных переменных.

Чтобы придать формуле содержание, ее интерпретируют как утверждение, касающееся рассматриваемой предметной области. Под интерпретацией понимают всякую систему, состоящую из непустого множества D, называемого областью интерпретации, и какого-либо соответствия, относящего каждой предикатной букве p_kⁿ некоторое n-местное отношение в D, а каждой функциональной букве f_kⁿ некоторую n-местную функцию, отображающую Dⁿ ® D, и каждой константной букве f_k⁰ некоторый элемент из D. При заданной интерпретации переменные мыслятся пробегающими область D этой интерпретации. При заданной интерпретации всякой элементарной формуле приписывается значение "истинно" (И) или "ложно" (Л). Приписывание значения элементарной формуле p_kⁿ(t₁,..., t_n) осуществляется по следующему правилу: если термы предикатной буквы соответствуют элементам из D, удовлетворяющим отношению, определяемому данной интерпретацией, то значением элементарной формулы будет истина, в противном случае - ложь.

Значение неэлементарной формулы можно вычислить рекуррентно, исходя из значений составляющих ее формул. При этом, если А и В - формулы, то значения формул Ø A, A L B, A V B, B É A определяются по таблице истинности, представленной в табл. 3.1:

 

 

Таблица 3.1.

A	B	ØA	AVB	ALB	AÉB
И Л И Л	И И Л Л	Л И Л И	И И И Л	И Л Л Л	И И Л И

 

Отметим, что формула (" x)(A) обозначает утверждение: "для любого значения х из области D значение формулы А истинно (выполнено)", а формула ($ x)(A) обозначает утверждение: "существует такое значение х из области D, что значение формулы А истинно (выполнено)". Приведенные выше утверждения могут быть как истинны, так и ложны. В случае конечных областей значения истинность таких формул можно установить с помощью таблиц истинности. Очевидно, что некоторые формулы могут быть истинными или ложными в зависимости от выбранной интерпретации.

Формула А называется выполнимой тогда и только тогда, когда существует интерпретация I такая, что А принимает значение И в I. Если формула А принимает значение И в интерпретации I, то говорят, что I удовлетворяет формуле А. Если некоторая формула А принимает значение И при всех интерпретациях, то ее называют общезначимой. Так, например, формула P(a) É (P(a) V P(b)) истинна при любой интерпретации (это можно установить по таблице истинности), и, следовательно, эта формула общезначима. Формула называется невыполнимой, если при всех интерпретациях она принимает значение Л.

Формула А логически следует из формул B₁,... B_n тогда и только тогда, когда всякая интерпретация I, удовлетворяющая B₁ L... L B_n удовлетворяет также и А. Формулы B₁,... B_n называют посылками, а A - заключением логического следования и обозначают B₁,... B_n ╞ A.

Справедлива теорема (теорема дедукции): "Пусть даны формулы B₁,...,B_n и формула A. Формула А является логическим следствием B₁,... B_n тогда и только тогда, когда формула B₁ L... L B_n É A общезначима, т.е. ╞ (B₁ L... L B_n) É A ".

Задачей доказательства теоремы называют выяснение вопроса логического следования некоторой формулы А из заданного множества формул B₁,... B_n, что равносильно доказательству общезначимости формулы B₁ L... L B_n É A или невыполнимости формулы B₁ L... L B_n L Ø A.

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

Приведем пример записи некоторого факта в виде формулы исчисления предикатов:

ДАТЬ (МИХАИЛ, ВЛАДИМИРУ, КНИГУ)

($ х)(ЭЛЕМЕНТ (x, СОБЫТИЕ - ДАТЬ) L ИСТОЧНИК (x, МИХАИЛ) L

L АДРЕСАТ (x, ВЛАДИМИР) L ОБЪЕКТ (x, КНИГА)).

Здесь приведены различные способы записи одного факта: "Михаил дал книгу Владимиру".

иметь (Саша, книга) «Саша имеет книгу»

иметь (Саша, книги) → иметь (Саша, книга) «Если Саша имеет книги, то он имеет книгу»

(∀x) [человек (x) → иметь (x, книга)] «Каждый человек имеет книгу»

(∀x) [свободен (x) → (∃y) (на (y,x))] «Если кубик x свободен, то нет такого кубика y, который находится на кубике x»

 

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