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

16.(a (d b)) ((a (b d)) c) c (a (b d ))

17.(x2 x3 ) (x2 (x1 x3 ))

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

19.((c a) (c b)) ((a d) (b d))

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

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

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

23.((a d) (b d)) ((a c) (b c))

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

25.((a b) (c b)) ((d a) (c d))

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

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

28.((b d) (c d)) ((a b) (a c))

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

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

ЛАБОРАТОРНА РОБОТА №3. СТРУКТУРА ПРОГРАМИ МОВОЮ

PROLOG

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

3.1.1 Основні розділи програми

В якості реалізуючої системи PROLOGу будемо розглядати PDC

PROLOG. Він вибраний тому, що на противагу більшості реалізацій

PROLOGу, є компілятором.

В загальному, програма PDC PROLOGу (надалі будемо писати просто

PROLOG) складається з 3-4 розділів.

Розділ clauses – головна частина програми PROLOGу. Тут записуються факти та правила, які будуть використані для задовільнення цілі програми.

Розділ predicates – використовується для об'яви предикатів та доменів і опису типів їх аргументів. Коли ви об'являєте предикат, ви вказуєте PROLOGу

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

При використанні вмонтованих предикатів, наприклад, таких, як write, makewindow, nl і т.д., об'являти їх не має потреби.

Опис предикату починається з імені, потім, якщо вони існують, іде список типів аргументів, розділених комами і взятими в круглі дужки. Типи аргументу є або ж стандартними доменами, або ж доменами, які ви об'явили в розділі domains. Ім'я предикату повинно бути ідентифікатором.

Розділ domains - використовується подібно конструктору типів type в

Паскалі. За допомогою цього розділу можна перейменувати /перевизначити/

стандартні домени і описати домени складних типів даних. Якщо в вашій

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

взагалі не має потреби.

Розділ goal - використовується для задання вмонтованих (внутрішніх)

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

Розділ constants - застосовується для об'яви констант. Використовується синтаксис:

<Ідентифікатор> = <Макровизначення>.

Тут присутні наступні обмеження:

в одній стрічці повинно бути визначення тільки одної константи;

заборонена рекурсія при визначенні константи;

в описі констант система не розпізнає великі та малі літери;

ідентифікатори констант є глобальними і можуть бути об'явлені тільки один раз.

Розділ database це розділ бази даних. Іноді під час виконання програми вам необхідно змінити деякі факти, з якими працює програма. Факти знаходяться в динамічній або внутрішній базі даних. Факти, котрі розміщуються в динамічній базі даних, повинні бути описані в розділі database.

3.1.2 Стандартні домени

PROLOG має декілька вмонтованих стандартних доменів, основні з яких приводяться нижче (табл. 3.1). Ви можете використовувати стандартні домени при опису типів аргументів предикату. Їх не потрібно визначати в розділі domains.

				Табл. 3.1
	Стандартні домени
Домен		Опис
char	Символ, взятий в одинарні лапки цілі від -
integer	32768 до 32767 числа, з необов`язковим знаком
real	+ або - , який стоїть перед деяким числом
	DDDDDDD, потім необов`язкова десяткова
	крапка (.), яка стоїть перед наступним числом
	DDDDDDD і необов`якова експоненційна
	частина	(е(+		-)DDD):<+:	-
	>DDDDD<.>DDDDDDD<e<+ : ->DDD>
	Приклади дійсних чисел:
	42705 9999 86.74
	9111.769483 521е238 67.85е+21
	Допустимий	діапазон	чисел від 1е-307		до
	1е+308. При необхідності цілі числа
	автоматично перетворюються в дійсні.
string	Довільна	послідовність		символів,	яка
	заключена в подвійні лапки.
symbol	Існує два формати символів:
	1. послідовність букв, чисел і підкреслень, які
	починаються з великої букви;
	2. послідовність символів, які заключені в
	подвійні лапки (випадок, коли символ не
	починається з великої букви або ж коли
	містяться проміжки).

Число аргументів предикату називається арністю предикату. PROLOG

допускає предикати з однаковою назвою але різною арністю.

PROLOG проводить автоматичне перетворення доменів:

1.між стрічками і символами;

2.між цілим, символьним і дійсним доменом.

3.1.3 Синтаксис правила

Як ми вже зазначали, синтаксис правила складається з трьох частин:

голова: - <підціль>, <підціль>, ... , <підціль>.

Кожна підціль викликає відповідний предикат PROLOGу. PROLOG -

система тестує викликаний предикат і перевіряє чи може він задовільнитися.

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

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

3.1.4 Директиви комп`ютеру

