Представление знаний в интеллектуальных системах

1. Синтаксис логики предикатов. Примеры. Преобразование унарных предикатов в бинарные. Примеры Синтаксис логики предикатов. Примеры ПРЕДИКАТ — языковое выражение, обозначающее к.-л. свойство или отношение. П., указывающий на свойство отдельного предмета (напр., «зеленый», «теплый») Предикатом называется функция, которая возвращает логическое значение. С помощью предикатов часто определяют критерии сортировки или поиска.

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

Логика предикатов была разработана дли наиболее простого преобразования принципов логического мышления в записываемую форму. В логике предикатов вы, прежде всего, исключаете из своих предложений все несущественные слова. Затем вы преобразуете эти предложения, ставя в них на первое место отношение, а после него — сгруппированные объекты. В дальнейшем объекты становятся аргументами, между которыми устанавливается это отношение. В качестве примера в таблице 1 представлены предложения, преобразованные в соответствии с синтаксисом логики предикатов.

Логика предикатов, называемая также логикой первого порядка, допускает четыре типа выражений:

* Константы. Они служат именами индивидуумов: объектов, людей или событий.

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

* Предикатные имена. Они задают правила соединения констант и переменных, например, правила грамматики, процедуры, математические операции. Для предикатных имен используются символы наподобие следующих: Фраза, Посылать, Писать, Плюс, Разделить. Предикатное имя иначе называется предикатной константой.

* Функциональные имена представляют такие же правила, как и предикаты. Чтобы не спутать с предикатными именами, функциональные имена пишут одними строчными буквами: фраза, посылать, писать, плюс, разделить. Их называют также функциональными константами.

Синтаксис логики предикатов (пример)

* По-русски: Жак посылает книгу Мари,

* Логически: Посылка (Жак₂, Мари₄, Книга₂₂).

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

Унарные предикаты

Унарный предикат проверяет некоторое свойство одного аргумента. Типичный пример — функция, используемая в качестве критерия поиска первого простого числа.

Бинарные предикаты обычно сравнивают некоторое свойство двух аргументов. Например, чтобы отсортировать элементы по нестандартному критерию, программист передает алгоритму простую предикатную функцию. Это может понадобиться, если, например, элементы не могут корректно работать с оператором или сортировка должна выполняться по нестандартному критерию.

Унарные и бинарные предикаты имеют соответственно один и два аргумента. Фраза «Сократ есть человек» представима унарным предикатом Человек (Сократ), а «Жак любит Мари» — бинарным Любит (Жак₂, Мари₄). Любой унарный предикат можно преобразовать в бинарный следующим образом. Унарный предикат состоит из предикатного имени и значения своего единственного аргумента. Следовательно, его формат такой: Предикатное_имя (значение_аргумента). Значение аргумента есть конкретизация предикатного имени или переменной. Например, Человек (Сократ) указывает, что имя собственное «Сократ» — конкретизация имени совокупности «человек», а Человек (х) указывает, что х — человек (не что-либо иное). Фразу «Сократ — человек» можно представить бинарным предикатом Конкр (Сократ, человек).

2. Основные стратегии решения задач. Предварительные понятия и примеры Основные стратегии решения задач Общая схема для представления задач называется пространством состояний. Пространство состояний — это граф, вершины которого соответствуют ситуациям, встречающимся в задаче («проблемные ситуации»), а решение задачи сводится к поиску пути в этом графе. Процесс решения задачи включает в себя поиск в графе, при этом, как правило, возникает проблема, как обрабатывать альтернативные пути поиска. Две основные стратегии перебора альтернатив, а именно поиск в глубину и поиск в ширину.

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

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

* поставить, А на стол или

* поставить, А на С, или

* поставить С на А. (Рис.)

Ясно, что альтернативу «поставить С на стол» не имело смысла рассматривать всерьез, так как этот ход никак не влияет на ситуацию.

Как показывает рассмотренный пример, с задачами такого рода связано два типа понятий:

(1) Проблемные ситуации.

(2) Разрешенные ходы или действия, преобразующие одни проблемные ситуации в другие.

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

3. Преобразование унарных предикатов в бинарные. Примеры. Преобразование m-арных предикатов в произведение бинарных.

Преобразование унарных предикатов в бинарные Унарный предикат проверяет некоторое свойство одного аргумента. Типичный пример — функция, используемая в качестве критерия поиска первого простого числа.

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

Унарный предикат состоит из предикатного имени и значения своего единственного аргумента. Следовательно, его формат такой: Предикатное_имя (значение_аргумента). Значение аргумента есть конкретизация предикатного имени или переменной. Например, Человек (Сократ) указывает, что имя собственное «Сократ» — конкретизация имени совокупности «человек», а Человек (х) указывает, что х — человек (не что-либо иное). Фразу «Сократ — человек» можно представить бинарным предикатом Конкр (Сократ, человек).

Преобразование m-арных предикатов в произведение бинарных Фразу «Жак посылает книгу Мари» нетрудно представить тернарным (т.е. с тремя аргументами) предикатом:

