Лабораторная работа состоит из трех индивидуальных заданий на программирование на языке ПРОЛОГ и нескольких общих упражнений, которые приведены ниже и которые преподаватель уточняет на лекциях.

ЗАДАНИЕ N1 Отношения между объектами. (на Прологе и Паскале)

4.1.1. Методические указания

В практическом плане:

· определить заданное сложное отношение через заданные простые отношения средствами языка ПРОЛОГ;

· сформировать базу данных (явное задание) для простых отношений (база должна быть достаточно представительной для демонстрации возможностей программы);

· не использовать отсечение и предикаты ввода-вывода;

· протестировать целевой и другие предикаты, получить явные задания отношений, построить различные сечения отношений;

· если ответ на запрос содержит повторяющиеся значения, определить дополнительный предикат, содержащий вызов предиката типа findall, setof (см упражнение 3.9.2);

· для сравнения - написать программу на языке PASCAL (или другом процедурном языке), которая частично реализует те же функции.

В теоретическом плане:

Ø записать словесную интерпретацию правил ПРОЛОГ- программы;

Ø записать программу посредством формул логики предикатов.

Ø сравнить программы (ПРОЛОГ и PASCAL) по критериям:

§ пользовательские возможности;

§ возможности модификации;

§ объем текста программ;

§ трудозатраты;

§ и другие.

4.1.2. Варианты

1. Определены предикаты: студент(X,Y) - студент, обучающийся в данной группе; преподаватель(X,Y) - преподаватель, который ведет данный предмет; предмет(X,Y) – предмет, который преподается в данной группе. Определите предикат студент_обучающийся_у_преподавателя(X,Y).

