Логическая модель представления знаний

5.2. Логическая модель представления знаний

Логическая модель основана на системе исчисления предика­тов первого порядка. Знакомство с логикой предикатов начнем с исчисления высказываний.

Высказыванием называется предложение, относительно которого имеет смысл утверждать истинно (Т) оно или ложно (F). Например, предложения «лебедь белый» и «лебедь черный» будут вы­сказываниями. Из простых высказываний можно составить бо­лее сложные:

«лебедь белый или лебедь черный»,

«лебедь белый и лебедь черный»,

«если лебедь не белый, то лебедь чёрный».

В свою очередь, сложные высказывания можно разделить на простые, которые связаны между собой с помощью слов: и, или, не, если — то. Элементарными  (простыми) называются высказывания, которые нельзя разделить на части. Логика высказываний опери­рует логическими связями между высказываниями, т. е. она ре­шает вопросы типа: «Можно ли на основе высказывания А полу­чить высказывание Б?»; «Истинно ли В при истинности А?» и т.п. При этом семантика высказываний не имеет значения. Элемен­тарные высказывания рассматриваются как переменные логиче­ского типа, над которыми разрешены следующие логические операции:

()     отрицание (унарная операция);

          конъюнкция (логическое умножение);

Рекомендуемые материалы

             дизъюнкция (логическое сложение);

   импликация (если — то);

    эквиваленция.

Операция импликации должна удовлетворять следующим требованиям.

1. Значение результата импликации зависит от двух опе­рандов.

2. Если первый операнд (А) — истинный, то значение резуль­тата совпадает со значением второго операнда (В).

3. Операция импликации не коммутативна.

4. Результат импликации совпадает с результатом выражения .

Значения результатов логических операций над переменны­ми X и Y, являющимися элементарными высказываниями, при­ведены в табл. 5.1.

Таблица 5.1

Результаты вычисления логических операций

Исчисление высказываний позволяет формализовать лишь малую часть множества рассуждений, поскольку этот аппарат не позволяет учитывать внутреннюю структуру высказывания, которая существует в естественных языках. Рассмотрим ставший классическим пример рассуждения о Сократе:

Р: «Все люди смертны»

Q : «Сократ — человек»

 R:  «Сократ - смертен»

Используя для обозначения высказываний логические пере­менные P, R, Q можно составить формулу: , которая может быть интерпретирована как «Если все люди смертны и Со­крат является человеком, то Сократ является смертным». Однако эта формула не является общезначимой, поскольку относится только к одному объекту (Сократу). Кроме того, высказывание R не выводится из P и Q, т.е., если бы мы не сформулировали R за­ранее, мы не смогли бы записать приведенную выше формулу.

Чтобы осуществить этот примитивный логический вывод, высказывание Q следует разделить на две части: «Сократ» (субъ­ект) и «человек» (свойство субъекта) и представить в виде отно­шения «субъект — свойство», которое можно записать с помощью функции человек (Сократ).

Очевидно, что свойство конкретного субъекта с именем «Со­крат» быть «человеком» может быть присуще и ряду других субъ­ектов, что позволяет заменить константу «Сократ» на некоторую переменную, например X. Тогда получим запись человек (X), ко­торая обладает внутренней структурой, т.е. значение такого вы­сказывания будет зависеть от его компонент. Записанная функ­ция уже не является элементарным высказыванием, она называ­ется предикатом.

Приведем объяснение понятия предиката, данное Д. А. По­спеловым [1]: «Под предикатом будем понимать некоторую связь, которая задана на наборе из констант или переменных.

Пример предиката: «Р больше Q».

Если семантика Р и Q не задана, то о предикате сказать осо­бенно нечего. Пожалуй, только то, что он является антирефлек­сивным, антисимметричным и транзитивным. Но при задании семантики (т.е. областей определения переменных Р и Q) о пре­дикате можно будет сказать существенно больше. Например, если Р и Q — площади городов в России и Японии, то при задании списков городов и подстановке значений из этих списков в пере­менные мы получим отношение между двумя сущностями и смо­жем судить о его истинности, например:

«Площадь Волгограда больше площади Хиросимы» =Т;

 «Площадь Вологды больше площади Токио»=Р.

Иногда для утверждения об истинности или ложности преди­ката можно обойтись без подстановки. Например, если областью определения переменной X являются целые положительные чис­ла, то предикат «X > -5» будет тождественно истинен».

Основными синтаксическими единицами логики предикатов являются константы, переменные, функции, предикаты, кванто­ры и логические операторы. Формальный синтаксис исчисления предикатов первого порядка удобно представить в нормальной форме Бэкуса—Наура, которая традиционно применяется для за­писи грамматик языков программирования.

<константа>   <идентификатор1>

<переменная>  <идентификатор2>

 <функция>  <идентификаторЗ>

<предикат>  <идентификатор4>

 <терм>  <константа> | <переменная> |

                      | <функция> (<список термов>)

<список термов>  <терм> | <терм>, <список термов>

<атом>  <предикат> | <предикат> (<список термов>)

<литера>  <атом> |  <атом>

<оператор>  | |  |

 <список переменных>  <переменная> | <переменная>,

                                                   <список переменных>

<квантор>  <(<список переменных>) |

                             | < (<список переменных>)

<формула><литера> |  <формула> | <квантор> (<формула>) |   (<формула>) <оператор> (<формула>)

