Примеры программ с использованием фактов и правил

МИНИСТЕРСТВО ОБРАЗОВАНИЯ И НАУКИ

РОССИЙСКОЙ ФЕДЕРАЦИИ

ФГАОУ ВО «Крымский федеральный университет
имени В. И. Вернадского»

Таврическая академия (структурное подразделение)

Кафедра информатики

 

Козлова М.Г.

 

ЛОГИЧЕКОЕ ПРОГРАММИРОВАНИЕ

 

Учебно-методическое пособие

 

 

Симферополь
2016

КОЗЛОВА М.Г.

Логическое программирование: учебно-методическое пособие / М. Г. Козлова. ФГАОУ ВО «Крымский федеральный университет имени В. И. Вернадского». ― Симферополь, 2016. ― 54 с.

 

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

Предназначено для студентов 3-го курса направления подготовки 01.03.02 — Прикладная математика и информатика.

 

 

©Козлова М.Г., КФУ, 2016

СОДЕРЖАНИЕ

Лабораторная работа №1. Основы программирования на Прологе 4

Лабораторная работа №2. Использование рекурсии в Прологе.... 16

Лабораторная работа №3. Представление и обработка списков.……26

Лабораторная работа №4. Сортировка списков ………………….……35

Лабораторная работа №5. Множества......... ………………….……46

Лабораторная работа №6.............................. ………………….……11

Лабораторная работа №7.............................. ………………….……11

Лабораторная работа №8.............................. ………………….……11

Лабораторная работа №9.............................. ………………….……11

Лабораторная работа №10............................ ………………….……11

Список источников................................................................................

Приложение

 

 

ЛАБОРАТОРНАЯ РАБОТА №1

ОСНОВЫ ПРОГРАММИРОВАНИЯ НА ПРОЛОГЕ

Цель работы

Изучение структуры программ. Разработка Пролог-программ с использованием фактов и правил. Организация запросов к программе.

 

Краткие сведения

Основные понятия

Пролог — язык логического программирования, основанный на логике предикатов первого порядка. Пролог-программы содержат описание логических взаимосвязей, необходимых для решения задачи. С точки зрения логики предикатов элементарные выражения имеют вид

,

где — имя предиката, — аргументы.

Например, предложение «Степан является дядей Ольги» на Прологе запишется в виде: Uncle(stepan,olga), где Uncle — предикат, описывающий отношение «является дядей»; stepan, olga — объекты «Степан» и «Ольга», связанные отношением Uncle.

Предложения в Прологе бывают трех типов: факты, правила и запросы.

Факт используется для констатации того, что выполнено некоторое отношение между объектами. Например,

man(igor).

woman(anna).

parent(igor,anna).

Эти факты констатируют, что «igor — мужчина», «anna — женщина», «igor является родителем anna».

Правила — это утверждения, истинность которых зависит от некоторых условий. Например:

child(X,Y):- parent(Y,X).

grandmother(X,Y):- parent(X,Z), parent(Z,Y), woman(X).

Первое правило устанавливает, что «X является ребенком Y», если истинно выражение «Y является родителем X». Второе правило говорит, что «X является бабушкой Y», если выполняется, что существует такой Z, что «X является родителем Z» и «Z является родителем Y», и «X является женщиной».

Правила позволяют определять новые предикаты через уже имеющиеся. В данном случае предикат child (ребенок) определяется через предикат parent (родитель), и предикат grandmother (бабушка) через предикаты parent и woman (женщина).

Конечное множество правил и фактов образует логическую программу. В синтаксисе Пролога каждое правило и каждый факт заканчиваются точкой (признак конца предложения).

Множество всех утверждений, входящих в состав одного предиката, называется процедурой. Предикат реализуется в Пролог-программе с помощью процедуры. Например,

woman(anna). woman(irina). woman(svetlana).	предикат, описывающий женщин.
man(igor).	— предикат, описывающий мужчину.
parent(anna,igor). parent(igor,irina).	предикат, описывающий родителей.
grandmother (X,Y):- parent(X,Z), parent(Z,Y), woman(X).	процедура grandmother

В Прологе предложения каждой процедуры должны быть сгруппированы в одном месте.

Аргументы предиката могут быть конкретными или абстрактными. Конкретный аргумент задается именем (простейший случай). В Прологе принято, что имя аргумента — это идентификатор, начинающийся с маленькой буквы. Абстрактный аргумент — это переменная. Переменная обозначается идентификатором, начинающимся с заглавной буквы. Область действия переменной, входящей в предложение, ограничивается этим предложением. В связи с этим две переменные с одинаковыми именами из разных предложений — это две различные переменные.

