Информатика и программирование - Основы информатики, страница 11

В этом случае задачей пользователя или программиста является описание предметной области совокупностью утверждений в виде логических формул. Доказательство истинности утверждения осуществляется ЭВМ на основе исходных утверждений.

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

Метод резолюции заключается в выполнении следующих шагов:

1) взять отрицание формулы A и привести формулу к КНФ;

2) выписать множество дизъюнктов K = {D₁, ..., D_n} формулы ;

3) если во множестве существуют пара дизъюнктов D_i и D_j, один из которых содержит переменную Y, а другой – отрицание переменной , то соединить эти дизъюнкты дизъюнкции D_i + D_j и сформировать новый дизъюнкт  +  , исключив переменные Y и ;

4) возможны три случая:

- если дизъюнкты D_i и D_j содержат только переменные Y и , то получен пустой дизъюнкт и логическое следствие верно;

- если во множестве K не существует двух дизъюнктов, для которых применим шаг 3, то логическое следствие неверно;

- если полученный дизъюнкт не является пустым, то и добавить его к множеству K и вновь выполнить шаг 3.

Пример 7.35. Рассмотрим логический вывод знаний. Пусть для некоторого студента справедливы три факта, являющихся аксиомами – исходными утверждениями для логического вывода:

1) если студент болеет, то он принимает лекарства;

2) если студент не болеет, то он ходит на учебу;

3) студент не принимает лекарства.

Следует ли из этих аксиом следующее высказывание:

4) студент ходит на учебу.

Выделим в этих утверждениях простые высказывания:

A = «студент болеет»;

B = «студент принимает лекарства»;

C = «студент ходит на учебу».

Запишем утверждения с помощью этих простых высказываний с учетом того, что конструкция «если A, то B» соответствует логической операции импликации A → B:

1) A → B;

2)  → C;

3)  ;

4) C.

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

= A;

A → B = + B;

=  ,

где «+» – дизъюнкция; «» – операция конъюнкции; «→» – операция логического следствия (импликация).

Проверим, является ли высказывание 4 логическим выводом из утверждений 1-3:

[(A → B)  ( → C)  ] → C.

В соответствии с методом резолюций возьмем отрицание от данного выражения и преобразуем его к КНФ:

= ( + B)  (A + C)   .

Множество K включает следующие дизъюнкты:

K = { + B, A + C, , }.

Из двух дизъюнктов  + B и A + C получим новый дизъюнкт B + C, который включается в множество K:

K = { + B, A + C, , , B + C}.

Из двух дизъюнктов B + C и получим новый дизъюнкт C, который также включается во множество K:

K = { + B, A + C, , , B + C, C}.

Полученный дизъюнкт C является отрицанием дизъюнкта , а значит, высказывание 4 является логическим следствием из утверждений 1-3. □

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

Предикат – это функция, возвращающая значения 1 («истина») или 0 («ложь») в зависимости от значений аргументов. Например, P(x,y)=(x>y).

В логике предикатов вводятся две операции.

1. Квантор существования .

Выражение x P(x) (читается: «существует x, для которого P(x)») истинно, если существует такое значение x из множества M, при котором P(x) = 1:

x P(x) = P(x₁) + P(x₂) + …

2. Квантор общности .

Выражение x P(x) («для любого x P(x)») истинно, если P(x) = 1 для всех значений x из множества M:

x P(x) = P(x₁) · P(x₂) · …

Рассмотрим пример представления знаний с помощью предикатов.

Пример 7.36. Приведем структуру описания следующего объекта с помощью логики предикатов: «Солнечная система состоит из центрального светила и девяти планет, обращающихся вокруг него».

Выражения «состоит из» и «представляет собой» используют для того, чтобы описать структуру некоторого объекта. Описание может быть статическим и динамическим.

В случае статического описания указывается взаимное пространственное расположение частей. В случае динамического описания – законы их относительного перемещения в пространстве или описание иных видов движения (их зависимости от времени).

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

