Дискретна математика

Тоді (1) = 5, (2) = 6, (3) = 3 і т.д.

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

послідовності записати одна над іншою (перша застосована підстановка повинна бути записана першою), то верхній і нижній рядки утворять результуючу підстановку.

Отже, наприклад, (2) = ( (2)) = (6) = 5 і т. д. Звідси робимо висновок, що зображення оберненої (скінченної) підстановки отримується перестановкою рядків, що зображують початкову підстановку. Хоча таке зображення краще в розрахунках, воно потребує багато зайвого місця, особливо в тих випадках, коли багато елементів не міняються в процесі підстановки. Існує більш просте позначення, котре може вживатися безпосередньо для деяких простих підстановок і опосередковано для всіх скінченних.

Визначення. Нехай А = {а1,…,аn}. Підстановку називають циклом (циклічною підстановкою), якщо

Припустимо, що А В і множина В проста. Розширюючи підстановку на всі елементи В, можна визначити підстановку так, що

(x), якщо х А,

: х x, якщо х В\А.

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

якщо відома область А, ми можемо позначити підстановку як (a1, a2,…,аn). Ця підстановка називається

циклом довжини n.

Приклад 3. Розглянемо знову підстановку

Підстановка є циклом довжини 5 і може бути записана як (1, 3, 6, 5, 4).

Не всі підстановки є циклами. Наприклад, підстановка в прикладі 1 не є циклом. Нагадаємо, що підстановка має вигляд

Тому (1) = 5, (5) = 4, (4) = 1, звідки робимо висновок, що підстановка містить цикл (1, 5, 4). Починаючи з 2, отримуємо інший цикл – (2, 6). Таким чином, маємо

11

= (1, 5, 4) (2, 6) і = (2, 6) (1, 5, 4).

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

Теорема 4. Кожна підстановка на скінченній множині А виражається у вигляді добутку циклів, що не перетинаються.

Доведення. Оскільки |A| = n N, то А має таку ж кількість елементів, що й Nn . Тому без втрати загальності ми можемо обмежитись розгляданням підстановки на Nn .У теоремі стверджується, що = 12 … r, де кожне i, i = 1,2,…,r, є циклом і цикли не перетинаються. Для доведення теореми наведемо потрібні цикли.

Спочатку знайдемо найменший елемент х1 Nn такий, що (х1) х1 і (х) = х для всіх х, 1 х < х1. Якщо такого х1 не існує, то = I (тобто є тривіальним порожнім добутком циклів). В іншому випадку

розрахуємо х1, (х1), 2(х1), 3(х1) і т. д. Всі ці елементи знаходяться в Nn. Тому елементи в цій послідовності повинні містити повторення. Припустимо, що k(х1) – перший такий елемент. Покажемо, що k(х1) = х1.

Припустимо, що це співвідношення не виконується. Тоді l(х1) = k(х1) для деякого l, 0<l<k. Отже l-1(х1) = -

1 l(х1) = -1 k(х1) = k-1(х1) і т. д.

Тому l-1(х1) = k-1(х1), тобто k-l(х1) = 0(х1) = х1, що суперечить мінімальності k (тому що k-l < k). Таким чином, k(х1) = х1 і підстановка 1 = (х1, (х1), 2(х1),…, k-1(х1)) задає цикл всередині .

Якщо всі елементи х Nn такі, що (х) х (будемо називати такі елементи нестаціонарними), містяться в 1, то = 1 – єдиний цикл (який не перетинаєтся). В іншому випадку знайдемо наступний найменший елемент х2 Nn такий, що (х2) х2 і х2 не зустрічається в 1. З х2 будуємо множину різних ступенів : 2 = (х2, (х2), 2(х2),…, m(х2)). Це цикл довжини не менше 2 і він не перетинаєтся з 1.

Якщо всі нестацівонарні елементи вичерпані, то = 1 2 = 2 1. Очевидно, що множину нестаціонарних елементів, що не входять в ці цикли, можна зменшити, і в кінці кінців ми прийдемо до .

Отже, = 1 2 3 … r для деякого r N.

Розглянемо тепер ситуацію з множинами А: |A| = n і B A, |B| = r n, взявши за проблему визначити число бієктивних функцій з А в В чи, що еквівалентно, число ін‘єктивних відображень з В в А.

