Отрицание как неудача. Предикат not

Рассмотрим фразу: «Ваня любит все игры кроме баскетбола.». Попробуем записать её на Прологе. Первая часть этого утверждения выражается легко: «Ваня любит Х, если Х – игра», или же:

Like(wanja,X):-game(X).

Однако необходимо исключить баскетбол. Это можно сделать, воспользовавшись иной формулировкой:

Если Х – баскетбол, тогда „Ваня любит Х” не будет истиной, иначе, если Х – игра, то „Ваня любит Х”.

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

like(wanja, X):- basketball(X),!,fail.

Like(wanja, X):- game(X).

Тут отсечение отбросит рассмотрение другого правила, если игра – баскетбол, а fail вызовет неуспех.

Этот пример показывает, что желательно иметь унарный предикат not, такой, что not(Цель) будет истиной в случае, когда Цель является ложью. На Прологе его можно описать так:

not(P):- P,!, fail;

True.

Пролог-система имеет встроенный предикат not, реализованный подобным образом.

Тогда пример можно переписать следующим образом:

Like(wahja,X):- game(X),

Not(basketball(X))

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

Следующая программа показывает использование предиката not.

Domains

name = symbol

gpa = real

 

Predicates

honor_student(name)

student(name, gpa)

Probation(name)

 

Clauses

honor_student(Name):-

Student(Name, GPA),

GPA>=3.5,

Not(probation(Name)).

student("Betty Blue", 3.5).

student("David Smith", 2.0).

student("John Johnson", 3.7).

probation("Betty Blue").

probation("David Smith").

 

На запрос honor_student(Name) она выдаст список студентов, средний балл которых больше или равен 3,5 за исключением студентов Betty Blue и David Smith, которые проходят практику.

ТРУДНОСТИ В ИСПОЛЬЗОВАНИИ ОТСЕЧЕНИЯ И ОТРИЦАНИЯ

Отметим сначала достоинства использования отсечения:

1. С помощью предиката cut можно повысить эффективность программы.

2. Используя cut, можно описать взаимоисключающие правила, поэтому существует возможность запрограммировать утверждения типа: если P, то Q, иначе R.

Ограничения на использование отсечения выходят за пределы декларативной стороны Пролог-программы. Если в программе нет отсечения, то можно менять порядок фактов и целей. Когда же предикат cut присутствует в программе, то изменение порядка фактов может выйти на её декларативное изменение (дать другое решение).

Если исключение отсечения из программы не меняет её декларативный смысл, то такое отсечение называют «зелёным». В другом случае отсечение называют «красным».

Работать с отрицанием также нужно с осторожностью. Трудности возникают потому, что отрицание, которое здесь используется, не полностью соответствует математическому отрицанию.

Если задать системе следующий запрос:

Цель: not(dog(baks)),

она возможно ответит „да”. Однако этот ответ нельзя рассматривать как утверждение о том, что „Бакс не собака”. Просто системе не достаточно информации для подтверждения высказывания „Бакс - собака”. Такой подход берёт своё начало от предположения о замкнутости мира. Согласно данному предположению мир замкнут в том смысле, что всё существующее в нем либо указано в программе, либо может быть выведено из неё. И в другом случае, когда чего-то нет в программе (или не может быть выведено), то оно является ложным, и следовательно будет истинным его отрицание.

Мы же традиционно не считаем мир замкнутым: если в программе явно не указано, что dog(baks), то это не означает, что мы хотим сказать: Бакс не собака.

Приведём ещё один пример осторожного применения not:

Predicates

R(symbol)

G(symbol)

P(symbol)

Clauses

r(a).

g(b).

P(X):-not(r(X)).

На запрос цель: g(X), p(X) система ответит X=b, а на цель: p(X),g(X) – no (нет). Вся разница в том, что в первом случае переменная Х в момент обработки p(X) была уже связанной, а в другом – этого ещё не произошло.

ПРАКТИЧЕСКИЕ ЗАДАНИЯ

1. Следующие отношения классифицируют числа на три класса – положительные, нуль и отрицательные:

класс(Число, положительное): - Число>0.

Класс(0, нуль).

