3787 ПРЕДСТАВЛЕНИЕ ЗНАНИЙ В ИНФОРМАЦИОННЫХ СИСТЕМАХ

ЛАБОРАТОРНАЯ РАБОТА № 1

 

УНИФИКАЦИЯ

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

ТЕОРЕТИЧЕСКАЯ ЧАСТЬ

 

Информационные системы (ИС) входят в число важнейших компонентов науки и производства. Они широко используются для обучения и решения конкретных задач в различных областях человеческой деятельности: в автоматизированных системах управления (АСУ) и научных исследований (АСНИ), системах автоматизации проектирования (САПР), информационно-поисковых системах (ИПС), системах управления базами данных (СУБД), экспертных системах (ЭС), системах поддержки принятия решения (СППР) и т.д.

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

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

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

 

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

 

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

 

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

В основе формально-логической модели лежит понятие формальной теории T:

T = < B, F, A, R >,

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

F – подмножество выражений теории T, называемых формулами теории;

A – выделенное множество формул, называемых аксиомами теории T;

Rконечное множество отношений {r1,…,rn} между формулами, называемыми правилами вывода.

 

Чтобы придать формуле содержание, ее интерпретируют как утверждение, распространяющееся на некоторую область D (область интерпретации).

 

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

 

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

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

Алфавит языка предикатов первого порядка:

-          разделители:  запятая -“,” , открывающая скобка - “(”, закрывающая скобка - “)”;

-          константы – строчные буквы – “a ”,…;

-          переменные – прописные (заглавные) буквы – “A ” ,…;

-          предикаты – заглавные буквы;

-          функции (не предикаты) – строчные буквы – “f ”,…;

-          логические операции:

1)     Ø - отрицание,

2)     Ù - коньюнкция,

3)     Ú - дизъюнкция,

4)     ® - импликация (если…то…),

5)     « - эквивалентность (…тогда и только тогда, когда…),

6)     $ - квантор существования (существует…),

7)  " - квантор общности (для любого…).

 

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

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

Терм – выражение, включающее константы, переменные и N-местные функции от термов.

Атом – элементарная функция – это выражение, включающее константы, переменные, функции и предикаты.

Атом или его отрицание называется литералом.

Правильная формула (ПФ) – это атом, ØH, GÚH, GÙH, ($X)G, ("X)H, где G, H– ПФ; X– переменная; ($X)G означает: существует X, для которого справедливо G; ("X)H означает: для любого X справедливо H.

Правило вывода – процедура, которая из одной или нескольких ПФ производит другие ПФ.

 

Исходные ПФ в теории T называются аксиомами.

 

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

Недостатком формально-логической модели являются жесткие ограничения, свойственные всем формальным моделям.

 

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

Пусть имеются два конкретных предложения:

P1ÚP2Ú…ÚPn  и ØP1ÚQ2ÚQ3Ú…ÚQn.

Из них можно вывести новое предложение, называемое резольвентой, как дизъюнкция исходных предложений без дополняющих друг друга пар типа P1 и ØP1.

 

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

Заменой S (унификатор) называют   конечное   множество   упорядоченных   пар {t1/U1,…,tn/Un} = S, где пара ti/Ui означает, что переменная Ui заменяется термом (константы, переменные и функции от термов) ti. Применение S к   выражению E  обозначают  как ES.  Пример:

E = F(q(X),a,Y),  S1 = {Z/X, U/Y},  S2= {Y/X, f(X)/Y}, S3= {b/X, m(b)/Y}.

Тогда

ES1=F(q(Z),a,U), ES2=F(q(Y),a,f(X)), FS3=F(q(b),a,m(b)).