Число перестановок (без повторів) з n елементів по r позначається nPr і розраховується так же, як і nPn, за винятком того факту, що процес припиняється після заповнення r ящиків. Таким чином,

nPr = n (n–1) … (n–r+1).

Легко бачити, що, продовжуючи процес заповнення ящиків, n – r елементів, що залишилися, можна розмістити по останнім n – r ящикам n-rPn-r способами. Тому і

nPr = (nPn)/ (n-rPn-r) = n! / (n–r)!

При розрахунку nPr ми знаходимо число бієктивних функцій з А в В. Підрахуємо число таких функцій.

Визначення. Нехай А – скінченна множина і B A, |А| = n r = |B|. Множина В називається з‘єднанням (без повторів) з n елементів по r. Число таких з‘єднань позначається Сrn.

Розрахунок Сrn відбувається наступним чином. Покладемо |A| = n. Візьмемо випадкову підмножину B A таку, що |В| = r. Тоді В є шляхом підстановки з n елементів по r. Число ін‘єктивних функцій на А, що мають B своим шляхом, є nPr . Якщо f є такою функцією і g –інша така функція, яка має ту ж саму область значень, то g пов‘язане з f спввідношенням g = f, де – підстановка на В.

Функції g і f визначають одну і ту ж комбінацію, і в дійсності число функцій, що визначають цю комбінацію, рівне числу підстановок на B. Отже, nPr = Сrn rPr, звідки Сrn = (nPr)/(rPr) = n!/r! (n–r)!

Оскільки відносні доповнення єдині і |A\B| = n – r , то звідси робимо висновок, що Сrn= Сn–rn. Розглянемо як функції деякі відомі матаматичні об‘єкти.

Визначення. Послідовністю на множині S називається всюду визначена функція N Z.

Якщо : N Z – задана послідовність і (n) = sn, то звичайно позначають послідовність не , а (sn) чи (s1,s2,…,sn,…). В цьому випадку sn називають n-м членом послідовності.

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

Визначення. Нехай дані множини А, В і C. Позначимо через [В C] множину всіх функцій з множини В в множину C. Функція F: А [B C] називається функціоналом.

Приклад 4. Нехай Р – множина програм, тобто текстів програм, які повинні бути оброблені компілятором. Аналогічно нехай I і О – множини відповідно вихідних і вхідних значень, які доступні програмі для вводу і виводу. Тоді компілятор (з відповідної мови) є функціоналом типу P [I O]; для даної р Р він намагається створити машинний код, який при виконанні буде читати i I і видавати о О.

Приклад 5. Нехай всі дані належать R. Тоді якщо f: a [x a + x], то f(2): x 2 + x і f(2)(3) = 5, тоді як f(3): x 3 + x і f(3)(3) = 6 і т. д.

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

12

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

Визначення. Нехай Х – множина, на якїй задано відношення еквівалентності . Тоді Х розбивається відношенням на -еквівалентні класи; множина -еквівалентних класів на Х позначається Х/ .

Визначення. Нехай Х і Y – множини, х і y – відношення еквівалентності на них і f: Х Y – всюду визначена функція. Позначимо через f відношення f: X/ х Y/ y таке, що f ={([x], [f(x)]) : x X}, де [x] – клас еквівалентності х. Якщо f – функція то х1 хх2 f([х1]) = f([х2]) і f є відображенням, що зберігає еквівалентність. В цьому випадку говорять, що f: X Y індукує відображення f: X/ х Y/ y.

Наочний спосіб зображення такого відображення наведено на рис. 9.

Якщо розглянути відображення f, погоджене з відношенням еквівалентності, то можна переходить від х1 до у1 чи через х2, використовуючи співвідношення y2 = f(х2) і х1 хх2, чи через y2, використовуючи співвідношення y1 = f(х1) і y2 хy1.

В цьому випадку {2,3} X/ х 2 х3 [2] = [3] і f ([2]) = f([3]). Тому f є функцією і f зберігає відношення еквівалентності.

Приклад 7. Нехай Х, Y і f є ті ж, що і в прикладі 6, і відношення еквівалентності x і y індукують розбиття {{1},{2,3}} і {{1,4},{9}} відповідно. В цьому випадку індуковані відношення дають

