Студопедия

КАТЕГОРИИ:


Архитектура-(3434)Астрономия-(809)Биология-(7483)Биотехнологии-(1457)Военное дело-(14632)Высокие технологии-(1363)География-(913)Геология-(1438)Государство-(451)Демография-(1065)Дом-(47672)Журналистика и СМИ-(912)Изобретательство-(14524)Иностранные языки-(4268)Информатика-(17799)Искусство-(1338)История-(13644)Компьютеры-(11121)Косметика-(55)Кулинария-(373)Культура-(8427)Лингвистика-(374)Литература-(1642)Маркетинг-(23702)Математика-(16968)Машиностроение-(1700)Медицина-(12668)Менеджмент-(24684)Механика-(15423)Науковедение-(506)Образование-(11852)Охрана труда-(3308)Педагогика-(5571)Полиграфия-(1312)Политика-(7869)Право-(5454)Приборостроение-(1369)Программирование-(2801)Производство-(97182)Промышленность-(8706)Психология-(18388)Религия-(3217)Связь-(10668)Сельское хозяйство-(299)Социология-(6455)Спорт-(42831)Строительство-(4793)Торговля-(5050)Транспорт-(2929)Туризм-(1568)Физика-(3942)Философия-(17015)Финансы-(26596)Химия-(22929)Экология-(12095)Экономика-(9961)Электроника-(8441)Электротехника-(4623)Энергетика-(12629)Юриспруденция-(1492)Ядерная техника-(1748)

Операционная и декларативная семантика. Интерпретация





Теория логических программ

Лекция №5

 

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

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

Декларативная семантика логических программ основана на стандартной теоретико-модельной семантике логики первого порядка. Для ее описания потребуется некоторая новая терминология.

Пусть P – логическая программа. Универсуум Эрбрана программы P, обозначаемый U(P) – это множество всех основных термов, которые могут быть построены из констант и функциональных символов, входящих в Р. Пусть, например, Р – программа 3.1, определяющая натуральные числа:

natural_number(0).

natural_number (s(X))¬ natural number (X).

В программе имеется один символ константы – 0 и один унарный функциональный символ – s. Универсум Эрбрана U(Р) данной программы есть {0, s (0),(s(s0)),...}. В общем случае универсуум Эрбрана бесконечен, если в программу входит хотя бы один функциональный символ. Если в программу не входят символы констант, то выбирается произвольным образом одна константа.

Базис Эрбрана, обозначаемый В(Р), есть множество всех основных целей, которые можно построить с помощью предикатов программы Р и термов универсуума Эрбрана. Если универсуум Эрбрана бесконечен, то бесконечен и базис Эрбрана. В нашем примере программа содержит один предикат – natural_number. Базис Эрбрана – {nalural_number (0), natural_number (s (0)),...}.

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



Интерпретация I является моделью логической программы, если каждый основной пример А ¬ В,...,Bправила программы удовлетворяет следующему свойству: если В,...,Bпринадлежат I, то и А принадлежит I. Интуитивно ясно, что моделями являются интерпретации, согласованные с декларативным пониманием предложений программы.

В нашем примере цель natural_number(0) должна входить в каждую модель; кроме того, если natural_number(X) принадлежит модели, то и natural_number(s(Х)) принадлежит модели. Таким образом, любая модель программы 3.1 содержит весь базис Эрбрана.

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

Декларативное значение программы для natural_number, т.е. ее минимальная модель, совпадает с полным базисом Эрбрана – {natural_number (0),natural_number,(s (0)), natural_number (s (s (0))),...}.

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

Для заданной логической программы Р имеется естественная функция ТP, отображающая интерпретации в интерпретации и определенная следующим образом:

TP(I) = {А|А принадлежит В(Р), А ¬ В, В,...,В, п³0 – основной пример предложения в Р, В, В,...,В, принадлежат I}.

Данное отображение монотонно, так как если интерпретация I содержится в интерпретации J, то ТP (I) содержится в ТP (J).

Это отображение позволяет описать модели иным способом. Интерпретация I является моделью втом и только в том случае, если Т (I ) содержится в I.

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

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





Дата добавления: 2014-01-07; Просмотров: 283; Нарушение авторских прав?; Мы поможем в написании вашей работы!


Нам важно ваше мнение! Был ли полезен опубликованный материал? Да | Нет



ПОИСК ПО САЙТУ:


Рекомендуемые страницы:

Читайте также:
studopedia.su - Студопедия (2013 - 2021) год. Все материалы представленные на сайте исключительно с целью ознакомления читателями и не преследуют коммерческих целей или нарушение авторских прав! Последнее добавление
Генерация страницы за: 0.002 сек.