класс(Число, отрицательное): - Число<0.

Сделать данную процедуру более эффективной с помощью отсечения.

1. Пусть имеется программа:

Р(4).

р(5):-!.

Р(6).

Напишите ответы Пролог-системы на такие запросы:

а) цель: p(X).

б) цель: p(X), p(Y).

c) цель: p(X),!, p(Y).

Объясните полученные ответы.

1. Напишите программу нахождения максимума двух чисел, используя предикат отсечения.

4. Индивидуальное задание 1. Разработать программу на языке Пролог, использующую метод отсечения и отката для решения следующей задачи: из состава студенческой группы выбрать и вывести на экран фамилии студентов, удовлетворяющих одному из условий таблицы 1.

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

Таблица 1.

№ варианта	Условие выборки
	Родившихся в 1979 году
	Родившихся в Рыбнице
	Живущих в общежитии
	Изучавших немецкий язык
	Сдавших экзамен по высшей математике на «4»
	Состоящих в браке
	Живущих вместе с родителями
	Сдавших в школе экзамен по химии на «5»
	Учившихся в рыбницкой школе
	Живущих на ул. Вершигора
	Имеющих автомобиль
	Имеющих компьютер
	Чья работа связана с командировками
	Чье имя Александр
	Имеющих детей
	Блондинов
	Имеющих спортивный разряд
	Служивших в армии
	Владеющих украинским языком
	Работающих по специальности
	Переболевших гриппом в текущем году
	Совершивших прыжки (прыжок) с парашютом
	Умеющих стрелять
	Владеющих приемами рукопашного боя
	Летавших на самолете

Индивидуальное задание 2. Составить программу на языке Пролог для вычисления функций А = А (x, y, z) и В = В (x, y, z) при условиях, заданных в таблице 2. Задачу решить для двух значений x, заданных соответственно в верхней и нижней строках.

Таблица 2.

№	Вид функций при условиях	x	y	z
		0,981   -0,32	-2,625	0,512
		-1,251   8,367	0,827	0,001
		0,263   3,251	0,321	0,466
		6,002   -0,622	3,235	0,541
		1,625     6,31	5,4	0,252
		0,625   17,421	10,365	0,828
		0,451   2,444	0,869	-0,166
		0,335   0,001	0,025	0,805
		5,982   3,258	4,005	-0,661
		8,251   -0,92	0,11	0,765
		1,542   0,085	0,261	0,032
		5,061   1,426	1,22	3,5
		-4,5   1,62	0,75	0,845
		0,025   3,741	-0,82	0,16
		0,412   0,011	0,275	-0,486
		-15,246   3,52	4,642	2,401
		6,55   0,08	2,75	0,15
		0,465   5,15	6,33	3,25
		15,331   -2,23	-0,823	15,221
		1,825   9,052	8,426	17,5
		7,8   0,65	-5,5	2,3
		6,32   -0,85	1,25	0,22
		7,15   0,11	2,55	0,12
		1,34   4,31	2,981	3,075
		3,75   0,22	-6,72	1,05

 

 

КОНТРОЛЬНЫЕ ВОПРОСЫ

1. Для чего предназначен предикат fail и как его использовать?

2. Что такое cut? Для чего его применяют?

3. назовите положительные стороны предиката cut.

4. Дерево типа «И/ИЛИ»: методы построения и работы с ним.

5. В чём суть стратегии поиска в глубину?

6. Достоинства и недостатки стратегии поиска в глубину.

7. Устранение недостатков поиска в глубину с помощью Пролога.

8. Что значит «зелёное отсечение»? «красное отсечение»? Как эти виды отсечений влияют на декларативный смысл программ?

9. Объясните назначение и работу предиката not.

10. Какие трудности могут возникнуть при работе с предикатами отсечения и отрицания?

 

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

ТЕМА: Рекурсия.

ЦЕЛЬ: Научиться использовать возможности Пролога при организации повторяющихся действий.

ТЕОРЕТИЧЕСКАЯ ЧАСТЬ

ИТЕРАЦИЯ И РЕКУРСИЯ

 

Рассмотрим сначала организацию циклической обработки, а затем рекурсивные структуры данных.

