Студопедия — Глава 6
Студопедия Главная Случайная страница Обратная связь

Разделы: Автомобили Астрономия Биология География Дом и сад Другие языки Другое Информатика История Культура Литература Логика Математика Медицина Металлургия Механика Образование Охрана труда Педагогика Политика Право Психология Религия Риторика Социология Спорт Строительство Технология Туризм Физика Философия Финансы Химия Черчение Экология Экономика Электроника

Глава 6






Мова логічного програмування Prolog

Prolog – це найбільш відома мова логічного програмування, яка використовується для вирішення задач, в яких діють об’єкти та відношення між цими об’єктами. Програмування на мові Prolog відноситься до декларативного стилю програмування і має спільні властивості з функціональним програмуванням [3].

Теоретичною основою логічного програмування є логіка предикатів – один з розділів алгебри логіки. Логіка предикатів займається дослідженням відношень між об’єктами та доказами їхнього існування [4]. Такі відношення називаються предикатами і записуються у вигляді

P(t1, t2, t3, …, tn),

де: P – позначення предикату

t1, t2, t3, …, tn – об’єкти чи терми.

Предикати можна об’єднати за допомогою логічних операцій у формули, які складають фрази (висловлювання). Фраза, що містить тільки один позитивний літерал (логічна формула), називається фразою Хорна і має вигляд:

С Ú ˜E Ú ˜F Ú ˜G (5.1)

Фраза 5.1 означає, що С істина тоді і тільки тоді, коли E, F і G одностайно істинні. Звичайно, 5.1 можна переписати у вигляді імплікації зі зворотною стрілкою:

C E, F, G (5.2)

Така фраза є основою побудови висловлювань програми на логічної мові програмування Prolog.

Склад та структура програми

Програма на мові Prolog складається з висловлювань трьох типів: факти, правила та питання. Твердження складається з двох частин: ліва частина – висновок, права частина – умова, які розділяються знаком «:-» (двокрапка і дефіс) [1, 4].

Факт – це твердження, що є безумовною істиною, який складається з висновку за яким не виходить ніяких умов, наприклад:

лікар (василь).

Це можна прочитати так:

Василь - лікар*).

Сукупність фактів складають деякий світ, у межах якого дійсні твердження програми.

На прикладі родинних відносин (рис. 5.1) введемо відношення батьки (parent) між двома об’єктами X і Y, яке встановлює той факт, що X є батьком чи мати для Y:

parent (X, Y).

Рисунок 5.1 – Схема родинних відношень

Тоді родинні зв’язки, які зображені на рис. 5.1, запишемо у вигляді списку фактів:

parent (тетяна, ігор).
parent (ігор, сергій).
parent (ігор, ліза).
parent (сергій, ганна).
parent (сергій, петро).
parent (марина, ганна).
parent (петро, юлія).

При написанні фактів потрібно дотримуватись наступних правил:

- імена всіх відносин та об’єктів з маленької літери;

- спочатку записується ім’я відносин, потім в круглих дужках через кому об’єкти;

- в кінці ставиться крапка.

Після написання будь-якої програми та їй завантаження середовище Prolog може відповісти на запитання.

Запитання – це твердження, що містить лише умову без висновку. Запитання складається з одній або декількома цілей [2]. Якщо всі цілі досягненні, Prolog дає позитивну відповідь – Так (Yes), у протилежному випадку – негативну відповідь Ні (No). Якщо у параметрах предикатів існують зміни, тоді, при позитивній відповіді, зміни конкретизуються, тобто приймають конкретне значення (див. нижче). В таблиці 5.2 наведені приклади запитань у контексті вищевказаної програми родинних відношень.

Таблиця 5.2 – Приклади запитань
Запитання Відповідь
? parent(сергій, ганна). Yes
? parent(сергій, ліза). No
? parent (сергій,X). X = ганна; X = петро;
? parent (X, ліза). X = сергій

 

Правила - це залежні відношення і дозволяють Prolog робити виведення, порівнюючи одну частину інформації з іншою [1, 2].

