До лабораторних робіт

ДИСКРЕТНА МАТЕМАТИКА

 

 

МЕТОДИЧНІ ВКАЗІВКИ

до лабораторних робіт

для студентів першого освітнього рівня
підготовки за спеціальністю
122 “Комп’ютерні науки”

 

 

Затверджено
на засіданні кафедри
автоматизованих систем управління.

Протокол № 12 від 12.05.2017 р.

 

Львів – 2017

Дискретна математика: метод. вказівки до лабораторних робіт для сту­дентів першого освітнього рівня підготовки за спеціальністю 122 “Комп’ютерні науки” / уклад.: Д. Д. Зербіно. – Львів: Видавництво Львівської політехніки, 2017. – 40 с.

Укладач                                       Зербіно Д. Д., канд. техн. наук, доц.

Відповідальний за випуск     Шпак З. Я., канд. техн. наук, доц.

Рецензенти                                    Цмоць І. Г., д-р техн. наук, проф.,

                                                  Висоцька В. А., канд. техн. наук, доц.

 

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

Тема: мова програмування PROLOG як засіб перевірки тверджень.

Мета: За допомогою PRL перевірити закони теорії множин.

 

Вступ. Мова PROLOG є однією з найпростіших комп’ютерних мов декларативного типу. На відміну від алгоритмічних мов, декларативні мови вимагають певних зусиль від програмістів для представлення у вигляді абстрактних тверджень опису самої задачі та способів її розв’язку. Фактично, перебираючи способи розв’язку, комп’ютер повинен сам знайти розв’язок. Тому декларативні програми виглядають стисло та зрозуміло. Представлення способів розв’язку задачі у вигляді тверджень дозволяє значно спростити програму структурно, однак, суттєво обмежує можливості програміста, ставлячи його у жорсткі рамки логіки тверджень, якими він повинен оперувати. Тому PROLOG перекладається як “Programming by Logic” – програмування за допомогою логіки. Ми будемо використовувати його модифіковану версію PRL.

Твердження оточують нас у повсякденному житті, ними можна описати будь-що, вони несуть деяку інформацію про все і накладають певні логічні обмеження на будь-що: властивості, дії, структуру, тощо. За допомогою тверджень можна будувати нові логічні конструкції, які фактично є припущеннями (тобто, можуть бути вірними або хибними). У даній версії PRL змінними в твердженнях можуть бути лише цілі числа. Їх можна інтерпретувати як константи, або номери слів, або індекси інших тверджень, або щось інше. Тому для того, щоб твердження набули реального змісту, необхідно уявляти інтерпретацію цих чисел на елементи реального світу. Розглянемо наступне твердження:

 

Перетин_множин(Y):-  множина1(Y),  множина2(Y).

 

Це твердження можна інтерпретувати так: «для того, щоб елемент Y належав до множини Перетин_множин, необхідно, щоб він належав до множини множина1, а також, до множини множина2». Позначка «:-» в твердженнях буквально означає: для того, щоб знайти елементи, які позначені зліва від позначки, необхідно виконати всі твердження, що знаходяться справа (або нижче) від позначки. В кінці твердження ставиться крапка.

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

 

множина1(5).  множина1(2).       множина1(7).

 

можна розглядати як окремі твердження, що числа 5, 2, 7 є альтернативними (взаємозамінними, чи еквівалентними) при розгляді елементів з «множина1».

Будь-яке твердження може посилатися на інші твердження (як було показано у вище наведеному прикладі). Твердження, яке посилається, називається батьківським, а те, на яке посилаються – дочірнім. Будь-яке твердження може бути вірними чи хибними на момент виклику. Від цього залежить, піде програма вперед, чи назад. Наприклад, твердження «множина1(3)» у нашому прикладі є хибним, а «множина1(7)» є істинним, але після виконання останнього, повторне застосування «множина1(7)» буде хибним, оскільки в таблиці є лише одне число 7.

Тведження та їх альтернативи виконуються послідовно. Якщо ви розглядаєте «множина1(Y)», то спочатку за Y буде закріплено значення 5, причому ця константа з таблиці множина1 тимчасово забирається (для того, щоб повторно не розглядати ті елементи, які на даний момент вже розглядаються).