x y t (СОЛНЕЧНАЯ_СИСТЕМА (х, t) 

 СОСТОИТ_ИЗ(x, y, t) 

 z₀ z₁ … z₈ z (((z  y)  ((z = z₀) + (z = z₁) + … + (z = z₈)) 

 СОЛНЦЕ(z₀)  МЕРКУРИЙ(z₁)  ВЕНЕРА(z₂) 

ЗЕМЛЯ(z₃)  МАРС(z₄)  ЮПИТЕР(z₅)  САТУРН(z₆) 

 УРАН(z₇)  НЕПТУН(z₈) 

  КООРДИНАТЫ(z₀, t, )  ( = 0)) 

 (КООРДИНАТЫ (z_k, t, ) 

 (_k = a_k)  (_k = b_k)  (_k = c_k  d_k  t)))),

где  – логическая операция эквивалентности, «» – операция арифметического сложения; «» – операция арифметического умножения; t – время.

Для описания пространственного положения космических тел определяются: – координатный вектор в сферической системе координат  = < , , > (соответственно,  = 0 следует понимать как ( = 0)  ( = 0)  ( = 0), а  как кортеж из трех кванторов); a_k, b_k, c_k, d_k – числа, определяющие соответственно радиус орбиты, угол наклона орбиты, положение на орбите, период обращения.

Названия Солнца и девяти планет символизируют не только имя, но и все существенные характеристики соответствующего объекта. Например:

МАРС(z₄)  (ИМЯ (z₄, МАРС)  МАССА(z₄; 6,410¹³) 

 ПЕРИОД_ВРАЩЕНИЯ_ВОКРУГ_СВОЕЙ_ОСИ(z₄; 24,5) 

 СРЕДНИЙ_ДИАМЕТР(z₄, 6776)).

Общий вид такого описания можно представить схемой

x y t (А(x, t)  СОСТОИТ_ИЗ(x, y, t)  S(y, t)),

где S(y, t) – описание совокупности y как статической или динамической системы пространственно организованных элементов. □

Возможность получения новых знаний из уже имеющихся знаний (аксиом) посредством логического вывода делает логические модели представления знаний широко используемыми в системах искусственного интеллекта.

7.4.Семантические сети

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

Представим с помощью семантической сети следующие факты:

«все кашалоты – киты»,

«Моби Дик – кашалот»,

«киты имеют хвост».

Моби Дику посвящен одноименный роман американского писателя Германа Мелвилла.

Из данных фактов можно выделить следующие объекты, которые будут являться узлами сети: «Моби Дик», «кашалот», «кит», «хвост».

Взаимосвязь этих объектов опишем с помощью отношений:

- «часть – целое» (IS-A) (пример: «стол» IS-A «мебель»);

- «целое – частное» (PART-OF) (пример: «рука» PART-OF «тело»).

Семантическая сеть, описывающая факты, представлена на Рис. 7 .12.

Рис. 7.12. Представление фактов семантической сетью

Используя отношения IS-A и PART-OF, из имеющихся фактов можно вывести факты «Моби Дик – кит» и «Моби Дик имеет хвост».

Семантическая сеть представляет собой ориентированный граф с поименованными дугами и вершинами. Вершинам графа, описывающего семантическую сеть, соответствуют:

- события представляют собой действия, происходящие в реальном мире;

- объекты представляют объекты реального мира, а также их особенности и характеристики (цвет, размер, качество), а применительно к событиям – продолжительность, время, место.

Дуги графа семантической сети отображают многообразие отношений между объектами, которые условно можно разделить на четыре класса:

- лингвистические отношения в свою очередь подразделяются на глагольные (время, вид, род, залог, наклонение), атрибутивные (цвет, размер, форма) и падежные;

- логические отношения, используемые в алгебре высказываний: дизъюнкция, конъюнкция, отрицание, импликация и др.;

- теоретико-множественные: отношение части целого (PART-OF), отношение множества и элемента (IS-A);

- квантифицированные отношения общности и существования; они используются для представления таких утверждений как «Любой станок надо ремонтировать», «Существует работник А, обслуживающий склад Б».

Рассмотренный выше пример семантической сети отображал теоретико-множественные отношения между объектами, представляющие понятия предметной области. Рассмотрим использование семантических сетей для представления событий.

Чтобы представить некоторые знания о событиях в виде семантической сети, необходимо выделить данные события. События обычно описываются глаголом. После этого выделяются следующие объекты: