Основы логического программирования на языке ПРОЛОГ

Дизъюнкция может быть записана в виде импликации: A 1 v А 2 v... v A n В 1 & B 2 & … & B m. Рассматривая логику предикатов 1-го порядка, импликация записывается так: A 1, А 2,..., A n В 1, B 2, …, B m (n 0, m 0) ( при этом принято посылку импликации писать справа, а заключение слева от знака операции).

Понятие факта За основу декларативного описания предметной области принимается специальная форма представления в виде фактов и правил. Факты это отношения или свойства, имеющие место между объектами данной предметной области. Факты имеют общий вид: property(objecti, object2,..., objectN) или relation(objecti, object2,..., objectN) где property это свойство объектов, a relation отношение между объектами.

Примеры записи фактов Предложение: «Маше нравятся цветы». Факт: нравится (маша, цветы). где, отношение это нравится, объекты маша, цветы. Предложение: «Шариковая ручка». Факт: ручка(шариковая) где, шариковая является свойством объекта ручка.

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

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

Общая форма правила relation(object,object,....object) :- relation(object,....object), relation(object,....object). Множество фактов, правил вместе с запросом представляют собой логическую программу (definite program).

Примеры Предложения: «Маше нравятся цветы». «Аня любит сына». «Сын Ани любит Машу». Факты: нравится(маша, цветы) любит(аня, сын) любит(сын, маша)

Примеры Предложения: « Оля любит всех, кого любит Аня». «Нам нравится все, что нравится человеку, которого мы любим». Правила: "Для любого X, если любит(аня, X), то из этого следует, что любит(оля, X)" или «если любит(аня, Х), то любит(оля, Х)». Запишем посылку справа, а заключение (следствие) слева от знака импликации, как это принято в логическом программировании. любит(оля, X) любит(аня, X). "Для любых X, Y, Z, если любит(Х, Y) и нравится (Y, Z), то из этого следует, что нравится(Х, Z)". нравится(Х, Z) любит(Х, Y) & нравится( Y, Z)

множество фактов и правил нравится(маша, цветы) нравится(Х, Z) любит(Х, Y), нравится(Y, Z) любит(аня, сын(аня)) любит(сын(аня), маша) любит(оля, X) любит(аня, X)

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

Примеры 1. Нравятся ли сыну Ани цветы? 2. Любит ли Аня Машу? 3. Кому нравятся цветы? 4. Кого любит Оля? 5. Нравятся ли цветы тому, кто любит Машу? 6. Нравятся ли Ане цветы? 1. нравится(сын(аня), цветы) 2. любит(аня, маша) 3. нравится(Х, цветы) 4. любит(оля, X) 5. любит(Х, маша), нравится(Х, цветы) 6. нравится(аня, цветы)

Дерево решения для запроса: «Нравится ли сыну Ани цветы?» нравится(сын, цветы) Х= сын(аня) нравится(Х, Z) любит(Х, Y), нравится( Y, Z) Z= цветы любит(сын, Y), нравится(Y, цветы), Y= маша любит(сын, маша) нравится(маша, цветы), нравится(маша, цветы)

Дерево для запроса: «Определить того, кто любит Машу и кому нравятся цветы?» любит(Х, маша), нравится(Х, цветы) любит(сын(аня), маша) Х=сын(аня) нравится(сын(аня), цветы) Х= сын(аня) нравится(Х, Z) любит(Х, Y), нравится( Y, Z) Z= цветы любит(сын(аня), Y), нравится(Y, цветы), Y= маша любит(сын(аня), маша) нравится(маша, цветы), нравится(маша, цветы)

СИНТАКСИС И СЕМАНТИКА ПРОЛОГ - ПРОГРАММ

Объекты данных

Атомы и числа Атом - это отдельный объект, считающийся элементарным. Атомы и переменные могут представлять собой цепочки следующих символов: o прописные буквы А, В,..., Z o строчные буквы а, b,..., z o цифры 0, 1, 2,..., 9 o специальные символы: + - * / = :. & _ ~

Атомы и числа Атомы можно создавать тремя способами: 1) из цепочки букв, цифр и символа подчеркивания _, начиная со строчной буквы: анна, nil, х 25, х_25, х_25AB, х_, х__у. 2) из специальных символов:, ======>,...,., : : = (Следует помнить, что часть цепочек специальных символов имеют в Прологе заранее определенный смысл. Например :- ). 3) из цепочки символов, заключенной в одинарные кавычки. Например, атом, начинающийся с прописной буквы. Заключая его в кавычки, он становится отличным от переменной: 'Дом', 'Лев_Толстой'.

