Дизъюнкция Хорна в анализе структуры информационных систем

Глава 2. Формальное представление системы программирования Prolog,  как языка предикатов математической логики.

Смена поколений вычислительной техники приводится к очередной научно технической революции. С появлением нового поколения ЭВМ не только стал решаться принципиально новый класс задач во всех отраслях науки и техники, но и существенно расширяются возможности при решении прежних традиционных задач на новом, более качественном, уровне.  Более высокий качественный уровень в решении задач предполагает обеспечение необходимой и достаточной интеллектуальной поддержкой. Интеллектуализация информационно-вычислительных систем это использование не только нового поколения инструментальных средств, но и нового поколения математического, алгоритмического и программного обеспечения для решения сложных задач. Искусственный интеллект (ИИ) – это программная система, имитирующая на компьютере мышление человека. Для создания такой системы необходимо изучать процесс мышления человека, решающего определенные задачи или принимающего решения в конкретной области, выделить основные шаги этого процесса и разработать программные средства, воспроизводящие их на компьютере. Интеллектуальная система – это информационно-вычислительная система с интеллектуальной поддержкой при решении задач без участия оператора. Система искусственного интеллекта, созданная для решения задач в конкретной проблемной области, называется экспертной системой. Источником знаний для наполнения экспертных систем служат эксперты, работающие в соответствующей предметной области. В течение последних десятилетий в рамках исследований по искусственному интеллекту (ИИ) сформировалось новое самостоятельное направление – экспертные системы (ЭС), или инженерия знаний (ИЗ). Экспертная система (ЭС)- это система искусственного интеллекта (интеллектуальная система), предназначенная для решения плохо формализованных и слабо структурированных задач в определенных проблемных областях, на основе заложенных в ней знаний специалистов-экспертов. В задачу этого направления входят исследование и разработка программ, использующих знания и процедуры вывода для решения задач, являющихся трудными для людей-экспертов. В отличие от специализированных систем ИИ экспертные системы могут быть отнесены к системам ИИ общего назначения – системам, которые не только исполняют заданные процедуры, но на основе мета процедур поиска генерируют и используют процедуры решения новых конкретных задач. Логические основы работы системы Пролог-Д. В последнее время к разработке экспертных систем все чаще стал привлекаться специализированный языка искусственного интеллекта Пролог. Свое название Пролог получил от сокращения «Программирование логики». Математической основой языка программирования Пролог являются исчисления предикатов преимущественно первого порядка, метод резолюции, теория рекурсивных функций. В настоящее время создано большое число различных по эффективности и мощности Пролог-систем, каждая из которых предлагает свой синтаксис языка и свой набор встроенных предикатов. Математическая логика является теоретической основой логического программирования. Цель данного раздела определить начальные понятия математической логики, необходимые для изложения принципов работы с системой. Пролог-Д. Интерпретатор языка Пролог предназначен для проведения практикума на персональных компьютерах с базами знаний, экспертными системами и изучением принципов логического вывода в системах искусственного интеллекта. Для решения задачи с помощью Пролога-Д достаточно описать знания об этой задаче, а процесс построения решения при этом сводится к некоторой рутинной процедуре. Описание знаний возможно осуществить с помощью совокупности дискретных объектов и отношений между ними. Объекты, если их соотнести с решаемой задачей, образуют ее предметную область. Например, если задача состоит в описании родственных отношений, то предметная область-множество людей, а если задача вычислительная, то предметной областью будет множество целых чисел. Объекты, при описании их средствами математической логики, должны иметь имена. За определением имен следует описание соотношений между объектами и выражение свойств этих отношений. Построение решения задачи производится на основе логического вывода, манипуляцией предложениями, описывающими данную задачу.

Программа на Прологе включает в себя постановку задачи в виде множества формул логики предикатов первого порядка и описания цели – формулировку теоремы, которую нужно доказать, исходя из множества фактов и правил, содержащихся в этой постановке. 
Формализм исчисления предикатов первого порядка оказался удобным для описания постановки задачи на языке, близком к естественному. Таким образом, язык Пролог имеет четкую математическую основу. В основе языка лежит исчисление предикатов первого порядка, и в этом смысле язык является подмножеством формальной логики. Но Пролог включает не все формальное исчисление, а только некоторое его подмножество, представленное Хорновскими дизъюнктами. 
Дадим несколько определений. Пусть имеется некоторое множество объектов, называемое предметной областью. Выражение P(X1, X2, …, Xn), где  Xi, i=1,…,n – так называемые предметные переменные, а P принимает значения 0 или 1, называется логической функцией или предикатом. Предикат от n переменных называют n-местным. 
Предикат P(X1, X2, …, Xn) задает отношение между элементами X1,X2,…,Xn и обозначает высказывание, что «X1,X2,…,Xn  находятся между собой в отношении P». Например, если отношение родитель(X,Y) означает, что X является родителем для Y (но не наоборот!), то высказывание родитель(«царь Петр I», «царевич Алексей») является истинным, а отношение родитель

(«царь Петр I», «царевна  Софья») – ложным. Важно понимать, что имена отношений и их размерность («арность») произвольны и зависят только от целей их использования. 
Из подобного рода элементарных отношений с помощью логических связок образуют более сложные отношения, которые в свою очередь являются предикатами, то есть могут принимать те же значения – «истина» или «ложь». В качестве связок используются конъюнкция (логическое И), дизъюнкция (логическое ИЛИ), импликация (логическое следование), отрицание, эквивалентность. 
Рассмотрим классический пример рассуждений с использованием логических связок. Пусть имеются следующие рассуждения на естественном языке (в данном случае – аксиомы): 
Все люди смертны. 
Сократ – человек. 
Теорема, логически вытекающая из этих двух аксиом: 
Сократ смертен. 
Эти аксиомы можно переписать так (в терминах исчисления предикатов): 
Для всех X, если X – человек, то смертен X 
И человек(Сократ ) 
Соответственно наш пример можно перевести на Пролог (пока еще без учета синтаксиса версии PDC Prolog): 
смертен( Х) :- человек ( Х ). 
человек(сократ). 
Здесь собственное имя «Сократ», представляющее строковую константу, записано с маленькой буквы, поскольку во всех версиях Пролога с большой буквы записывается имя переменной. При работе этой небольшой программы можно задать системе вопрос: является ли Сократ смертным, и система ответит «Да»: 
? смертен(сократ). 
Да 
Это простой пример, но его достаточно, чтобы показать целесообразность использования Пролога для реализации различного рода рассуждений,

потому что можно задать большое количество фактов и правил, Система,

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

Язык Пролог в 1980-х годах был включен в ряд советских вузовских и школьных учебников информатики для изучения элементов математической логики, принципов логического программирования и проектирования баз знаний и моделей экспертных систем. С этой целью на IBM PC и ряде советских школьных компьютеров были реализованы учебные русскоязычные интерпретаторы Пролога.

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

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

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

Глава 3.Оценка процедурной части  программы «TreeFound».

Во всех экспертных системах существует зависимость между входным 
потоком данных и данными в базе знаний. Во время консультации входные 
данные сопоставляются с данными в базе знаний. Результатом сопоставления 
является отрицательный или утвердительный ответ. В системе, 
базирующейся на правилах утвердительный результат является действием 
одного из продукционных правил. Эти продукционные правила определяются 
входными данными. 
 
Таким образом, экспертная система, базирующаяся на правилах (на 
Турбо-Прологе) содержит множество правил, которые вызываются посредством входных данных в момент сопоставления. Экспертная система также содержит интерпретатор в механизме вывода, который выбирает и активизирует различные модули системы. 
 
Работу этого интерпретатора можно описать последовательностью трех 
шагов: 
 
1. Интерпретатор сопоставляет образец правила с элементами данных в 
базе знаний. 
 
2. Если можно вызвать более одного правила,то интерпретатор использует 
механизм разрешения конфликта для выбора правила. 
 
3. Интерпретатор применяет выбранное правило , чтобы найти ответ на 
вопрос. 
 
Этот трех шаговый процесс интерпретации является циклическим и 
называется циклом "распознавание-действие". 
 
В системе, базирующейся на правилах, количество продукционных правил 
определяет размер базы знаний. Некоторые наиболее сложные системы имеют 
базы знаний с более чем 5000 продукционных правил. 
 