f([2]) = [f(2)] = [4] = {1 ,4},f([3]) = [f(3)] = [9] = {9}.

Через те, що 2 х3, то [2] = [3] в X/ х , але (4, 9) r, оскільки [4] [9] в Y/ r. В порівнянні з рис.9 цей приклад дає відношення, зображені на рис.10. Через те, що не можна з‘єднати сторони прямокутника у всіх випадках, то відношення еквівалентності не зберігаються.

13. Решітки

Ґр тк ми називається частково впорядкована множина, в якій два елемента x та y мають точну нижню межу, яка називається перетином (позначається x y), та точну верхню межу, яка називається об’єдн нням (позначається x y). Ґратки називаються повними, якщо будь-яка їх підмножина має точні верхні та нижні межі. Очевидно, що будь-які не порожні повні ґратки мають найменший елемент 0 та найбільший елемент 1. Дійсно, якщо два кожні елементи мають точну верхню межу, то в ґратках є тільки один максимальний елемент, який буде й універсальною верхньою межею, тобто одиницею впорядкованої множини. Аналогічно, існування точної нижньої межі для двох довільних елементів забезпечує існування універсальної нижньої межі – нуля впорядкованої множини.

Лема 8.1. Будь-який ланцюг є ґратками, в яких x y співпадає з найменшим, а x y – з найбільшим із елементів x та y.

Це очевидно, тому що для будь-якого ланцюга або x y, або y x, тому або x y = x, або x y = y.

Наприклад, будь-яку абсолютно впорядковану множину (множину цілих чисел) можна перетворити на ґратки, означивши для будь-яких елементів x та y x y = min(x, y),

x y = max(x, y).

Система підмножин будь-якої множини A (булеан A) – частково впорядкована

множина за включенням множин. Ця система є ґратками, елементами яких є множини, а операціями – звичайні теоретико-множинні операції об‘єднання та перерізу. Впорядкована множина раціональних чисел не є повними ґратками, тому що в ній

немає універсальних меж 0 та 1. У впорядкованій множині дійсних чисел умова повноти буде виконуватись, якщо додати до неї в якості універсальних меж – та + .

Підґр тк ми ґраток L називається підмножина X L така, що якщо a X, b X, то a b X та a b X. Порожня підмножина та будь-яка одноелементна підмножина є підґратками. Підґратки

ґраток самі є ґратками з тими самими операціями об‘єднання та перетину. Взагалі, якщо a£b в ґратках L, то (замкнений) інтервал [a, b], що містить всі елементи xÎL, які задовольняють

13

умові a x b, завжди буде підґратками. Для ланцюга та його елементів a£b можна визначити поняття напіввідкритих інтервалів: (a, b] = {x | a < x b} та [a, b) = {x | a x < b}, а також відкритий інтервал (a,b) = {x | a< x <b}. Якщо ці множини не порожні, то вони також є підґратками.

14. Тр нзитивне т рефлексивне з мик ння

Тр нзитивним з мик нням (чи просто замиканням) відношення на множині R називається нескінченне об‘єднання

n 1 2 ... n ...

n 1

Транзитивне замикання відношення на множині R позначають +. Можна також визначити транзитивне замикання таким чином: ri + rj тоді і тільки тоді, коли ri n rj для деякого n 1. Або ri + rj , якщо існує така послідовність r1, r2,...,rk із нуля і більше елементів множини R, що ri r1, r1 r2, ..., rk-1 rk , rk rj. Транзитивність замикання відношення на множині R є наслідком, очевидно, означення замикання. Приклад. 1. Нехай – відношення на множині N таке, що = {(x, y): y = x + 1}. Тоді + = {(x, y): x < y}.

2. Нехай L – множина станцій Київского метро і a, b та c – послідовно розташовані його станції. Якщо

відношення 1 на L визначене як 1 = {(x, y): x є наступною за у станцією}, то (a, b) і (b, c) 1 і (a,a), (b,b),

(c,c) і (a,c) 12. Отже, 1+ = L L.