Посылка (Жак₂, Мари₄, Книга₂₂).

Определив новые предикаты, можно представить эту фразу произведением (конъюнкцией) бинарных предикатов:

Отправитель (Посылка, Жак₂)

Получатель (Посылка, Мари₄)

Объект (Посылка, Книга₂₂).

Данная логическая формула читается так: «отправитель посылки — Жак, получатель посылки — Мари и объект посылки — книга».

Этот пример подсказывает правило преобразования m-арных предикатов (с m аргументами) в эквивалентное произведение бинарных предикатов. Всякий m-арный предикат состоит из предикатного имени и m значений аргументов:

Предикатное_имя (значение₁, значение₂, …, значение_m).

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

Посылка (отправитель, получатель, объект).

Функция «отправитель посылки» учитывается первым аргументом, функция «получатель посылки» — вторым, функция «объект посылки» — третьим. Первоначально выбранный порядок аргументов для соответствия «функция — аргумент» может быть произвольным, но должен сохраняться неизменным. Функциональную организацию m-арного предиката можно представить так:

Предикатное_имя (функция₁, функция₂, …, функция_т).

При записи m-арного предиката через бинарные предикаты используется специальное соглашение, позволяющее сохранить и явно указать соответствующие функциональные отношения. Каждая функция становится именем бинарного предиката, первый аргумент которого является именем исходного m-арного предиката, а второй — значением относящегося к этой функции аргумента. Функциональная организация исходного m-арного предиката и значения его аргументов представляются произведением бинарных предикатов:

Функция₁ (предикатное_имя, значение₁) Функция_m (предикатное_имя, значение_m).

4. Основные стратегии решения задач. Поиск в ширину Основные стратегии решения задач Общая схема для представления задач называется пространством состояний. Пространство состояний — это граф, вершины которого соответствуют ситуациям, встречающимся в задаче («проблемные ситуации»), а решение задачи сводится к поиску пути в этом графе. Процесс решения задачи включает в себя поиск в графе, при этом, как правило, возникает проблема, как обрабатывать альтернативные пути поиска. Две основные стратегии перебора альтернатив, а именно поиск в глубину и поиск в ширину.

Поиск в ширину В противоположность поиску в глубину стратегия поиска в ширину предусматривает переход в первую очередь к вершинам, ближайший к стартовой вершине. В результате процесс поиска имеет тенденцию развиваться более в ширину, чем в глубину, что иллюстрирует Поиск в ширину программируется не так легко, как поиск в глубину. Причина состоят в том, что нам приходится сохранять все множество альтернативных вершин-кандидатов, а не только одну вершину, как при поиске в глубину. Более того, если мы желаем получить при помощи процесса поиска решающий путь, то одного множества вершин недостаточно. Поэтому мы будем хранить не множество вершин-кандидатов, а множество путей-кандидатов. Таким образом, цель в ширину (Пути, Решения) истинна только тогда, когда существует путь из множества кандидатов Пути, который может быть продолжен вплоть до целевой вершины. Этот продолженный путь и есть Решение.

5. Явное представление ссылок. Представление функциями. Примеры Явное представление ссылок Символы объектного языка, такие как Жак₂, Мари₄ и Книга₂₂, введены для того, чтобы избежать двусмысленности ссылок на вполне определенных людей и книгу. Фраза «Жак посылает книгу Мари» указывает определенное «почтовое событие» (или «действие отправления»), на которое желательно иметь возможность ссылаться в дальнейшем. Следовательно, придется дать ему имя индивидуума Посылка₈ и указать, что оно — часть множества событий с именем совокупности посылки. Перевод фразы на бинарные предикаты выглядит так:

Отправитель (Посылка₈, Жак₂)

Получатель (Посылка₈, Мари₄)

Объект (Посылка₈, Книга₂₂)

Элем (Посылка₈, посылки) Предикатное имя Элем означает «есть элемент такого-то множества»

Представление функциями Отношения между значением Посылка₈ и аргументами тернарного предиката Посылка можно выразить также функциями на множестве почтовых посылок (одной переменной). Функция называется также функциональной формой. Фраза «Жак посылает книгу Мари» выражается в терминах функций следующей формой:

Равно (отправитель (Посылка₈), Жак₂)

Равно (получатель (Посылка₈), Мари₄)

Равно (объект (Посылка₈), Книга₂₂)

Элем (Посылка₈, посылки).

Предикат Равно представляет отношение равенства. Это выражение используют определенные на множестве «посылок» функции, значения которых представляют конкретизации, касающиеся Посылки₈.

Примеры Рассмотрим фразы той же синтаксической формы, что и «Жак посылает книгу Мари», но с кванторами По-русски: Жак посылает что-то каждому (всем одно и то же),

Логически: Посылка (Жак₂, х, у).

По-русски: Жак посылает что-то каждому (но не обязательно всем одно и то же) Логически-1: Посылка (Жак₂, х, у),

