Р.У. Себеста - Основные копцепции языков программирования (2001) (1160794), страница 161
Текст из файла (страница 161)
Переменные в языке Рго!оя как по использованию, так и по семантике, имеют лишь отдаленное отношение к переменным в императивных языках. 624 Глава 15. Языки логического программирования Последний вид терман называется структурой. Структуры представляют собой атомарные высказывания исчисления предикатов и имеют ту же форму: функтор(список параметров) Функтор — это любой атом. Он используется только для идентификации структуры. Список параметров может быть любым списком атомов. переменных и других структур. Как указывалось выше, структуры — это средство для формулирования фактов в языке Рго)оя. Их можно рассматривать как объекты, при этом они позволяют выражать факты в виде нескольких связанных между собой атомов.
В этом смысле структуры являются отношениями, поскольку они устанавливают отношения между термами. Структура также является предикатом, когда из ее контекста следует, что она представляет собой запрос (вопрос). 3 $.6.2. Факты Наше обсуждение операторов языка Рго)оа начинается с тех операторов, которые используются для построения гипотез или базы данных предполагаемой информации— операторов, с помощью которых можно логически вывестн новую информацию. В языке Рго1ой есть две основные формы операторов; они соответствуют хорновским дизъюнкгам без головы и с головой в исчислении предикатов. Простейшая форма хорновского дизъюнкта без головы в языке Рго)ой представляет собой отдельную структуру, интерпретируемую как безусловное утверждение, или факт.
Следовательно, факты — это просто высказывания, которые предполагаются истинными. Приведенный ниже пример иллюстрирует виды фактов, которые могут быть в программе на языке Рго)ой: йева1е (вЛе11еу) . ва1е(Ь111) . гева1е(вагу). ва1е(за)се). багЛег(Ь111, За)ге). йаГЛег(Ь111, вЛе11е). воГЛег(вагу, Захе]. воГЛег(вагу, вЛе11еу).
Эти простые структуры утверждают определенные факты об объектах с именами з а хе, вЛе11еу, Ь111 и вагу. Например, первая структура утверждает, что вЛе11еу — бева1е. Последние четыре структуры связывают два свои параметра отношением, которое названо в функгорном атоме: например, пятое высказывание можно интерпретировать как утверждение о том, что объект Билл (ь111) является отцом (баглег) Джека (захе ) . Заметим, что эти высказывания на языке Рго1оа, как и высказывания в исчислении предикатов, не имеют вну(ремней семантики. Они означают все, что будет угодно программисту. Например, рассмотрим высказывание ГагЛег (Ь111, За)ге) . Оно может означать, что у Билла и Джека один и тот же отец, или что Джек — отец Билла. Наиболее общее и строгое значение этого высказывания, однако, заключается в том, что Билл является отцом Джека. 625 15.6.
Основные влементы языка Рта(од 1$.6.3. Правиле Другая основная форма оператора в языке Рго!ой лля построения баз данных соответствует хорновскому лизъюнкту с головой. Эту форму можно сравнить с известной теоремой в математике, из которой можно вывести заключение, если удовлетворяется совокупность заданных условий. Правая часть этого оператора является антецедентом, или частью если, а левая часть — следствием, или частью то. Если антецедент оператора языка Рго!ок истинен, то следствие этого оператора также должно быть истинным. Поскольку они являются хорновскими дизъюнхтами, следствие оператора в языке Рго!ой является отдельным термам, в то время как антецедент может быть либо отдельным термом.
либо конъюнкцией. Конъюнкции (соп)ос()опз) состоят из составных термов, отделенных друг от друга логическими операциями "И". В языке Рго)од операция "И" является неявной. Структуры. определяющие атомарные высказывания в конъюнкции, разделяются запятыми, так что запятые можно рассматривать как операторы "И". В качестве примера конъюнкции рассмотрим следующее выражение: Хева1е (я)зе11еу), сп11г) (я)зе11еу) . Общая форма хорновского дизъюнкта в языке Рго)од такова: следствие 1 : — антецедентное выражение Читается это следующим образом: "следствие ! может быть истинным, если истинно антецедентное выражение, или оно может быть сделано истинным путем некоей конкретизации ее переменных". Рассмотрим в качестве примера следующее высказывание: апсеягог(вагу, я)зе11еу): — вот)зег(вагу, япе11еу) . Оно утверждает, что если Мери (п1егу] является матерью (вот)зег) Шелли (я)зе11еу), то Мери является наследником (апсеягог) Шелли.
Хорновские дизъюнхты с годовой называются правиламн (го)ез), поскольку они формулируют правила логического след- ствия между высказываниями. Как и дизъюнктивная форма в исчислении предикатов, оператор в языке Рго!ой может использовать переменные лля обобщения их значения.
Напомним, что переменные в дизъюнктивной форме представляют собой неявный квантор всеобщности. Следующий пример демонстрирует использование переменных в операторе языка Рго)ой: рагепт (Х, Х): — вот)зег (Х, Х) . рагепс (Х, Х): — йас)зег (Х, Х) . дгапс)рагепс (Х, Е): — рагепс (Х, Х), рагепс (Х, 2) . я1)э11по (Х, Х): — вот)тег (Х, Х), воспег (М, Х), Хат)зег (Р, Х), 1ас)зег (Г, Х) Эти операторы представляют собой правила импликации, установленные для нескольких переменных, или универсальных объектов. В данном случае универсальными обьектами являются переменные Х, Х, 2, М и Р.
Первое правило утверждает, что если существуют конкретизации переменных Х и Х, определяющие, что факт вот)зег (Х, Х) является истинным, то для этих же самых конкретизаций переменных Х и Х факт рагепс (Х, Х) является истинным. 626 Глава 15. Языки логического программирования 1$.6.4. Цель До сих пор мы рассматривали операторы языка Рго!ой для логических высказываний, которые используются для описания известных фактов и правил, описывающих логические отношения между фактами. Эти операторы составляют основу модели доказательства теорем.
Теорема формулируется в форме высказывания, которое система должна доказать или опровергнуть. В языке Рго)ой зти высказывания называются целями, или запросами (г)цег!ез). Синтаксическая форма цели в языке Рго)ой идентична форме хорновского днзъюнкта без головы. Например, мы могли бы иметь выражение пап(ангес)). На него система должна дать ответ да или нет. Ответ да означает, что система доказала, что цель была истинной при заданных фактах и отношениях, хранящихся в базе данных. Ответ нет означает, что либо было доказано, что цель ложна, либо система просто неспособна ни доказать, ни опровергнуть ее.
Высказывания в форме конъюнкции и высказывания, содержащие переменные, также допускаются в качестве целей. При наличии переменных система не только контролирует корректность цели, но и идентифицирует конкретизации переменных, делающие цель истинной. Например, системе может быть представлен следующий запрос: хат)зег1Х, пи)се) .
В этом случае система с помощью идентификации попытается найти конкретизашпо переменной Х, делающую цель истинной. Поскольку цели и некоторые операторы, не являющиеся целями, имеют одну и ту же форму (хорновских дизьюнктов без головы), реализация языка Рго!ой должна иметь какие-то средства для того, чтобы отличать их друг от друга. Интерактивные реализации языка Рго!оя делают это просто с помощью двух способов ввода, указываемых путем разных интерактивных подсказок: один — для ввода фактов и правил, другой — для ввода целей. Пользователь может изменить способ ввода в любой момент.
И.6.$. 0роцеес логического вывода в взыке Рго!оа В этом разделе изучается резолюция в языке Рго1оя. Для эффективного использования языка Рго!оя требуется, чтобы программист точно знал, что именно делает система языка Рго)ой с его программой. Запросы называются целпмн (яоа!). Когда цель представляет собой составной оператор, каждый из входящих в нее фактов (структур) называется подцелью (зцЬяоа1). Для доказательства того, что цель истинна, процесс логического вывода должен найти цепочку правил логического вывода и/или факты в базе данных, которые связывают цель с одним или несколькими фактами в базе данных. Например, если Д вЂ” зто цель, то она либо должна быть найдена как факт в базе данных, либо процесс логического вывода должен найти факт Р, и следующую последовательность высказываний Р„Р, ...
Р„: Р.: — Р РЗ Рг 627 15.б. Основные влементы языка Рго(оа Конечно, процесс часто усложняется тем, что правила могут иметь составные правые части или переменные. Процесс поиска фактов Р„если они существуют, в основном сводится к сравнению (или поиску соответствия между термами). Поскольку доказательство подцели осуществляется с помощью поиска соответствия между высказываниями. иногда его называют сопоставлением. В некоторых случаях доказательство подпели называется удовлетворением (заг(з(у)па) этой подцели. Рассмотрим следующий запрос: жаг. (ЬоЬ) .
Эта цель имеет простейший вид. Он относительно прост для того, чтобы резолюция опрелелила, истинно ли это высказывание или ложно; образец этой цели сравнивается с фактами и правилами в базе данных. Если факт пап(ЬоЬ). содержится в базе данных, то доказательство является тривиальным. Допустим, однако, что в базе данных содержатся приведенные ниже факт и правило логического вывода: гасЬег(ЬоЬ). п1ап(Х) : — Гаспег(Х).
Тогда можно потребовать, чтобы система языка Рго(ой нашла два эти утверждения и использовала их для логического вывода истинности цели. Это может привести к необходимости выполнить унификацию, чтобы временно конкретизировать переменную Х значением ЬоЬ. Рассмотрим теперь цель мал (Х) . В этом случае система языка Рго(ок должна сравнить данную цель с высказываниями, хранящимися в базе данных. Первое обнаруженное высказывание, имеющее форму указанной цели, с любым объектом в качестве параметра приведет к конкретизации переменной Х значением этого объекта. Если в базе данных нет высказываний, имеющих форму указанной цели, система отмечает, что цель не может быть достигнута, отвечая по.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