На цих прикладах видно, що замикання відношення в загальному випадку не є рефлексивним. Однак іноді зручно зробити його таким. Це можна легко зробити. Приймемо, що еквівалентне відношення I = {(x, x) | xR} на множині R, є нульовим ступенем будь-якого відношення на множині R. Таким чином, 0 = I для будь-якого на множині R.

Визначення. Рефлексивним з мик нням відношення множині R (позначається *) називається множина

* n .

n 0

Можна також визначити рефлексивне замикання таким чином:

1)ri * ri для всіх ri R;

2)ri * rj , якщо ri + rj;

3)в * немає нічого іншого, крім того, що міститься там згідно з 1) і 2).

Замикання відношень пов‘язані між собою очевидним співвідношенням * = + I.

Приклад. Використовуючи відношення , визначене в попередньому прикладі, отримуємо * = {(x,y): x y).

15. Відношення т структури

Вище ми підкреслювали можливість задання множин визначенням властивостей її елементів. Цей зв‘язок двобічний. Звичайно, властивість характерризує елемент множини. Зв‘язок елементів задається відношенням. Останнє задається множиною n-ок, тобто графіком відношення. Цю множину можна також задати властивістю, але мова вже йде про властивість n-ок. Як зазначено вище, цей зв‘язок також двобічний. Властивість n-ок будемо називати предикатом і зображувати формулою. Істинність останньої взаємно однозначно пов‘язана з належністю відношенню відповідної n-ки. Якщо P(x1,...,xn) - предикат або формула на змінних x1,...,xn, то тоді можна побудувати множину n-ок:

{(x1,..., xn): P(x1,...,xn) набуває істинного значення}.

Нех й з д н множин {(x1,...,xn)}. Тоді формулу P(x1,..., xn) можн розв’язати, тобто з’ясув ти істинн вон чи ні, використовуючи н лежність відповідної n-ки до множини {(x1,...,xn)}. Звич йно, P не обов’язково буде предст влено “г рною” формулою. Т ким чином, ці дв підходи еквів лентні.

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

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

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

-вставити новий набір з n елементів;

-вилучити набір з n елементів;

-модифікувати набір, що містить n елементів. Почнемо з найпростішої нормальної форми.

14

Визначення. Файли в першій нормальній формі (1NF), чи – простіше - нормалізовані файли, мають записи фіксованої довжини, що складаються з елементів, взятих з множин, чиї елементи далі не можуть бути розбиті, і в кожен момент часу цей файл може бути зображений як масив значень m n. Кожен запис, будучи набором з n елементів, може бути записаний як рядок масиву.

Приклад 5.1. Розглянемо відношення FAM1 між батьками і дітьми. Кожен запис містить в вказаному порядку прізвище і імена батька, матері і дітей. Отже, можливі записи:

(Коміренко, Петро, Оксана, (Ольга, Тарас)) FAM1, (Заплюйсвічко, Федір, Лідія, (Любов)) FAM1.

Тепер, якщо ми позначимо через F і М множини батьків і матерів, то, за означенням, маємо: Петро (Коміренко) F, Оксана (Коміренко) М,

Федір (Заплюйсвічко) F, Ліза (Заплюйсвічко) М.

Таким чином, в сім‘ї Коміренко більше однієї дитини, відповідний запис більше, і, отже, порушені умови першої нормальної форми.

З FAM1 ми можемо отримати FAM2, побудувавши його з S, F, M і С, де S – множина прізвищ, а С – множина дітей, шляхом конструювання записів:

(Коміренко, Петро, Оксана, Ольга), (Коміренко, Петро, Оксана, Тарас), (Заплюйсвічко, Федір, Лідія, Любов).

Відношення FAM2 знаходиться в 1NF і може бути представлене за допомогою табл.1.

Однак не зовсім ясно, що буде, якщо, наприклад, подружжя Простибоженків не має дітей? Якщо ми хочемо мати в файлі запис про них, то необхідно переглянути структуру файлу. Цебто, все належить розпочати зпочатку. Уведемо наступну термінологію.

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

Отже, ПРІЗВИЩЕ, БАТЬКО, МАТИ і ДИТИНА є атpибутами різних полів в FAM2. Для отримання доступу до записів у файлі використовується так звані ключі. Більш точно це може бути визначене у термінах атрибутів.

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

Варто зазначитити, що в файлі може бути багато різних ключів.