В Прологе выделяется анонимная переменная — знак подчеркивания «_», — которая предписывает проигнорировать значение аргумента. Например, в предложении

mother(X):- parent(X,_), woman(X).

определяется предикат mother (мама), условная часть которого содержит предикат «X является родителем Y». В связи с тем, что для предиката mother не важно, родителем кого именно является X, то второй аргумент в предикате parent — анонимная переменная.

Запрос (цель) инициализирует процедуру поиска в программе (факты + правила). Пролог просматривает факты и правила в поисках предиката, сопоставимого с запросом.

Запрос может быть простым (подцель). Это предикат, относительно которого нужно выяснить, выполняется он или нет. Аргументами такого предиката могут быть как конкретные объекты, так и переменные. Запрос может состоять из одной или нескольких подцелей. Чтобы ответить на запрос, Пролог пытается проверить, выполняются ли соответствующие предикаты. Последовательность подцелей — это одновременное выполнение всех подцелей. Если запрос содержит переменные, то Пролог-система должна найти конкретные объекты, которые, будучи подставлены вместо переменных, обеспечивают достижение цели. Если ни для одной такой подстановки Пролог-система не может вывести цель из предложений программы, то ответом на запрос будет no (нет).

Рекурсия — алгоритмический метод, используемый в Прологе и означающий обращение процедуры к самой себе. Классическим примером рекурсивного определения на Прологе служит определение предиката ancestor (предок), состоящего из двух предложений:

ancestor(X,Y):- parent(X,Y).

ancestor(X,Y):- parent(Z,Y), ancestor(X,Z).

Первое правило определяет «непосредственного предка» — родителя, а второе — «отдаленного предка» (предка родителя).

 

Типы доменов Пролога

Домен определяет множество допустимых значений, которые может принимать объект, принадлежащий этому домену. В табл. 1.1 приведены шесть встроенных типов доменов Пролога.

Таблица 1.1

Тип данных	Ключевое слово	Пример
Символы	char	'б', '? ', 'z'
Целые числа	integer	32, -120
Действительные числа	real	0.12, -3.14
Строки	string	"baby", "157"
Символьные имена	symbol	p, q, r, anna, "Ivan"
Файлы	file	proba.txt

 

В Прологе можно вводить собственные имена типов доменов для придания смысла аргументу предиката. Типы доменов используются для описания предикатов в разделе predicates. Например:

domains

title, producer = symbol

year = integer

predicates

film (title, producer, year)

или

predicates

film (symbol, symbol, integer)

Пролог-программа может состоять из пяти разделов:

1) domains — описание доменов, которые описывают классы объектов, используемых в программе;

2) database — определение баз данных, которые являются предикатами динамической базы данных;

3) predicates — описание предикатов, используемых в программе;

4) clauses — описание фактов и правил;

5) goal — описание запроса (цели) создаваемой программы.

 

Арифметические операторы

Арифметические операции: + (сложение), - (вычитание), / (деление), * (умножение), div (частное от деления нацело), mod (остаток от деления нацело). Операндами операций div и mod могут быть только целые значения.

Операции отношения: >, >=, <, <=, =, <>, ><, где операции <>, >< означают «неравно».

Функции:

sin(X)	– возвращает синус своего аргумента;
cos(X)	– возвращает косинус своего аргумента;
tan(X)	– возвращает тангенс своего аргумента;
arctan(X)	– возвращает арктангенс вещественного значения, с которым связан X;
ln(X)	– натуральный логарифм X;
log(X)	– десятичный логарифм X;
exp(X)	– е в степени X;
sqrt(X)	– корень квадратный из X;
abs(X)	– если значение X — положительная величина value, то abs(X) возвращает это значение; в противном случае (–1)*value;
round(X)	– округляет значение X (результат вещественный);
trunk(X)	– усекает (отбрасывает дробную часть) Х.

 

Цель программы

Цель — формулировка задачи, которую программа должна решить. Пролог использует внутренние и внешние цели. Внутренние содержатся в программе в разделе goal, внешние вводятся с клавиатуры после запуска программы. Если цель внутренняя, то при выполнении программы Пролог-система ищет первое решение и заканчивает работу, если же цель внешняя, то Пролог-система ищет все решения. Программа работает на доказательство цели. Подцели цели доказываются слева направо последовательно, подцель за подцелью.

 

Примеры программ с использованием фактов и правил

 