Зрозуміло, що Y – це символічна назва, яка чинна лише в тому твердженні, де вона використовується. Навіть, якщо Y ви зустрінете в іншому твердженні, то між ними немає жодного зв’язку. В процесі виконання поточного твердження після присвоєння значення Y мінятися не може. Точніше, воно може мінятися лише тоді, коли програма натрапляє на суперечку (наприклад, при умові Y >5). При обробці суперечки програма робить крок назад і шукає альтернативне твердження. Якщо цього не можливо, то вона робить ще один крок назад, і так далі. У наведеному прикладі «крок назад» означає, що константа «5» вертається в таблицю, а змінна Y вивільняється, після чого програма знову йде вперед, тобто, змінній Y надається наступне значення «2». Так буде до тих пір, доки виконання не натрапить на крапку – тоді розв’язок знайдено і твердження вірне. В іншому випадку вичерпаються всі можливі варіанти альтернатив і розв’язок не знайдено.

Якщо у загальній конструкції, де твердження перелічені через кому, існує хоча б одне хибне твердження, то загальна логічна конструкція також буде хибною. Тобто, кома означає кон’юнкцію (логічне «І»), або ситуацію, коли перелік необхідних умов ще завершений.

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

Внутрішнє представлення. Таким чином, програма нагадує лабіринт, в якому щоб не заблукати, необхідно рухатися назад по своїх слідах. В комп’ютері будь-яка інформація представляється як звичайна таблиця (або її інтерпретація у формі алгоритму, або її частковий випадок – послідовність біт). Будь-яке твердження також інтерпретується як таблиця з вірних розв’язків (вона може бути безмежною). Які з цих даних у таблиці є вхідними, а які є вихідними – не важливо. Тому завжди можна вважати, що ті дані, які є відомими – це вхідні дані, а ті дані, які є невідоми, будуть вважатися вихідними – їх просто необхідно знайти у таблиці вірних розв’язків. Наприклад, якщо A = B + C уявляти як безмежну таблицю зі стовпцями A, B, C, то стовпець B можна знайти з цієї таблиці як B = A – C.

Основна мета будь-якого твердження – отримати невідомі значення через відомі. Тому інтерпретатор мови PRL робить таку заміну автоматично, під час виконання програми. Якщо ж на момент виконання цього твердження будуть відомі усі три значення, то воно буде розглядатися як логічна умова продовження батьківського твердження.

«Дія» у декларативному підході – це звичайна інформація, яка з’являється після успішного виконання твердження. З огляду на це, якщо вибране твердження виявилося хибним, то будь-які зміни, зроблені програмою (тобто, її дії), можна відмінити (без будь-яких наслідків) і вибрати для виконання інше (альтернативне) твердження. Наприклад, якщо в таблицю додавалися дані, то вони будуть автоматично забрані. В цьому розумінні PROLOG-програмування наближається до таких природних методів мислення, як припущення та вибір варіанту. Наприклад, якщо припущення A = B + C стає хибним (суперечливим), то змінним A, B, C вертається їх попередні значення, а програма робить кроки назад та намагається виконати інші альтернативи (їх може бути скільки завгодно). Програма працює доти, доки не доведе або не спростує саме перше твердження в її тексті.

Синтаксис. Програма починається з головного твердження, яке знаходиться на початку. Кожне твердження має наступну структуру:

 

 <Назва_твердження (параметри)> :-   < Назва_твердження (параметри)>,

 < Назва_твердження (параметри)>,…, < Назва_твердження (параметри)>.

 

Параметри в твердженнях не є обов’язковими. Між дочірніми твердженнями ставиться кома, а в кінці твердження – крапка. Пробіли, табуляцію і перенос рядка можна ставити в довільних місцях, тому що вони пропускаються інтерпретатором. Заголовок твердження від тіла відокремлюється позначкою, що складається з двокрапки і тире. Це трактується так: «для того, щоб зробити < твердження-заголовок >, необхідні дії < послідовність тверджень >». Якщо програма натрапляє на крапку, то це означає, що твердження-заголовок реалізувалося. Альтернативні твердження мають однакові заголовки.

Параметри - це послідовність назв змінних через кому. Якщо до цієї послідовності додати довільні змінні, які не використовуються, то результат обчислень не поміняється. Використання конкретних значень в параметрах заборонено, для їх використання необхідно вводити нові змінні, наприклад: N =5, обєм_відра (N, V). У найпростішому випадку параметрів взагалі не існує.

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

Виконання. При вході в будь-яке твердження виділяються нові змінні, які мають початкове значення «невідомо». Якщо твердження запускалося з параметрами від іншого (батьківського) твердження, то всі значення від батьківського твердження переписуються у новоутворені змінні дочірнього твердження. При успішному завершенні твердження всі невідомі змінні, які стали відомими, передаються у батьківське твердження.

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

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

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

обєм_відра (0, 0).