Логически-2: Посылка (Отправитель (посылка, Жак₂) Получатель (посылка, х) Объект (посылка, у)),

Логически-3: (Отправитель z (Жак₂) Получатель (z, x) Объект (z, y) Эм (z, посылки)).

Три представления фразы «Жак посылает что-то каждому» соответствует трем представлениям фразы «Жак посылает книгу Мари».

6. Основные стратегии решения задач. Стратегия поиска в глубину Основные стратегии решения задач Общая схема для представления задач называется пространством состояний. Пространство состояний — это граф, вершины которого соответствуют ситуациям, встречающимся в задаче («проблемные ситуации»), а решение задачи сводится к поиску пути в этом графе. Процесс решения задачи включает в себя поиск в графе, при этом, как правило, возникает проблема, как обрабатывать альтернативные пути поиска. Две основные стратегии перебора альтернатив, а именно поиск в глубину и поиск в ширину.

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

если В — это целевая вершина, то положить Реш = [В], или если для исходной вершины В существует вершина-преемник В1, такая, что можно провести путь Реш1 из В1 в целевую вершину, то положить Реш = [В | Peш1]. Рис. 11.4

На Пролог это правило транслируется так:

решить (В, [В]) :;

цель (В).

решить (В, [В | Реш1]) :;

после (В, В1),

решить (В1, Реш1).

Эта программа и есть реализация поиска в глубину. Мы говорим «в глубину», имея в виду тот порядок, в котором рассматриваются альтернативы в пространстве состояний. Всегда, когда алгоритму поиска в глубину надлежит выбрать из нескольких вершин ту, в которую следует перейти для продолжения поиска, он предпочитает самую «глубокую» из них. Самая глубокая вершина — это вершина, расположенная дальше других от стартовой вершины.

7. Семантика логики предикатов Стратегия определения семантических значений компонент и формул логики предикатов базируется на понятии интерпретации логической формулы. Напомним это понятие.

Объектами изучения естественных и формальных языков являются в частности, синтаксис (который позволяет распознавать фразы среди набора слов) и семантика (которая придает определенное значение фразам). В равной мере это относится к исчислению высказываний.

Уже отмечалось, что высказывание либо истинно, либо ложно. Поэтому введем семантическую область {И, Л}. Интерпретировать формулу — значит приписать ей одно из двух значений истинности И или Л.

Семантика (то есть набор правил интерпретации формул) должна быть композиционной: значение формулы должно быть функцией значений ее составляющих. Точнее, значение истинности формулы зависит только от структуры этой формулы и от значений истинности составляющих ее высказываний. Таким образом, связки исчисления высказываний представляют функции истинности: например значение истинности формулы будет известно, если известны значения истинности Х и Y. Следующие две таблицы описывают семантику отрицания и бинарных связок.

Интерпретация — это отображение i, сопоставляющее каждому элементарному высказыванию р некоторое значение истинности. Интерпретацию i, заданную на множестве элементарных высказываний, можно распространить (продолжить) на множество формул (высказываний) посредством таблиц истинности. Соответствующее продолжение (расширение) I тоже называется интерпретацией. Интерпретация, при которой истинностное значение формулы есть И, называется моделью этой формулы.

Литера — это элементарное высказывание или его отрицание. Литеры р и противоположны. Интерпретация определяет разбиение множества L литер на два подмножества Lи и Lл, каждое из которых содержит по одному элементу из каждой пары противоположных литер.

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

Точнее, интерпретация I — это тройка (D, Ic, Iv) со следующими свойствами:

· D — непустое множество, область интерпретации.

· Ic — функция, которая сопоставляет каждой функциональной n-местной константе f некоторую функцию Ic (f) из Dn в D и которая сопоставляет каждой предикатной m-местной константе Р некоторую функцию Ic (Р) из Dm в {И, Л}.

· Iv — функция, сопоставляющая каждой переменной некоторый элемент из D.

Теперь можно задать для интерпретации I = (D, Ic, Iv) такие правила, которые каждой формуле, А ставят в соответствие некоторое значение истинности I (A), а каждому терму t сопоставляется элемент I (t) из D.

· Если х — свободная переменная, то I (x)=def Iv (x).

· Если f — функциональная n-местная константа, t1, …, tn — термы, то I (f (t1, …, tn)) =def= =(Ic (f))(I (t1), …, I (tn))

· Если Р — предикатная m-местная константа, t1, …, tm — термы, то I (P (t1, …, tm)) =def= =(Ic (P))(I (t1), …, I™)

· Если s и t термы, то I (s=t) есть И при I (s)=I (t), а иначе Л.

· Если, А и В — формулы, то А, (АВ), (АВ), (АВ) и (АВ) интерпретируются как в исчислении высказываний.

Осталось задать интерпретацию для двух типов квантифицированных формул. Введем сначала одно понятие. Если I — интерпретация c областью DI, x — переменная, d — элемент из DI, то Ix/d означает такую интерпретацию J, что DJ = DI, Jc = Ic, Jv (x) = d и Jv (y) = Iv (y) для всех свободных переменных у отличных от х.