Кожен ключ відношення/файлу FAM2 повинен містити атрибут ДИТИНА. Розглянемо інший приклад.

Приклад. Кожен власник комп‘ютера змушений придбати до нього запасні частини. Тому ми можемо розглянути файл, структура котрого наведена у табл.2.

Таблиця 2

Атрибут Компанія є ключем в SUP1; вся інша інформація в файлі доступна за допомогою ключа. Таким чином, наприклад, можливо отримати атрибут Відділ за допомогою ключа ―Золотий лев‖ чи ж Менеджер з ―Білайт‖.

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

На рис 14 представлені у графічному вигляді залежності полів в відношенні SUP1.

Місцезнаходження

Компанія

Менеджер

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

15

файл також код поставки, з котрого ми можемо з‘ясувати швидкість і частоту поставок. Для уникнення зайвої деталізації будемо використовувати номер компанії і номер запасної частини (табл.3.).

Таблиця 3

З таблиці 3 визначимо, які перетворення ми можемо робити з SUP2, а які ні:

вставка. Наприклад, ми не можемо додати в файл запис, що компанія 4 (―МКС‖) знаходиться в Харкові, без вказання деталей, які вона може доставляти;

видалення. Якщо Компанія 6 (―Білайт‖) припинила постачання запчастини 1, то ми зобов‘язані вилучити всі записи, які стосуються цієї компанії і мають в полі Запчастина код 1; модифікація. Якщо код продавця для Києва змінився, наприклад, через транспорт, то відповідне поле повинно бути змінене у кожному записі, де є код Київ в полі Місцезнаходження.

16.Норм ліз ція відношень. З практичної точки зору ми повинні розділити інформацію в SUP2

так, щоб по можливості уникнути повторів. Таким чином, ми отримаємо можливість вставки/вилучення частини запису в SUP2. Можливе і розумне розділення наводиться в SUP3 (табл.4). Тоді залишок інформації в SUP2 може міститись в відношенні Запчастина (табл.5).

Використовуючи цю кофігурацію, можна, наприклад:

а) включити в SUP3 запис, що компанія 4 знаходиться в Харкові (код продавця 3);

б) вилучити посилання на компанію 6 як на продавця запчасти 1, але залишити відповідний запис в

SUP3;

в) змінити код продавця для Києва на 7 шляхом заміни лише трьох рядків відповідним компаніям з кодом 1, а не всіх шести.

Результати цих змін наведені в табл. 6 і табл. 7.

Таблиця 6

16

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

кккваыва

Компанія

Місцезнаходження

Всі не-ключі повністю залежать від ключів. Саме ця обставина пояснює переваги такого рішення перед попереднім. Таким чином, ми виділили властивість нормальної форми, яка виводить нас за рамки 1NF, і обумовлює її подальшу нормалізацію.

Визначення. Файл має другу норм льну форму (2NF), якщо він має форму 1NF і неключові атрибути повністю залежні від ключа.

Приклад 3 (продовження). Файл SUP3 все ще є достатньо незручним в тому розумінні, що для даного запису продавець може бути встановлений за допомогою встановлення запису з відомим значенням ключового поля Компанія чи ж поля Місцезнаходження. Це є причиною того, що в вимозі включити в SUP3 запис, що компанія 4 знаходиться в Харкові (код продавця 3) код продавця для Харкова повинен бути вставлений перед записом кода компанії, а вимога вилучити посилання на компанію 6 як на продавця запчасти 1, але залишити відповідний запис в SUP3, можливо, потребує змінити більше одного запису для модифікації єдиного поля даних, що відноситься до коду продавця. На практиці ми можемо позбавитися цієї проблеми, перебудувавши відношення SUP3 в SUP4 і DEL (табл.8,9).

Відзначимо, що коди продавця, що змінюються таким чином, виключають можливість того, що будьякі інші записи в файлі містять суперечливу інформацію. В відношенні SUP3, наприклад на деякому етапі модифікації SUP2 можна отримати записи вигляду ―Продавець компанії 6 - 2‖ і ―Продавець компанії 1 - 7‖ ,

