Лабораторна робота 1 Основні поняття прологу. Знайомство із середовищем visual prolog. Структура програм visual prolog. Прості та складні цілі. Уніфікація і Бектрекінг

• Название: Лабораторна робота 1 Основні поняття прологу. Знайомство із середовищем visual prolog. Структура програм visual prolog. Прості та складні цілі. Уніфікація і Бектрекінг
• Дата: 04.06.2022
• Размер: 72.95 Kb.
• Имя файла: L1.docx
• Тип: Лабораторна робота; #569327

Міністерство освіти і науки України

Харківський національний університет радіоелектроніки

Кафедра штучного інтелекту

Дисципліна «Введення до штучного інтелекту»

Лабораторна робота №1

«Основні поняття прологу. Знайомство із середовищем visual prolog .

Структура програм visual prolog.

Прості та складні цілі. Уніфікація і Бектрекінг»

Виконав: ст. гр.

Прийняла: ст. викл. кафедри

Харків – 2021

1. Мета

Мета лабораторної роботи – знайомство з Visual Development Environment (VDE), її основними компонентами і можливостями, практичне освоєння основ мови Visual Prolog 7.5, розробка простих логічних програм, побудова бази даних засобами Visual Prolog, завдання простих та складних цілей, використання механізмів уніфікації і бектрекінгу для вирішення поставлених задач.

2. Завдання

Для заданого орієнтованого графу (рис. 1) визначити:

1. 
   усі вузли, доступні з заданого за один крок (привести всі варіанти);
   
2. 
   те ж за 2 кроки (вершину треба ввести з клавіатури);
   
3. 
   усі вузли, з яких можна потрапити в заданий за один крок (привести всі варіанти), те ж за два кроки (вершину треба ввести з клавіатури);
   
4. 
   чи є в базі фактів конкретний шлях із вузла "Х" в вузол "У" (відповідь: «так» чи «ні»);
   
5. 
   чи є вузли, з яких не виходять ребра, відповідь: "так", чи "ні".
   

Рисунок 1 – Орієнтовний граф

3. Хід виконання

3.1 Аналітичне рішення
Орієнтовний граф можна зазначити у базі фактів у вигляді фактів про вершини (apex(Name)) та ребра (way(From, To, Weight)).

1. 
   Для змінних From та Weight=1 перевіряємо, чи є From вершиною (apex(From)), та уніфікуємо факти ребр предикатом edge(From, To, Weight), для кожного унікованого предикату виводимо значення To, та повертаємось назад завдяки бектрекінгу.
   
2. 
   Алгоритм ідентичний попередньому завданню, але значення From беремо з консолі, Weight=2.
   
3. 
   Для змінних To та Weight перевіряємо, чи є To вершиною (apex(To)), та уніфікуємо факти ребр предикатом edge(From, To, Weight), для кожного унікованого предикату виводимо значення From, та повертаємось назад завдяки бектрекінгу.
   
4. 
   Для змінних From та To, якщо уніфікується edge(From, To, _), виводимо «так» і застосовуємо усічення для закінчення пошуку рішень, якщо усічення не втрапилось (нема уніфікованих предикатів) – виводимо «ні».
   
5. 
   Уніфікуємо apex(From), якщо уніфікується not(edge(From, _, _)), виводимо «так» і закінчуємо пошук усіченням, якщо усічення не втрапилось – виводимо «ні».
   

3.2 Лістинг програми
implement main

open core, console
class facts - apexes

apex : (node Apex).
class facts - ways

way : (node From, node To, weight Weight).
class predicates

validateNode : (node) determ.

printApexesFrom : (node, weight) procedure.

printApexesTo : (node, weight) procedure.

hasWay : (node, node) procedure.

hasApexWithNoWay : () procedure.
clauses

apex("a").

apex("b").

apex("c").

apex("d").

apex("e").

apex("f").

apex("g").
way("c", "d", 1).

way("a", "c", 1).

way("a", "e", 1).

way("c", "e", 1).

way("a", "f", 1).

way("a", "f", 2).

way("e", "f", 1).

way("b", "e", 1).

way("b", "f", 1).

way("b", "f", 2).
validateNode(Node) :-

apex(Node), !;

writef("\"%\" не вершина графа!", Node), nl, !, fail.
printApexesFrom(From, Weight) :-

validateNode(From),

writef("Вершины, в которые можно попасть из % за % шагов:", From, Weight), nl,

(

way(From, To, Weight),

writef(" %;", To), nl,

fail

);

