конспект лекцій для студентів
спеціальностей № 8.080403, 8.091501
ІОТ факультету
всіх форм навчання
Логічне програмування. Конспект лекцій для студентів спеціальностей № 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 році Р.Ковальський на конгресі зробив доклад присвячений логічному програмуванню. Доклад викликав велику цікавість до логічного програмування і сприяв бурному розвитку напряму.
1.2. СУЧАСНИЙ СТАН ЛОГІЧНОГО ПРОГРАМУВАННЯ
Теоретичний напрям „Логічне програмування”, працює на стику двох дисциплін: математичної логіки і теоретичного програмування.
Логічне програмування займається наступними питаннями:
Ø шукає нові методи опису задачі;
Ø шукає нові методи формального логічного висновку.
Мови, що побудовані на ідеях логічного програмування, відносять до декларативних мов. На декларативній мові описують завдання, а не визначають алгоритм.
Розвиток напряму „Логічне програмування” породив нову парадигму програмування „Логічне програмування”.
Взагалі парадигма програмування визначає спосіб мислення і програмування, що не пов’язаний з конкретною мовою програмування.
Парадигма програмування характеризується: засобами опису даних, методами і ефективністю цих методів до розв’язку певних класів задач.
Парадигма „Логічного програмування” така: Задача описується твердженнями на основі предикатів. Розв’язок задачі знаходиться за допомогою логічного виводу.
Методи „Логічного програмування” дозволяють розв’язувати задачі, які вимагають динамічного формування алгоритму розв’язку задачі під час роботи системи. Засоби опису даних дозволяють просто описувати знання предметної області у вигляді тверджень або будувати реляційні бази даних.
Мови логічного програмування традиційно застосовують для створення інтелектуальних систем: експертних систем, систем аналізу та прийняття рішень, систем машинних перекладів, програм розуміння текстів природної мови, навчаючих систем, тощо.
Однак „Логічне програмування” ефективно не тільки при розробці інтелектуальних систем.
Мови, що побудовані на ідеях логічного програмування, мають потужні механізми пошуку та перебору даних з механізмами відкату у випадку невдачі.
Такі механізми дозволяють просто і компактно розв’язувати класи задач, що працюють з великою кількістю даних і вимагають швидкого пошуку та перебору даних за багатьма ключами. Причому ключі для відбору можна динамічно змінювати, залишаючи програму без змін.
Мови логічного програмування дозволяють просто реалізовувати роботу зі структурами: списками, деревами, структурами будь якої складності, що визначає користувач.
2. ОПИС ЗАДАЧІ НА ПРОЛОЗІ. ФАКТИ І ПРАВИЛА
2.1. ОПИС ЗАДАЧІ НА ПРОЛОЗІ
Пролог - декларативна мова. Програма на Пролозі описує задачу у вигляді тверджень на основі предикатів. Для більшості діалектів Прологу опис задачі використовується Пролог-машиною для розв’язку задачі за допомогою логічного виводу. Пролог-машиною називають виконуючу систему оболонки конкретної реалізації мови Пролог. Мова Visual-Prolog відрізняється від інших діалектів Прологу тим, що компілятор компілює опис задачі безпосередньо у машинний код, який реалізує логічний вивід.
Опис задачі на мові Пролог аналогічний опису задачі на природній мові. Такий опис складається з трьох типів тверджень: завжди істинні твердження; твердження істинність якого треба довести; твердження, які істинні при істинності умов. Для утворення тверджень програміст використовує дані задачі, або знання які відомі йому про об’єкти предметної області поза задачею.
Розглянемо задачу1: Відомо, що в родині, Дмитро батько Володимира, і Дмитро батько Олександра. Визначити, хто в родині брати.
Для формування тверджень виявляють в задачі об’єкти і відношення між об’єктами. Об’єкти задачі: Дмитро, Володимир, Олександр. Відношення між об’єктами задачі – батько, брати. Твердження формуються на основі відношень. Відношення між об’єктами можуть бути істинними. Існують також відношення між об’єктами, істинність яких невідома і її треба визначити.
Завжди істинні твердження формуються з істинних відношень. Їх одержують з того, що відомо в задачі.
Сформуємо істинні твердження:
Ø Дмитро батько Володимира (1 );
Ø Дмитро батько Олександра (2 ).
Сформуємо твердження, яке описує що треба знайти в задачі: Визначити X та Y, які є братами. Воно формулюється на основі відношення брати для об’єктів X та Y. Щоб знайти об’єкти предметної області, які є братами сформуємо умовне твердження разом з умовами, при яких умовне твердження істинне.
Для формування твердження істинного при істинності умов скористаємося знаннями про родинні стосунки. Невідомі об’єкти будемо позначати змінними. Відомо, що: X та Y будуть братами, якщо в них спільний батько Z.
Твердження істинне при істинності умов формується з відношення брати між X та Y. А умови, при яких умовне твердження буде істинним формуються з відношення батько для об’єктів X і Z та об’єктів Y і Z.
Кожний з розглянутих типів тверджень характеризується істинністю. Тому твердження на мові Пролог зручно записувати в предикатній формі.
Предикат – це логічна функція, що визначена на будь-якій предметній області, і яка приймає одне з двох значень: істина чи неправда.
Кожний тип твердження має свою форму запису(синтаксис). За синтаксисом компілятор Прологу визначає тип твердження.