Правила интерпретации будут такими:

· Если, А — формула и х — переменная, то I (хА) есть И при условии, что Ix/d (А) есть И для всех элементов d из D.

· Если, А — формула и х — переменная, то I (хА) есть И при условии, что Ix/d (А) есть И хотя бы для одного элемента d из D

Формула, А исчисления предикатов называется истинной при интерпретации I, если I (A)=И.

Теперь видно, что запрещение перекрытия кванторов, действующих на одну и ту же переменную, не является существенным ограничением. В частности, интерпретируется как и интерпретируется как. Ясно также, почему требуется условие Dш; без него естественные импликации не всегда были бы истинны.

Заметим также, что эти правила интерпретации соответствует интуитивным представлениям. В частности, формальное значение кванторов хорошо моделирует их естественное значение.

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

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

Прежде всего задаем семантическое значение для каждого базисного выражения. Затем вводим семантические правила вычисления семантических значений сложных логических формул по известным значениям семантических компонент. Иначе говоря, приписываем семантическое значение все более и более крупным составляющим логической формулы, так что в конце концов семантическое значение будет приписано и всей формуле. Этот процесс называется композиционным методом.

Предположим для определенности, что универсум рассуждения содержит лишь имена трех людей: «Жак Дюпон», «Мари Дюран», «Джорж Буль» — и название одной книги: «Законы мышления». С каждым именем индивидуума, используемым в логических формулах, можно следующим образом связать одно из перечисленных имен, которое станет семантическим значением:

Левый столбец составлен из лингвистических сущностей, т. е. из лексических компонент особой синтаксической категории некоторого языка. Правый — из сущностей реального мира.

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

Фундаментальным понятием семантики является понятие истины реального мира. Более общее понятие — истина в модели. Здесь моделью является реальный мир. Состояние реального мира позволяет приписывать семантические значения «истинно» или «ложно» предикатам и функциям. Например:

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

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

8. Функции, выполняемые экспертной системой

Экспертная система — это программа, которая ведет себя подобно эксперту в некоторой проблемной области.

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

Часто к экспертным системам предъявляют дополнительное требование — способность иметь дело с неопределенностью и неполнотой. Информация о поставленной задаче может быть неполной или ненадежной; отношения между объектами предметной области могут быть приближенными. Например, может не быть полной уверенности в наличии у пациента некоторого симптома или в том, что данные, полученные при измерении, верны; лекарство может стать причиной осложнения, хотя обычно этого не происходит. Во всех этих случаях необходимы рассуждения с использованием вероятностного подхода.

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

· решение задач с использованием знаний о конкретной предметной области — возможно, при этом возникнет необходимость иметь дело с неопределенностью

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

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

9. (10)Структура экспертной системы

Грубая структура экспертной системы

При разработке экспертной системы принято делить ее на 3 основных модуля, показано на рис. 14.1:

(1) база знаний,

(2) машина логического вывода,

(3) интерфейс с пользователем.

Рис. 14. 1. Структура экспертной системы.

База знаний содержит знания, относящиеся к конкретной прикладной области, в том числе отдельные факты, правила, описывающие отношения или явления, а также, возможно, методы, эвристики и различные идеи, относящиеся к решению задач в этой прикладной области. Машина логического вывода умеет активно использовать информацию, содержащуюся в базе знаний. Интерфейс с пользователем отвечает за бесперебойный обмен информацией между пользователем и системой; он также дает пользователю возможность наблюдать за процессом решения задач, протекающим в машине логического вывода. Принято рассматривать машину вывода и интерфейс как один крупный модуль, обычно называемый оболочкой экспертной системы, или, для краткости, просто оболочкой.

В описанной выше структуре собственно знания отделены от алгоритмов, использующих эти знания. Такое разделение удобно по следующим соображениям. База знаний, очевидно, зависит от конкретного приложения. С другой стороны, оболочка, по крайней мере в принципе, независима от приложений. Таким образом, разумный способ разработки экспертной системы для нескольких приложений сводится к созданию универсальной оболочки, после чего для каждого приложения достаточно подключить к системе новую базу знаний. Разумеется, все эти базы знаний должны удовлетворять одному и тому же формализму, который оболочка «понимает». Практический опыт показывает, что для сложных экспертных систем наш сценарий с одной оболочкой и многими базами знаний работает не так гладко, как бы этого хотелось, за исключением тех случаев, когда прикладные области очень близки. Тем не менее даже если переход от одной прикладной области к другой требует модификации оболочки, то по крайней мере основные принципы ее построения обычно удается сохранить.

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

(1) Выбрать формальный аппарат для представления знаний.

(2) Разработать механизм логического вывода, соответствующий этому формализму.

(3) Добавить средства взаимодействия с пользователем.

(4) Обеспечить возможность работы в условиях неопределенности.

