- •1. Вступ в логічне програмування
- •1.1. Виникнення логічного програмування
- •1.2. Сучасний стан логічного програмування
- •Опис задачі на пролозі. Факти і правила
- •2.1. Опис задачі на пролозі
- •2.2. Факти
- •Цільове твердження
- •Умовні твердження
- •Приклад програми на пролозі
- •2.6. Виконання програми на пролозі
- •2.7. Статична та динамічна бази даних
- •2.8. Підготовка фактів для внутрішньої бази даних
- •2.9. Опис фактів внутрішньої бази даних
- •2.10. Предикати роботи з внутрішньою базою даних
- •2.11. Приклади використання внутрішньої бази даних
- •3. Основні поняття visual-prolog
- •3.1. Загальні відомості
- •3.3. Домени елементарних об’єктів
- •3.4. Терми
- •3.4.1. Константа
- •Анонімна змінна
- •3.4.3. Структури
- •3.5. Програма на пролозі
- •4. Механізми прологу
- •Механізм узгодження цілі з базою даних
- •4.2. Механізм звороту
- •4.3. Механізм звороту і відсік
- •4.4. Рекурсія
- •4.4.1. Рекурсивний метод розв’язку задач
- •Рекурсивні методи 2-х доменів:
- •Застосуємо висхідний метод рекурсії до розв’язку задачі:
- •Висхідна рекурсія
- •4.4.4. Предикат repeат
- •Міркування про те, як треба писати програму
- •5. Обробка рядків
- •5.1. Загальні відомості
- •1.1 Стандартні предикати обробки рядків
- •5.3. Лексиграфічне порівняння рядків
- •2Низхідна рекурсія
- •6.1. Метод низхідної рекурсії
- •6.2. Загальна характеристика рекурсивних методів
- •6.3. Низхідна та висхідна рекурсії
- •7. Робота зі списками
- •7.1. Списки. Оголошення списків
- •7.2. Увід-вивід списків
- •7.3. Основна операція на списках
- •7.4. Формування списків стандартним предикатом
- •Процедура з’єднує два списки.
- •Процедура розділяє список на два за вказаним елементом.
- •2.1 Сортування списків на пролозі
- •Сортування методом пухирця
- •7.8. Складені списки
- •8. Предикати вводу-вивіду
- •8.1. Предикати вводу
- •8.2. Предикати виводу
- •9. Файли
- •9.1. Символічне ім’я файлу
- •9.2. Вхідний і вихідний потоки
- •9.3. Організація файлу та методи доступу до файлу
- •9.4. Робота з файлами різними методами доступу
- •9.5. Закриття файлу
- •9.6. Предикати роботи з каталогами
- •9.7. Предикати, що працюють з атрибутами файлів
- •Література
МІНІСТЕРСТВО ОСВІТИ І НАУКИ УКРАЇНИ
Запорізький національний технічний університет
ЛОГІЧНЕ ПРОГРАМУВАННЯ
Visual Prolog
конспект лекцій для студентів
спеціальностей № 8.080403, 8.091501
ІОТ факультету
всіх форм навчання
2004
Логічне програмування. Конспект лекцій для студентів спеціальностей № 8.080403, 8.091501 ІОТ факультету всіх форм навчання. / Укл.: І.В.Левада. - Запоріжжя: ЗНТУ, 2004. - 58с.
Укладач: І.В.Левада, старший викладач
Рецензенти: доцент, к.т.н. С.М. Сердюк
Відповідальний за випуск: А.В.Притула, доцент, к.т.н.
Затверджено
на засіданні кафедри
„Програмних засобів”
Протокол № 2
Від 15.05.2004
Рекомендовано до видання навчально-методичною комісією факультету „Інформатики та обчислювальної техніки” як конспект лекцій по дисципліні „Логічне програмування”.
Протокол №2 від 15.05.2004
Лекції містять відомості з історії виникнення логічного програмування, його ідеї. В лекціях розглянуті основні поняття мови Пролог, однієї з програмних реалізацій ідей логічного програмування, механізми мови Пролог і методи розробки програм на Visual Prolog. Матеріал лекцій ілюструється багатьма прикладами програм, що утворені засобами Visual – Prolog версія 5.2.
1. Вступ в логічне програмування
1.1. Виникнення логічного програмування
У ХІХ столітті німецький математик Фреге поставив перед собою мету проаналізувати формальну структуру чистого мислення. Фреге розробив універсальну систему позначень понять, використовуючи яку, можна було записувати у формалізованому виді думки. Він вважав, що подавання логічно вірних висловлювань у формалізованому вигляді, можна було б використовувати при дедуктивних міркуваннях. Проте формалізацією дедуктивних міркувань сам Фреге не займався. А можливість такого використання універсальної системи позначень приймав на віру.
Норвезький математик Скулен і австрійський математик Курт Гедель довели, що система універсальних позначень понять Фреге повна, і її можна використовувати для запису в формалізованому виді логічно вірних висловлювань.
Розвиток ідей Фреге привів до виникнення такої гілки математичної логіки, як „Обчислювальне числення предикатів”, яка займається пошуком алгоритмів формального логічного висновку. Формалізувати логічний висновок – це значить, забезпечити доказ істинності твердження поза змістом цього твердження. Тобто, використовувати один алгоритм для доказу істинності будь-яких тверджень певного класу.
В 1930 році Математик Жак Ербран придумав декілька версій алгоритму формального логічного висновку. В цих алгоритмах була використане поняття уніфікації(ототожнення тверджень). Уніфікація вказує правила, за якими два твердження можуть бути ототожнені. За допомогою уніфікації стало можливо пов’язувати декілька логічних ланцюгів висловлювань в один.
У 1955 році вперше були зроблені спроби запрограмувати алгоритм формального логічного висновку Жака Ербрана. Проте, алгоритм не підходив для обчислення на комп’ютері. При реалізації алгоритму початкова ціль породжувала декілька нових цілей. Нові цілі породжували знову декілька цілей. Продовжуючись, процес утворював таку кількість цілей, що комп’ютер не міг їх обробити. Тобто, при спробах використання цього алгоритму виникав комбінаторний вибух. Див. Рис.1.
РИС.1
У 1961 році Робінсон придумав, яким чином включити в алгоритм формального логічного виводу процедуру уніфікації, щоб обійти комбінаторний вибух при розв’язку малих задач. Цей метод одержав назву метод резолюції. Наприкінці 60 – років, Корделл Грін з Стенфорду спробував використовувати метод резолюції сучасним способом, як основу системи логічного програмування. Достоїнством системи був загальний план розробки діалогової системи. Недоліком було те, що він не працював на великих задачах. Для великих задач він був складним. У 60-і роки метод резолюційного програмування отримав широке поширення.
Для застосування методу резолюції було розроблено
В середині 60-х років Фостер і Елкок була створена мова для обчислення, на якій програміст міг записувати у формалізованому вигляді істинні твердження – аксіоми. Використовуючи введені аксіоми, виконуюча система робила вивід про істинність питання поставленого до неї.
Система Фостера і Елкоку була прообразом того, чим займається сучасне логічне програмування. Однак автори не використали в системі мову „Числення предикатів”, вони використовували звичайні математичні позначення.
На початку 70-х років Масачусетський технологічний інститут прийшов до висновку, що займатися доказом істинності тверджень на основі математичної логіки нерозумно. Спеціалісти Масачусетського технологічного інституту, використавши інший підхід, розробили мову програмування Пленер.
У Польщі Р.Ковальський продовжував займатися цим питанням на основі логіки і активно агітував за цій підхід. Надалі був придуманий метод лінійної резолюції, який удосконалював метод резолюції. Метод лінійної резолюції цілком усунув проблему комбінаторного вибуху. Ковальський запропонував інтерпретувати процес доведення істинності твердження в процес обчислення, де кожний шаг це виклик процедури, яка повертає обчисленні значення.
Починаючи з цього моменту були створені усі компоненти для виникнення Прологу – мови програмування з використанням логіки:
Загальний план розробки діалогової системи на основі логіки, який інтерпретувався як процес обчислення;
Запис висловлювань, що описують задачу, у вигляді хорновських диз’юнктів;
Алгоритм формального логічного висновку на основі методу лінійної резолюції.
У 1971 році в Марселі дослідник Алан Колмероу створив мову програмування Пролог. Назва мови означає – програмування в термінах логіки.
Одночасно, з народженням мови програмування Пролог, народився новий теоретичний напрям „Логічне програмування”.
У 1974 році Р.Ковальський на конгресі зробив доклад присвячений логічному програмуванню. Доклад викликав велику цікавість до логічного програмування і сприяв бурному розвитку напряму.