В данной записи любое имя в угловых скобках представляет собой тип синтаксического объекта. Определение каждого типа начинается с появления его имени в левой части каждой записи, т. е. слева от знака . В правой части каждой записи приводятся возможные способы организации синтаксически корректных объектов определяемого типа. Альтернативные варианты разде­лены знаком |, который можно интерпретировать как ИЛИ. Но­мера идентификаторов следует трактовать в том смысле, что идентификаторы, используемые для обозначения объектов раз­ных типов, должны быть различимыми. Например, константы обозначаются именами <идентификатор1>, которые формиру­ются из строчных букв, причем первым символом должен быть один из следующих: a, b, c, d e, k, l, m, n, x, y, z, v, w, u. Имена пе­ременных <идентификатор2> должны начинаться, например, с заглавной буквы. Идентификаторы функций <идентификатор3> состоят из строчных букв, при этом первой является f, g, h, p или q. Имена предикатов <идентификатор4> должны состоять из про­писных букв. Функции, как и предикаты, задают некоторую связь между переменными или константами. Но от­ношение не характеризуются истинностным значением. С помо­щью функции можно представить сложный объект, например, функция fbook (Author, Tytle, Publisher, Year) представляет набор информации, характеризующей книгу. Предикат и функция от­личаются также на синтаксическом уровне, а именно: функции могут являться аргументами предикатов (т.е. термами), а преди­каты — нет. Следует заметить, что в логике предикатов более вы­соких порядков по сравнению с первым аргументами предикатов могут быть другие предикаты. Функции с нулевым числом мест (аргументов) являются аналогами констант. Предикат без аргу­ментов эквивалентен высказыванию.

Кванторы в логике предикатов необходимы для определения области действия переменных. Так, в логическом выводе о Сок­рате высказывание «Все люди смертны» можно уточнить следую­щим образом:

«Для всех X, если X является человеком, то X является смерт­ным».

Введя предикаты ЧЕЛОВЕК(Х) и СМЕРТЕН(X), можем со­ставить логическую формулу ЧЕЛОВЕК(X)®СМЕРТЕН(X). Что­бы показать справедливость этой формулы для любого X, исполь­зуется квантор общности:

"Х — «для любого X».

Тогда рассматриваемое утверждение запишется в виде "(X)ЧЕЛОВЕК(X)®СМЕРТЕН(X).

Кроме квантора общности в логике предикатов есть квантор существования: $Х — «существует хотя бы один такой X, что ...» или «найдется хотя бы один X, такой, что ...»

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

Если в логическую формулу входит несколько кванторов, не­обходимо учитывать их взаимное расположение. Рассмотрим возможные интерпретации логической формулы ЛЮБИТ(Х, Y) с квантифицированными переменными. При этом существует несколько вариантов размещения кванторов, один из которых "X$Y ЛЮБИТ(Х, Y). Эту формулу можно интерпретировать двояко:

• для любого X существует хотя бы один человек Y, которого любит X;

• существует по крайней мере один человек Y, которого любят все X;

Для устранения этой неопределенности введем скобки и по­рядок применения кванторов — слева направо, тогда получим следующие формулы, соответствующие интерпретациям:

1. ("X)($Y) ЛЮБИТ(Х, Y).

2. ($Y)("X) ЛЮБИТ(Х, Y).

Рассмотрим остальные варианты расположения кванторов и их интерпретации.

3. ("X)("Y) ЛЮБИТ(Х, Y) и ("Y)("X) ЛЮБИТ(Х, Y) - «Всеобщее человеколюбие».

4. ($X)("Y) ЛЮБИТ(Х, Y) - «Существует хотя бы один человек, который любит всех людей».

5. ("Y)($X) ЛЮБИТ(Х, Y)) - «Каждого человека кто-нибудь любит».

6. ($X)($Y) ЛЮБИТ(Х, Y) и ($Y)($X) ЛЮБИТ(Х, Y) - «Существует хотя бы один человек, который не утратил чувства любви».

В одной логической формуле не допускается применение раз­ных кванторов к одной переменной, например выражение ($Х)("Х)Р(Х) является недопустимым.

Отрицание кванторных выражений выполняется в соответст­вии со следующими правилами:

Справедливость приведенных выражений вытекает из смысла кванторов. Эти соотношения позволяют любую формулу в логи­ке предикатов представить в виде предваренной нормальной формы (ПНФ), в которой сначала выписываются все кванторы, а затем — предикатные выражения, приведенные к виду КНФ.

Пример ПНФ:

Обратите внимание на лекцию "4 Создание списков".

В логике предикатов первого порядка не разрешается приме­нение кванторов к предикатам (более высокие порядки это поз­воляют).

Формула, в которой все переменные связаны, называется предложением. Каждому предложению можно поставить в соот­ветствие определенное значение — «истина» или «ложь».

Пример: пусть — функция, задающая отношение «отец»; Р(Х) — предикат, задающий отношение «человек». Тогда логическая формула  будет интерпретироваться как «Все существа, отцом которых является человек, - люди».

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

Сложные формулы в логике предикатов получаются путем комбинирования атомарных формул с помощью логических опе­раций. Такие формулы называются правильно построенными ло­гическими формулами (ППФ). Интерпретация ППФ возможна только с учетом конкретной области интерпретации, которая представляет собой множество всех возможных значений термов, входящих в ППФ. Для представления знаний конкретной пред­метной области в виде ППФ необходимо прежде всего устано­вить область интерпретации (мир Хербранда), т.е. выбрать кон­станты, которые определяют объекты в данной области, а также функции и предикаты, которые определяют зависимости и отно­шения между объектами. После этого можно построить логичес­кие формулы, описывающие закономерности данной предметной области. Записать знания с помощью логической модели не удается в тех случаях, когда затруднен выбор указанных трех групп элементов (констант, функций и предикатов) или когда для описания этих знаний не хватает возможностей представления с помощью ППФ, например когда знания являются неполными, ненадежными, нечеткими и т.д.

Логическая модель применяется в основном в исследователь­ских системах, так как предъявляет очень высокие требования к качеству и полноте знаний предметной области.