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

Можна задати такі питання:

Що можуть купити judy i kelly? can_buy(judi,X) can_buy(kelly,X).

Хто може купити бутерброд з гарячою сосискою? can_buy(X,hot_rod).

2.1.2 Як змінні отримують свої значення

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

Поки змінна не отримає свого значення, вона називається вільною, а коли отримує значення – зв'язаною. Але вона залишається зв'язаною тільки на час,

який необхідний для отримання одного розв'зку на запит, потім PROLOG

звільнює її, повертає і шукає альтернативні розв' язки.

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

Лістинг 2.2

predicates

nondeterm likes(symbol,symbol)

clauses

likes(ellen, reading). likes(john, computers). likes(john, badminton). likes(leonard, badminton). likes(eric, swimming). likes(eric, reading).

Побудуємо запит:

Чи існує особа, яка любить читання і купання?

likes(Person,reading) and likes(Person,swimming)

змінна Person – вільна; її значення невідомо до тих пір, поки PROLOG

пробує знайти розв'язок, інший аргумет – reading – відомий. PROLOG робить пошук факту, який порівнює першу частину запиту. Використовуючи перший факт програми:

likes(ellen,reading)

Враховуючи другу частину запиту, PROLOG повинен шукати факт: likes(ellen,swimming)

PROLOG веде пошук цього факту з самого початку программи, але

співставлення не проходить (тому, що не існує такого факту в програмі).

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

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

(eric, reading). Тому Person зв'язується з eric. Він задовільняє і другій частині запиту. PROLOG відповідає:

Person = eric 1 Solution

2.1.3 Анонімні змінні

Анонімні змінні використовуються у випадку, коли вам потрібна

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

Лістинг 2.3

predicates

male(symbol)

female(symbol)

nondeterm parent(symbol, symbol)

clauses male(bill). male(joe).

female(sue). female(tammy).

parent(bill, joe). parent(sue, joe). parent(joe, tammy).

Анонімна змінна може бути використана на місці любої змінної.

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

Наприклад, якщо вам потрібна інформація тільки про батьків, тоді ви можете використати запит:

Goal:parent(Who, _)

де символ _ позначає анонімну змінну. Система видасть результат:

Who=bill

Who=sue

Who=joe

3 Solution.

Анонімні змінні можуть також використовуватись і в фактах: owns(_,shoes).

eats(_).

В цьому випадку анонімна змінна порівнює все.

2.1.4 Складні цілі: кон`юнкція та диз`юнкція

