Лекция №2

Резюме

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

Составной терм строится из функтора (называемого главным функтором терма) и последовательности из одного или более термов, называемых аргументами. Функторзадается своим именем, т.е. некоторым атомом, и арностью, или числом аргументов. Константы рассматриваются как 0-арные функторы. Синтаксически составной терм записывается как f(t,t,…t),где f – имя n-арного функтора, а t– аргументы.. Для n-арного функтора f используется запись f/n. Функторы с одинаковыми именами, но различными арностями различны. Терм является основным , если в нем не содержится переменных; в противном случае терм неосновной.

Цели – это атомы или составные, в общем случае неосновные термы.

Подстановка – это конечное (возможно, пустое) множество пар вида Х = t, где X – переменная, t – терм, причем переменные в левых частях пар различны. Для любой подстановки Q = {X= t,X=t,…,X=t} и терма S терм SQ обозначает результат одновременной замены каждого вхождения в S переменной Xна t,1<i<n. Терм SQ называется примером терма S.

Логическая программа –конечное число предложений. Предложением,или правилом, является замкнутое квантором общности утверждение вида

A¬ B,B,…B, k³0,

где A и B– цели. Декларативное понимание такого утверждения – «А следует из конъюнкции целей B;», процедурная интерпретация – «для ответа на вопрос А ответь на конъюнктивный вопрос B,B,…B». А называется заголовком предложения, последовательность B– телом предложения. При k = 0 предложение называется фактом или единичным предложением и имеет запись A., декларативное понимание – «A истинно», процедурная интерпретация – «цель А выполнена». При k = 1 предложение называется итерационным.

Вопросом называется конъюнкция вида

A,…,A?n>0.

где A– цели. Считается, что переменные в вопросе связаны квантором существования.

Вычислениелогической программы Р строит пример заданного вопроса, логически выводимый из Р. Цель G выводимаиз Р, если существует такой пример А цели G, что A ¬ B,…B, n ³ 0, – основной пример предложения в Р и каждое В, выводимо из Р. Выводимость цели из тождественного факта рассматривается как особый случай.

С помощью логической выводимости индуктивно определяется значение программы Р. Множество основных примеров фактов из Р принадлежит значению Р. Основная цель G входит в значение, если существует такой основной пример G ¬ B,…Bправила из Р, что B,…Bвходят в значение Р. Таким образом, значение состоит из тех основных примеров, которые выводятся из программы.

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

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