Введення в мову Пролог

А.1. Мова програмування ПРОЛОГ і її особливості.

Пролог є якісно новою мовою програмування. Завдяки можливості обробляти міркування людини, її можна назвати засобом розробки систем штучного інтелекта. Тим не менше Пролог - це мова програмування загального призначення. Вона застосовується в багатьох додатках, включаючи експертні системи, інтерпретатори, компілятори.

Пролог суттєво відрізняється від інших мов програмування. Творці Прологу опиралися на декларативну точку зору на програмування на відміну від традиційних мов (такі як Фортран, Кобол, Сі або Бейсік), які є процедурно-орієнтованими або алгоритмічними й для них основним методом програмування є розбивка завдання на дискретні кроки і їхній послідовний опис у вигляді машинних команд. Виконання програм на таких мовах незворотне, тому що пам’ять постійно обновляється.

Декларативність Прологу дозволяє розуміти програму, не відслідковуючи динаміку її виконання. Пролог-програма – це набір фактів і правил. Рішення програми виходять у процесі зв’язування цих правил і фактів. Не потрібно писати докладних вказівок для керування висновком. Замість цього визначаються можливі рішення завдання на основі фактів і правил, які дозволяють програмі вибирати правильні рішення.

Оскільки мова Пролог заснована на універсальних формалізмах логічних виразів, вихідний текст Пролог-програм значно менше залежить від машинних особливостей, чим вихідні тексти, що написані на інших мовах.

Пролог заснований на розв’язанні предикатів - одному з розділів символьної логіки. Однак програмування на Пролозі відрізняється від логічного програмування насамперед точним, а не абстрактним, операційним значенням програм. Крім того, Пролог містить і деякі нелогічні засоби, що ріднять його із традиційними мовами.

Основний алгоритмічний метод Прологу - рекурсія. З її допомогою досягається такий же ефект, який реалізується при вживанні ітеративних керуючих конструкцій (наприклад, циклу "поки") у процедурних мовах.

Кожна мова програмування будь-якого типу характеризується властивими йому механізмами керування й обробки даних.

Пролог має наступний набір механізмів:

- механізм висновку з пошуком і поверненням;

- вбудований механізм зіставлення зі зразком;

- зручне й гнучке деревоподібне подання структури даних з можливістю її зміни.

А.2. ПРОЛОГ як обчислювальний формалізм.

Для подання знань розроблений ряд обчислювальних формалізмів. Кожний обчислювальний формалізм складається із двох частин:

1) дескриптивної (описової) мови;

2) множини процедур, здатних реалізувати формальний зміст опису, складеного дескриптивною мовою, або, інакше кажучи, обробляючої структури формалізму.

Найпоширеніші обчислювальні формалізми - мережі, фрейми, правила продукцій і об’єктно-орієнтоване програмування, кожний з яких визначається своєю концепцією й орієнтований на певний вид знань. Останнє є їхнім основним недоліком, тому що можуть існувати знання, що не піддаються опису за допомогою звичного формалізму. Цього недоліку позбавлене подання знань мовою логіки предикатів (предикат - це вираз, результатом якого є «істина» або «неправда») за рахунок мінімуму концептуальних обмежень. Вони можуть бути виражені у вигляді двох пропозицій:

1) існують сутності;

2) існують відносини між сутностями.

Основні концепції традиційних обчислювальних формалізмів - ієрархія й спадкування - виражаються за допомогою логіки предикатів, і, отже, на мовах, що базуються на логіці предикатів.

При рішенні проблем штучного інтелекту привабливість Прологу зростає тому, що Пролог сам є обчислювальним формалізмом. Його дескриптивна мова - це логіка предикатів, а обробна структура - інтерпретатор, до якого доданий ряд вбудованих предикатів (в основному для здійснення арифметичних операцій) і процедур загального призначення (для спеціальної обробки БД). Тобто Пролог-програма представляє знання про систему адекватно аксіоматичній логіці предикатів. Завдяки цій властивості, Пролог зручний для створення експертних систем.

А.3. Фразова форма логіки предикатів. Фрази Хорна

Предикат - логічна функція одного або декількох аргументів. Всі логічні вирази, що використовуються, в класичному обчисленні предикатів мають значення “істина” або “неправда”. У логіці предикатів елементарним неподільним на компоненти об’єктом, що володіє значенням істинності, є атомарна формула.

Атомарна формула записується як позначення предиката, за яким у дужках розташовуються кілька аргументів. Кож ний аргумент - це терм. Загальний вид атомарної формули:

p(tl,t2,...,tn) (1)

р - позначення предиката; tl,...,tn - терми.

Терм - це або константа, або змінна, або вживання функції. Загальна формула вживання функції:

f(vl,v2,...,vk) (2)

f - позначення функції; vl,...,vk - терми.

Фразова форма логіки предикатів - це спосіб запису формул, при якому вживаються тільки з’єднувачі:

Ù (“і”), Ú (“або»), | (“не”).

Літерал - це позитивна або негативна атомарна формула. Кожна фраза - це безліч літералів, з’єднаних символом Ú.

Негативні літерали розміщуються наприкінці кожної фрази:

PlÚ P2Ú... Ú Pn Ú Nl Ú N2 Ú... Ú Nn (3)

Pi - позитивний літерал, Ni - негативний. Така форма запису фрази називається клаузальною.

Будь-яке зв’язування предикатів можна привести до клаузальной форми. Доказом тому служать наступні співвідношення:

F -> G = |F Ú G (4)

F - G = (F -> G) Ù (G -> F) (5)

-> - визначник імплікації (“з F треба G”);

- - визначник тотожності.

Фраза Хорна - це фраза, що містить тільки один позитивний літерал, наприклад:

C Ú |E Ú |F Ú |G (6)

Використовуючи зворотну стрілку імплікації, фразу можна переписати:

C <- Е Ù F Ù G (7)

(C імпліцюється E,F,G).

Пролог-Програма складається із фраз Хорна. Безпосередньо формула (7) позначає запис правила на Пролозі. Запис факту спрощений відсутністю конъюнктивного зв’язування умов і виглядає як атомарна формула (1).