Пример 1.1. Рассмотрим программу, в которой используется предикат likes(X,Y), описывающий отношение «X предпочитает Y».

predicates
likes(symbol, symbol). % Описание предиката
clauses

% Определение предиката, используя факты
likes(igor,"Italy").
likes(anna,"Germany").
likes(igor,"Germany").
likes(dima,"France").
likes(german,"Spain").

% Определение предиката, используя правила
likes(elena,R):- likes(dima,R).

likes(nina,R):- likes(igor,R), likes(anna,R).

Факты задают предпочтения объектов igor, anna, dima, german. Первое правило указывает, что «elena предпочитает то же, что и dima» (т. е. France). Второе правило указывает, что «nina предпочитает то, что предпочитают igor и anna одновременно» (т. е. Germany). Созданной программе можно задать цель:

goal
likes(X,"Spain"), write(X), nl, fail.

Символ Х обозначает наличие в запросе переменной. Результатом решения программы будет нахождение значения Х, удовлетворяющего поставленной цели, т. е.:

german

На запрос

goal
likes(igor,R), write(R,", "), nl, fail.

будут найдены все решения, удовлетворяющие цели, а именно:

Italy,

Germany,

На запрос

goal
likes(X,R), write(X," ",R), nl, fail.

будут выведены на экран все возможные значения пар (Х,Y), т. е.

igor Italy

anna Germany

igor Germany

dima France

german Spain

elena France

nina Germany

 

Пример 1.2. Рассмотрим пример решения квадратного уравнения .

predicates % Описание предикатов

equation(real, real, real).

answer(real, real, real).

clauses

% Предикат, описывающий дискриминант

equation(A,B,C):- D = B*B - 4*A*C,

answer(A,B,D), nl.

answer(_,_,D):- % D<0 - нет решений

D < 0,

write("Not real answer"),!.

answer(A,B,D):- % D=0 - единственное решение

D = 0,

X = -B/(2*A),

write("One solve X=", X),!.

answer(A,B,D):- % D>0 - не единственное решение

W = sqrt(D),

X1 = (-B+W)/(2*A),

X2 = (-B-W)/(2*A),

write("Two solves X1=",X1," X2=",X2).

Тогда, на запрос

goal

equation(1,1,1).

на экране появится Not real answer

На запрос

goal

equation(1,2,1).

будет решение One solve X=-1

На запрос

goal

equation (1,-15,50).

будет выдано решение Two solves X1=10 X2=5

Варианты заданий

Задание 1.1. Имеется N объектов и заданы отношения между ними: родитель, мужчина, женщина. Требуется определить новое отношение и выявить круг лиц, ему удовлетворяющих.

1. Определить предикат ОТЕЦ и найти всех отцов.

2. Определить предикат МАТЬ и найти всех матерей.

3. Определить предикат ДЕТИ и найти всех детей конкретного лица.

4. Определить предикат ВНУКИ и найти всех внуков конкретного лица.

5. Определить предикат СЫН и найти всех сыновей и сыновей конкретного лица.

6. Определить предикат ДОЧЬ и найти всех дочерей и дочерей конкретного лица.

7. Определить предикат ДЕДУШКА и найти всех дедушек и дедушек конкретного лица.

8. Определить предикат БАБУШКА и найти всех бабушек и бабушек конкретного лица.

9. Определить предикат ДВОЮРОДНЫЙ ДЕДУШКА и найти всех двоюродных дедушек и двоюродных дедушек конкретного лица.

10. Определить предикат ДВОЮРОДНАЯ БАБУШКА и найти всех двоюродных бабушек и двоюродных бабушек конкретного лица.

11. Определить предикат ТЕТЯ и найти всех тетей и тетей конкретного лица.

12. Определить предикат ДЯДЯ и найти всех дядей и дядей конкретного лица.

13. Определить предикат БРАТ и найти всех братьев и братьев конкретного лица.

14. Определить предикат СЕСТРА и найти всех сестер и сестер конкретного лица.

15. Определить предикат ДВОЮРОДНЫЙ БРАТ и найти всех двоюродных братьев и двоюродных братьев конкретного лица.

16. Определить предикат ДВОЮРОДНАЯ СЕСТРА и найти всех двоюродных сестер и двоюродных сестер конкретного лица.

17. Определить предикат ТРОЮРОДНЫЙ БРАТ и найти всех троюродных братьев и троюродных братьев конкретного лица.

18. Определить предикат ТРОЮРОДНАЯ СЕСТРА и найти всех троюродных сестер и троюродных сестер конкретного лица.