Тоді в тілі твердження замість < Назва_твердження (параметри)> може бути <Назва_таблиці (параметри)>. Це означає, що для успішного виконання тіла твердження у вказаній таблиці повинен бути знайдений рядок, що задовольняє поточним значенням вказаних параметрів, наприклад: номер =5, обєм_відра (номер, V) буде виконане лише тоді, коли в таблиці «обєм_відра» знайдеться таке значення, наприклад: обєм_відра (5, 13), тоді V прийме значення 13. Інакше пошук в таблиці буде неуспішним і призведе до пошуку альтернативного твердження.

Існує відмінність між істинністю фактів, які занесені в таблицю як константи від істинності фактів, що оформлені як альтернативні твердження за допомогою операції присвоєння. Як ми говорили, після знаходження в таблиці обєм_відра (5, 13) навпроти нього автоматично ставиться внутрішня тимчасова позначка «розглядається». Таким чином, цей факт вже не прийматиме участі в подальшому розгляді на всьому щляху з вірних тверджень, аж до відміни операції N =5, обєм_відра (N, V). Якщо б цей же факт оформити як твердження, наприклад так: обєм_відра (N, V):- N = 5, V = 13, то запит N =5, обєм_відра (N, V) завжди буде успішним, скільки б разів до нього не зверталися, тому що твердження не вилучаються з програми, а лише відкидаються, якщо вони не вірні.

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

Ключові слова введені в інтерпретатор для зручності програмування:

fail – завжди хибне твердження, наприклад: A =5, A =6. Завжди спричиняє пошук альтернативи.

not( <Назва_твердження (параметри)> ) – заперечення вказаного твердження. Наприклад, якщо дане твердження із заданими параметрами є хибним, то конструкція «not» з цими ж параметрами буде вірним твердженням.

write(" <текст> ", <параметри>, …, " <текст> ", <параметри> ) –

виводить у результуючий файл вказаний текст з вказаними значеннями.

suppose( <Назва_таблиці (значення) > ) – припускає існування вказаних значень у таблиці: вказані данні тимчасово додаються в кінець таблиці, навіть якщо такі дані в ній вже є. При відміні цього твердження з таблиці забираються додані дані.

! – припиняє шукати альтернативи для поточного твердження.

_ – прочерк замість значення означає невідоме значення, наприклад: S =_.

Реалізація. Інтерпретатор PRL.EXE реалізований на асемблері для процесорів INTEL PENTIUM на кафедрі АСУ НУ «Львівська політехніка». Після запуску необхідно вказати папку з текстовим документом PRL-програми. Після виконання в блокноті запускається текстовий файл з результатами програми. Якщо синтаксис програми містить помилку, то на екрані запускається текстовий документ з текстом про помилку в тому місці, де вона знайдена. Програма безкоштовна і призначена для навчальних цілей.

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

 

не_рівно(X,Y):- not(рівно(X,Y)).

рівно(X,Y):- X=Y.

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

 

не_більше(X,Y):- not(більше(X,Y)).

 більше(X,Y):- X >Y.

Приклад 3. Необхідно сформулювати правило «менше_або_рівно». Це твердження еквівалентно попередньому твердженню «не_більше», яке ми розглядали як заперечення. Тепер розглянемо його як дві альтернативи: «вірно тоді, коли  менше» або «вірно тоді, коли  рівно»:

 

менше_або_рівно(X,Y):- X<Y.

менше_або_рівно(X,Y):- X=Y.

Приклад 4. Необхідно додати у множину {12, 34, 23} елементи 56 та 45:

 

Приклад:- A=56,suppose(множина1(A)), B=46,suppose(множина1(B)), роздрук.

множина1(12). множина1(34). множина1(23).

роздрук:- множина1(елемент), write(елемент), fail.

роздрук:- write().

Приклад 5. Необхідно перевірити закон Моргана для множин: A \(B È C) = (A \ B)Ç(A \ C). Для цього введемо позначення: для A – множина1, для B – множина2, для C – множина3.

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

 

Закон_Моргана:-

     write("ліва частина:"), різниця1обєднання23 (X), write(X), fail.

Закон_Моргана:-

    write("права частина:"), перетин_різниць12_13 (X), write(X), fail.

 обєднання23(X):- множина2(X), suppose(множина2(X)).

 обєднання23(X):- множина3(X), suppose(множина3(X)), not(множина2(X)).

різниця1обєднання23(X):-

       множина1(X),suppose(множина1(X)), not(обєднання23(X)).

 перетин_різниць12_13(X):- різниця12(X), різниця13(X).

 різниця12(X):- множина1(X), suppose(множина1(X)), not(множина2(X)).

 різниця13(X):- множина1(X), suppose(множина1(X)), not(множина3(X)).

 

