Сдам Сам

ПОЛЕЗНОЕ


КАТЕГОРИИ







Универсальные модели представления знаний





В ИИС используются 4универсальные модели представления знаний:

логические модели, сетевые модели (семантические сети, фреймы), продукционные системы.

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

 

Лекция. Основы построения логических моделей знаний

Понятие формальной системы

Основой логических моделей является понятие формальной системы, задаваемой четверкой M = (T, P, A, F).

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

Множество P есть множество синтаксических правил. С их помощью из элементов T образуют синтаксически правильные выражения, например, из слов ограниченного словаря строятся синтаксически правильные выражения. Должна существовать процедура П(Р), позволяющая определить, является ли

некоторое выражение синтаксически правильным.

В множестве Р выделяется подмножество А априорно истинных выражений (аксиом). Должна существовать процедура П(А) проверки принадлежности любого синтаксически правильного выражения множеству А.

Множество F есть множество семантических правил вывода. Применяя их к элементам А, можно получать новые синтаксически правильные выражения, к которым снова можно применять правила из F. Так формируется множество выводимых в данной формальной системе выражений. Если имеется процедура П(F), позволяющая определить для любого синтаксически правильного выражения является ли оно выводимым, то соответствующая формальная система называется разрешимой.



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

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

Использование логик различного типа при построении синтаксических и семантических правил порождает логические модели различных типов.

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

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

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

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

Предложение «Шел снег» также не является высказыванием, так как, чтобы судить о его истинности, нужны дополнительные сведения о том, когда и где шел снег.

Объединяя предложения с помощью связок типа «и», «или»,«если… то…», можно образовывать новые предложения.

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

Конъюнкция (логическое И) истинна только тогда, когда оба составляющих ее высказывания истинны.

Дизъюнкция (логическое ИЛИ) ложна только тогда, когда ложны оба составляющих ее высказывания.

У импликации (соответствует связке «Если…, то…») первый операнд называется посылкой, а второй – заключением. Импликация ложна только тогда, когда ее посылка истинна, а заключение – ложно.

Логическая операция эквивалентность соответствует связке «тогда и только тогда». Ее результатом является истина, если оба высказывания или одновременно истинны, или одновременно ложны.

Логическое отрицание выполняется над одним высказыванием. Высказывание и его отрицание всегда имеют противоположные истинностные значения.

Символы, используемые для обозначений высказываний, называют атомами.

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

1) атом есть формула;

2) если A и B – формулы, то формулами являются

и ØA, A Ù B, A Ú B, A ® B, A « B.

 

Здесь связки обозначены символами:

Ú - логическое ИЛИ (дизъюнкция);

Ù - логическое И (конъюнкция);

® - логическое СЛЕДУЕТ (импликация);

« - логическое ЭКВИВАЛЕНТНО (эквиваленция);

Ø - логическое отрицание.

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

Формула, состоящая из n различных атомов, имеет 2n различных интерпретаций.

Формула, истинная при всех интерпретациях, называется общезначимой (например, A Ú ØA).

Формула, ложная при всех интерпретациях, называется противоречивой (например, A ÙØA).

Формула, для которой существует хотя бы одна интерпретация, при которой она истинна, называется выполнимой.

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

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

1) A Ú ØA = true (истина);

A Ù ØA = false (ложь);

2) правило двойного отрицания

Ø (ØA) = A;

3) A ® B = ØA Ú B;

4) A « B = (A ® B) Ù (B ® A);

5) законы коммутативности

A Ú B = B Ú A, A Ù B = B Ù A;

6) законы ассоциативности

(A Ú B) Ú C =A Ú (B Ú C), (A Ù B) ÙC = A Ù (B Ù C);

7) законы дистрибутивности

A Ú (B Ù C) = (A Ú B) Ù (A Ú C), A Ù (B Ú C) = (A Ù B) Ú (A Ù C);

8) законы де Моргана

Ø(A Ú B) = ØA Ù ØB, Ø(A Ù B) = ØA Ú ØB;

9) A ® B = ØB ® ØA.

Исчисление предикатов

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

а) константы, обозначающие индивидуальный объект или понятие;

б) переменные, которые в разное время могут обозначать разные объекты;

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

г) предикаты, используемые для представления отношений между объектами в некоторой предметной области;

д) кванторы – средство задания количественных характеристик предметной области.

Предикат – это логическая функция, принимающая только истинностные значения «истина» или «ложь».

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

Запись , являющаяся простейшей (атомарной) формулой, означает, что истинно высказывание: объекты связаны отношением P.

С помощью тех же логических связок, что и в исчислении высказываний (И, ИЛИ, НЕ, СЛЕДУЕТ, ЭКВИВАЛЕНТНО), можно строить более сложные формулы.

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

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

1. атом есть формула;

2. если A и B – формулы, то формулами являются и

ØA, A Ù B, A Ú B, A ® B, A « B;

3. если - есть формула, то формулами являются и и .

Интерпретация формул в исчислении предикатов – это задание областей значений всем константам, функциональным и предикатным символам. Формула, интерпретируемая на области D, принимает значения истина или ложь по следующим правилам:

а) если заданы значения формул A и B, то истинностные значения формул ØA, A Ù B, A Ú B, A ® B, A « B получаются по таблицам истинности, справедливым для исчисления высказываний;

б) формула получает значение истина, если для каждого из D имеет значение истина, в противном случае ее значение – ложь.

в) формула получает значение истина, если хотя бы для одного из D имеет значение истина, в противном случае ее значение – ложь.

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

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

Ø($ ) = ( ) (Ø );

Ø( ) = ( ) (Ø ).









Не нашли то, что искали? Воспользуйтесь поиском гугл на сайте:


©2015- 2018 zdamsam.ru Размещенные материалы защищены законодательством РФ.