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

Рассмотрим основные понятия исчисления предикатов I порядка. В логике предикатов элементарным объектом, обладающим истинностным значением, является атомарная формула. Атомарная формула состоит из символического обозначения предиката и термов, выступающих в роли аргументов этого предиката. Для предиката должны быть заданы домены аргументов - множества, являющиеся областью их определения.

В общем случае обозначение предиката - это имя отношения, существующего между аргументами. Атомарная формула записывается как обозначение предиката, за которым в скобках располагаются несколько аргументов. Каждый аргумент - это терм. Общий вид атомарной формулы: P (t1, t2, …, tn). Здесь P обозначение предиката, а t1, t2, …, tn - термы. Терм - это либо константа, либо переменная, либо употребление функции [13].

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

1) атомарная формула - ППФ;

2) если А и В - ППФ, то ППФ будут и формулы:

 

~А, А^В, АvВ, А«В, А®В, $x A, "x A [13].

 

Построение теории некоторой области знаний с использованием логики предикатов начинается с анализа области знаний. Он выполняется следующим образом. Вначале выделяется множество значимых сущностей из этой области; данное множество называется областью интерпретации. На следующем этапе определяется, какие функции над элементами области интерпретации представляются важными, если только такие функции вообще существуют. Функция - это отображение n элементов из области интерпретации (n - количество аргументов функции) на один элемент этой области [13].

Затем идентифицируются значимые отношения, которые существуют между элементами области интерпретации. Отношение - это отображение n элементов из области интерпретации (n - количество аргументов отношения) на истинностное значение (т.е. на элемент из множества {истина, ложь}). В заключении значимые отношения оформляются синтаксически, т.е. при помощи аксиом.

Следующим шагом после установления области интерпретации описываемой области знаний будет выбор обозначений для представления элементов области интерпретации. Сначала подбираются обозначения для констант - a, b, c, и т.д. Значениями этих констант будут элементы из области интерпретации. Затем подбираются обозначения для каждой важной функции. Заметим, что функция сама по себе не может иметь значения. Значением может обладать только употребление функции. Функция, представленная некоторым обозначением, определяется семантически путем указания значений различных ее употреблений (т.е. указанием конкретных случаев отображения n элементов из области интерпретации на один элемент этой области). В заключение для каждого важного отношения из области интерпретации подбираются обозначения предикатов. Отношение, представленное обозначением предиката, определяется семантически путем указания истинностных значений различных конкретных случаев этого отношения (т.е. указанием того, как данное отношение отображает n элементов из области интерпретации на истинностное значение). Конкретный случай отношения представляется атомарной формулой, построенной на основе выбранных обозначений предикатов, функций и констант [13].

Интерпретация ППФ состоит из четырех типов присваивания:

3) Каждой константе, входящей в ППФ, приписывается некоторый элемент из области интерпретации.

4) Каждой переменной, входящей в ППФ, приписывается элемент из области интерпретации.

5) Каждому употреблению функции в ППФ приписывается элемент из области интерпретации. Множество таких присваиваний для некоторой конкретной функции определяет эту функцию семантически.

6) Каждой атомарной формуле, входящей в ППФ, приписывается истинностное значение. Множество таких присваиваний для некоторого конкретного отношения определяет это отношение семантически [13].

Фразовая форма логики предикатов - это способ записи формул, при котором употребляется только соединители &, v и ~. Литерал - это позитивная или негативная атомарная формула. Каждая фраза - это множество литералов, соединенных символом v. Негативные литералы размещаются в конце каждой фразы, а позитивные вначале. Фразу можно рассматривать как обобщение понятия импликация. Если А и В - атомарные формулы, то формула А→В может также быть записана как ~АvВ. Поскольку ~А - негативно, а В - позитивно, то фразовая форма будет иметь вид: Вv ~А.

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

Фраза Хорна - это фраза, содержащая только один позитивный литерал. Например, фраза CÚ ~EÚ ~FÚ ~G является фразой Хорна. Если воспользоваться обратной стрелкой, то эта фраза имеет вид CE,F,G [13].

Математические отношения, которые мы получили в 1 главе §3 пунктах 2 и 3, можно переписать с помощью фраз Хорна следующим образом.

Определим бинарное отношение смежности двух вершин А и В на множестве V в виде двуместного предиката дуга, где оба аргумента принадлежат домену V. Определенное нами отношение достижимости вершины А из вершины В в графе G(V,E), запишем предикатом путь с двумя аргументами, где оба аргумента принадлежат домену V.

 

 (1).

 

Зададим двуместный предикат, определяющий существование гамильтоновой цепи в графе G (V,E) из вершины А в вершину В - цепь, оба аргумента которого принадлежат домену V - конечному множеству вершин.

 

 (2)

 

Предикат количество, первый аргумент которого принадлежит домену 2VxV, а второй - домену N - множеству натуральных чисел, определяет количество вершин в пройденном простом пути. Предикат пр_цепь, где первые два аргумента принадлежат домену V, а третий принадлежит домену 2VxV, определяет простой путь между вершинами А и В, т.е. путь в котором каждая дуга встречается по одному разу.

Определим предикат ребро, оба аргумента которого принадлежат домену V, ставящий в соответствие каждой дуге ребро графа.

 

(3).

 

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

 

Предикат длина, определяет длину гамильтоновой цепи, первые два его аргумента принадлежат домену V, третий - домену N. Предикат вес, задает вес ребра, первые два его аргумента принадлежат домену V, третий - домену N.

Для задачи коммивояжера получаем следующее:

 

.

 

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

Для второй задачи определим бинарное отношение смежности двух вершин на множестве V в виде трехместного предиката дуга, первые два аргумента принадлежат домену V, а третий - домену N. Определенное нами отношение достижимости одной вершины из другой вершины в графе G(V,E), запишем двуместным предикатом путь, оба аргумента которого принадлежат домену V. Определение этого предиката в виде фразы Хорна будет аналогичным с фразой (1) (см. выше).

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

 

Предикат цепь определяет существование цепи из одной вершины в другую, где первые два аргумента принадлежат домену V, а третий принадлежит домену 2ExE. Предикат длина возвращает длину заданной цепи, первый аргумент, которого принадлежит домену 2ExE, а второй - домену N.