Лебедева Н.С. Методическое пособие по программированию на Turbo Prolog

Подождите немного. Документ загружается.

TRANSPORTA UN SAKARU INSTITŪTS

Н. С. Лебедева

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

Учебное пособие

Рига

2002

Transporta un sakaru institūts

Институт транспорта и связи

Лебедева Н.С. Логическое программирование. Учеб. пособие. – Рига:

Transporta un sakaru institūts, 2002. – 91 с.

Данное учебное пособие предназначено для студентов компью-

терных специальностей, изучающих курс «Логическое программи-

рование». Рассмотрены основы логического программирования. Дается

описание, синтаксические элементы и основы программирования на

Турбо-Прологе. Рассмотрена работа с базами данных и с системными

предикатами, необходимыми для программирования. Изложение

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

ных заданий для выполнения на ЭВМ. Пособие может быть полезно

всем, кто интересуется построением экспертных систем и проекти-

рованием интеллектуальных систем. Пособие предполагает знакомство

читателя с основами математической логики.

Содержание

Введение..........................................................................................................5

1. Основные понятия языка Турбо-Пролог .............................................7

1.1. Введение в язык Турбо-Пролог ....................................................... 7

1.2. Объекты данных Турбо-Пролога..................................................... 8

1.3. Факты ................................................................................................. 9

1.4. Правила ............................................................................................ 10

1.5. Цели.................................................................................................. 11

1.6. Переменные ..................................................................................... 12

2. Основы программирования на Турбо-Прологе.........................13

2.1. Структура программ на Турбо-Прологе ....................................... 13

2.2. Описание доменов .......................................................................... 14

2.3. Описание предикатов ..................................................................... 14

2.4. Сопоставимость термов.................................................................. 15

2.5. Встроенные предикаты................................................................... 16

2.6. Предикат отрицания ....................................................................... 17

2.7. Операция ''=''.................................................................................... 17

2.8. Декларативный и процедурный смысл программ........................ 18

2.9. Структуры........................................................................................ 19

3. Программирование повторяющихся операций ........................22

3.1. Повторение и откат......................................................................... 22

3.2. Метод отката после неудачи .......................................................... 24

3.3. Метод отсечения и отката .............................................................. 25

3.4. Рекурсия........................................................................................... 27

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

4. Списки.......................................................................................................31

4.1. Введение .......................................................................................... 31

4.2. Операции над списками.................................................................. 32

4.2.1. Поиск элемента в списке ......................................................... 34

4.2.2. Добавление элементов в список ............................................. 35

4.2.3. Деление списка на подсписки ................................................. 35

4.2.4. Объединение списков .............................................................. 36

4.2.5. Сортировка списков................................................................. 37

4.3. Списки и базы данных .................................................................... 40

5. Деревья......................................................................................................42

5.1. Основные понятия .......................................................................... 42

5.2. Основные операции над деревьями ...............................................43

5.2.1. Поиск элемента в дереве.........................................................43

5.5.2.Добавление нового элемента в дерево ....................................44

5.2.3. Удаление элемента из дерева ..................................................47

6. Организация баз данных....................................................................... 50

6.1. Основные понятия...........................................................................50

6.2. Предикаты для работы с базами данных.......................................51

6.3. Способы создания динамических баз данных ..............................51

7. Работа с файлами ................................................................................... 55

7.1. Основные понятия...........................................................................55

7.2 Предикаты для работы с файлами .................................................. 56

7.3. Запись в файл ................................................................................... 58

7.4. Чтение из файла...............................................................................59

8. Создание окон. Использование звука................................................. 60

Рекомендуемая литература ...................................................................... 64

Приложение 1. Лабораторные работы ................................................... 65

Лабораторная работа 1 Работа с фактами и правилами......................65

Лабораторная работа 2 Повторяющиеся операции ............................. 67

Лабораторная работа 3 Структуры, окна, звук .................................... 71

Лабораторная работа 4 Списки .............................................................75

Лабораторная работа 5 Деревья ............................................................ 78

Лабораторная работа 6 Базы данных. файлы....................................... 80

Приложение 2 Встроенные предикаты Турбо-Пролога...................... 81

Функциональные группы предикатов ..................................................81

Алфавитный список предикатов ........................................................... 82

Введение

Логика представляет точный язык для явного выражения целей,

знаний и предположений. Логика дает основание, позволяющее выводить

следствия из исходных положений, позволяет исходя из знаний об

истинности или ложности некоторых утверждений сделать заключение об

истинности или ложности других утверждений. Логика давно используется

и при проектировании компьютеров и при анализе компьютерных

программ. Непосредственное использование логики в качестве языка