Всі не-ключі безпосередньо (будемо говорити нетранзитивно) і повністю залежать від ключів. Саме ця обставина пояснює переваги такого рішення перед попереднім. Таким чином, ми виділили властивість нормальної форми, яка виводить нас за рамки 2NF, і обумовлює її подальшу нормалізацію. Варто зазначити, що нетранзитивність відношення залежності є внутрішньою властивістю, з якої і виникає поняття третьої нормальної форми.

17

Визначення. Файл знаходиться в третій норм льній формі (3NF), якщо він є файлом 2NF, і кожен атрибут, що не є ключем, нетранзитивним чином залежить від ключа.

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

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

Практичне використання відношень SUP4 і DEL потребує явного зв‘язку атрибуту Місцезнаходження файлу SUP4 з атрибутом Місцезнаходження файлу DEL. Це – відношення еквівалентності (між компонентами різних файлів, що мають одне і те ж ім‘я). Подібні відношення еквівалентності можуть бути використані для визначення внутрішніх зв‘язків і інших структурних даних. В якості ілюстрації розглянемо рис.17. Діаграма на рис. 17a зображає дерево, діаграма на рис. 17b подібна діаграмі структурних даних, а

2

3

4

5

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

зберігаються. З математичної точки зору це є розбиттям на класи еквівалентності. Отже, ми можемо визначити випадкове представлення цього дерева як елемент множини T = D/E, де

D = {a = (x, a, p), b = (y, b, z), c = (u, c, v), d = (q, d, r), e = (s, e, t)}, E = {(x, b), (y, d), (p, c), (z, e)}.

17. Зн ки і символи

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

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

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

18

штучного інтелекту виникла нова наука про мову як знакову систему – семіотика, яка включає наступні складові: синтаксис, семантику і прагматику.

Змовними знаками (словами, виразами) пов'язана функція позначення предметів (речей, процесів, властивостей, явищ тощо). Предмети позначаються іменами, що можуть бути: 1) простими (―книга‖) і складними (―комп‘ютеризована система керування‖); 2) власними (―Дніпро‖) і загальними (―комп'ютер‖).

Зіменами пов'язані: значення (предмет, що позначається) і зміст (спосіб, яким ім'я позначає предмет, наприклад ―Тарас Шевченко‖ і ―Автор ―Кобзаря‖ мають те ж значення, але різний зміст. Звичайно говорять про семантичний трикутник

значення

Людині властиво формулювати думки реченнями (розповідними (далі висловлювання), наказовими, запитальними). Речення мають складну структуру, зокрема включають дескриптивні (імена предметів (позначають предмети), предикатори (позначають властивості чи відношення предметів)) і логічні (і, чи, якщо ... то, рівносильно, кожен тощо) терміни.

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

Наприклад, ―Студенти вивчають іноземну мову‖ – правильне речення; ―Глокая куздра штеко будланула бокр і курдячит бокренк‖ - не речення; ―Студентами вивчаючи іноземну мову‖ – неправильне речення.

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

Наприклад, висловлювання ―НТУУ ―КПІ‖ знаходиться в Лондоні‖ – хибне, хоча має значення; висловлювання ―НТУУ ―КПІ‖ знаходиться в Києві‖ – істинне; речення ―Круглий квадрат солодко наспівує‖ – абсурдне, не має значення.

18. Способи визн чення мов

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

1.1. Граматики виникли в результаті спроби використовувати методи математики при дослідженні природних мов. Широке їхнє застосування в сфері інформатики, керування й обробки даних обумовлені ефективністю застосування граматик при розв‘язанні лінгвістичних проблем у згаданих сферах. Алгоритмічні мови звичайно визначаються граматиками.

Основна ідея граматик полягає в поступовому формуванні структури слів обумовленої мови в спеціальних допоміжних символах алфавіту D з наступною заміною допоміжних символів символами алфавіту E обумовленої мови.