1. Определены предикаты: мужчина(X); женщина(X); родитель(X,Y). Определите следующие предикаты тетя(X,Y); братья(X,Y).
2. Определены предикаты: отец(X,Y); мать(X,Y); мужчина(X); женщина(X). Определите предикаты: двоюродные_братья(X,Y); племянник(X,Y); внук(X,Y); внучка(X,Y).
3. Определены предикаты: отец(X,Y); мать(X,Y); мужчина(X); женщина(X); муж_жена(X,Y). Определите предикаты тесть(X,Y); теща(X,Y); сват(X,Y).
4. Определены предикаты: отец(X,Y); мать(X,Y); мужчина(X); женщина(X); муж_жена(X,Y). Определите предикаты троюродные_братья(X,Y); племянник(X,Y).
5. Определены предикаты: отец(X,Y); мать(X,Y); мужчина(X); женщина(X). Определите предикаты: внучатый_племянник(X,Y), внучатая_племянница(X,Y)..
6. Определены предикаты: отец(X,Y); мать(X,Y); мужчина(X); женщина(X). Определите предикаты сводные_братья(X,Y); сводные_братья_или_сестры(X,Y).
7. Определены предикаты: отец(X,Y); мать(X,Y); мужчина(X); утверждает(X,Y) (X утверждает, что Y – убийца). Определите предикат: убийца(X). X - убийца, если это утверждают Y и Z, которые являются двоюродными братьями.
8. Определены предикаты: отец(X,Y); мать(X,Y); мужчина(X); женщина(X); знакомы(X,Y). Определить предикат: люди_одного_круга(X,Y), если X,Y - братья, или сестры, или они знакомы, или их родители знакомы.
9. Определены предикаты: станция_назначения(X,Y); станция_отправления(X,Y); промежуточная_станция(X,Y). (X - станция, Y- поезд). Определить предикат пересадочная_станция (X,Y,Z) для поездов X и Y, который истинен, если поезда следуют через одну промежуточную станцию Z, или станция назначения Z одного поезда является станцией отправления Z другого.
10. Определены предикаты: отец(X,Y); мать(X,Y); мужчина(X); женщина(X); муж_жена(X,Y). Определить предикат однокровные(X,Y), если у них общий прадедушка.
11. Определены предикаты: мужчина(X); женщина(X); родитель(X,Y). Определить отношение прямой_родственник(X,Y). X – прямой родственник Y, если X - отец, мать, дедушка, бабушка, брат или сестра Y.
12. Определены предикаты: мужчина(X); женщина(X); родитель(X,Y). Определить предикаты: тесть(X,Y); теща(X,Y); свекр(X,Y); свекровь(X,Y).
13. Определены предикаты: сессия(V,W,X,Y,Z) (V,W,X,Y,Z - названия предметов сессии); экзамен(X,Y,Z) (студент X сдал предмет Y с оценкой Z). Определить предикаты: отличник(X) (студент X сдал все экзамены сессии на "отлично"); двоечник(X) (студент X сдал какой-либо из экзаменов сессии на"неуд").
14. Определены предикаты: мужчина(X); женщина(X); родитель(X,Y); муж_жена(X,Y). Определить отношения тесть(X,Y), теща(X,Y).
15. Определены предикаты: мужчина(X); женщина(X); родитель(X,Y); муж_жена(X,Y). Определить отношения золовка(X,Y), своячница(X,Y).
16. Определены предикаты: мужчина(X); женщина(X); родитель(X,Y); муж_жена(X,Y). Определить отношения кузены(X,Y), кузины(X,Y).
17. Определены предикаты: мужчина(X); женщина(X); родитель(X,Y); муж_жена(X,Y). Определить предикат двоюродная_бабушка(X,Y).
18. Определены предикаты: имеет_специальность(X,Y); муж_жена(X,Y). Определить предикат имеют_общие_интересы(X,Y). X и Y имеют общие интересы, если они коллеги или их жены (мужья) коллеги.
19. Определены предикаты: занимается_спортом(X,Y); имеет_специальность(X,Y). Определить предикат имеют_общие_интересы(X,Y). X и Y имеют общие интересы, если они коллеги или занимаются одним видом спорта.
20. Определены предикаты: мужчина(X); женщина(X); родитель(X,Y); муж_жена(X,Y). Определить отношение шурин(X,Y).
21. Определены предикаты: мужчина(X); женщина(X); родитель(X,Y); нравится(X,Y). Определить отношение близкие_по_духу(X,Y), если существует нечто, что обоим нравится, либо они братья или сестры.
22. Определены предикаты: мужчина(X); женщина(X); родитель(X,Y); профессия (X,Y). Определить отношение связаны_общим_интересом(X,Y). X и Y связаны общим интересом, если у них одна и та же профессия или их жены - родные сестры.
23. Определены предикаты: нравится(X,Y), вор(X), дефицитная вещь(X), милиционер(X), не_боится(X,Y). Определить отношение: мог_украсть(X,Y). .X мог украсть Y, если X - вор и Y - есть вещь, которая нравится X или если Y - дефицитная вещь, а Z - милиционер, причем X не боится Z.
24. Определены предикаты: студент(X,Y) - студент, обучающийся в данной группе; предмет(X,Y) – предмет, по которому данная группа сдает экзамен. Определить отношение: экзамен(X,Y), студент X сдает экзамен по дисциплине Y, если он учится в группе, которая сдает экзамен по этой дисциплине.
25. Определены предикаты: студент(X,Y) - студент, обучающийся в данной группе; преподаватель(X,Y) – преподаватель, который читает лекции в данной группе. Определить отношение: лекции(X,Y), студент X слушает лекции преподавателя Y, если он учится в группе, которой читает лекции данный преподаватель.
26. Определены предикаты: студент(X,Y) - студент, обучающийся в данной группе; присутствовал(X,Y) – студент, который присутствовал на занятиях в данный день. Определить отношение: встретились(X,Y,Z), два студента X,Y встретились в некоторый день Z, если они учатся в одной группе и оба присутствовали на занятиях в этот день.
27. Определены предикаты: дорога(X,Y) - дорога, включает данную станцию; станция(X,Y) – станция, на которую данный поставщик поставляет груз. Определить отношение: поставщик(X,Y), поставщик поставляет груз на дорогу, если он поставляет груз на какую-либо станцию этой дороги.
28. Определены предикаты: дорога(X,Y) - дорога, включает данную станцию; отправляет(X,Y) – станция, на которую данное предприятие поставляет груз; получает(X,Y) – станция, от которой данное предприятие получает груз. Определить отношение: является_клиентом(X,Y), предприятие является клиентом дороги, если оно отправляет или получает грузы с какой-либо станции этой дороги.
29. Определены предикаты: нравится(X,Y). Определить отношение любит(X,A). X любит все то, что нравится Y и Z, или любит P, которому нравятся цветы.

ЗАДАНИЕ N2. Работа со списками

4.2.1. Методические указания

В практическом плане:

· определить заданное отношение между списками и их элементами средствами языка ПРОЛОГ;

· не использовать предикаты ввода-вывода;

· не использовать сложные встроенные предикаты, выполняющие специфические операции над списками;

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

В теоретическом плане:

Ø записать словесную интерпретацию правил ПРОЛОГ- программы;

Ø записать программу посредством формул логики предикатов.

4.2.2. Варианты