Правила Prolog складаються з обох частин твердження: висновку та умови. Іноді висновок називають головою, умови – тілом правила.

Голова - це факт, який буде вірним, якщо деяка кількість умов виконається. Тіло - це множина умов, котрі повинні бути істинними, щоб Prolog міг довести, що голова правила вірна [2].

Наприклад, введемо відношення child "дитина", зворотне до parent "батьки" і запишемо у вигляді правила:

child(Y, X):-parent (X, Y).

Правило читається так: для всіх X та Y, Y дитиною X, якщо X – батько (мати) Y.

Правило доповнює базу даних програми новою сутністю child. Зараз можна запитати:

?-child(ліза, ігор).

В базі даних програмі немає фактів child,але є правило, яке залежить від існуючих фактів parent. У даному випадку Prolog підставляє умовну частину правила замість запитання:

parent (ігор, ліза),

після чого ініціює процедуру пошуку в базі даних.

Основи мови Prolog

Програма на мові Prolog складається з речень. Речення бувають трьох видів: факти, правила, запитання. Всі речення складаються з термів [1, 2, 3].

Терм – це або константа, або змінна, або вживання функції. Вживання функції записується як символьне позначення функції за яким в дужках знаходиться список аргументів. Кожен аргумент теж є термом.

f (t1, t2, …, tn),

де: f - позначення функції; t1, t2, …, tn - терми.

Терм записується як послідовність літер. Літери поділяються на чотири категорії: прописні букви, строкові букви, цифри, спеціальні символи такі як: + – * / \ < > ^:. ˜ &? _ @ # $.

Константами є поіменні конкретні об’єкти або конкретні відношення. Існує два види констант: атоми та числа.

Атомом називаєтьсяконкретний об’єкт, який починається з малой літери. Якщо атом береться в одиночні лапки, то його ім’я може складатися з будь-яких літер. Наприклад:

liz

—>

=====>

міс_Джонс

міс_джонс

key5689

’микола’

’Джордж-сміт’

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

Змінні складаються з літер, цифр та символів підкреслення та починаються з прописної літери або символу підкреслення. Наприклад:

А

Висновок

_33

Структура – це єдиний іменований об’єкт, який складається з сукупності інших об’єктів, які називаються параметрами. Параметри записуються в дужках через кому після імені структури. Наприклад, представимо структуру дата, яка складається з трьох параметрів: день, місяць, рік:

дата(22, травня, 2000)

Ім’я структури називається функтором, кількість параметрів – арністю. Prolog дозволяє застосування структур з однаковим функтором і різною арністю.

Відповідь на запитання і пошук рішень

Відповідь на запитання здійснюється на основі фактів і правил, з яких складається програма. Необхідно звернути увагу на те, що повнота відповіді залежить від повноти складу бази даних програми (фактів), що описують «світ» програми [4].

Основний механізм, на якому базується пошук рішень, є співставлення термів, і називається уніфікацією.

Уніфікація може бути успішною або ні. Якщо уніфікація успішна, тоді ціль досягнуто. Успіх уніфікації залежить від складу термів, які співставленні. Крім того, якщо терм є зміною або у складі терму входить зміна, в результаті уніфікації зміна може бути конкретизована (отримати значення), якщо уніфікація успішна. Prolog керується наступними правилами [3, 4]:

1) Якщо уніфікуються дві константи, тоді уніфікація є успішною, якщо обидві константи однакові.

2) Якщо уніфікуються зміна з константою або структурою, уніфікація є успішною, а зміна конкретизується значенням константи або структури.

3) Якщо уніфікуються дві вільні зміни, у подальшому вони сприймаються як одна, тобто, якщо одна із змін конкретизується, друга зміна теж конкретизується тим же значенням.

4) Якщо уніфікуються дві структури, тоді уніфікація є успішною, якщо функтори і арність структур однакові, а відповідні параметри структур уніфікуються за вищевказаними правилами.

5) Уніфікація завжди успішна, якщо терм зіставляється з анонімною зміною (підкреслення).

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

Методичні вказівки

Етапи виконання роботи