Пролог реализует только два типа повторяющихся действий: бэктрекинг и рекурсию. В следующей части программы показано использование бэктрекинга для реализации цикла. На поставленный запрос будут выводится все возможные решения.

Clauses

country(england).

Country(france).

Country(germany).

Country(denmark).

print_countries:-country(X),

write(X), % печать значения Х

nl, % перевод курсора на новую строку

Fail.

print_countries.

Первая фраза говорит: «Найдя решение для предиката country(X), вывести страну X и перейти на новую строку». Затем вызывается предикат fail. В данном случае fail означает: если для поставленной цели могут быть найдены альтернативные решения, то вернуться и найти их.

Встроенный предикат fail всегда имеет ложное значение. Однако мы могли бы форсировать бэктрекинг, используя какой-нибудь другой, всегда ложный предикат типа 10=3+4 или country(abracadabra) (проверьте данное утверждение, заменив в своей программе fail на один из указанных предикатов).

Таким образом, будут получены все страны, и процесс обработки системой первой фразы завершиться. После этого начнётся обработка другой фразы того же предиката print_countries. Она ничего не делает, а только завершает успехом работу системы. Получите конечный вывод решения. Чем он отличается от вывода, если из программы убрать последнюю фразу print_countries?

Для наглядности в рассматриваемую программу можно внести следующие изменения:

1. напечатать заголовок;

2. напечатать все возможные решения запроса;

3. напечатать в конце заключительную фразу.

Тогда нужно модифицировать описание предиката print_countries.

print_countries:-write(“Some delightful places to live are:”), nl, fail.

print_countries:-country(X), write(X), nl, fail.

print_countries:-write(“And may be some others…”), nl.

Нужно ли теперь писать в конце фразу print_countries как факт? Почему?

Рассмотрим следующий предикат: repeat.

Repeat:-repeat.

Такой трюк позволяет реализовать управляющую структуру, которая позволяет получить бесконечное число развязок. Более детально её работу понять после изучения понятия ''хвостовая рекурсия''. Для примера рассмотрим следующую программу:

Clauses

Repeat.

Repeat:-repeat.

Typewriter:- repeat,

Readchar(C),

Write(C),

char_int(C,13).

Эта программа показывает, как работает repeat. Правило typewriter… описывает процедуру, которая воспринимает символы с клавиатуры и печатает их на экране, пока не будет нажата клавиша ENTER (ASCII код = 13).

Она работает следующим образом:

1. Выполняется repeat (который ничего не делает).

2. Потом считывается символ в переменную С.

3. Затем печатается значение С.

4. Потом проверяется, не имеет ли С значение 13 в коде ASCII.

5. Если это так, программа завершается. Иначе начинается бэктрекинг и пересмотр альтернатив. Ни write, ни readchar не генерируют альтернативных развязок, поэтому бэктрекинг идёт до repeat, который позволяет получить альтернативные развязки.

6. Теперь обработка может вернуться в начало, считывать другой символ, печатать его, проверять на равенство 13.

Другой путь реализации повторений – это использование рекурсии. Рассмотрим рекурсивную программу вычисления значения факториала n!, которую можно интерпретировать следующим образом. Если n=1, то n!=1 (запишем factorial(1,1):-!), иначе n!=n*(n-1). Последнее вычисление обеспечивается следующей фразой определения factorial(Х,FactX).

factorial(1,1):-!.

factorial(Х,FactX):-Y=X-1,

Factorial(Y,FactY),

FactX=X*FactY.

Предыдущая рекурсивная программа вычисления факториала может быть описана на Паскале в следующем итерационном виде:

p:=;

for i:=1 to n do

p:=p*I;

FacN:=p;

Или же используя цикл while:

p:=1;

i:=1;

while i<=n do

Begin

p:=p*i;

i:=i+1

end;

FacN:=p;

ПРАКТИЧЕСКИЕ ЗАДАНИЯ

1. Наибольший общий делитель G(M,N) для двух чисел M и N можно обозначить рекурсивной схемой:

 

 

M, если N=0;

G(M,N) =

G(N,mod(M,N)), если N<>0.

 

