Пример 3. Опишите на языке Пролог-Д вычисление функции Хевисайда, определяемую формулой:
ì 0, если x<0;
h(x) = í 0, если x=0;
î 1, если x>0.
База знаний должна содержать описание предиката меньше и равно, который выше уже был описаны, предикат, выполняющийся при вычислении функции Хевисайда, будет называться ХЕВИСАЙД. Этот предикат будет иметь два аргумента, первый это аргумент функции, а второй ее значение. Предикат ХЕВИСАЙД определяется через два альтернативных описания для всех значений x
МИР(X,Y)<-НЕ(БОЛЬШЕ(X,Y);
ХЕВИСАЙД(X,0)<-МИР(X,0);
ХЕВИСАЙД(X,1)<-БОЛЬШЕ(X,0);
К этой базе знаний можно задать различные вопросы.
?ХЕВИСАЙД(20,X);
ответ системы Пролог-Д: X=1. И, наконец, последний встроенный предикат - это предикат - "отсечение", предназначенный для управления логическим выводом. Этот предикат потребуется для решения следующих проблем:
1. Ограничение количества найденных решений.
2. Нахождение некоторого особенного решения задачи.
3. Ограничение объема поиска, с целью повышения эффективности работы компьютера. Предикат "отсечение" обозначается знаком восклицания - (!).
Необходимо отметить, что это традиционное обозначение отсечения в системах логического программирования. Если данный предикат использовать в качестве цели в предложении, то полученный при этом эффект можно проиллюстрировать дверью, через которую можно пройти только слева направо, но нельзя вернуться назад через эту дверь. Роль двери выполняет символ !. Как известно система Пролог-Д будет пытаться выполнять цели в предложении порядке просмотра слева направо, начиная от символа <- от первой до последней цели. Если какая-либо цель оказывается не выполненной, то осуществляется возврат и делается попытка найти альтернативные решения. Отсечение ограничивает возможность поиска альтернатив с того момента, как была просмотрена цель, обозначенная символом !. По этой причине, если не выполнены цели А,Б,В, возврат для нахождения альтернативных решений в предложении пример<-А,Б,В,!,Г,Д,Е; возможен, а, если не выполнены цели Г,Д или Е, то уже нет. Рубикон при движении слева направо перейден. Необходимо отметить важность этого предиката особенно при описании задач, допускающих множественные решения. Иллюстрация предиката отсечение на примере базы знаний мама. Действительно, у каждого человека не может быть две матери, поэтому, определив для данного человека имя матери, необходимо прекратить дальнейшие поиски.
мама(Саша,Петя)<-!;
мама(Наташа,Ваня)<-!;
мама(Оля,Петя)<-!;
мама(Катя,Даша)<-!;
мама(Люда,Сережа)<-!;
мама(Петя,Костя)<-!;
к базе знаний может быть задан вопрос
?мама(x,Даша); ответ системы Пролог-Д:
x=Kатя ДРУГИХ РЕШЕНИЙ НЕТ.
После нахождения первого решения поиск альтернатив не производится.
5. Рекурсия.
Существует огромное количество задач, в которых отношения между объектами можно определить, только используя сами определяемые соотношения. При этом получаются правила, называемые рекурсивными. Применение рекурсии для описания задач при работе с системами логического программирования широко распространенный прием. Рекурсия будет проиллюстрирована несколькими примерами построения программ, как вычислительных, так и логических. Первым примером будет пример вычисления наибольшего общего делителя (НОД) двух чисел. Предикат, который выполняется, если найден НОД двух данных чисел будет иметь имя нод и три аргумента: числа a,b и значение НОД - c. Для описания вычисления НОД используются следующие соображения. Во-первых, если, а=b, то c=a=b; Во-вторых, если, а>b, то необходимо вычислить НОД для чисел b и a-b; В-третьих, если b>a, то необходимо вычислить НОД для чисел a и b-a. Эти три утверждения естественным образом могут быть записаны на Прологе-Д.:
нод(а,а,а);
нод(а,b,c)<-БОЛЬШЕ(а,b),ВЫЧИТАНИЕ(a,b,d),нод(b,d,c);
нод(а,b,c)<-БОЛЬШЕ(b,а),ВЫЧИТАНИЕ(b,a,d),нод(a,d,c);
ВЫЧИТАНИЕ(X,Y,Z)<-УМНОЖЕНИЕ(1,X,Z,Y);
Если к этой базе знаний задать вопрос:
?нод(10,15,x);
ответ системы Пролог-Д:
x=5 ДРУГИХ РЕШЕНИЙ НЕТ
Предикат нод, определенный выше оказывается обратимым. В качестве второго примера рассматривается задача о вычислении элементов последовательности: 0, 1, 1, 2, 3, 5, 8, 13, 21 ,34, 55, 89, 144,... , известной как последовательность Фибоначчи. Каждый элемент ее определяется следующими правилами:
f0 =0,
f1 =1,
fn =fn-1+fn-2, при n>1
Первая формула соответствует утверждению о том, что значение нулевого элемента последовательности равно нулю. Это можно записать в виде факта: Фиб(0,0);. Вторая строка соответствует утверждению: первый элемент равен 1. На Прологе-Д это можно записать так: Фиб(1,1);. Третья строка представляет собой запись рекурсивного соотношения:
Фиб(N,X)<-БОЛЬШЕ(N,1),ВЫЧИТАНИЕ(N,1,М),
ВЫЧИТАНИЕ(N,2,К), Фиб(М,Y), Фиб(K,Z),
СЛОЖЕНИЕ(Y,Z,X);
ВЫЧИТАНИЕ и СЛОЖЕНИЕ - имена предикатов вычитание и сложение, определяемых с помощью правил:
СЛОЖЕНИЕ(X,Y,Z)<-УМНОЖЕНИЕ(1,X,Y,Z);
ВЫЧИТАНИЕ(X,Y,Z)<-УМНОЖЕНИЕ(1,X,Z,Y);.
Данные предложения представляют собой базу данных на языке Пролог-Д, позволяющую вычислять значения элементов последовательности. B ответ на вопрос:
?Фиб(10,X);
ответ системы Пролог-Д:
x=55 ДРУГИХ РЕШЕНИЙ НЕТ
Необходимо сказать, что такой путь решения данной задачи не самый лучший. Для нахождения N+1 числа Фибоначчи требуется 2* (N+1)-1 рекурсивное обращение. Однако этого можно избежать, если перейти к другой базе знаний, в которой предикат с именем "Фиб" определен как трехарный, то есть имеющий три аргумента, включающий в себя в качестве аргумента значения N-ого и N-1- ого элементов последовательности. Такая база знаний получается в результате перевода на язык Пролог-Д утверждений.
1. 0-ой элемент последовательности есть 0, а (-1) -ый элемент не определен. Фиб(0,x,0);.
Второй аргумент обозначен x. В данном случае значение x может быть любым.
2. 1-й элемент последовательности есть 1, а нулевой-0. Фиб(1,0,1);. 3. N -й член последовательности Фибоначчи определяется через (N-1) -Й член последовательности.
Фиб(N,F,f)<-БОЛЬШЕ(N,1),ВЫЧИТАНИЕ(N,1,M),Фиб (M,Ф,F), СЛОЖЕНИЕ (Ф, F, f);.
Обращение к этой базе знаний будет иметь вид:
?Фиб(10,F,f);.
ответ системы Пролог-Д:
F=55, f=34 ДРУГИХ РЕШЕНИЙ НЕТ
При работе с этой базой знаний для вычисления N - го числа Фибоначчи необходимо всего лишь N рекурсивных обращений. Для системы Пролог-Д характерна особенность, проявляющаяся при работе с рекурсивными программами. В общем случае, порядок предложений в базе знаний не имеет значения. Однако, в нижеследующем примере это не так
родитель(X)<- родитель(Y),отец(Y,Z);
родитель(Коля);
отец(Коля, Петя);
родитель(Петя);
В первом предложении голова имеет то же имя, что и одна из целей - "родитель". В процессе поиска ответа в этой базе знаний будет применено правило: предложение, стоящее первым, будет и применено первым - известное как принцип поиска в глубину. Это приведет к тому, что система будет обращаться только к первому предложению базы знаний и ответ на вопрос ?родитель(Петя); не будет найден никогда. Вместе с тем, небольшое изменение базы знаний, перестановка двух предложений местами, приводит к удачному поиску решения:
родитель(Коля);
родитель(X)<-родитель(Y), отец(Y,X);
отец(Коля, Петя);
?родитель(Петя);.
Неограниченно-повторное обращение к предложению может быть и более замаскированным так, как это получается в примере:
ВЫШЕ(А,В)<-НИЖЕ(В,А);
НИЖЕ(В,А)<-ВЫШЕ(А,В);
ВЫШЕ(Коля, Петя);
?НИЖЕ(Петя, Коля);.
Однако если третье предложение стоит на первом месте, то повторного обращения не произойдет и ответ будет найден. Такая ситуация называется петля. При вычислении элементов последовательности Фибоначчи, может появляться бесконечная петля при исполнении программы. В самом деле, если вопрос имеет вид:
?Фиб(0,x,y);,
то первый возможный результат x =_0, y =1. Далее в попытке отыскать следующее решение возникает бесконечная петля, так как будет отыскиваться Фиб(-1,x,y), Фиб(-2,...),... . Для контроля за подобной ситуацией необходима модификация базы знаний. Первые два предложения должны быть записаны в виде:
Фиб(0,x,1)<-!;
Фиб(1,1,1)<-!;,
тогда при поиске альтернативного решения после получения ответа на вопрос:
?Фиб(0,x,y); x=_0, y =1
будет получен результат:
ДРУГИХ РЕШЕНИЙ НЕТ.
Данный пример иллюстрирует первое возможное использование предиката "отсечение". И еще одно чисто эстетическое предложение. База знаний на Прологе-Д будет выглядеть лучше, если предложения с одинаковыми именами расположены в одном месте. Для сравнения приводится две базы знаний:
1. 2.
мама(Таня, Надя); мама(Таня, Надя);
бабушка(X,Y)<-мама(X,Z), мама(Надя, Катя);
мама(Z,Y), бабушка(X,Y)<-мама(X,Z),
мама(Надя, Катя); мама(Z,Y);.
6. Графические возможности системы Пролог-Д.
Когда речь идет о компьютерной графике, построение изображения на экране интерпретируется серией команд. Таким образом, всякое изображение ассоциируется с алгоритмом его построения. Однако, эта концепция не укладывается в принципы декларативного программирования, принятые в системе Пролог-Д. Если последовать этой концепции то необходимым становится описание элементов рисунка в виде совокупности графических объектов, соотношений и связей между ними. В этом случае описание последовательности действий художника - исполнителя становится излишним. В системе Пролог-Д определен набор графических примитивов, отображающих графические объекты и построенных таким образом, что с точки зрения синтаксиса каждый из них может быть только целью, и принимает значение "истина" (выполняется), если на экране появляется графическое изображение объекта. При записи в правиле нескольких графических примитивов и выполнении данного правила на экране появляется объединение графических образов в той последовательности, как они описаны в правиле. Во всех графических встроенных предикатах аргументами должны быть целыми или переменными, конкретизированными целыми, или не конкретизированными переменными. Если это требование не выполнено, то появится сообщение об ошибке. Параметр v - вертикальный размер, а h - горизонтальный размер экрана. Для стандартной платы видеоадаптера VGA v=349, h=639. В предикатах ТОЧКА, ЛИНИЯ, ОКРУЖНОСТЬ, ЗАКРАСКА последний параметр задает цвет. Как правило, если на этом месте стоит не конкретизированная переменная, то также выводится сообщение об ошибке. Для обозначения цвета при использовании видеоадаптера VGA принята кодировка цветов, изображенная в таблице 3.4.1. В системе Пролог-Д имеет место особенность использования встроенных предикатов, обусловленная спецификой графических средств системы IBM-PC. Для использования графики необходимо открыть графический файл с помощью предиката ЗАПИСЬ_В(“grp:”). После завершения работы необходимо открыть файл для вывода текста ЗАПИСЬ_В(“con:”).