10. (9)Модальная логика предикатов. Модальные операторы. Примеры модальных операторов В обыденном языке часто говорят о допустимости чего-либо, о гипотетических событиях, целях, которые можно пытаться достигнуть, догадках о будущем. Большая часть фраз языка может быть то истинной, то ложной в зависимости от обстоятельств, текущего момента, точки зрения каждого из нас. В естественных языках модальности «возможный», «необходимый» и допустимый выражаются вспомогательными глаголами, такими как «должен» и «могу».

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

Для обозначения модальности «необходимо» используется символ ?. Формула? F читается «необходимо, чтобы F» или «F необходимо». Двойственный? оператор обозначается через ?. Формула? F читается «возможно, что F» или «F возможно». Один из этих операторов принимается за основной, а другой определяется через него и отрицание (эквивалентность ?F?F можно установить, применяя доводы, подобные тем, которые можно использовать при доказательстве соотношения).

В обыденном языке употребляются и другие модальные формы, которые важно перевести в логику. Деонтическая логика вводит модальности «разрешено» «обязательно», реализующая модальные языковые конструкции «разрешается» «надо, чтобы». Эпистемическая логика, или логика знания, исследует модальности «знания» и «веры», тогда как временная логика вводит модальности «иногда» и «всегда» (в «будущем» и «прошлом») вместе с их отрицаниями «часто» и «никогда».

Ввиду формального сходства между этими логическими системами их часто изучают все вместе или хотя бы по группам. Часто используют термин модальная логика для обозначения совокупности этих логик. Старейшая среди них — логика возможного. Часто именно ее называют модальной.

Название модальная логика происходит от того, что модальные логические системы вводят такие операторы над логическими формулами, которые позволяют модифицировать их интерпретацию. Например, в утверждениях «Возможно, что F», «Поль думает, что F», «Часто правда, что F», «В будущем, возможно, будет правда, что F», предшествующие логической формуле F выражения являются модальными операторами. Они могут относиться к какой угодно логической формуле F. Значение истинности зависит не только от значения истинности формулы F, которую они содержат, но и от момента провозглашения модальной формулы (временные логики), от человека, который думает, что F, или верит, что F (логика веры), или от необходимого, возможного или случайного характера некоторого факта (логики возможного).

Модальные операторы Имеется сходство между определениями каждой из пар операторов (вроде «возможно"/ «определено», «иногда"/ «всегда» и т. д.) и определением пары кванторов существования/ общности. Это подсказывает следующее определение модальных операторов:

Модальный оператор общностиявляется:

· либо именем модального оператора,

· либо выражением, состоящим из имени модального оператора, за которым следует список (t1, t2, …, tn) термов ti (i=1,2, …, n).

Модальный оператор существования Ўопределяется через отрицание модального оператора общности:

ЎF =defF.

Примеры модальных операторов

· Алетические операторы:

— ?: необходимо;

?А истинно тогда и только тогда, когда

А необходимо истинно (а)

или, А абсолютно истинно (b)

или, А истинно во всех возможных мирах. (с)

— ?: возможно;

?А истинно,

если, А может оказаться истинным, (а)

или если, А условно истинно, (b)

или если, А истинно в некотором из возможных миров. (с)

(Интерпретации (а), (b) и © для? и? соответственны; в каждой из пар (а), (b) и © сгруппированы двойственные интерпретации).

· Временные оператор:

— G: всегда (в будущем);

GА истинно, если, А остается истинным навсегда.

— H: всегда (в прошлом);

HА истинно, если, А всегда было истинным.

— F: иногда (в будущем);

FА истинно, если, А иногда будет истинным.

— Р: иногда (в прошлом);

РА истинно, если, А иногда оказывалось истинным.

— U: до тех пор пока;

U (А, В) истинно, если, А истинно (начиная с текущего момента) до тех пор, пока В не станет истинным в некоторый момент в будущем.

(G, F и Н, Р двойственные операторы в смысле FA и РА. Некоторые временные логики учитывают только будущее. В этом случае часто употребляются обозначения? и? соответственно для операторов G и F)

· Эпистемические операторы:

— верит (а)

верит (а)А истинно, если индивид, а верит в формулу А

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

11. Синтаксис модальной логики предикатов. Примеры Пусть М1, М2, …, Мn — модальные ораторы. Правила образования модальных формул таковы:

· Все правила построения из логики предикатов (первого порядка) являются также правилами построения в модальной логике предикатов.

· Если F — формула и Мi — модальный оператор, то MiF — формула.

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

Примеры

· По-русски: Возможно, что Жак посылает книгу Мари,

Логически:? Посылка (Жак₂, Мари₄, Книга₂₂).

· По-русски: Не было возможным, чтобы Жак посылал что-нибудь каждому,

Логически Р ((? (Отправитель (z, Жак₂)Получатель (z, x) Объект (z, y) Элем (z, посылки))))

(Словесное прочтение этой формулы таково: в прошлом (Р) не является () возможным (?), чтобы Жак посылал что-нибудь каждому).

· По-русски: Если Жак верит данному высказыванию, то он верит, что верит ему (аксиома позитивной интроспексии)

Логически: верит (Жак₂) р верит (Жак₂)(верит (Жак₂)р).