множина1(123). множина1(234). множина1(451). множина1(345).

множина2(234). множина2(512). множина3(512). множина3(451).

 

Приклад 6. Знайти всі підмножини заданої множини:

робота_з_підмножинами:- S=0, Знайти_підмножину (S), друк, fail.

Знайти_підмножину(S):- X=_.; вибрана порожня множина

Знайти_підмножину(S):-

                          множина_1(X), X>S, suppose(підмножина (X)),

                       Знайти_підмножину (X).

підмножина(0).; Нульовий елемент використовуємо для оголошення

множина_1(1). множина_1(2). множина_1(3).

 друк:- підмножина(X), X>0, write(X), fail.

 друк:- write("-----------").

У цьому прикладі за допомогою твердження «Знайти_підмножину» утворюється нова множина «підмножина». Для кожної знайденої підмножини виконується допоміжне твердження «друк», яке виводить у вихідний файл всі ненульові елементи підмножини.

Завдання 1. Для розуміння концепції та синтаксису мови PRL необхідно запустити всі приклади; перевірити закони Моргана (перетин різниць та об’єднання різниць) для свого варіанту завдань, яке береться з ідентифікатору вашого мобільного обладнання IMEI (його можна отримати через дзвінок на номер *#06#). Наприклад, цей номер дорівнює 1234512345. Тоді для вашого варіанту елементами множин будуть числа 123, 234, 345, 451, 512 (без повторень). Після цього множини необхідно сформувати так, щоб кожна пара множин не була однаковою і мала не порожній перетин.

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

 

Побудова_спіралі_з_натуральних_чисел:-

     X=1, Y=0, Z=2, suppose(елемент_спіралі(X,Y,Z)),

                         Додати_число_до_спіралі(X,Y,Z).

Додати_число_до_спіралі(X,Y,Z):-

     зліва=X-1,зправа=X+1,зверху=Y-1,знизу=Y+1,

     елемент_спіралі(зліва,Y,P1),suppose(елемент_спіралі(зліва,Y,P1)),

     not(елемент_спіралі(X,зверху,P2)),N=Z+1,suppose(елемент_спіралі(X,

зверху,N)),write("уверх",X,зверху,N), Додати_число_до_спіралі(X,зверху,N).

Додати_число_до_спіралі(X,Y,Z):-

     зліва=X-1,зправа=X+1,зверху=Y-1,знизу=Y+1,

     елемент_спіралі(X,знизу,P1),suppose(елемент_спіралі(X,знизу,P1)),

     not(елемент_спіралі(зліва,Y,P2)),N=Z+1,suppose(елемент_спіралі(зліва,

    Y,N)), write("вліво",зліва,Y,N), Додати_число_до_спіралі(зліва,Y,N).

Додати_число_до_спіралі(X,Y,Z):-

     зліва=X-1,зправа=X+1,зверху=Y-1,знизу=Y+1,

     елемент_спіралі(зправа,Y,P1),suppose(елемент_спіралі(зправа,Y,P1)),

     not(елемент_спіралі(X,знизу,P2)),N=Z+1,suppose(елемент_спіралі(X,

    знизу,N)), write("вниз",X,знизу,N), Додати_число_до_спіралі(X,знизу,N).

Додати_число_до_спіралі(X,Y,Z):- Z<500,

     зліва=X-1,зправа=X+1,зверху=Y-1,знизу=Y+1,

     елемент_спіралі(X,зверху,P1), suppose(елемент_спіралі(X,зверху,P1)),

not(елемент_спіралі(зправа,Y,P2)),N=Z+1,suppose(елемент_спіралі(зправа,

Y,N)),write("направо",зправа,Y,N),Додати_число_до_спіралі(зправа,Y,N).

Додати_число_до_спіралі(X,Y,Z):- Z >500, write("-------------------").

елемент_спіралі(0,0,1).; оголошення таблиці

просте_число(X):- not(існує_дільник_для(X)).

існує_дільник_для(N):- End=N-1, натуральне_число(дільник,End), дільник>1, ділення_без_остачі(результат, N, дільник).

ділення_без_остачі(результат,ділене,дільник):-

     ділене = результат*дільник, ділене = результат*дільник.

натуральне_число(N,End):- N=End.

натуральне_число(N,End):- New=End-1, New>0, натуральне_число(N, New).

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

вибрати_якщо_відповідає_моєму_варіанту(X,Y,Z):- ….