Delphi | Сети | ПК | Маршрутизаторы | Моделирование | Протоколы | Экспертные системы | Художественные возможности материалов Удаленный доступ | Доменные имена развития компьютерной графики

Аплеты | SQL | Надежность | Задачи | Информационные процессы | Очередь JAVA | Отказы изделия | Расчет надежности показателей | Инфсис

Логическое программирование

Другие главы учебника "Экспертные системы"

• Что такое экспертная система?
• Представление знаний
• Системы, основанные на знаниях Метод активных и реактивных составляющих токов Электротехника курсовая работа
• Объектно-ориентированное программирование
• Представление неопределенности знаний и данных
• Эвристическая классификация
• Иерархическое построение
• Решение проблем конструирования
• Средства формирования пояснений
• Системы с доской объявлений
• Формирование знаний на основе машинного обучения
• Рассуждения, основанные на прецедентах
• Программирование на языке CLIPS

8.1.1. Исчисление высказываний

Исчисление высказываний представляет собой логику неанализируемых предположений, в которой пропозициональные константы могут рассматриваться как представляющие определенные простые выражения вроде "Сократ — мужчина" и "Сократ смертен". Строчные литеры р, q, r, ... в дальнейшем будут использоваться для обозначения пропозициональных констант, которые иногда называют атомарными формулами, или атомами.

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

(S. U) ЕслиU является атомом, то у является ППФ.

(S¬) Если U является ППФ, то —U также является ППФ.

(S. v) Если U и ф являются ППФ, то (U u ф) также является ППФ.

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

Выражение -U читается как "не U", а (U v ф) читается как дизъюнкция "U или ф (или оба)". Можно ввести другие логические константы — "л" (конъюнкция), "D" (импликация, или обусловленность), "=" (эквивалентность, или равнозначность), которые, по существу, являются сокращениями комбинации трех приведенных выше констант. .

(U ^ ф) Эквивалентно¬(¬U v ф). Читается "U и ф".

(U ф) Эквивалентно (¬U v ф). Читается "U имплицирует ф".

(U==ф) Эквивалентно (Uф)^(фU). Читается "U эквивалентно ф".

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

¬(U^ф) преобразуется в (¬Uv¬ф), ¬(U v ф) преобразуется в (-U^ф) , ¬¬U преобразуется в U .

Последний этап преобразований — внесение дизъюнкций внутрь скобок: (£ v (U ^ф))) заменяется ((£vU\(U)^(£vф)).

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

¬(pvq)(-p^A-q) Исходное выражение.

¬¬(pvg)v(-p^- q) Исключение~.

(pvq)v(-p^- q) Ввод - внутрь скобок.

(¬pv(pvq))v(¬pv(pvq)) Занесение v внутрь скобок.

{{-p, р, q}, {¬q, р, q} } Отбрасывание А и v в конъюнктивной нормальной форме.

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

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

преобразуется в две фразы:

p,q<¬q.

в которых позитивные литералы сгруппированы слева от знака стрелки, а негативные справа.

Более строго, фраза представляет собой выражение вида

в котором p₁..., р_т q₁,..., q_n являются атомарными формулами, причем т=>0 и п=>0. Атомы в множестве р₁,..., р_т представляют заключения, объединенные операторами дизъюнкции, а атомы в множестве q₁ ..., q_n — условия, объединенные операторами конъюнкции.