Також можна використати складну ціль, щоб знайти рішення, в якому дві підцілі А і В справджуються (кон`юнкція), або розв`язок, в якому справджується хоча б одна із підцілей А або В (диз`юнкція).

Наприклад, розглянемо програму (лістинг 2.4):

Лістинг 2.4

predicates car(symbol,real,integer,symbol,integer) truck(symbol,real,integer,symbol,integer)

clauses

car(chrysler, 130000, 3, red, 12000). car(ford, 90000, 4, gray, 25000). car(datsun, 8000, 1, red, 30000). truck(ford, 80000, 6, blue, 8000). truck(datsun, 50000, 5, orange, 20000).

Загрузимо і запустимо цю програму, задавши ціль:

Goal: car(Make,Odometer,Years_on_road,Body,25000).

Cпробуємо знайти автомобіль, вартість якого становить рівно 25000.

PROLOG-система видасть одне рішення – ford. Але такий запит не природній.

В житті ми будуємо питання іншим чином. Чи існує в продажі автомобіль,

вартість якого менша за 25000? Таке питання можна реалізувати наступним складним запитом:

car(Make,Odometer,Years_on_road,Body,Cost) and Cost < 25000.

Якщо ж потрібно реалізувати в PROLOG питання наступного типу:

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

25000? Тоді ми повинні використовувати складну ціль: car(Make,Odometer,Years_on_road,Body,Cost) and Cost < 25000 or truck(Make,Odometer,Years_on_road,Body,Cost) and Cost < 25000.

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

1.Програма PROLOGу складається з фраз. Фрази бувають двох типів:

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

Правила – це залежні відношення. Вони дозволяють PROLOGу

отримувати деяку інформацію із іншої.

2.Факти мають загальну форму:

property(obj, obj1, ... objn) або ж

relation(obj, obj1, ... objn), де property виражає властивість об`єктів, а relation – відношення між об`єктами.

3. Кожний факт відноситься до одного або ж декількох об`єктів.

Наприклад, в факті PROLOGу likes(tom,baseball) відношенням є likes, а

об`єктами tom і baseball. Він описує речення:

Тому подобається бейсбол.

А в факті left-hander(tom) властивістю є left-hander, об`єктом – tom. Він описує речення : Том - лівша.

4. Правила мають загальну форму:

голова if тіло,

яка в програмі приймає вигляд: relation(obj, obj1, ... objn) if relation(obj, obj1, ... objn) and

....

relation(obj, obj1, ... objn).

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

Наприклад, відношення parent(joe,X) співставляючись з Parent(joe,Y) ...

зв'язує змінні Х та У відповідним чином.

4. В PROLOG зв'язування (присвоєння) проходить двома способами: на вході і виході. Коли змінна потрапляє в фразу, вона стає вхідним параметром і позначається (i); а, коли виходить із фрази – стає вихідним параметром, який позначається (о).

Позначення.

Для полегшення читання в PROLOG використовуються наступні

позначення:

«:-» cимвол if;

«,» слово аnd;

«;» cлово or.

2.2 Контрольні запитання до лабораторної роботи

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

1.дівчина (Галя);

2.подобається (Що, івану);

3.подобається (Що, івану) if подобається (Що, петру).

2.Напишіть фрагменти PROLOGівських програм, які задають наступні твердження української мови:

1.Місто - Київ.

2.Місто Київ красиве.

3.Київ - столиця України.

4.Як називається столиця України?

3.Напишіть правило PROLOGу, яке відображає наступну ситуацію. Є

факти: батько(микола, іван), мати(ніна, іван). Потрібно описати правило, яке визначає батьків Івана.

4.Нехай у PROLOG системи є набір фактів:

батьки(микола, ніна, іван)

батьки(петро, галя, андрій)

батьки(віктор, надія, марія).

Кожний з фактів трактується так. Перші два аргументи предикату є батьками особи, яку визначає третій предикат. Що буде, якщо реалізовувати запити:

1.Goal: батьки(X,Y,_);

2.Goal: батьки(_,_,Х).

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

1. Запрограмувати свій варіант логічної функції (згідно таблиці 2.1)

мовою PROLOG (див. приклад нижче).

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

може бути описана відповідним предикатом PROLOGу. Предикат характеризує відношення між сигналами на вході і виході. Базові функції основних компонент об'єктів описують за допомогою таблиць істинності.

Покажемо як це робиться на прикладі моделювання роботи лінії зв'язку типу взаємовиключного АБО, схема якого приведена на рис. 2.1.

Рис. 2.1. Базова лінія зв'язку XOR

В наступній програмі (лістинг 2.5) вона описана предикатом xor.

Лістинг 2.5

domains

d = integer

predicates

nondeterm not_(d, d) and_(d, d, d)

or_(d, d, d)

nondeterm xor(d, d, d)

clauses

not_(1, 0). not_(0, 1). and_(0, 0, 0). and_(0, 1, 0). and_(1, 0, 0). and_(1, 1, 1). or_(0, 0, 0). or_(0, 1, 1). or_(1, 0, 1). or_(1, 1, 1).

xor(Input1, Input2, Output) :- not_(Input1, N1), not_(Input2, N2),

and_(Input1, N2, N3), and_(Input2, N1, N4),

or_(N3, N4, Output).

Задаємо ціль:

goal: xor(Input1,Input2,Output).

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

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

3.Оформити звіт з лабораторної роботи згідно встановлених правил.

Табл. 2.1

Варіант логічної функції

1.((a | b) | (a ~ b)) | ((c d) (d c))

2.((b c) (a c)) ((a | d) | (d b ))

3.((a c ) (b c)) ((a | d) (b d))

4.((a | b) | (a b )) ((c d) (d c))

5.((a b) (a b)) ((c d) (c ~ d))

6.((c a) (c b)) ((a d) (b d))

7.((a ~ b) (a b)) ((c ~ d) (c d))

8.((c a) (c b)) | ((a d) (b d))

9.((a b) (a b)) ((d c) (d ~ c))

10.((a c) (b c)) ((a | d) | (b | d))

11.(a c ) (a b ) (b c) (a b) (c b )

12.(a c) ((b d ) (a d ) (d b) (a d)) (a c )

13.(a c ) (a b ) (b c) (a b) (b c)

14.(b d) ((d c) (a c) (d c ) (a c )) (b d)

15.((a c) (a d)) (((c (c b)) c ) a)