С.А.Cавушкин
РЕКУРСИВНО-ЛОГИЧЕСКОЕ
ПРОГРАММИРОВАНИЕ
Учебное пособие для студентов специальностей
«Программное обеспечение вычислительной техники и
Автоматизированных систем» и «Математическое
Обеспечение и администрирование автоматизированных
Систем»
Москва – 2009
МОСКОВСКИЙ ГОСУДАРСТВЕННЫЙ
УНИВЕРСИТЕТ ПУТЕЙ СООБЩЕНИЯ (МИИТ)
Кафедра «Математическое обеспечение
Автоматизированных систем управления»
С.А.Cавушкин
РЕКУРСИВНО-ЛОГИЧЕСКОЕ
ПРОГРАММИРОВАНИЕ. ТЕОРИЯ И ПРАКТИКА.
Рекомендовано редакционно-издательским советом
университета в качестве учебного пособия для
студентов специальностей «Программное обеспечение
Вычислительной техники и автоматизированных
Систем» и «Математическое обеспечение и
Администрирование автоматизированных систем»
Москва – 2009
УДК 519.6, 519.852
Cавушкин С.А. Рекурсивно-логическое программирование. Теория и практика. Учебное пособие для студентов специальностей “Программное обеспечение вычислительной техники и автоматизированных систем” и “Математическое обеспечение и администрирование автоматизированных систем”. - М.: МИИТ, 2009 - 88 с.
В учебном пособии излагаются сведения по математической логике, которые лежат в основе языка ПРОЛОГ и логического программирования. Описаны синтаксис и семантика языка ПРОЛОГ. Семантика языка тесно увязана с методом резолюций для логики предикатов. Сформулированы варианты заданий и методические указания для выполнения лабораторных работ.
Рецензенты: зав. кафедрой ВСС МИИТа кандидат техн. наук, доцент В. Н. Нагинаев
© Московский государственный
университет путей сообщения
(МИИТ), 2009
Подписано к печати – Изд №??-09 Формат – 60х84/16
Усл.-п. л. – 5,5 Заказ № Тираж – ??? экз
127994, Москва, ул. Образцова, 15
Типография МИИТа
СОДЕРЖАНИЕ
1. Парадигмы программирования. 5
2. Теоретические основы логическоого программирования. 7
2.1. Логика высказываний и логика предикатов. 7
2.1.1. Формулы. Синтаксис и семантика формул. 7
2.1.2. Интерпретация формул в логике высказываний. 11
2.1.3. Интерпретация в логике предикатов первого порядка. 12
2.1.4. Равносильность формул логики высказываний. 16
2.1.5. Тождественная истинность формул логики высказываний. 18
2.1.6. Равносильность формул логики первого порядка. 19
2.1.7. Тождественная истинность, общезначимость, выполнимость, противоречивость формул логики предикатов 21
2.1.8. Рассуждения в логике высказываний (предикатов) 21
2.2. Метод резолюций 23
2.2.1. Метод резолюций в логике высказываний. 23
2.2.2. Подстановка и унификация. 25
2.2.3. Метод резолюций для логики первого порядка. 29
2.2.4. Стратегии метода резолюций. 34
2.3. Отношения и предикаты. 39
3. ПРОЛОГ- ЯЗЫК РекуРсивно-ЛОГИЧЕСКОГО ПРОГРАММИРОВАНИЯ. 40
3.1. ПРОЛОГ-история возникновения 40
3.2. Синтаксис языка ПРОЛОГ. 40
3.3. Семантика языка ПРОЛОГ. 42
3.4. Язык ПРОЛОГ и метод резолюций. Логическая интерпретация языка Пролог. 48
3.5. Работа в пролог-системе 49
3.6. Описание инфиксных операций 50
3.7. Списки в языке ПРОЛОГ. 51
3.8. Арифметика в языке ПРОЛОГ. 57
3.9. Отсечение и отрицание в языке ПРОЛОГ. 59
3.10. Встроенные предикаты языка ПРОЛОГ. 61
3.11. Работа с базой данных в языке ПРОЛОГ. 64
3.12. Предикаты поиска 68
3.13. Решение головоломки на языке ПРОЛОГ(задача Эйнштейна) 69
4. ЛАБОРАТОРНЫЕ РАБОТЫ ПО РекуРсивно-ЛОГИЧЕСКОМУ ПРОГРАММИРОВАНИЮ 75
4.1. ЗАДАНИЕ N1 Отношения между объектами. (на Прологе и Паскале) 75
4.1.1. Методические указания. 75
4.1.2. Варианты. 76
4.2. ЗАДАНИЕ N2. Работа со списками 80
4.2.1. Методические указания. 80
4.2.2. Варианты. 81
4.3. ЗАДАНИЕ N3. Разные задачи 84
4.3.1. Методические указания. 84
4.3.2. Варианты. 85
4.4. Содержание отчета 88
ЛИТЕРАТУРА. 90
Парадигмы программирования
Парадигма (от греч. παράδειγμα, «пример, модель, образец») — осмысление мира на основе идей, взглядов и понятий. Современное значение этого термина в философии науки используется для обозначения исходной концептуальной схемы, модели постановки проблем и их решения, методов исследования.
Под парадигмой программирования будем понимать систему взгляд, подходов, позиций, определяющую стиль программирования на концептуальном уровне. Парадигма программирования представляет (и определяет) то, как программист видит процесс выполнения программы и, в конечном счете, саму программу.
В литературе формулируется большое число парадигм программирования. Мы выделим следующие:
Императивное программирование — процесс вычисления описывается в виде последовательности команд, изменяющих состояние вычислительной среды. Этот стиль программирования является традиционным и связывается с именем фон Неймана, который разработал основные архитектурно-функциональные принципы построения вычислительных машин (программного управления выполнением программы, хранимой в памяти программы, счетчик команд), которые легли в основу понятия фон-Неймановской архитектуры вычислительных устройств и фон-Неймановского стиля программирования.
Процедурное программирование — часто используется как синоним императивного программирования. При этом команды реализуются вызовами процедур.
Объектно-ориентированное программирование — программа – это набор взаимодействующих объектов. Каждый объект обладает набором свойств, а также набором методов - программ, которые связывают значения свойств объекта и различных объектов друг с другом.
Функциональное программирование — программа представляется в виде композиции и суперпозиции функций. Программы не представляют собой последовательности инструкций и не имеют глобального состояния.
Логическое программирование — программа обычно определяет, что надо вычислить, а не то, как это надо делать. Выполнение программы основано на выводе новых утверждений из набора исходных утверждений, согласно заданным логическим правилам вывода.
Структурное программирование — в настоящее время общепринятая методология, в основе которой лежит представление программы в виде иерархии структур управления (последовательное исполнение операций, ветвление в зависимости от выполнения некоторого заданного условия, цикл, вызов подпрограмм). Разработка программы ведётся пошагово, методом «сверху вниз». Исторически возникло из традиционного императивного программирования путем ограничения применения «неструктурных» операторов, таких как оператор GOTO (безусловного перехода). Использование произвольных переходов в тексте программы приводило к получению запутанных, программ, по тексту которых практически невозможно понять порядок исполнения и взаимозависимость фрагментов.
Программа, управляемая данными — программа представляется в виде графа с вершинами двух видов – процедуры и данные. Данные могут быть входами и выходами процедур. Программа запускается посредством запроса вида «ДАНО-НАЙТИ».
Из выбранных парадигм нас интересуют императивное программирование и его разновидности, как представляющие традиционный стиль программирования, а также логическое программирование, которое является темой данного пособия. Остальные парадигмы приведены в качестве примеров.
Дата: 2016-10-02, просмотров: 188.