1. Даны списки целых чисел L1, L2. Построить список L3, состоящий из элементов списка L1, к которому добавлены все элементы списка L2, не входящие в L1.
2. Даны списки целых чисел L1, L2. Построить список L3 по следующему правилу: если L1 является подсписком L2, то из L2 исключить L1; в противном случае присоединить L1 к L2.
3. Множества заданы списками целых чисел L1 и L2. Получить в виде списка L3 множество, представляющее собой объединение множеств L1 и L2.
4. Множества заданы списками целых чисел L1 и L2. Получить в виде списка L3 множество, представляющее собой пересечение множеств L1 и L2.
5. Множества заданы списками строк L1 и L2. Получить в виде списка L3 множество L1\L2.
6. Дан список L1, элементом которого являются списки целых чисел. Построить список L2, изменив порядок элементов в L1 на обратный, и изменить порядок на обратный в каждом подсписке.
7. Дан список литер L1. Построить список L2, исключив из L1 все повторяющиеся литеры.
8. Даны списки литер L1 и L2. Построить список L3 по следующему правилу: если L1 является префиксом L2, то исключить этот префикс и добавить его в качестве суффикса; в противном случае - присоединить к L1 список L2.
9. Дан список литер L. Исключить из списка все строчные литеры.
10. Дан список L. Если длина списка нечетна, то напечатать центральный элемент. В противном случае распечатать первую половину списка.
11. Дан список L. Если длина списка нечетна, построить список L1, поменяв местами левую и правую часть списка, в противном случае оставить список без изменения.
12. Даны два списка символов L1, L2. Если L1 есть подсписок L2, то определить следующий после L1 элемент списка L2, иначе ответом является слово no.
13. Список чисел разделить на 3 списка: числа, меньшие данного числа; равные данному; большие данного.
14. Даны два упорядоченных списка. Образовать из элементов этих списков новый список, также упорядоченный.
15. Из двух списков чисел извлечь общие числа, большие данного и поместить их в третий список.
16. В списке L1 найти элементы, имеющиеся в списке L2 и заменить их на элементы из списка L3 по номеру соответствующего элемента из списка L2.
17. В списке L1 найти элементы, имеющиеся в списке L2 и заменить их на элементы из списка L3 по номеру соответствующего элемента из списка L1.
18. В списке L1 найти элементы, имеющиеся в списке L2 и заменить их на элементы из списка L3 по номеру соответствующему количеству произведенных замен.
19. Имеется список слов. Составить список различных слов данного списка с указанием частоты их появления в нем.
20. Реализовать операции вставки и удаления записей из упорядоченного списка.
21. Отсортировать список, используя метод вставки.
22. Осуществить процедуру слияния двух упорядоченных списков.
23. Переупорядочить элементы списка так, чтобы вначале шли все отрицательные элементы, а затем все неотрицательные элементы.
24. Реализовать операцию поиска максимального элемента списка методом турнира. На каждом этапе попарного сравнения формируется новый список.
25. Имеется два упорядоченных списка. Определить принадлежат ли все элементы второго списка первому списку.

26. Удалить из списка все элементы, принадлежащие второму списку.

1. Элементы списка представляют собой слагаемые многочлена (если коэффициент при степени 0, то элемент в списке отсутствует). Выполнить операцию сложения двух многочленов, представленных списками.
2. Множества целых чисел заданы списками L1, L2, L3. Построить список L4, представляющий собой пересечение множеств L1, L2, L3.
3. Даны списки L1,L2,L3. Если L1 является префиксом L2, а L3 - суффиксом L2, то ответ yes, иначе - no.
4. Даны списки L1, L2, L3. Если конкатенация L1 и L2 - есть префикс L3, то ответ - yes, иначе - no.
5. Даны списки L1, L2, L3. Если L1 и L2 являются подсписками L3, то сформировать новый список, удалив из L3 подсписки L1 и L2, в противном случае оставить L3 без изменения.
6. Имеется два списка. Определить является ли первый список подсписком второго.

4.3. ЗАДАНИЕ N3. Разные задачи

4.3.1. Методические указания

В теоретическом плане:

Ø сформулировать цель задачи в виде отношения между входными и выходными данными;

Ø записать словесную интерпретацию правил ПРОЛОГ- программы;

Ø записать программу посредством формул логики предикатов.

В практическом плане:

· определить отношение между входными и выходными данными средствами языка ПРОЛОГ;

• протестировать целевой и другие предикаты, получить явные задания отношений.

4.3.2. Варианты