· По-русски: Если Жак не верит данному высказыванию, то он верит, что не верит ему (аксиома негативной интроспексии)

Логически: верит (Жак₂) р верит (Жак₂)(верит (Жак₂)р).

· По-русски: Если факт, что Жак верит данному высказыванию, влечет, что оно истинно, то Жак знает это высказывание,

Логически: (верит (Жак₂) р р) (знает (Жак₂) р). (Во многих случаях желательно, чтобы убеждения людей были истинными. Это приводит к понятию скорее знания, чем веры)

· По-русски: Жак верит, что он послал книгу (а не что-нибудь иное) Мари,

Логически: верит (Жак₂) (Рх[Посылка (Жак₂, Мари₄, х) Элем (х, книги)].

· По-русски: Жак верит, что он послал книгу (вполне определенную) Мари,

Логически: х [верит (Жак₂) (Р Посылка (Жак₂, Мари₄, х) Элем (х, книги)].

(Последнее выражение показывает, что в системе убеждений Жака имеется формула типа [Р Посылка (Жак₂, Мари₄, х) Элем (х, книги)]. Но ее окончательный вид зависит от конкретного объекта, к которому относится переменная х. Предпоследнее выражение показывает, что в системе убеждений Жака содержится формула (Рх[ПосылкаЭлем).)

12. Правила «если-то» для представления знаний

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

· если предварительное условие Р то заключение (вывод) С

· если ситуация S то действие А

· если выполнены условия С1 и С2 то не выполнено условие С

" Если-то" -правила обычно оказываются весьма естественным выразительным средством представления знаний. Кроме того, они обладают следующими привлекательными свойствами:

· Модульность: каждое правило описывает небольшой, относительно независимый фрагмент знаний.

· Возможность инкрементного наращивания: добавление новых правил в базу знаний происходит относительно независимо от других правил.

· Удобство модификации (как следствие модульности): старые правила можно изменять и заменять на новые относительно независимо от других правил.

· Применение правил способствует прозрачности системы.

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

(1) Вопросы типа «как»: Как вы пришли к этому выводу?

(2) Вопросы типа «почему»: Почему вас интересует эта информация?

Если

1 тип инфекции — это первичная бактериемия и

2 материал для посева был отобран стерильно, и

3 предполагаемые ворота инфекции — желудочнокишечный тракт То имеются веские аргументы (0.7) за то, что инфекционный агент является бактерией Рис. 14. 2. «Если-то» -правило медицинской консультативной системы MYCIN (Shortliffe, 1976). Параметр 0.7 показывает степень доверия этому правилу.

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

если условие, А то заключение В с уверенностью F

Правила, содержащиеся в базе знаний, имеют вид ИмяПравила: если Условие то Заключение где Заключение — это простое утверждение, а Условие — это набор простых утверждений, соединенных между собой операторами и и или. Мы также разрешим в части условия использовать оператор не, хотя и с некоторыми оговорками. Заметим, что оператор и связывает операнды сильнее, чем или, что соответствует обычным соглашениям.

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

Если лампа1 включена и лампа1 не работает и предохранитель1 заведомо цел то лампа1 заведомо неисправна.

Вот другой пример правила:

Если радиатор работает то предохранитель1 заведомо цел.

Эти два правила опираются на некоторые факты (относящиеся к нашей конкретной схеме), а именно что лампа1 соединена с предохранитель1 и что лампа1 и радиатор имеют общий предохранитель. Для другой схемы нам понадобится еще один набор правил. Поэтому было бы лучше сформулировать правила в более общем виде (используя прологовские переменные) так, чтобы они были применимы к любой схеме, а затем уже дополнять их информацией о конкретной схеме. Например, вот одно из полезных правил: если прибор включен, но не работает, а соответствующий предохранитель цел, то прибор неисправен.

Рис. 14. 6. Соединения между предохранителями и приборами в простой электрической схеме.

На наш формальный язык это транслируется так:

правило_поломки:

если Прибор включен и

не (Прибор работает) и Прибор соединен с Предохранитель и Предохранитель заведомо цел То Прибор заведомо неисправен.

База знаний такого рода показана на рис. 14. 7.

13. Трехзначная семантика для модальной логики предикатов. Пример Семантику для модальной логики предикатов можно определить, как для классической. Проиллюстрируем модальную семантику, введя аппроксимацию (замена одних объектов другими, в том или ином смысле близкими к исходным, но более простыми) некоторых форм логики возможного с помощью трехзначной логики. Бинарная логика с двумя значениями {Л или 0, и И или 1} самая элементарная. Истина и ложь — это два множества высказываний, и законы (классической) логики утверждают, что любое высказывание есть элемент хотя бы одного из этих множеств (закон исключения третьего) и что никакое высказывание не является элементом сразу двух этих множеств (закон противоречия).

Какие изменения надо внести в эту теорию, если вводятся модальности «возможно» и «необходимо»? Надо рассмотреть несколько классов высказываний. Обозначим через N класс «необходимых» высказываний, через Р — «возможных», через I -«невозможных» (или «абсурдных») и через С — «нейтральных» (или «возможно (случайно) ложных»). Никакое высказывание не принадлежит одновременно N и С или I и Р. Далее, класс N содержится в Р, а класс I — в С. Это отражено в законах следования возможного из необходимого и нейтрального из абсурдного:

любое необходимое высказывание возможно;

любое абсурдное высказывание не является необходимым.

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

любое высказывание принадлежит либо N, либо U, либо I.

Посмотрим, как эту теорию модальности можно перевести в алгебраическую форму. Каждому из классов N, U, I соответствует своя интерпретация: «необходимо», «проблематично», «невозможно». Возьмем три символа 2, 1, 0. Эти логические значения сопоставляем указанным интерпретациям. Каждому высказыванию можно приписать логическое значение. Эта трехзначная логика предложена Лукасевичем.

В логике Лукасевича каждое высказывание обладает одним из значений 0, 1 или 2 (интерпретируемых как семантическое значение высказывания). Семантические значения можно находить, используя таблицы, приведенные ниже. Они задают семантику для аппроксимации модальной логики возможного с помощью трехзначной логики. Иное описание этой семантики возможно, но мы не будем его рассматривать.

14. Экспертные системы. Разработка оболочки Если мы посмотрим на правила наших двух маленьких баз знаний рис. 14.5 и 14.7, мы сразу увидим, что они по своему смыслу эквивалентны правилам Пролога. Однако, с точки зрения синтаксиса Пролога, эти правила в том виде, как они написаны, соответствуют всего лишь фактам. Для того, чтобы заставить их работать, самое простое, что может прийти в голову, это переписать их в виде настоящих прологовских правил. Например:

Животное это млекопитающее :;

Животное имеет шерсть;

Животное 'кормит детенышей' молоком.

Животное это хищник :;

Животное это млекопитающее, Животное ест мясо.

.. .

Теперь эта программа сможет подтвердить, что тигр по имени Питер — это действительно тигр, если мы добавим в нее некоторые из свойств Питера (в виде прологовских фактов):

питер имеет шерсть.

питер ленив.

питер большой.

питер имеет 'рыжевато-коричневый цвет'.

питер имеет 'черные полосы'.

питер ест мясо.

Тогда мы можем спросить:

?- питер это тигр.

yes

?- питер это гепард.

no

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

(1) Мы не можем попросить систему объяснить свой ответ; например, как она установила, что Питер это тигр, и почему Питер это не гепард.

(2) Прежде, чем задать вопрос, нужно ввести в систему всю необходимую информацию (в виде прологовских фактов). Но тогда пользователь, возможно, введет какую-нибудь лишнюю информацию (как в нашем примере) или же упустит какую-нибудь информацию, имеющую решающее значение. В первом случае будет проделана ненужная работа, а во втором — система будет давать неверные ответы.

Для того, чтобы исправить эти два недостатка, мы нуждаемся в более совершенном способе взаимодействия между пользователем и системой во время и после завершения процесса рассуждений. Поставим себе целью добиться того, чтобы система взаимодействовала с пользователем так, как в следующем примере диалога (ответы пользователя даются полужирным шрифтом, реплики пролог-системы — курсивом):

Пожалуйста, спрашивайте:

питер это тигр.

Это правда: питер имеет шерсть?

да.

Это правда: питер ест мясо?

нет.

Это правда: питер имеет острые зубы?

да.

Это правда: питер имеет когти?

почему.

Чтобы проверить по прав3, что питер это хищник, Чтобы проверить по прав5, что питер это тигр Это был ваш вопрос Это правда: питер имеет когти?

да.

Это правда: питер имеет глаза, направленные вперед?

да.

Это правда: питер имеет рыжевато-коричневый цвет?

да.

Это правда: питер имеет черные полосы?

да.

(питер это тигр) это правда Хотите узнать, как?

да.

питер это тигр было выведено по прав5 из питер это хищник, было выведено по прав3 из питер это млекопитающее было выведено по прав1 из питер имеет шерсть было сказано и

питер имеет острые зубы было сказано и

питер имеет когти было сказано и

питер имеет глаза, направленные вперед было сказано и

питер имеет рыжевато-коричневый цвет было сказано и

питер имеет черные полосы было сказано Как видно из диалога, система задает пользователю вопросы, касающиеся «примитивной» информации, например:

Это правда: питер ест мясо?

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

(1) сообщив системе в качестве ответа на вопрос необходимую информацию или

(2) спросив систему, почему эта информация необходима.

Последняя из двух возможностей полезна, поскольку она позволяет пользователю заглянуть внутрь системы и увидеть ее текущие намерения. Пользователь спросит «почему» в том случае, когда вопрос системы покажется ему не относящимся к делу либо когда ответ на вопрос системы потребует от него дополнительных усилий. Из объяснений системы пользователь поймет, стоит ли информация, которую запрашивает система, тех дополнительных усилий, которые необходимо приложить для ее приобретения. Предположим, например, что система спрашивает: «Это животное ест мясо?» Пользователь, не знающий ответа на этот вопрос, поскольку он никогда не видел, как это животное ело что-либо, может решить, что не стоит ждать, пока он застанет животное за едой и убедится, что оно действительно ест мясо.

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

Процесс рассуждений

Наш интерпретатор будет принимать вопрос и искать на него ответ. Язык правил допускает, чтобы в условной части правила была И / ИЛИ-комбинация условий. Вопрос на входе интерпретатора может быть такой же комбинацией подвопросов. Поэтому процесс поиска ответов на эти вопросы будет аналогичен процессу поиска в И / ИЛИ-графах, который мы обсуждали в гл. 13.

Ответ на заданный вопрос можно найти несколькими способами в соответствии со следующими принципами:

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

· если В найден в базе знаний в виде факта, то Отв — это «В это правда»

· если в базе знаний существует правило вида

· «если Условие то В» ,

· то для получения ответа Отв рассмотрите Условие

· если вопрос В можно задавать пользователю, спросите пользователя об истинности В

· если в имеет вид В1 и В2, то рассмотрите В1, а затем,

если В1 ложно, то положите Отв равным «В это ложь», в противном случае рассмотрите В2 и получите Отв как соответствующую комбинацию ответов на вопросы В1 и В2

· если В имеет вид В1 или В2, то рассмотрите В1, а затем,

если В1 истинно, то положите Отв равным «В1 это правда», в противном случае рассмотрите В2 и получите Oтв как соответствующую комбинацию ответов на вопросы В1 и В2.

Вопросы вида не В обрабатываются не так просто, и мы обсудим их позже.

Формирование ответа на вопрос «почему»

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

а — это правда?

В ответ пользователь может спросить:

почему?

Объяснение в этом случае выглядит примерно так:

Потому, что Я могу использовать а, чтобы проверить по правилу Па, что b, и Я могу использовать b,

чтобы проверить по правилу Пb, что с, и Я могу использовать с, чтобы проверить по правилу Пc, что d, и

.. .

Я могу использовать y,

чтобы проверить по правилу Пy, что z, и

z — это ваш исходный вопрос.

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

Рис. 14. 8. Объяснение типа «почему». На вопрос «Почему вас интересует текущая цель?» дается объяснение в виде цепочки правил и целей, соединяющей текущую цель с исходным вопросом пользователя, находящимся в верхушке дерева. Эта цепочка называется трассой.

Будем называть такую цепочку трассой. Трассу можно себе представлять как цепочку правил, соединяющую в И / ИЛИ-дереве вопросов текущую цель с целью самого верхнего уровня так, как это показано на рис. 14.8. Таким образом, для формирования ответа на вопрос «почему» нужно двигаться в пространстве поиска от текущей цели вверх вплоть до самой верхней цели. Для того, чтобы суметь это сделать, нам придется в процессе рассуждений сохранять трассу в явном виде.

Формирование ответа на вопрос «как»

Получив ответ на свой вопрос, пользователь возможно захочет увидеть, как система пришла к такому заключению. Один из подходящих способов ответить на вопрос «как» — это представить доказательство, т. е. те правила и подцели, которые использовались для достижения полученного заключения. Это доказательство в случае нашего языка записи правил имеет вид решающего И / ИЛИ-дерева. Поэтому наша машина логического вывода будет не просто отвечать на вопрос, соответствующий цели самого верхнего уровня — этого нам недостаточно, а будет выдавать в качестве ответа решающее И / ИЛИ-дерево, составленное из имен правил и подцелей. Затем это дерево можно будет отобразить на выходе системы в качестве объяснения типа «как». Объяснению можно придать удобную для восприятия форму, если каждое поддерево печатать с надлежащим отступом, например:

питер это хищник было выведено по прав3 из питер это млекопитающее было выведено по прав1 из питер имеет шерсть было сказано и

питер ест мясо было сказано

15. Рассуждения, использующие логические формулы. Рассуждения по поводу знаний Исчисление предикатов содержит правила вывода, применимые к одним логическим формулам для получения других. Особенно важны правила «modus ponens» (Если Х и (Х Y) — теоремы, то Y есть теорема) и «обобщения» (Если х не связана в теореме Р, то хР — теорема). Правила вывода порождают некоторое множество формул из примитивных (исходных, первоначальных) формул. В исчислении предикатов выведенные формулы называются «теоремами», а последовательность примененных для их получения правил вывода (с указанием используемых в них формул) — «доказательством теоремы». Многочисленные приложения исчисления предикатов к ИИ можно толковать как методы доказательства теорем.

При доказательстве теорем обычно используют процедуры опровержения. Множество гипотез {Hj}, подходящих для доказательства теоремы, добавляют к множеству присущих области экспертизы аксиом {Ai}. Затем стремятся получить опровержение (или прийти к противоречию), присоединяя {} - отрицание утверждения теоремы — к системе {Hj, Ai} и пытаясь доказать формулу