Виконання завдання складається з чотирьох етапів:

1) складання схеми зв’язків між об’єктами;

2) формулювання і запис правила з використанням квантору загальності [4];

3) запис правила на мові Prolog;

4) формулювання запитань та отримання відповідей у середовищі Prolog.

При виконанні другого етапу достатньо звертати увагу лише на декларативний сенс правила. У відмінності від цього, на наступному етапі більш уваги слід звернути на процедурний сенс правила для підвищення ефективності пошуку рішень.

Приклад виконання завдання

Задача: Скласти правило для визначення предикату «донька» на основі фактів. жінка (ім’я), батьки (ім’я_батька, ім’я_дитини).

Рішення: Предикат «донька» позначимо daughter(X, Y), де X – імя доньки, Y – імя одного з батьків (мамо або тато). Базу фактів можна скласти на основі схеми родинних відношень, яка представлена на рис. 5.1. Необхідно додати ще факти, які визначать жінок:

woman(тетяна).

woman(ліза).

woman(ганна).

woman(марина).

woman(юлія).

Предикат можна сформулювати наступним чином: для всіх X і Y, X є донькою Y, якщо X є жінкою, і Y є батьком X.

Тоді, правило на мові Prolog має вигляд:

daughter(X,Y):- woman(X), parent(Y,X).

Після цього можна поставити запитання (табл. 5.3)

Таблиця 5.3 – Приклади запитань
Запитання Пояснення Відповідь
? daughter(ганна,марина). Чи є Ганна донькою Марини? Yes
? daughter(ганна, X). Хто є батьком (мати або тато) Ганни? X = марина; X = сергій
? daughter(X,марина). Хто є донькою Марини? X = ганна
? daughter(_,ліза). Чи є у Лізи донька? No

Контрольні запитання

1) Визначення поняття предикату.

2) Визначення понять: факт, правило, запитання.

3) Основні визначення мови Prolog: терм, атом, константа, змінна, структура.

4) Правила уніфікації термів.

5) Поясніть, як Prolog-система дає відповідь на запитання.

Глава 6







Дата добавления: 2015-08-27; просмотров: 446. Нарушение авторских прав; Мы поможем в написании вашей работы!



Композиция из абстрактных геометрических фигур Данная композиция состоит из линий, штриховки, абстрактных геометрических форм...

Важнейшие способы обработки и анализа рядов динамики Не во всех случаях эмпирические данные рядов динамики позволяют определить тенденцию изменения явления во времени...

ТЕОРЕТИЧЕСКАЯ МЕХАНИКА Статика является частью теоретической механики, изучающей условия, при ко­торых тело находится под действием заданной системы сил...

Теория усилителей. Схема Основная масса современных аналоговых и аналого-цифровых электронных устройств выполняется на специализированных микросхемах...

Уравнение волны. Уравнение плоской гармонической волны. Волновое уравнение. Уравнение сферической волны Уравнением упругой волны называют функцию , которая определяет смещение любой частицы среды с координатами относительно своего положения равновесия в произвольный момент времени t...

Медицинская документация родильного дома Учетные формы родильного дома № 111/у Индивидуальная карта беременной и родильницы № 113/у Обменная карта родильного дома...

Основные разделы работы участкового врача-педиатра Ведущей фигурой в организации внебольничной помощи детям является участковый врач-педиатр детской городской поликлиники...

Философские школы эпохи эллинизма (неоплатонизм, эпикуреизм, стоицизм, скептицизм). Эпоха эллинизма со времени походов Александра Македонского, в результате которых была образована гигантская империя от Индии на востоке до Греции и Македонии на западе...

Демографияда "Демографиялық жарылыс" дегеніміз не? Демография (грекше демос — халық) — халықтың құрылымын...

Субъективные признаки контрабанды огнестрельного оружия или его основных частей   Переходя к рассмотрению субъективной стороны контрабанды, остановимся на теоретическом понятии субъективной стороны состава преступления...

Studopedia.info - Студопедия - 2014-2024 год . (0.01 сек.) русская версия | украинская версия