Дискретная математика. Лабораторные

аргументом відношення є змінна, то вона уніфікується з константою, а

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

Розглянемо дві фрази спеціального вигляду:

Р(а) – заключення без умови і Р(а) – умова без заключення. Наявність

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

Якщо при резолюції двох фраз, що входять в склад теорії, отримується

пуста фраза, тоді теорія буде непослідовною.

Розглянемо на прикладі застосування принципу резолюції і уніфікації.

Нехай маємо відношення ІТ-ШНИК(х), яке позначає твердження х є

артистом і аналогічне відношення ПРОГРАМІСТ(х). Це дає змогу вираз

“Програміст є IT-шником” формалізовати наступною імплікацією:

ІТ ШНИК х ПРОГРАМІСТ х .

Тепер, після задання виразу “Волков – програміст”, попробуємо довести

за допомогою методу резолюції вираз “Волков – ІТ-шник”.

Спочатку, добавимо до попередніх фраз теорії формулу заперечення того

твердження, яке ми хочемо довести. Матимемо наступні фрази теорії:

ІТ ШНИК х ПРОГРАМІСТ х (1)

Формулу (1) перепишемо в вигляді ~ IT шник(x) ПРОГРАМІСТ (x) . Потім зробимо уніфікаційну підстановку х: Волков відносно формул (1) і (2). В

результаті можемо видалити тотожньо істинну формулу:

~ ПРОГРАМІСТ Волков ПРОГРАМІСТ Волков .

Залишок з`єднаємо зв`язкою і знову ж видалимо. В результаті маємо

пусту фразу, що дає непослідовність нашої теорії. Звідки, методом обгрунтування логічного висловлення виводиться формула ІТ ШНИК Волков .

1.1.6 Механізм логічного виведення і керування пошуком

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

А: -В1, В2,..., Вn.

Наше речення інтерпретується наступним чином: “А є істинним, якщо

В1,В2,...,Вn є істинними”.

Кажуть, що А є заголовком цього речення, а В1,В2,...,Вn його тіло. Якщо n=0, тоді таке речення визначає деякий факт і записується “А”.

Речення А і Ві є прикладами цілей або ж викликами процедур, які складаються із предикату і його аргументів R(x,y).

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

По-перше, тому що факти завжди є істинними, тоді ціль успішно задовільняється, якщо вона співставляється з існуючим фактом. По-друге, ціль вважається істинною, якщо вона співпадає з деяким заголовком “А” всі підцілі якого “В1,В2,...,Вn” можуть бути успішно завершені. Якщо спроба співставлення підцілей і фактів закінчується невдало, а залишаються альтернативні і ще не використані правила та факти, тоді PROLOG-система буде здійснювати повернення і використовувати ці альтернативи. Якщо всі альтернативи перебрані і закінчились невдало, тоді кажуть що початкова ціль незадовільна.

Порядок оцінки цілей в самому реченні – з ліва направо.

1.2 Створення програм в Visual PROLOG

Розглянемо процес створення проекту в VP.

1.Створіть новий проект. Для цього потрібно вибрати команду меню

Project | New Project, активується вікно Application Expert.

2.Далі необхідно визначити базовий каталог та ім’я проекту. Ім’я в полі Project Name задаємо як ”Lab1”. Встановити прапорець

Multiprogrammer Mode та клацнути мишою на поле Name of

.PRJ File. При цьому в полі з’явиться ім’я файлу проекту Lab1.prj

(рис. 1.1).

Рис. 1.1. Загальні налаштування проекту в вікні Application

Expert

3.Наступний крок – визначення цілей проекту. Для цього на вкладці

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

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

Рис. 1.2. Параметри мети проекту

4.Встановити потрібні опції компілятора для створеного Lab1-

проекту, для чого в головному меню середовища візуальної розробки потрібно вибрати команду Options | Project | Compiler Options. При цьому активується вікно Compiler Options. В цьому вікні відкрийте вкладку Warnings (рис. 1.3).

Рис. 1.3. Налаштування опцій компілятора

5.Виконайте наступні дії:

Встановити перемикач Nondeterm. При цьому компілятором

Visual PROLOG’а за замовчуванням приймається, що всі предикати, що визначаються в програмі, є недетермінованими,

тобто можуть породити більше одного рішення.

Зняти прапорці Non Quoted Symbols, Strong Type Conversion Check та Check Type of Predicates. Це дозволить придушити деякі можливі попередження компілятора, які не є важливими для розуміння прикладу, що виконується.

Натиснути кнопку ОК з метою збереження налаштувань опцій компілятора.

6.Створіть новий файл програми, для чого в головному меню середовища візуальної розробки виберіть команду File | New. При цьому на екрані з’явиться нове вікно редагування з ім’ям noname.pro (рис. 1.4).

Рис. 1.4. Тестова програма «Hello, World!»

7.В вікні, що з’явилося, надрукувати наступний програмний код:

GOAL

Потрібно вияснити, чи є фраза Р(а), наслідком існуючої множини

фраз.

1.4 Завдання до лабораторної роботи

1.Задати будь-який науковий текст у вигляді предикатів та речень мовою PROLOG. Поставити до тексту 15 запитань.

2.Відповісти на контрольні запитання п. 1.2.

3.Оформити звіт згідно правил оформлення.

ЛАБОРАТОРНА РОБОТА №2. ОСНОВНІ КОНЦЕПЦІЇ МОВИ

PROLOG

2.1 Теоретичні відомості

2.1.1Факти та правила

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

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

Китайська авторучка зручна.

зручна(китайська_авторучка).

Вані подобається авторучка, якщо вона зручна.

подобатись(ваня,авторучка) if зручна(китайська_авторучка).

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

Ваня любить автомобілі

ілюструє відношення між об'єктами Ваня і автомобілі; зв'язком є любить.

Правило, яке визначає, коли речення:

Ваня любить автомобілі

буде істинним, має вигляд:

Ваня любить автомобілі, якщо вони швидкі.

Факти. В PROLOG зв'язок між об'єктами називається фактом. Факти можуть виражати як властивості, так і відношення. Так речення:

Прапор червоний. Валя - студентка.

можуть бути задані наступними фактами:

червоний(прапор)

студентка(Валя).

Правила визначають, які висновки можна зробити з даних фактів.

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

Наприклад, речення Що любить Ваня може бути трасформоване в запит

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

Узагальнення.

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

Факти – це відношення, або ж властивості, про які ви, програміст, знаєте,

що вони істинні.

Правила – це залежні відношення; вони дозволяють PROLOGу робити виведення, порівнюючи одну частину інформації з іншою.

2. Правила PROLOGу складаються з трьох частин: голови, символу, тіла.

Голова – це факт, який буде вірним, якщо деяка кількість умов виконається. Голову ще іноді називають заключенням, або ж відношенням залежності.

Символ – відділяє голову правила від тіла; може бути текстовим типу or

або ж if.

Тіло – це множина умов (або список файлів), котрі повинні бути

істинними, для того щоб PROLOG міг довести, що голова правила вірна.

Розглянемо наступну програму (лістинг 2.1):

Лістинг 2.1

predicates

nondeterm can_buy(symbol, symbol) person(symbol)

nondeterm car(symbol) likes(symbol, symbol) for_sale(symbol)

clauses can_buy(X, Y) :- person(X), car(Y),

likes(X, Y), for_sale(Y).

Person(kelly).

Person(judy).

Car(lemon).

Car(hot_rod).

Likes(kelly, hot_rod).

Likes(judy, pizza).

For_sale(pizza).

For_sale(lemon).

For_sale(hot_rod).