write("Конец списка"), nl.
printApexesTo(To, Weight) :-

validateNode(To),

writef("Вершины, из которых можно попасть в % за % шагов:", To, Weight), nl,

(

way(From, To, Weight),

writef(" %;", From), nl,

fail

);

write("Конец списка"), nl.
hasWay(From, To) :-

writef("Существует ли путь из % в %: ", From, To),

(

way(From, To, _), !, write("да");

write("нет")

), nl.
hasApexWithNoWay() :-

write("Существует ли вершины, из которых не исходят ребра: "),

(

apex(From),

not(way(From, _, _)), !, write("да");

write("нет")

), nl.
run() :-

init(),

(

write("1. "),

printApexesFrom("a", 1)

),

(

write("2. Введите вершину From: "),

From = readLine(),

printApexesFrom(From, 2)

),

(

write("3. "),

printApexesTo("e", 1),

write("Введите вершину To: "),

To = readLine(),

printApexesTo(To, 2)

),

(

write("4. "),

hasWay("a", "d")

),

(

write("5. "),

hasApexWithNoWay()

),

(

write("Нажмите Enter чтобы продолжить..."),

_ = readChar()

),

succeed.
end implement main
goal

console::runUtf8(main::run).
4. Результат виконання програми

Рисунок 2 – Результат виконання програми
5. Висновки
Під час виконання лабораторної роботи була побудована база знань орієнтованого графу, були використані механізми уніфікації, бектрекінгу та усічення для вирішення практичних задач при розробці логічної програми на мові Visual Prolog 7.5.

6. Відповідь на контрольні питання
6.1 Голова та тіло правила
На мові Prolog правила мають наступний синтаксис:
rule(arg1, arg2) :- anotherRule(x, arg2).

rule(y, arg) :- is(y, arg).
Оператор :- відділяє голову та тіло правила. Голова правила визначає паттерн. Якщо виклик предикату задовольняє паттерну, то значення предикату задається відповідним тілом.
6.2 Замкнутість виведення в Пролозі
Єдиним механізмом машини логічного висновку Прологу є пошук з поверненням (англ. Backtracking). Пошук з поверненням - метод знаходження рішень цільового затвердження в логічній програмі. Цей метод дозволяє знайти всі рішення, або деяку частину з них, або навіть одне рішення.
6.3 Порядок виконання кожного правила у VIP
Пролог завжди починає пошук рішення з першого факту та / або правила, і зберігає знайдені рішення доти, поки не перегляне всі факти та правила до кінця.

Механізм логічного висновку Прологу бере умови з правила (тіла правила) і переглядає весь список відомих фактів і правил, намагаючись задовольнити умовам.

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

Якщо всі умови не можуть бути узгоджені з відомими фактами, то правило не виводить нічого.
6.4 Правильно побудована формула (ППФ).

1. 
   Атомарна формула є правильною.
   
2. 
   Якщо та – ППФ, то ППФ також будуть:
   

6.5 Зелені і червоні відсікання
Відсікання – механізм, який зупиняє перебір наступних правил та механізм відкату.

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

Червоне відсікання – відсікання, яке застосовується у зв’язку з тим, що сама логіка програми вимагає закінчити пошук альтернативних рішень.
6.7 Мета (або цільове твердження) логічної програми
Мета є точкою входу програми. Мета є правилом, зазначеним у секції GOAL. Мета є диз’юнктом Горну, і точкою виходу програми є її успішне виконання (succeed).
6.8 Чи має значення в Пролозі порядок запису фактів і правил
У мові Prolog нема значення порядок запису фактів та правил.
7. Словник
Декартовий добуток - множина, елементами якого є всілякі впорядковані пари елементів вихідних множин.

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

Закони ЛВ

1. 
   Комутативність
   

2. 
   Асоціативність
   

3. 
   Дистрибутивність
   

4. 
   Ідемпотентність
   

5. 
   Елімінація
   

6. 
   Інволюція заперечення
   

7. 
   Закон доповнення
   

8. 
   Тотожності з константами
   

9. 
   Закони де Моргану
   

Порядок виконання операцій

1. 
   Заперечення.
   
2. 
   Кон'юнкція.
   
3. 
   Диз'юнкція.
   
4. 
   Імплікація.
   
5. 
   Еквівалентність.
   

Закони ЛППП

1. 
   Закон заміни зв’язних змінних
   

2. 
   Комутативність кванторів
   

3. 
   Дистрибутивність кванторів
   

4. 
   Закон де Моргану
   

Алгоритм приведення до ПНФ (попереджання нормальна форма)

1. 
   Виключаємо еквівалентність та імплікацію.
   
2. 
   Застосовуємо закон інволюції заперечення та закони де Моргану.
   
3. 
   Якщо виникають колізії, замінюємо змінні.
   
4. 
   Застосовуючи закон дистрибутивності кванторів, виносимо квантори у початок формули.
   

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

Алгоритм переходу від ПНФ до ССФ (скулемовська стандартна форма)

Для кожного квантору існування у ПНФ:

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

Диз'юнкт Горна - диз'юнктивний одночлен з не більше ніж одним позитивним літералом.

Лексема

У якості лексем мови Visual Prolog виступають:

• 
  старші ключові слова: class domains inherits predicates clauses end interface properties constants facts monitor resolve constructors goal namespace supports delegate implement open
  
• 
  молодші ключові слова: align digits failure language q uot and div finally mod rem anyflow do foreach multi single as else from nondeterm then bitsize elseif guard or to catch erroneous if orelse try determ externally in procedure
  
• 
  знаки пунктуації: ; ! ,. # [] | () {}:: - ::
  
• 
  оператори: + - / * ^ = div mod quot rem <> <>> <<=> =: = ==
  

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

Усі ключові слова, крім as і language, зарезервовані, і використовувати їх у якості імен не допускається. Ключове слово end завжди комбінується з іншими ключовими словами.

Багато-символьні знаки пунктуації не повинні розділятися пробілами.

Оператори

Операції визначають обчислення, які повинні бути виконані над зазначеними даними. У мові Prolog існують наступні оператори: + - / * ^ = div mod quot rem <> <>> <<=> =: = ==

Усі оператори мови Prolog бінарні, але існують унарні плюс та мінус.

Багато-символьні оператори не повинні розділятися пробілами.

Ідентифікатори

У мові Prolog розрізняють чотири види ідентифікаторів: рядкові, заголовні, анонімні і еліпсис.

Рядковий ідентифікатор - послідовність літер, цифр і знаків підкреслення, що починається з малої літери.

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

Анонімний ідентифікатор - знак підкреслення: _.

Еліпс - знак трьох крапок: ....

Літерали

У якості літералів виступають цілі і речові числа, символи, рядки, двійкові дані, списки і складові терми.

Типи даних

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

• 
  integer - цілі числа.
  
• 
  real - дійсні числа.
  
• 
  string - рядки (будь-яка послідовність символів, укладена в лапки).
  
• 
  char - одиночний символ, укладений в апострофи.
  
• 
  symbol - послідовність латинських букв, цифр і символів підкреслення, що починається з маленької літери або будь-яка послідовність символів, укладена в лапки.
  

Терм – вираження, що позначає якийсь об’єкт предметної області.

Простий терм

До простих термів відносяться числа, символи, рядки і ідентифікатори, описані у лексиці мови.

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

Функтор – ім'я терма, позначається рядковим ідентифікатором.

Арність терма – кількість його аргументів. Терм з аргументами називають -арним (або -місцевим) термом.

Нульарний терм – складовий терм без аргументів.

Рекурсивний терм – терм, у якого один або декілька аргументів виражаються тим же термом.

Змінні

Змінні в Пролозі пишуться великими ідентифікаторами і можуть бути або вільними, або пов'язаними. Змінна в Пролозі не змінює своє значення і, будучи вільною, вона набуває його лише один раз. Щоб пов'язана змінна набула іншого значення, її треба «відв'язати» від поточного значення за допомогою процесу, званого відкотом, тобто зробити «звільнення» змінної.

Вільна зміна – зміна, яка не зв’язана будь-яким значенням або квантором.

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

Основні і неосновні терми

Терми, в які не входять вільні змінні, називаються основними. Терми, що містять вільні змінні, називаються неосновними.

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

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

Предикат

Предикат – двозначна -арна функція виду , де – терми, –предметна область, .

Простий (атомарний) предикат складається з предикатного символу і наступних за ним термів – аргументів предиката.

Складовий предикат утворюється з простих предикатів за допомогою:

• 
  логічних зв'язок «і» (кон'юнкція), «або» (диз'юнкція), «ні» (Заперечення), «якщо ... тоді» (імплікація)
  
• 
  кванторів загальності та існування.
  

У чому полягає різниця між простим предикатом і складовим термом

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

Механізм логічного висновку в Пролозі

Єдиним механізмом машини логічного висновку Прологу є пошук з поверненням (англ. Backtracking). Пошук з поверненням - метод знаходження рішень цільового затвердження в логічній програмі. Цей метод дозволяє знайти всі рішення, або деяку частину з них, або навіть одне рішення.

Чи має значення в Пролозі порядок запису фактів і правил

У мові Prolog нема значення порядок запису фактів та правил.

Структура Пролог-програми, які секції обов'язкові

Структура Prolog-програми складається з наступних секцій:

• 
  CLAUSES.
  
• 
  PREDICATES.
  
• 
  DOMAINS.
  
• 
  GOAL.
  

Секції CLAUSES та GOAL є обов’язковими.

Секції: факти; правила; предикати; домени; константи; БД фактів; мета

• 
  Секція CLAUSES є серце Prolog-програми; тут містяться факти і правила, якими буде оперувати Prolog, намагаючись відповісти на запит.
  
• 
  Секція PREDICATES служить для оголошення імен предикатів і типів їх аргументів. Вбудовані предикати Prolog оголошувати не потрібно.
  
• 
  Секція DOMAINS служить для оголошення використовуваних в програмі типів даних, які не є стандартними для Prolog.
  
• 
  Секція GOAL містить вбудований запит (мета).
  
• 
  У секції DATABASE, факти утворюють динамічну або внутрішню базу даних; вона може змінюватися в процесі виконання програми.
  
• 
  У секції CONSTANS оголошуються константи.
  

Уніфікація

Уніфікація - процес встановлення відповідності між двома предикатами і присвоєння значень вільним змінним, що входять в предикат.

Пошук з поверненням (бектрекінг)

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

• 
  Пролог для пошуку вирішення проблеми використовує спосіб повернення і повторного пошуку, званий пошуком з поверненнями (backtracking).
  
• 
  При пошуку збігу з метою Пролог змушений вибирати один з двох варіантів.
  
• 
  Він встановлює маркер в місці розгалуження, іменований точкою повернення (backtracking point), і вибирає першу підціль.
  
• 
  Якщо ця підцель не досягається (що еквівалентно потрапляння в глухий кут), Пролог повертається в точку повернення і намагається досягти альтернативну підцель.
  

Відсікання (зелене та червоне)

Відсікання – механізм, який зупиняє перебір наступних правил та механізм відкату:

• 
  Відсікання поміщається в тілі правила оператором !. Коли процес проходить через відсікання, негайно задовольняється звернення до cut і виконується звернення до чергової підцелі (якщо така є).
  
• 
  Одного разу пройшовши через відсікання, вже неможливо зробити відкат до підцілей, розташованим в оброблюваному пропозиції перед відсіканням, і також неможливо повернутися до інших пропозицій, що визначає обробляє предикат (предикат, що містить відсікання).
  

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

Червоне відсікання – відсікання, яке застосовується у зв’язку з тим, що сама логіка програми вимагає закінчити пошук альтернативних рішень.

8. Перелік джерел

1. 
   Адаменко А. Н., Кучуков А.М. Логическое программирование и Visual Prolog гл.8-11 2
   
2. 
   Марков В. Н. Современное логическое программирование на языке Visual Prolog 7.5
   
3. 
   Братко И. Программирование на языке Пролог для искусственного интеллекта. - с. 18–90.
   
4. 
   Клоксин У., Меллиш К. Программирование на языке Пролог. - М.: Мир, 1987.- 336 с.
   
5. 
   Стерлинг Л., Шапиро Э. Искусство программирования на языке Пролог. – М.: Мир, 1990.- 334 с.
   
6. 
   Чень Ч., Ли Р. Математическая логика и автоматическое доказательство теорем. - М.: Наука, 1983.- 360 с.
   
7. 
   Рябова Н. В. Электронный конспект лекций по курсу «Основы проектирования систем искусственного интеллекта» для студентов специальности 8.080404 – Интеллектуальные системы принятия решений. – Харьков, ХНУРЭ, Электронная библиотека кафедры ИИ, 2004. - 96 с.
   
8. 
   Методичні вказівки до організації самостійної роботи з вивчення курсу „Основи проектування систем штучного інтелекту” для студентів спеціальності 8.080404 – Інтелектуальні системи прийняття рішень / Упорядник: Рябова Н.В. – Харків, ХНУРЕ, 2004р., 16с. (електронний варіант).