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

Способы представления знаний- логические модели

Логические модели.

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

Логические модели строятся на основе логики высказываний и исчисления предикатов []. Логика высказываний используется для решения логических задач алгебраическим методом. Каждое утвердительное предложение называется высказыванием. Высказывание рассматривается как истинное или ложное. Над высказыванием можно выполнять логические операции. Примеры высказываний; “Сигналы поступают на шину адреса”, ”Студенты сдают экзамен”. Из простых высказываний строятся составные, используя логические связки (и, или, не). Выражения, которые представляются простыми и сложными высказываниями образуют формулу. Идея решения задач с использованием логики высказывания состоит в том, чтобы сначала описать ситуацию, используя формулы логики высказывания, а затем доказать общезначимость или противоречивость всей совокупности этих формул. Общезначимая формула истинна при всех интерпретациях, а противоречивая – ложна при всех толкованиях.

Простые высказывания	Иванов студент. Студент сдает экзамен.	(А) (В)
Сложное высказывание	Если Иванов студент То Иванов сдает экзамен	(А®В)

Чтобы удовлетворительно описать предметную область, для обозначения различных объектов вводятся переменные.

Для создания логических моделей можно использовать формулы логики предикатов 1-го порядка [].

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

В отличие от логики высказываний число интерпретаций этой формулы велико.

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

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

Правило на языке высказываний: 1 .Иванов — студент. 2. Студенты сдают экзамены. 3. Вывод: Иванов сдает экзамен.

Правило на языке Пролог: сдает_экзамен (X):– student (X). student (“Иванов”).

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

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

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

рис.3.2. Семантическая сеть, отражающая взаимоотношения между атрибутами микропроцессора и программы.

Можно создать объект, для этого разрабатываем структуру, описывающую все объекты с общим названием МИКРОПРОЦЕССОР.

СОЗДАТЬ_СТРУКТУРУ (имя = микропроцессор,

атрибут = система команд,

атрибут = выполнять программу)

На основе этой структуры можно создать объект и ряд правил

ТО объект= микропроцессор

Чем чаще используется слово, тем более оно семантически значимо.

Источник

Логическая модель представления знаний

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

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

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

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

ДАТЬ (МИХАИЛ, ВЛАДИМИРУ, КНИГУ);

($x) (ЭЛЕМЕНТ (x, СОБЫТИЕ-ДАТЬ) ? ИСТОЧНИК (x, МИХАИЛ) ? АДРЕСАТ ? (x, ВЛАДИМИР) ОБЪЕКТ(x, КНИГА).

Здесь описаны два способа записи одного факта: «Михаил дал книгу Владимиру».

Логический вывод осуществляется с помощью силлогизма (если из A следует B, а из B следует C, то из A следует C).

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

где B — счетное множество базовых символов (алфавит) теории S;

F — подмножество выражений теории S, называемые формулами теории (под выражениями понимаются конечные последовательности базовых символов теории S);

A — выделенное множество формул, называемые аксиомами теории S, то есть множество априорных формул;

R — конечное множество отношений 1, …, r_n> между формулами, называемые правилами вывода.

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

Покажем метод резолюций.

В методе используется несколько понятий и теорем.

Понятие тавтологии, логической формулы, значением которой будет «истина» при любых значениях входящих в них атомов. Обозначается ?, читается как «общезначимо» или «всегда истинно».

Теорема 1. А?В тогда и только тогда, когда ?АВ.

Теорема 2. А1, А2, . Аn ? В тогда и только тогда, когда ? (A1?A2?A3?…?An) В.

Символ ? читается как «верно, что» или «можно вывести».

В основе метода лежит доказательство тавтологии

Теоремы 1 и 2 позволяют записать это правило в следующем виде:

что дает основания утверждать: из посылок и можно вывести .

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

1. Устраняются операции эквивалентности и импликации:

;

.

2. Операция отрицания продвигается внутрь формул с помощью законов де Моргана:

3. Логические формулы приводятся к дизъюнктивной форме: .

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

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

1.Приведение посылок к дизъюнктивной форме:
, , .

2.Построение отрицания выводимого заключения . Полученная конъюнкция справедлива, когда и одновременно истинны.

3.Применение правила резолюции:

;

;

;

(противоречие или «пустой дизъюнкт»).

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

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

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

Алгоритм унификации предикатных логических формул включает следующие шаги.

1. Исключение операций эквивалентности.
2. Исключение операций импликации.
3. Внесение операций отрицания внутрь формул.
4. Исключение кванторов существования. Это может произойти на шаге 3 вследствие применения законов де Моргана, а именно; в результате отрицания меняется на , но при этом может произойти и обратная замена. Тогда для исключения поступают следующим образом; все вхождения некоторой переменной, связанной квантором существования, например , заменяются в формуле на новую константу, например а . Эта константа представляет собой некоторое (неизвестное) значение переменной X , для которого утверждение, записанное данной формулой, истинно. При этом важно то, что на все места, где присутствует X , будет подставлено одно и то же значение а , пусть оно и является неизвестным в дан­ный момент. Такие константы называются сколемовскими , а опера­ция — сколемизацией (по имени известного математика Сколема).
5. Кванторы общности выносятся на первые места в формулах. Это также не всегда является простой операцией, иногда при этом приходится делать переименование переменных.
6. Раскрытие конъюнкций, попавших внутрь дизъюнкций.

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

Пример: представим средствами логики предикатов следующий текст:

«Если студент умеет хорошо программировать, то он может стать специалистом в области прикладной информатики».

«Если студент хорошо сдал экзамен по информационным системам, значит, он умеет хорошо программировать».

Представим этот текст средствами логики предикатов первого порядка. Введем обозначения: X — переменная для обозначения студента; хорошо — константа, соответствующая уровню квалификации; Р(Х) — предикат, выражающий возможность субъекта X стать специалистом по прикладной информатике; Q(Х, хорошо) — предикат, обозначающий умение субъекта X программировать с оценкой хорошо; R(Х, хорошо) — предикат, задающий связь студента X с экзаменационной оценкой по информационным системам.

Теперь построим множество правильно построенных формул:

Q(Х, хорошо).

R(Х, хорошо)Q(Х, хорошо).

Дополним полученную теорию конкретным фактом
R(иванов, хорошо).

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

1. Выполним преобразование исходных формул теории в целях приведения к дизъюнктивной форме:

(Х_,хорошо)Р(Х);

(Х,хорошо)(Х,хорошо);

2. Добавим к имеющимся аксиомам отрицание выводимого заключения

(иванов).

3. Построим конъюнкцию дизъюнктов

(Х_,хорошо)Р(Х)??P(иванов, хорошо)??Q(иванов, хорошо), заменяя переменную X на константу иванов.

Результат применения правила резолюции называют резольвентой. В данном случае резольвентой является (иванов).

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

(Х, хорошо)(Х, хорошо)(иванов, хорошо) (иванов, хорошо).

5. Запишем конъюнкцию полученной резольвенты с последним дизъюнктом теории:

(иванов, хорошо)(иванов, хорошо) (противоречие).

Следовательно, факт Р(иванов) выводим из аксиом данной теории.

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

1. На первом шаге вывода используется отрицание выводимого заключения.
2. В каждом последующем шаге вывода участвует резольвента, полученная на предыдущем шаге.

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

Источник