19. Определить предикат ПЛЕМЯННИК и найти всех племянников и племянников конкретного лица.

20. Определить предикат ПОТОМОК и найти всех потомков и потомков конкретного лица.

21. Определить предикат ПРЕДОК и найти всех предков и предков конкретного лица.

22. Определить предикат ПОТОМОК МУЖСКОГО ПОЛА и найти всех потомков мужского пола и потомков мужского пола конкретного лица.

23. Определить предикат ПОТОМОК ЖЕНСКОГО ПОЛА и найти всех потомков женского пола и потомков женского пола конкретного лица.

24. Определить предикат ПРЕДОК МУЖСКОГО ПОЛА и найти всех предков мужского пола и предков мужского пола конкретного лица.

25. Определить предикат ПРЕДОК ЖЕНСКОГО ПОЛА и найти всех предков женского пола и предков женского пола конкретного лица.

Задание 1.2. Написать программу на Прологе.

1. Заданы три числа a, b, c. Определить, сколько среди них положительных.

2. Заданы четыре числа a, b, c, d. Определить количество нулевых значений.

3. Заданы четыре числа a, b, c, d. Определить, сколько среди них отрицательных.

4. Задана прямая . Для произвольной точки определить, как расположена она относительно прямой: выше прямой; на прямой; ниже прямой.

5. Заданы три числа a, b, c. Определить, являются ли они упорядоченными: по возрастанию; равны (a = b = c); по убыванию; не упорядочены. Сколько среди них отрицательных?

6. Заданы три числа a, b, c. Найти сумму положительных чисел.

7. Заданы три числа a, b, c. Определить, сколько среди них отрицательных.

8. Заданы три числа a, b, c. Определить среди них количество максимумов.

9. Заданы три числа a, b, c. Определить среди них количество минимумов.

10. Заданы три числа a, b, c. Определить минимальное значение среди положительных.

11. Заданы три числа a, b, c. Определить максимальное значение среди отрицательных.

12. Для произвольных чисел a, b, c определить количество действительных корней уравнения .

13. Заданы три точки , , . Определить их взаимное расположение: все точки совпадают; две точки совпадают, а третья отличается; все точки отличаются.

14. Заданы три точки , , . Определить их взаимное расположение: точки лежат на одной прямой; точки образуют невырожденный треугольник.

15. Задана система координат в пространстве и произвольная точка (x, y, z). Определить, как расположена точка относительно системы координат: в начале системы координат; на одной из осей; вне осей координат.

16. Заданы прямая и две точки , . Определить их взаимное расположение: точки по одну сторону прямой; точки по разные стороны от прямой; одна точка на прямой, а другая — нет; обе точки на прямой.

17. Задана система координат на плоскости и произвольная точка (x, y). Определить, где лежит точка: на пересечении осей координат; на оси Х; на оси Y; вне осей координат.

18. Задана система координат на плоскости и произвольная точка (x, y). Определить, где лежит точка: на осях координат; в I квадранте; во II квадранте; в III квадранте; в IV квадранте.

19. Задана окружность с центром (x, y) и радиусом r. Определить взаимное расположение окружности и осей координат: окружность пересекает обе оси; окружность пересекает только ось Х; окружность пересекает только ось Y; окружность не пересекает осей координат.

20. Задан отрезок своими концами , . Определить взаимное расположение отрезка и осей координат: отрезок параллелен оси Х; отрезок параллелен оси Y; отрезок не параллелен осям координат; отрезок вырожден.

21. Задан отрезок своими концами , . Определить взаимное расположение отрезка и осей координат: отрезок лежит на какой-то оси координат; отрезок параллелен какой-то оси координат; отрезок не параллелен осям координат.

22. Задан треугольник своими сторонами a, b, c. Определить, образуют ли они: равносторонний треугольник; равнобедренный треугольник; не образуют треугольника.

23. Задан треугольник своими сторонами a, b, c. Определить, образуют ли они: прямоугольный треугольник; тупоугольный треугольник; остроугольный треугольник; не образуют треугольника.

24. Заданы прямые , . Определить их взаимное расположение: пересекаются; параллельны; совпадают.

25. Заданы два круга с центрами , и радиусами , соответственно. Определить взаимное расположение кругов: один внутри другого; пересекаются; не пересекаются.

ЛАБОРАТОРНАЯ РАБОТА №2

12345Следующая ⇒

Поделиться:

Воспользуйтесь поиском по сайту: