Пособие содержит большое
количество примеров, тестирование которых проводилось в режиме Test Goal в
свободно распространяемой среде логического программирования Visual Prolog <...> В
предложенных
материалах
подробно
изложены
основы
программирования на языке Пролог в среде Visual Prolog. <...> 1.2 Логика и исчисление высказываний
Рассмотрим три высказывания на естественном языке:
«Стрекоза является насекомым» - фактическая истина;
«Любой город обладает населением в несколько тысяч человек» -
истина языка;
«Если из того, что четырехугольник является квадратом,
следует, что все его углы и стороны равны между собой, то из того,
что не все углы и стороны четырехугольника равны между собой,
следует, что четырехугольник не является квадратом» - истинность
данного высказывания определяется по смыслу слов. <...> Каждая
буква, входящая в формулу, в свою очередь может быть формулой, поэтому
более правильным должно использование термина пропозициональная форма. <...> Пропозициональная форма истинная ПРИ ЛЮБЫХ значениях входящих
в нее пропозициональных переменных называется тавтологией. <...> Пропозициональная форма ложная ПРИ ЛЮБЫХ значениях входящих в
нее пропозициональных переменных называется противоречием. <...> Пропозициональная форма истинная ПРИ НЕКОТОРЫХ значениях
входящих в нее пропозициональных переменных называется выполнимой. <...> 1.3 Логическое следствие и логический вывод
Выявление того факта, что из множества высказываний (формул
исчисления) логически следует некоторое другое высказывание (формула)
является одной из основных задач исчисления высказываний. <...> U логически влечет W (W логически следует из U) в исчислении
высказываний, что обозначим как U => W, если пропозициональная форма U
→ W является тавтологией. <...> 8
1.4 Метод резолюций
Ключом к пониманию метода резолюций является следующее рассуждение:
Чтобы доказать, что {F1,…,Fn }=>F, необходимо доказать, что формула
F1&…&Fn → F является тавтологией. <...> Метод
резолюций
базируется
на
возможности <...>
Системы_искусственного_интеллекта._Часть_I._Рекурсивно-логическое_программирование_учебное_пособие.pdf
Федеральное государственное бюджетное образовательное учреждение
высшего профессионального образования
«Тульский государственный педагогический университет
имени Л. Н. Толстого»
Кафедра информатики и методики обучения информатике
В. С. ВАНЬКОВА, Ю. М. МАРТЫНЮК, Н. Н. ХАБАРОВ
СИСТЕМЫ ИСКУССТВЕННОГО ИНТЕЛЛЕКТА.
Часть I.
РЕКУРСИВНО-ЛОГИЧЕСКОЕ ПРОГРАММИРОВАНИЕ
Тула
2012
1
Стр.1
ББК 32.813я73
УДК 519.764.4
В 17
Рецензенты:
кандидат биологических наук,
доцент кафедры информационных технологий Н.М.Исаева,
(Тульский государственный педагогический университет им. Л.Н.Толстого);
кандидат педагогических наук, доцент кафедры
информационных систем и компьютерных технологий Е. А. Снижко
(БГТУ им. Д. Ф. Устинова)
В 17 Ванькова, В. С.
Системы искусственного интеллекта: Учеб. пособие: В 2 ч. /
В.С. Ванькова, Ю. М. Мартынюк, Н.Н.Хабаров – Тула: Тул. гос. пед.
ун-т им.Л.Н.Толстого, 2012. – Ч.I. Рекурсивно-логическое
программирование – 64с.
В учебном пособии представлен материал для формирования навыков
рекурсивно-логического программирования. Пособие содержит большое
количество примеров, тестирование которых проводилось в режиме Test Goal в
свободно распространяемой среде логического программирования Visual Prolog
5.2.
Учебное пособие предназначено студентам, обучающимся
по
направлениям 010500.62 «Математическое обеспечение и администрирование
информационных систем», 010300.62 «Фундаментальная информатика и
информационные технологии», и может быть использовано студентами,
проходящими подготовку в рамках группы направлений 010000 «Физикоматематические
науки».
Материалы данного учебного пособия содержат теоретические основы
элективных курсов соответствующей тематики в средней школе.
УДК 519.764.4
ISBN 978-5-87954-765-8
В.С.Ванькова,
Ю.М.Мартынюк,
Н.Н.Хабаров, 2012
ТГПУ, 2012
2
Стр.2
СОДЕРЖАНИЕ
ПРЕДИСЛОВИЕ..........................................................................................................................5
МАТЕМАТИЧЕСКИЕ ОСНОВЫ ЛОГИЧЕСКОГО ПРОГРАММИРОВАНИЯ....................6
1.1 Схема построения формальной системы............................................................................6
1.2 Логика и исчисление высказываний...................................................................................6
1.3 Логическое следствие и логический вывод........................................................................7
1.4 Метод резолюций.................................................................................................................9
1.5 Формальная теория..............................................................................................................9
1.6 Отношение и предикат ......................................................................................................10
1.7 Кванторы............................................................................................................................10
1.8 Язык логики предикатов....................................................................................................11
1.9 Логический вывод в исчислении предикатов...................................................................13
КОМПЬЮТЕРНАЯ ИНТЕРПРЕТАЦИЯ ЛОГИКИ...............................................................14
2.1 Логическое программирование.........................................................................................14
2.2 Виды предложений Хорна.................................................................................................15
ОСНОВЫ ЯЗЫКА VISUAL PROLOG.......................................................................................18
3.1 ПРОграммирование в ЛОГике ..........................................................................................18
3.1.1 Предикаты...................................................................................................................19
3.1.2. Факты..........................................................................................................................19
3.1.3. Правила.......................................................................................................................20
3.1.4. Запросы (цели) ...........................................................................................................21
3.1.5. Переменные................................................................................................................21
3.1.6. Комментарии..............................................................................................................23
3.2 Программы Visual Prolog...................................................................................................24
3.2.1 Основные разделы программ......................................................................................24
3.2.2 Стандартные домены..................................................................................................25
3.3 Сопоставление и унификация ...........................................................................................26
3.4 Поиск с возвратом..............................................................................................................28
3.4.1 Основные правила поиска с возвратом......................................................................28
3.4.2 Управление поиском решений ...................................................................................30
3.5 Арифметические выражения. Ввод и вывод данных .......................................................34
3.5.1 Функции и предикаты.................................................................................................34
3.5.2 Генератор случайных чисел........................................................................................35
3.5.3 Возврат вычисленного значения ................................................................................36
3.5.4 Предикаты вывода ......................................................................................................36
3.5.5 Предикат ввода............................................................................................................37
3.5.6 Предикат not ................................................................................................................38
3.6 Простые и составные объекты..........................................................................................39
3.6.1 Составные объекты данных и функторы ...................................................................39
3.6.2 Правило декларирования доменов для составных объектов.....................................42
3.7 Повтор и рекурсия .............................................................................................................44
3.7.1 Откат с петлями...........................................................................................................44
3.7.2 Оптимизация хвостовой рекурсии..............................................................................45
3.7.3 Использование аргументов в качестве переменных цикла .......................................46
3.8 Рекурсивные структуры данных .......................................................................................48
3.8.1 Списки .........................................................................................................................48
3.8.1.1 Сопоставление в списках.........................................................................................48
3.8.1.2 Определение списков...............................................................................................48
3.8.1.3 Вычисления в списках .............................................................................................50
3.8.1.4 Печать списков.........................................................................................................50
3.8.1.5 Изменение данных в списках...................................................................................51
3.8.1.6 Поиск всех решений для цели сразу........................................................................52
3
Стр.3
3.8.1.7 Принадлежность к списку........................................................................................53
3.8.1.8 Объединение списков ..............................................................................................53
3.8.2 Деревья ........................................................................................................................55
3.8.2.1 Обход дерева ............................................................................................................55
3.8.2.2 Создание дерева .......................................................................................................56
3.8.2.3 Бинарные поисковые деревья. .................................................................................57
3.9 Внутренняя база фактов Пролога......................................................................................58
3.10 Функции и возвращаемые значения................................................................................59
3.11 Предикаты обработки строк в Прологе..........................................................................60
3.12 Управление детерминизмом в Прологе. .........................................................................61
СПИСОК ЛИТЕРАТУРЫ..........................................................................................................63
4
Стр.4
ПРЕДИСЛОВИЕ
Данное учебное пособие предназначено студентам, постигающим основы
логического программирования, при изучении дисциплины элективного
модульного блока «Системы искусственного интеллекта». На его страницах
проводится
систематизация знаний по математической логике и
иллюстрируется приложение теории формальных систем к системам
логического программирования.
В предложенных материалах подробно изложены основы
программирования на языке Пролог в среде Visual Prolog. Рассмотрены
процессы сопоставления и унификации, поиска с возвратом и управления
исполнением программ на уровне использования предиката отсечения и
неудачи. Исследуется возможность использования откатов и рекурсии (в том
числе и хвостовой). Изучаются возможности использования простых и
составных объектов данных (списков), арифметических выражений,
встроенных функций и предикатов.
Разобрано большое количество примеров, приводятся комментарии по их
использованию и тестированию. Примеры часто взаимосвязаны и дополняют
друг друга.
Пособие может быть использовано студентами вузов и преподавателями,
осуществляющими теоретическую и практическую подготовку по указанному
направлению в рамках элективных курсов и кружковой работы.
5
Стр.5
МАТЕМАТИЧЕСКИЕ ОСНОВЫ ЛОГИЧЕСКОГО
ПРОГРАММИРОВАНИЯ
1.1 Схема построения формальной системы
Общая схема построения любой формальной системы Т такова:
1) Язык системы Т:
определяется алфавит – перечень элементарных символов системы;
определяются правила построения формул (синтаксис) – формула считается
правильно построенной тогда и только тогда, когда она построена в
соответствии с этими правилами;
2) Аксиомы системы Т:
выделяется конечное или перечислимое (определяемое с помощью
некоторого алгоритма перечислений) множество формул, которое
называется аксиомами системы.
3) Правила вывода системы Т:
Фиксируется обычно конечное множество предикатов Ri (i>0) на множестве
всех формул. Если для формул F1,…Fn+1 утверждение Ri (F1,…Fn+1)
истинно, то говорят, что формула Fn+1 непосредственно выводима из формул
F1,…Fn по правилу Ri.
Задание языка, аксиом и правил вывода исчерпывает задание
формальной системы как точного математического объекта.
Выводом в формальной системе Т называется любая конечная
последовательность формул системы Т, в которой каждая формула является
либо аксиомой системы Т, либо непосредственно следует из каких-либо
предшествующих ей в этом выводе формул по одному из правил вывода Ri
системы Т.
Формула системы Т называется теоремой этой системы, если существует
вывод в формальной системе Т, заканчивающийся этой формулой.
1.2 Логика и исчисление высказываний
Рассмотрим три высказывания на естественном языке:
«Стрекоза является насекомым» - фактическая истина;
«Любой город обладает населением в несколько тысяч человек» -
истина языка;
«Если из того, что четырехугольник является квадратом,
следует, что все его углы и стороны равны между собой, то из того,
что не все углы и стороны четырехугольника равны между собой,
следует, что четырехугольник не является квадратом» - истинность
данного высказывания определяется по смыслу слов. Само же высказывание
содержит в себе высказывания и логические связки «если… то…», «не …».
Причем, если высказывания заменить переменными X и Y, то предложение
«если из X следует Y, то из не Y следует не X» будет логически истинным
независимо от смысла X и Y.
6
Стр.6