Написать программу, которая использует рекурсивно описанный предикат G(M,N) для нахождения наибольшего общего делителя пары чисел.

2. Индивидуальное задание. Разработать программы на языке Пролог:

а) использующую метод повтора, определяемый пользователем (задача А);

б) использующую правило рекурсии (задача В).

В задаче А надо вычислить таблицу значений функции y = f (x) для значений аргумента x ₁, x ₂, …, x ₆.

В задаче В (вид функции тот же, что и в задаче А) надо вычислить таблицу значений функции для значений аргумента х в интервале от x _н до x _к с шагом D x.

Таблица 1.

№ варианта	Вид функции	Исходные данные
a	b	Задача А	Задача В
x 1	x 2	x 3	x 4	x 5	x 6	x н	x к	D x
		–	0,75	0,9	4,85	10,3	9,15	3,14	–	1,35	6,5	0,8
		19,6	7,8	24,5	17,5	28,3	16,9		–	14,8	34,6
		1,38	-1,26	70,1	96,3	17,8	20,65	–	–
		–	1,68	0,85	1,29	1,78	1,35	0,6	–	1,2	2,4	0,2
		0,36	5,5	17,9	24,3	26,8	45,2		–
		0,9	1,86	0,15	0,36	0,44	1,1	0,98	0,83		1,2	0,15
		1,24	0,67	11,0	11,4	12,1	11,9	–	–	10,2	12,4	0,45
		2,8	0,45	4,8		59,5	40,2		–			4,5
		20,2	7,65	3,56	4,02	3,84	1,98	2,34	6,57	3,5		0,1
		4,6	2,5	0,49	1,28	1,56	1,14	–	–	0,75	1,8	0,3
		0,55	0,77	3,25	1,28	2,44	3,02	1,76	–	4,2	5,8	0,25
		7,38	0,3	9,5		11,8	10,3	–	–			0,35
		0,28	1,35	1,38	7,85	6,11	2,14	5,6	–	1,2	7,5	0,5
		0,9	0,66	7,35	3,24	6,5	4,18	7,9	–	2,3	8,9	1,3
		0,85	–	23,6	16,9	22,3	20,8	19,5	21,0	17,2	24,6
		1,16	–	1,06	1,24	1,17	0,86	–	–	0,25	1,28	0,33
		0,4	10,8	2,12	1,44	1,9	0,95	1,17	–	0,84	1,25	0,15
		1,28	0,03	14,8	35,0	28,3	16,4	25,9	31,0	12,6	34,9	7,6
		0,25	0,68	13,6	14,9	12,5	16,0	15,1	19,8	11,6	15,8	0,6
		1,6	1,24	0,39	0,48	0,96	0,84	0,73	–	0,2	1,4	0,35
		1,8	0,34	7,25	8,64	7,83	7,16	6,92	6,84	6,44	9,1	0,25
		0,44	2,28	6,34	7,25	7,07	6,83	6,56	–	6,44	8,1	0,12
		3,2	0,45	0,84	0,88	0,96	0,75	1,4	1,3	0,6	1,5	0,2
		17,6	10,45	4,3	3,9	4,25	2,28	1,96	–	1,9	3,8	0,3
		8,24	–	15,6	25,8	20,3	19,6	14,6	–	14,9	24,8	1,5

КОНТРОЛЬНЫЕ ВОПРОСЫ

1. Организация бесконечной рекурсии.

2. Метод повтора, определяемый пользователем.

3. Хвостовая рекурсия.

4. Какие операторы сравнения используются в Прологе?

5. Перечислите арифметические функции, реализованные в Прологе.

 

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

Тема: Организация работы со списками средствами Visual Prolog.

Цель: Научиться работать со списковыми структурами Visual Prolog.

ТЕОРЕТИЧЕСКАЯ ЧАСТЬ

СПИСКИ

 

Списки – это объекты, которые могут содержать различное число однотипных данных. Например: [1,2,3], [dog, cat, canary].

Предположим, нам необходимо создать справочную базу, в которой будем сохранять данные о лекционных курсах, которые могут читать профессора. Её можно реализовать с помощью следующей программы:

Predicates