Як процес формування структури слів обумовленої мови, так і процес заміни допоміжних символів символами алфавіту обумовленої мови, виконуються шляхом застосування правил підстановки (виведення) вигляду α→β, де α,β - слова в алфавіті D E. Якщо в граматиці є правило підстановки α→β, то слово γ безпосередньо породжує слово δ, якщо γ = ωα і δ= ωβ , де ω і - довільні слова в алфавіті D E. Рекурсія дозволить визначити породження словом γ слова δ. Залишається тільки визначити з чого розпочинається і чим закінчується процес породження. Для цього скористаємося поняттям початкового символу d0 (слово d0 приймаємо за споконвічно породжене слово, з якого починається породження будь-якого слова обумовленої мови) і термінального слова, що містить тільки символи алфавіту E (процес породження, розпочавшись зі слова d0 закінчується тільки при породженні термінального слова). Обумовлена граматикою мова включає всі термінальні слова, породжувані даною граматикою з початкового символу d0.

Приклад:

Граматика з алфавітами D = {d0,d1}, E = {0,1} і правилами: d 0 → 0d1

19

d1 → 1d1 d1 → ε

Тут 0 і 1 - термінальні символи, d0 і d1 не термінальні символи, причому d0 – початковий символ. Позначимо цю граматику G1.

Тоді наступні послідовності слів в алфавіті пов'язані відношенням безпосереднього породження: d 0 (початковий символ), 0d1 (тому що є правило підстановки d0→0d1), 0 (тому що є правило

підстановки d1 → ε);

d 0 (початковий символ), 0d1 (тому що є правило підстановки d0→0d1), 01d1 (тому що є правило підстановки d1 → 1d1), 01 (тому що є правило підстановки d1 → ε);

d 0 (початковий символ), 0d1 (тому що є правило підстановки d0→0d1), 01d1 (тому що є правило підстановки d0→0d1), 011d1 (тому що є правило підстановки d1 → 1d1), 011 (тому що є правило підстановки

d1 → ε).

Звідси робимо висновок, що слова 0, 01, 011 – слова мови, обумовленої (породжуваної) даною граматикою G1. Очевидно, що всі слова мови, породжуваної даною граматикою, складуть множину {0, 01, 011, 0111, ...}.

Тепер спробуємо визначити граматикою мову {ε, 00,0000, 000000, ...}.

Для цього можна обійтися тільки одним допоміжним символом d0 і правилами підстановки: d 0 → 00d0

d0 → ε

Тут 0 - термінальний символ, d0 не термінальний символ, причому d0 - початковий символ. Позначимо цю граматику G2.

Тоді наступні послідовності слів в алфавіті пов'язані відношенням безпосереднього породження: d0 (початковий символ), ε (тому що є правило підстановки d0→ ε);

d0 (початковий символ), 00d0 (тому що є правило підстановки d0→00d0), 00 (тому що є правило підстановки d0→ ε);

d0 (початковий символ), 00d0 (тому що є правило підстановки d0→00d0), 0000d0 (тому що є правило підстановки d0→00d0), 0000 (тому що є правило підстановки d0→ ε);

d0 (початковий символ), 00d0 (тому що є правило підстановки d0→00d0), 0000d0 (тому що є правило підстановки d0→00d0), 000000d0 (тому що є правило підстановки d0→00d0), 000000 (тому що є правило підстановки d0→ ε).

Звідси робимо висновок, що слов ε, 00, 0000, 000000 – слов мови, обумовленої (породжув ної) д ною гр м тикою G2. Очевидно, що всі слов мови, породжув ної д ною гр м тикою скл дуть множину {ε,

00, 0000, 000000, ...}.

1.2. Автомати призначені для задання поведінки деяких систем, у першу чергу комп'ютерів, шляхом визначення їхньої реакції (вихідного сигналу і наступного стану) на різні ситуації (комбінації вхідного сигналу і попереднього стану).

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

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

Тут d0 і d1 – стани, 0 і 1 – вхідні символи, перехід зі стану d0 у стан d1 здійснюється при вхідному символі 0 на вході автомата, а перехід зі стану d1 у стан d1 здійснюється при вхідному символі 1 на вході автомата.

Якщо прийняти, що автомат починає розпізнавати вхідну послідовність (послідовність вхідних символів), знаходячись у стані d0 на момент подачі першого символу, а ознакою розпізнавання вхідної послідовності як слова обумовленої мови є його перехід у стан d1 по закінченні слова, то наведений автомат розпізнає наступні слова:

0 – знаходячись у стані d0 автомат під впливом першого і єдиного символу цього слова перейде в стан d1, що і буде ознакою розпізнавання;

20