1. Использовать минимально достаточное множество условий при 
определении продукционного правила. 
 
2. Избегать противоречащих продукционных правил. 
 
3. Конструировать правила, опираясь на структуру присущую предметной 
области.

Экспертные системы, базирующиеся на логике. В экспертных системах, базирующихся на логике, база знаний состоит из утверждений в виде предложений логики предикатов.  
Такие предложения могут группироваться, образуя базу данных 
Турбо-Пролога. Правила могут либо описывать данные либо управ лять 
процессом внутренней унификации Турбо-Пролога. 
 
Так же как и в системе на правилах экспертная система, базирующаяся на 
логике, имеет множество правил, которые могут вызываться с помощью 
данных из входного потока. Система имеет также интерпретатор, который 
может выбирать и активизировать модули, включаемые в работу системы. 
 
Интерпретатор выполняет различные функции внутри системы на основе 
следующей схемы: 
 
1. Система имеет предложения в базе знаний, которые управляют поиском и 
сопоставлением. Интерпретатор сопоставляет эти предложения с элементами 
данных в базе данных. 
 
2. Если может быть вызвано более одного правила , то система использует 
возможности Турбо-Пролога для разрешения конфликта. Следовательно 
пользователю/программисту не нужно рассматривать потенциально возможные 
конфликты. 

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

Все перечисленные ниже атрибуты являются необходимыми, так как ни один 
из них не характерен для всех пород одновременно. 
 
1) лиственная; 
 
2) хвойная; 
 
3) мягкая; 
 
4) твердая; 
 
5) очень твердая; 
 
6) серо-коричневая; 
 
7) светло-красная; 
 
8) светлая; 
 
9) темная; 
 
10) смолистая; 
 
11) очень смолистая; 
 
12) Крупная текстура; 
 
13) Мелкая текстура. 
 
 
 
Каждая характеристика для конкретной породы либо верна, либо не верна. 
Для каждой породы справедливы следующие характеристики: 
Порода Характеристики  
 
Дуб 1,4,6,13 
 
Бук 1,4,7,12 
 
Осина 1,3,8,13 
 
Тис 1,5,9 
 
Ель 2,3,8,10 
 
Сосна 2,3,8,11 
 
Способ использования этой информации зависит от реализации экспертной 
системы. В нашем случае при проектировании базы знаний древовидная структура, множество идентифицирующих характеристик и наборы номеров характеристик для каждой породы составляют рабочую модель базы знаний для выбора породы. 
 
Заметьте, что номера характеристик являются искусственными фактами, 
необходимыми проектировщику, и введены они для того, чтобы 
функциональным модулям экспертной системы было легче идентифицировать 
характеристики и манипулировать ими. Проектирование и реализация системы, базирующейся на правилах. 
 
Сначала необходимо сделать декларации базы данных. База данных будет 
хранить ответы пользователя на вопросы системы пользовательского 
интерфейса (СПИ). Эти данные являются утвердительными или отрицательными ответами.  
 
Далее нужно объявить предикаты для выполнения вывода (машина вывода) и 
для взаимодействия с пользователем (система пользовательского 
интерфейса). 
 
Все вместе это следующие декларации: 
 
database 
 
xpositive(symbol,symbol) 
 
xnegative(symbol,symbol) 
 
predicates 

do_expert_job 
 
do_consulting 
 
ask(symbol,symbol) 
 
dog_is(symbol) 
 
it_is(symbol) 
 
positive(symbol,symbol) 
 
negative(symbol,symbol) 
 
remember(symbol,symbol,symbol) 
 
clear_facts 
 
Предикаты базы данных xpositive и xnegative используются для хранения 
утвердительных и отрицательных ответов пользователя. Первые четыре 
предиката нужны для взаимодействия с пользователем, а остальные шесть - 
для механизма вывода. 
Должны быть составлены восемь продукционных правил : по одному для 
каждой породы. Каждое правило должно идентифицировать породу по признаку принадлежности к группе. Правило it_is производит эту идентификацию. Затем правило positive идентифицирует характеристики собаки в каждом случае.