Ви можете включити в програму деякі директиви комп`ютеру безпосередньо в програмі або ж вибравши пункт меню Options /Compiler Directives. Наприклад, директиву include.

За допомогою директиви include ви можете підключити до програми написані вами попередньо процедури. Це робиться наступним чином. Додамо

стрічку include “my.pro” на початок вашої програми. А в файлі my.pro

описуються процедури, які використовуються в вашій програмі.

3.1.5 Бектрекінг

Часто при вирішенні конкретних задач вам необхідно переглядати всі можливі шляхи розв'язку задачі. Якщо розглянутий шлях не дає відповіді, ви мусите переглянути альтернативний шлях. Такий підхід до розв'язку задач дістав назву бектрекінг.

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

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

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

Лістинг 3.1

domains

name, thing = symbol

predicates likes(name, thing) reads(name) is_inquisitive(name)

clauses

likes(john, wine). likes(lance, skiing).

likes(Z,books) :-reads(Z), is_inquisitive(Z). likes(lance, books). likes(lance, films). reads(john). is_inquisitive(join).

Задамо системі запитання у вигляді цілі, яка складається з двох підцілей:

likes(X,wine), likes(X,books)

PROLOG починає виведення згідно основного принципу бектрекінгу.

Підцілі повинні задовільнюватися послідовно зверху вниз.

PROLOG визначає яка підціль буде використовуватись для задоволення відповідного фрагменту предикату згідно другого принципу бектрекінгу.

Фрагменти предикату розглядаються в тому порядку, в якому вони

розміщені в програмі - послідовно зверху вниз.

Підціль likes(X, wine) відповідає факту likes(john, wine). Тому Х зв'язується з john. Потім PROLOG пробує задовольнити наступну підціль справа. Виклик другої підцілі розпочинає новий пошук з Х = john. Перший пункт likes(john,wine) не відповідає підцілі likes(X,books), тому що wine не є тим же, що й books. Тому PROLOG пробує підібрати наступний пункт.

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

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

І накінець, четвертий принцип бектрекінгу говорить. Ціль буде

задоволена, коли будуть знайдені відповідні факти для кожного рівня дерева цілі.

3.1.5.1 Бектрекінг з внутрішньою ціллю

Бектерінг з внутрішньою ціллю ілюструється програмою (лістинг 3.2):

Лістинг 3.2

predicates type(symbol, symbol) is_a(symbol, symbol) lives(symbol, symbol) can_swim(symbol)

goal can_swim(What) ,

write("A ", What, " can swim.").

clauses

type(ungulate, animal). type(fish, animal). is_a(zebra, ungulate). is_a(herring, fish). is_a(shark,fish). lives(zebra, on_land). lives(frog, on_land). lives(frog,in_water).

lives(shark, in_water).

can_swim(Y) :-

type(X, animal) ,

is_a(Y, X) , lives(Y,in_water).

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

1. Наберіть останню програму і, використовуючи директиву trace,

розгляньте послідовність задоволення вмонтованої цілі.

2. Напишіть предикат PROLOGу, який буде визначати позицію букви в алфавіті:

alphabet-position (Letter, Position).

Наприклад Position=1 якщо Letter=a т.д.

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

1.Напишіть програму PROLOGа, яка б визначала і друкувала значення n!. Значення n вводиться з клавіатури і є цілим.

2.Напишіть програму, яка знаходить найменше спільне кратне двох цілих чисел a i b (значення яких вводяться з клавіатури) НСК(a,b) ,

a * b

скориставшись формулою: HCK(a, b) = HCD(a, b) , де НСД(a,b) позначає

найбільший спільний дільник. Для знаходження НСД(a,b)

використайте окремий предикат, який підключіть до вашої програми за допомогою директиви include.

3. Розв’язати задачу:

Чотири дівчини: Надія, Віра, Галина та Люба, намалювали по одному звіру. Вийшло два коні, одна вівця та одна корова. Що намалювала кожна дівчина, якщо:

Надія та Віра не малювали вівцю;

Галина не малювала корову;

Люба не малювала коня;

Віра та Галина, Галина та Люба, Надія та Люба намалювали різних звірів.

4.Розв’язати задачу:

Три дівчини: Оля, Олена та Маша, пішли в ліс. Дві з них збирали гриби, одна – ягоди. Що збирала кожна з дівчин, якщо Оля з Оленою та Маша з Оленою не збирали одне й те ж.

5.Розв’язати задачу:

Четверо студентів: Іван, Петро, Михайло та Сергій, приймали участь у олімпіадах з математики, фізики та програмування. Визначити вид дисципліни, в якій приймав участь кожний студент, якщо:

Сергій та Петро не приймали участь в олімпіаді з програмування;

Михайло не приймав участь в олімпіаді з математики;

Іван не приймав участь в олімпіаді з фізики;

Сергій та Іван виступали в одній дисципліні;

Кожний студент приймав участь тільки з однієї дисципліни.

6.Розв’язати задачу:

Четверо друзів: Іван, Петро, Семен та Володимир, проводили вільний час по-різному: двоє грали в шахи, один читав книжки, один дивився телевізор. Визначити, хто і яким чином проводив вільний час, якщо Семен не грав в шахи, а Петро не дивився телевізор.