1. Напишите программу решения числового ребуса вида . Задача состоит в том. чтобы заменить буквы D, О, N и т.д. на цифры таким образом, чтобы вышеприведенная сумма была правильной. Разным буквам должны соответствовать разные цифры.
2. Напишите программу для упрощения алгебраических сумм, в которых участвуют числа и переменные (строчные буквы). В выдаваемом результате требуется, чтобы переменные предшествовали числам, одинаковые переменные приводились как подобные члены, числовые слагаемые складывались.
3. Дано положение коня на шахматной доске. Определить минимальный путь коня в заданную точку.
4. Дано положение слона на шахматной доске. Определить минимальный путь слона в заданную точку при наличии на доске запрещенных полей.
5. Напишите программу "Ханойские башни".
6. Напишите программу решения задачи о восьми ферзях.
7. Написать программу ввода и вычисления арифметического выражения (операнды - целые числа).
8. Написать программу символьного умножения двух многочленов от одной переменной.
9. Написать программу интерпретации (вычисления) польской инверсной записи арифметического выражения (операнды - целые числа).
10. Написать программу символьного дифференцирования многочлена от одной переменной.
11. Написать программу вычисления значения логического выражения в дизъюнктивной нормальной форме.
12. Напишите программу, распознающую дизъюнктивную нормальную форму формулы логики высказываний.
13. Напишите программу, которая преобразует префиксную запись арифметического выражения в инфиксную, с учетом того, что знак умножения может быть опущен.
14. Написать программу перемножения двух многочленов от n переменных.
15. Написать программу символического дифференцирования многочлена от n переменных.
16. Написать программу символического дифференцирования дробно-рациональной функции.
17. Написать программу символического дифференцирования произвольного алгебраического выражения (операции + - * /).
18. Написать программу символического дифференцирования выражения, включающего тригонометрические функции (операции + -).
19. Написать программу вычисления значения логического выражения в конъюнктивной нормальной форме.
20. Напишите программу, распознающую конъюнктивную нормальную форму.

21. Напишите программу, определяющую является ли данное выражение правилом языка Пролог.

1. Напишите программу, которая читает символьную запись многочлена от одной переменной, список значений коэффициентов, значение переменной и вычисляет значение многочлена.
2. Напишите программу, моделирующую работу недетерминированного конечного автомата.
3. Напишите программу, которая имитирует игру "Крестики-нолики".
4. Напишите программу, которая имитирует игру "Пятнадцать" ("Восемь").
5. Напишите программу, которая имитирует игру "12 палочек" (на каждом шаге можно взять 1,2 или 3, проигрывает тот, кто берет последнюю).
6. На шахматной доске расположены белые и черные ферзи, ладьи, кони и слоны. Могут ли Белые безнаказанно взять фигуру Черных.
7. Написать программу интерпретации (вычисления) триадной записи программы (предусмотреть арифметические операции и присваивание).
8. Напишите программу, которая имитирует игру "Быки и коровы".

30. Напишите программу решения следующей логической головоломки.

Три друга заняли первое, второе и третье места в соревнованиях. Друзья - разной национальности, зовут их по-разному, и любят они разные виды спорта.

Майкл предпочитает баскетбол и выступил лучше чем американец. Израильтянин Саймон выступил лучше теннисиста. Игрок в крикет занял первое место.

Кто является австралийцем? Каким спортом занимается Ричард?

4.4. Содержание отчета

• Титульный лист.
• Содержание (содержит названия всех последующих пунктов)
• ЗАДАНИЕ N1. Отношения между объектами.
• Постановка задачи (копия задания)
• Авторское понимание задачи (более детальное изложение возможностей программы своими словами)
• Теоретический раздел
• Текст(ы) программы(мм)
• Результаты тестирования программы(мм)
• Выводы по заданию 1.
• ЗАДАНИЕ N2. Работа со списками.
• (Аналогично)
• ЗАДАНИЕ N3. Разные задачи.
• (Аналогично)
• Упражнения.
• ОБЩИЕ ВЫВОДЫ
• ИСПОЛЬЗОВАННАЯ ЛИТЕРАТУРА

ЛИТЕРАТУРА

1. Ч. Чень, Р. Ли Математическая логика и автоматическое доказательство теорем, М.: Наука, 1983.

2. Лавров И.А., Максимова Л.Л. Задачи по теории множеств, математической логике и теории алгоритмов, 3-е изд. - М.: Наука, 1995.

3. Братко И. Программирование на языке Пролог для искусственного интеллекта: Пер. с англ. -М.: Мир, 1990.- 560 с., ил.

4. Морозов М.Н. Логическое программирование. ПРОЛОГ. Kурс лекций.- http://www.marstu.mari.ru:8101/mmlab/home/prolog/study_l.html # LEC.- 2001.

5. Задача Альберта Эйнштейна. - http://ruslit.ioso.ru/puzzle_en.htm

если множество М – конечно, то можно просто перебрать все его значения и для каждого из них вычислить истинностное значение F, если же множество М – бесконечно, то вычисление истинностного значения представляет собой проблему, которая в общем виде неразрешима, а в каждом конкретном случае может представлять значительные трудности принципиального характера[1]