программирования, называемого логическим программированием,

возникло впервые в начале 70-х годов.

Логическое программирование радикально отклоняется от основ-

ного пути развития языков программирования. Логическое программи-

рование базируется на убеждении, что не человека следует обучать

мышлению в терминах компьютера, а компьютер должен выполнять

инструкции, свойственные человеку. Логическое программирование

предполагает, что сами инструкции даже не задаются, а вместо этого

явно, в виде логических аксиом формируются сведения о задаче и

предположения, достаточные для ее решения. Такое множество аксиом

является альтернативой обычной программе. Подобная программа

может выполняться при постановке задачи формализованной в виде

логического утверждения, подлежащему доказательству, такое

утверждение называется целевым утверждением. Выполнение

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

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

программе.

Создание логического программирования принадлежит Роберту

Ковальскому из Эдинбурга и Алену Колмероэ из Марселя. Р.Ковальский

разработал процедурную интерпретацию хорновых дизъюнктов. Он

показал, что аксиома

А, если В1, В2, …, Вn,

может рассматриваться и выполняться в качестве рекурсивного языка

программирования. В этом случае А является заголовком процедуры, а

набор Вi – телом процедуры. В дополнение к декларативному

пониманию: А истинно, если истины Вi, утверждение допускает и

следующие понимание: для решения А следует решить, В1 и В2 и … Вn.

При таком понимании процедура доказательства хорнова дизъюнкта

сводиться к интерпретации языка и к алгоритму унификации. Основу

вычислительной модели логических программ составляет алгоритм

унификации (отождествления). Унификация является основой

автоматической дедукции и логического вывода в задачах

искусственного интеллекта. Этот алгоритм является основой процедуры

доказательства методом резолюций, он обеспечивает основные операции

с данными при изменении значений переменных, передачу параметров,

выбор и создание данных.

А. Колмероэ и его группа в университете Марселя создали

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

Эта программа использовалась при построении систем обработки

текстов на естественном языке. Программа доказательств теорем

названная Прологом (от Progrmmatin en Logique), включала в себя

интерпретатор Ковальского.

Язык Пролог возвестил о начале новой эры в программировании.

Он ориентирован не на разработку решений, а на систематическое и

формализованное описание задачи с тем, чтобы решение следовало из

составленного описания. Теоретической основой Пролога является

раздел символьной логики, называемый исчислением предикатов.

Прологу присущ ряд свойств, которыми не обладают традиционные

языки программирования. К таким свойствам относятся механизм

вывода с поиском и автоматическим возвратом, встроенный механизм

сопоставления с образцом и простая, но выразительная структура

данных с возможностью ее изменять.

Пролог – это язык, до сих пор находящийся в развитии. В силу

того, что область его применений постоянно расширяется, в него вносят

все новые и новые возможности, призванные удовлетворить

возрастающие потребности пользователей. Далее будет более подробно

рассмотрена одна из версий Пролога – Турбо-Пролог.

1. Основные понятия языка Турбо- Пролог

1.1. Введение в язык Турбо-Пролог

Турбо-Пролог является компиляторно-ориентированным языком

программирования высокого уровня, разработан фирмой Borland

International. Турбо-Пролог предназначен для программирования задач

из области искусственного интеллекта, создания экспертных систем,

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

языковых конструкций. Встроенные предикаты Турбо-Пролога и другие

дополнительные возможности делают его пригодным для решения

многих стандартных задач из сферы бизнеса.

Турбо-Пролог является декларативным языком программирования.

Программы на Турбо-Прологе содержат утверждения, сделанные

программистом, т. е. ''декларации'' логических соотношений, необходи-

мые для решения задачи. Программист предоставляет самой системе

разобраться в совокупности способов решения задачи. Вместо расписы-

вания шагов выполнения программист должен определить логический

метод для достижения цели программы. Мощные внутренние унифика-

ционные процедуры будут затем искать решение поставленной задачи

(перебирая все возможные комбинации правил, пытаясь удовлетворить

заданную программистом цель). Сила Турбо-Пролога заключается в его

возможностях поиска и сопоставления.

Турбо-Пролог базируется на естественных для человека логических

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

описывающие задачу, а программа выполнит все необходимые действия.

Основная часть программы на императивном языке предназначена

для управления шагами программы, обрабатывающими данные. На

Турбо-Прологе, наоборот, большая часть управления программой либо

неявно содержится в конструкциях языка, либо объявлена в деклара-

тивной форме.

Обозначения, используемые в Турбо-Прологе для выражения логи-

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

предикатов рассматриваются отношения между утверждениями и

объектами.