Атомы и числа Числа в Прологе бывают целыми и вещественными. integer - целое число в диапазоне от до 32767; real - действительные числа с фиксированной или плавающей точкой в диапазоне от -1Е+308 до 1Е-307. При обычном программировании на Прологе вещественные числа используются редко. Причина этого кроется в том, что Пролог - это язык, предназначенный в первую очередь для обработки символьной, а не числовой информации. При символьной обработке часто используются целые числа, например, для подсчета количества элементов списка.

Переменные Переменные - это цепочки, состоящие из букв, цифр и символов подчеркивания. Переменные в Прологе не описываются, хотя и имеют тип, имя и могут принимать различные значения. Имя переменной должно начинаться с заглавной буквы или с символа подчеркивания: Х, Результат, Объект 2, Список_участников, _х 23, _23. Максимальная длина имени переменной равна 250 знакам.

Переменные В Прологе производится проверка текущего значения переменной. Переменная называется: свободной (free), если она не имеет текущего значения, занятой, (связанной (bound), означенной,) если ей присвоено какое-либо значение. В зависимости от текущего значения переменой X выражение X=3+Y рассматривается или как оператор присваивания (если X - свободная переменная), или как оператор сравнения (если переменная X занята).

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

Переменные Лексический диапазон имени - одно предложение. Например, если имя Х15 встречается в двух предложениях, то оно обозначает две разные переменные. Внутри одного предложения каждое его появление обозначает одну и ту же переменную. Для констант ситуация другая: один и тот же атом обозначает один и тот же объект в любом предложении, т.е. во всей программе.

Структура Пролог - программ domains /* секция объявления доменов */ database /* секция объявления динамических баз данных */ predicates /* секция объявления предикатов */ goal /* подцель_1, подцель_2, и т. д. */ clauses /* предложения (факты и правила) */

Описание в разделе domains Объявляются любые нестандартные домены, используемые для аргументов предикатов. Домены в Прологе являются аналогами типов в других языках. Основными стандартными доменами Турбо-Пролога являются: char - символ, заключенный в одиночные кавычки (например, 'а'); integer - целое от до (переводится в вещественное автоматически, если необходимо); real - вещественное (например, , бе-94, -791 е+21); string - последовательность символов, заключенных в двойные кавычки (например, "нажмите ввод"); symbol - либо набор латинских букв, цифр и символов подчеркивания, в котором первый символ - прописная буква ( например, n_fax ) ; либо последовательность символов, содержащая пробелы или начинающаяся со строчной буквы, заключенная в кавычки (например, "Список СУБД"). file - символическое имя файла, которое начинается с прописной буквы.

Примеры описаний domains name, firm, type = symbol freq, vol = integer

Описания в разделе predicates Объявляются предикаты и типы (домены) аргументов этих предикатов. Имена предикатов должны начинаться со строчной латинской буквы, за которой следует последовательность букв, цифр и символов подчеркивания (до 250 знаков). В именах предикатов нельзя использовать символы пробела, минуса, звездочки, обратной (и прямой) черты. Объявление предикатов имеет форму: predicates predicateName1 (domen11, domen12,..., domen1m) predicateNamen (domenn1, domenn2,..., domennk)

Примеры описаний predicates student( string,real) start good_student( string)

Описание в разделе clauses Размещаются факты и правила, с которыми будет работать Турбо-Пролог, выполняя цель программы. Факт - это утверждение о существовании некоторого отношения между аргументами, обозначаемого именем предиката. Факты - это фразы без условий и они содержат утверждения, которые всегда абсолютно верны. Форма записи фактов: clauses predicateName1 (term11, term12,..., term1 к).... predicateNameN (termN1, terniN2,..., termNL).

Примеры описаний clauses student("Петров",4.5). student("Сидоров",3.75). good_student( Name ) :- student( Name, В ), В >4.

Описание в разделе goal Задается внутренняя цель программы. Это позволяет программе запускаться независимо от среды разработки. Если внутренняя цель включена в программу, то Турбо-Пролог выполняет поиск только одного первого решения, и связываемые с переменными значения не выводятся на экран. Если внутренняя цель не используется, то в процессе работы есть возможность вводить в диалоговом окне внешнюю цель. При использовании внешней цели Турбо-Пролог ищет все решения и выводит на экран все значения, связываемые с переменными. В систему Турбо-Пролог включено более 200 встроенных стандартных предикатов и более дюжины стандартных доменов. В случае использования этих предикатов и доменов нет необходимости объявлять их в программе.

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

Пример Пролог - программы /* программа 1 */ Predicates /* описание предиката */ любит(symbol, symbol) clauses любит (маша, цветы). /* факт */ любит (петр, футбол). /* факт */ любит (петр, маша). любит (петр, X) if likes (маша,X). /* правило */