Рассмотрим предложение:

Катя любит яблоки.

Из данного предложения имеем факт, утверждающий, что Катя любит

яблоки. Изменим порядок слов, т. е. синтаксис данного предложения:

Любит Катя яблоки

Логика предикатов рассматривает отношение между объектами.

Отношение между Катей и яблоками называется отношением

связывания. Будем иметь следующую конструкцию

Отношение Объект Объект

Любит Катя Яблоки

Отношение “любит” связывает объекты ''Катя'' и ''яблоки'' в

конструкцию, обладающую определенным смыслом.

Отношение ''любит'' может быть названо предикатом:

Предикат Объект Объект

Любит Катя яблоки

То же самое можно записать в виде

Предикат (объект 1, объект 2)

или

Любит (Катя, яблоки)

1.2. Объекты данных Турбо-Пролога

Рис. 1.1. Объекты данных Турбо-Пролога

Система распознает тип объектов по его синтаксической форме в

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

для различных типов имеет свои формы. Переменные начинаются с

прописной буквы, атомы со строчной. Больше никакой дополнительной

Ст

уктуры

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

Константы

Переменные

Атомы

(

символы

)

Числа

Простые объекты

информации сообщать не требуется. Для изображения переменных и

атомов используются буквы латинского алфавита: прописные (A, В, …, Z),

строчные (a, b…z), цифры (0…9), специальные символы ( , / ( + – * / < > = :

_ ).

Атомы можно создать тремя способами:

1. из цепочки букв, цифр и символа подчеркивания, начиная со

строчной буквы: x, sister, y10, x_y ;

2. из цепочки символов, заключенный в одинарные кавычки, это

используется, если надо иметь атом начинающийся с прописной

буквы: ' X ', ' Anna';

3. из специальных символов: < - - - >, = = = = . , . . . , :: =.

Объекты данных в Турбо-Прологе называются термами.

1.3. Факты

Программа на Турбо-Прологе состоит из предложений. Каждое

предложение заканчивается точкой. Предложения бывают 3-х типов:

факты, правила, вопросы. Предложения состоят из термов. Терм –

синтаксическая единица.

Факты используются для констатации того, что выполнено

некоторое отношение между объектами.

Пример программы: родственные отношения.

Рассмотрим дерево родственных отношений

Рис. 1.2. Дерево родственных отношений

Введем отношение (предикат) – родители (parent) между объектами

parent(

Tanja

,

Olja

).

Это факт, определяющий, что Таня является родителем Оли, parent –

имя предиката, Tanja, Olja – его аргументы. Аргументы отношения могут

tanja petja

dima

olja

nina

быть конкретными объектами (константами) или абстрактными (Х, Y).

Объекты 1-го типа называются атомами, 2-го типа – переменными.

Отношения могут иметь произвольное число аргументов.

Запишем все имеющиеся факты:

parent(tanja, olja).

parent(petja, olja).

parent(dima, nina).

parent(olja, nina).

Факты содержат утверждения, которые являются всегда безусловно

верными.

При записи фактов надо соблюдать следующие правила:

Имена всех предикатов и объектов должны начинаться со строчной

буквы. Сначала записывают имя предиката, затем в круглых скобках имена

объектов. В конце ставиться точка. Факт может быть предикатом, не

содержащим объектов. Совокупность фактов называется базой данных.

Определяя с помощью фактов отношения между объектами, необходимо

учитывать, в каком порядке перечисляются имена объектов внутри круглых

скобок. Этот порядок может быть произвольным но, выбрав один раз

какой-то определенный порядок, необходимо следовать ему и далее.

Таким образом parent('Olja', 'Tanja') не одно и тоже, что

parent('Tаnja', 'Olja'). Простейший вид программы на Турбо-Прологе

представляет множество фактов.

1.4. Правила

Правила описывают утверждения, которые могут быть истин-

ными, только если выполнено некоторое условие. Правило имеет

заголовок и тело, которые разделяются специальным символом ''-''

(если). Тело правила состоит из одного или нескольких подцелей,

которые разделяются запятой или точкой с запятой. Смысл правила

заключается в том, что отношение в заголовке правила имеет

место только тогда, когда имеют место все отношения в теле

правила.

Запятая между подцелями указывает на конъюнкцию условий.

Это означает, что они должны быть выполнены одновременно.

Точка с запятой указывает на дизъюнкцию условий.

Типичное правило совпадает со словесным утверждением естественного

языка, ''А имеет место, если имеет место А1 и А2 и А3 и т.д. '' и имеет вид:

А: А1, А2, …, Аn,

где А, А1, А2 … Аn – произвольные предикаты.