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

Повертаючи до лінійних форм вигляду f = a1x1 + a2x2 +…+anxn, зазначимо, що додавання векторів і множення вектора на скаляр перетворюються у відповідні операції над лінійними формами.

Нехай у базі 1, 2,…, n лінійні перетворення і задаються відповідно матрицями A = ( aij ) і B = (

bij ) порядку n, причому = A і = B , де - база 1, 2,…, n.

Тоді можна установити такі зв'язки між операціями над лінійними перетвореннями і їх матрицями: а) для суми лінійних перетворень: через те, що ( + ) = + , одержуємо

тобто ( + ) = (A + B) .

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

б) для множення лінійного перетворення на скаляр g: через те, що (g ) = g ( ) одержуємо, (g )

= (g) .

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

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

в) для добутку лінійних перетворень: через те, що ( ) = ( ) , одержуємо

тобто ( ) = (AB) .

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

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

29. Алгебр К нтор

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

Визначення. Множина усіх підмножин P(U) будь-якої множини U утворює алгебру множин чи алгебру Кантора щодо теоретико-множинних операцій , , . У цій алгебрі, яку позначають звичайно Ak =P(U), , , , , U , де і U – виділені елементи, операції мають наступні властивості:

1)ідемпотентність: R R = R R, R R = R R;

2)комутативність: R S = S R, R S = S R;

3)асоціативність: R (S T) = (R S) T, R (S T) = (R S) T;

4)дистрибутивність: R (S T) = (R S) (R T), R (S T) = (R S) (R T);

5)властивості виділених елементів: R = , R U = R, R = R, R U = U;

6)властивість доповнення: R R = ,

R R = U;

7)властивість подвійного доповнення: (R ) = R;

8)правила де Моргана: (R S) = (R S ),

(R S) = (R S ).

Можна довести виконання кожного з алгебраїчних законів (1) – (8) алгебри Кантора. Як приклад покажемо, що виконується перший із законів дистрибутивності (4):

R (S T) = (R S) (R T).

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

а) R (S T) (R S) (R T);

31

б) R (S T) (R S) (R T).

Покажемо спочатку включення а). Якщо x R (S T), то x R і або x S, або x T. У першому випадку x R і x S, а звідси x R S. Міркуючи аналогічно, у другому випадку одержуємо x R і x T, а звідси x R T. Таким чином, у будь-якому випадку або x R S, або x R T, звідки x (R S) (R T). Останнє доводить, що виконується включення:

R (S T) (R S) (R T).

Тепер покажемо включення б). Якщо х (R S) (R T), то або x (R S), або x (R T). Звідси випливає, що в будь-якому випадку x R, а також або x S, або x T. Таким чином, x R і x S T, а отже x R (S T). Останнє доводить, що виконується включення:

R (S T) (R S) (R T).

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

R (R S) = R;

R (R S) = R,

а також модулярный закон:

якщо R T, то R (S T) = (R S) T.

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

R (R S) = (R ) (R S).

Звідси, за властивістю дистрибутивності, маємо:

(R ) (R S) = R ( S).

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

R ( S) = R .

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

R = R.

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

R (R S) = R.

30. Булеві лгебри

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

Визначення. Бульовою алгеброю B = A, , , , 0, 1 , називається алгебраїчна система з носієм A і сигнатурою, що включає дві бінарні операції - булевий добуток і - булеву суму й унарну операцію - булеве доповнення, такі, що для будь-яких x, y, z A і двох виділених елементів 1(I) і 0 (O) носія A виконуються такі властивості:

1) ідемпотентність: x x = x ,

x x = x;

2)комутативність: x y = y x,

xy = y x;

3)асоціативність: x (y z) = (x y) x,

x(y z) = (x y) x;

4)дистрибутивність: x (y z) = (x y) (x z),

x(y z) = (x y) (x z);

5)властивості виділених елементів: x 0 = x , x 1 = 1,

x0 = 0, x 1 = x;

6)властивість унарної операції: x x = 1,

xx = 0;

7)властивість подвійного застосування унарної операції: (x ) = x;

8)правила де Моргана: (x y) = (x y ),

(x y) = (x y ).

Тут відчувається аксіоматичний характер задання булевої алгебри. Ми вважаємо заданими операції, що мають властивості, об'єднані у 8 груп аксіом. Конкретна алгебра буде булевою тоді і тільки тоді, коли вона має такий набір операцій і він задовольняє наведеним аксіомам.

Прикладом найпростішої булевої алгебри є двохелементна алгебра B = {0,1}, , , , 0, 1 , де операції - ―найменший з‖, - ―найбільший з‖, - інший елемент. Ми можемо переконатися, що всі аксіоми булевої алгебри тут виконуються.

32

У булевих алгебрах операції і пов'язані цікавим співвідношенням, відомим як принцип двоїстості. Будь-яку властивість операцій булевої алгебри, сформульовану в термінах тільки булевих операцій , і після заміни операції на і на назвемо двоїстою властивістю. Легко помітити, що всі аксіоми булевої алгебри в цілому не змінюються при заміні операції на операцію і операції на операцію . Тому, якщо будь-яка властивість операцій булевої алгебри, сформульована в термінах тільки булевих операцій , доведена за допомогою аксіом булевої алгебри, то доведення при тій же заміні операції на операцію і операції на операцію перетворюється на доведення двоїстої властивості. Звідси робимо висновок про те, що кожній доведеній властивості операцій булевої алгебри, сформульованій в термінах тільки булевих операцій , і , відповідає двоїста властивість, що може бути доведена. У цьому і полягає принцип двоїстості.

Вважаючи, що всі групи властивостей (1) – (8) щодо теоретико-множинних операцій на множини P(U) виконуються, ми, за означенням, можемо стверджувати, що справедлива наступна

Теорема 7. Множина усіх підмножин P(U) будь-якої універсальної множини U з теоретикомножинними операціями об'єднання, перетину і доповнення утворює булеву алгебру з виділеними елементами (у якості 0) і U (у якості 1).

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

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

З іншого боку, справедлива наступна Теорема 8. У будь-якій булевій решітці виконуються тотожності

Доведення. Тотожність (*) випливає з єдиності доповнення і симетричності доповнення. Тоді функція f: A A, що приписує елементу a його доповнення a , є біекцією, а обернена до неї функція збігається з нею.

Покажемо, що функція f обертає частковий порядок на множині A, тобто з a b випливає a b . Дійсно, якщо виконується умова a b, то має місце a b b b . Але тоді, в силу того, що b b = O, можемо записати a b = O.

З іншого боку, через те, що b = b I, а a a = I, то b = b (a a ). Звідси, використовуючи закон дистрибутивності, одержимо

b (a a ) = (b a) (b a ).

Тепер, підставляючи отриманий раніше результат в останню тотожність і використовуючи властивості виділеного елементу O, одержуємо

(b a) (b a ) = (b a ),

що підтверджує обертання порядку, тому що a b . Тепер можна стверджувати, що функція f є ізоморфізмом решітки і двоїстої до неї решітки, що доводить (**). Теорема доведена.

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

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

Теорема 9. Кожна скінчена булева алгебра B ізоморфна алгебрі Кантора з носієм P(U) для універсальної множини U із придатною потужністю n N.

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

Базис індукції: при потужності носія булевої алгебри 1 чи 2 їй ізоморфні алгебри Кантора з носієм P(U) для універсальної множини U з потужністю 0 і 1 відповідно.

Індуктивне припущення: теорема виконується для потужності носія булевої алгебри менше k. Залишається довести, що теорема виконується для потужності носія булевої алгебри k. У цьому

випадку носій булевої алгебри містить елемент a такий, що 0 < a < 1.

31.Функції лгебри логіки.

Улогіці, яку ми почнемо вивчати трохи пізніше, важливе місце займають функції, аргументи і значення яких належать множині {0,1}.

Визначення. Функцією алгебри логіки f(x1, x2,…,xn) від n аргументів x1, x2,…,xn називається функція, що приймає, як і її аргументи, значення з множини {0,1}.

Будь-яка функція алгебри логіки f(x1, x2,…,xn) від n аргументів x1, x2,…,xn задається однозначно таблицею, що традиційно називається таблицею істинності і має такий вигляд:

33

Назва таблиці пов'язана з тим, що в логіці значення 0 і 1 інтерпретуються відповідно як істинне і хибне значення висловлювань і наведені таблиці застосовуються для аналізу значень істинності складних висловлень у залежності від значень істинності простих висловлювань, що їх складають.

Визначення. Функції алгебри логіки f і g називаються тотожними (позначається f = g), якщо на кожному наборі значень аргументів x1,x2,…,xn, кожний з яких є аргументом принаймні однієї з цих функцій, функції f і g приймають однакові значення.

Через те, що існує 2n різних двійкових наборів ( 1, 2,…, n), існує 2 , де = 2n, різних функцій алгебри логіки від n аргументів. Деякі з цих функцій, які можна розглядати як операції над операндами, що приймають значення з множини {0,1}, одержали свої назви. Розглянемо, зокрема, множину усіх 16 функцій алгебри логіки від 2 аргументів, наведену в наступній таблиці:

Зокрема, наведемо назви основних функцій, що використовуються у визначенні формул алгебри

логіки:

1)функція f12 називається диз‘юнкцією і може розглядатися як операція диз‘юнкції x1 x2 над операндами x1 і x2;

2)функція f2 називається кон‘юнкцією і може розглядатися як операція кон‘юнкції x1 x2 над

операндами x1 і x2;

3)функція f11 називається запереченням і може розглядатися як операція заперечення x1 над операндом x1;

4)функція f14 називається імплікацією і може розглядатися як операція імплікації x1 x2 над операндами x1 і x2;

5)функція f9 називається еквівалентністю і може розглядатися як операція еквівалентності x1 x2

над операндами x1 і x2.

Крім того, будемо використовувати функції f1 і f16, що називаються константами 0 і 1 відповідно. У різних побудовах формальних систем використовуються й інші функції і відповідні їм операції.

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

Визначення. Нехай = { 1(x11,...,x1k1), 2(x21,...,x2k2),…, m(xm1,..... ,xmkm)} – скінченна система функцій алгебри логіки. Функція називається елементарною суперпозицією (позначається (1)), якщо вона отримана одним з наступних способів:

1)з якоїсь функції j перейменуванням якоїсь з її змінних xji, тобто має вигляд j(xj1,...,xji-1,y, xji+1,…,x1kj), де змінна y, зокрема, може збігатися з однією із змінних xj1,...,xji-1, xji+1,…,x1kj;

2)з якоїсь функції j підстановкою замість якогось з її аргументів xji функції p , тобто має

вигляд j(xj1,...,xji-1, p(xp1,...,xpkp), xji+1,…,x1kj). Функція , що утворилася, залежить від всіх аргументів функцій j і p і, крім того, може залежати від xji.

Всі елементарні суперпозиції функцій системи складають клас (1) суперпозицій рангу 1 системи. Якщо визначений клас (r) функцій, що є суперпозиціями рангу r функцій системи , то клас (r+1) складають всі елементарні суперпозиції функцій з (r), тобто (r+1) = ( (r))(1) .

Суперпозиціями функцій системи називаються функції, що належать якому-небудь класу (r), де r= 1,2,….

Визначення. Суперпозиція основних функцій алгебри логіки x1 x2, x1 x2, x1, x1 x2, x1 x2 називається формулою.

Формули можна визначити й іншим чином, використовуючи поняття основних операцій алгебри логіки x1 x2, x1 x2, x1, x1 x2, x1 x2, що відповідають основним функціям алгебри логіки. Ці операції звичайно називаються логічними, в силу їхнього широкого застосування в логіці, де змінні x1, x2,… називаються логічними. Тоді формулами називаються логічні операції, що одержуються у такий спосіб.

Визначення формул.

1.Логічна змінна – формула.

2.Якщо F1, F2 – формули, то F1 F2, F1 F2, F1, F1 F2, F1 F2 – також формули.

3.Ніяких інших формул немає.

34

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

Теорема 10. Нехай = { j} – скінченна система функцій алгебри логіки, а складається з функцій алгебри логіки j, кожна з яких рівносильна якій-небудь функції із системи . Нехай функція f отримана з функції f , що є суперпозицією системи , заміною усіх функцій з , результатом суперпозиції яких є f , на рівносильні їм функції із системи . Тоді f = f.

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

Індуктивне припущення: теорема виконується для рангу r.

Покажемо, що теорема виконується для рангу r + 1. Очевидно, що обчислення значень аргументів для f і f приведе до тих же результатів у силу індуктивного припущення. Але тоді для кожного набору значень аргументів значення f і f рівні за визначенням f. Звідси робимо висновок, що f = f. Теорема доведена.

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

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

Визначення. Система функцій алгебри логіки = { j}, j=1,2,…,k, називається повною, якщо будьяка функція алгебри логіки може бути зображлена суперпозицією функцій із системи .

32. Алгебр відношень

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

Визначення. Алгеброю відношень = A, , , \, , називається алгебраїчна система з носієм A, що становить собою множину відношень, і сигнатурою, що включає теоретико-множинні операції - об'єднання двох сумісних відношень, - перетин двох сумісних відношень, \ - різниця двох сумісних відношень і - розширений декартів добуток двох відношень.

Варто нагадати, що n–арне відношення – це будь-яка підмножина декартового добутку n множин,

скажімо A1,A2,…,An. Якщо A1 A2 … An, ai1 A1, ai2 A2,…,ain An, і (ai1, ai2,…,ain) , то говорять, що ai1,ai2,…,ain знаходяться у відношенні , а (ai1, ai2,…,ain) називають n-кою або кортежем n–арного відношення

. Таким чином, n–арне відношення – множина кортежів, в кожному з яких міститься n елементів, по одному відповідно з множин A1,A2,…,An у тому ж порядку.

Нехай A1 = {Чубарук, Простибоженко, Мотренко, Линник, Басанець}, A2 = {Богданський, Кодоб‘янський, Кравцов, Теленик}, A3 = {дискретний аналіз, математичний аналіз, фізика, функціональний аналіз}, A4 = {5, 4, 3, 2, н/з}, A5 = {ФІ-01, ФІ-02,ФФ-01,ФБ-01}, A6 = {професор, доцент, асистент}, A7 = { 17, 34, 51, 68, 85, 102}, A8 = {05.01.2001, 10.01.2001, 15.01.2001, 20.01.2001}. Будемо вважати, що елементами множини A1 (а в термінології розділу 1 значеннями домена A1) є імена студентів, множини A2 – імена викладачів, множини A3 – назви навчальних дисциплін, множини A4 – оцінки, множини A5 – шифри навчальних груп, множини A6 – учені звання, множини A7 – обсяги навчальних занять по дисциплінах, множини A7 – дати іспитів.

Тоді табл.2.1 задає 5-місне відношення 1 (результати іспитів), значення атрибутів якого належать

відповідно доменам A1, A3, A2, A8, A4.

Таблиця 2.1

35

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

Визначення. Об'єднанням двох сумісних відношень i і j називається множина i j усіх кортежів, кожний з який належить щонайменше одному з цих відношень.

Приклад. Табл.2.6 задає 5-місне відношення 6 (результати двох іспитів), що є результатом об'єднання двох сумісних відношень 1 і 2 і значення атрибутів якого належать відповідно доменам A1, A3,

A2, A8, A4.

Таблиця 2.6

Визначення. Перетином двох сумісних відношень i і j називається множина i j усіх кортежів, кожний з який належить як відношенню i, так і відношенню j.

Приклад. Табл. 2.7 задає 5-місне відношення 7 (загальні результати іспитів), що є результатом перетину двох сумісних відношень 1 і 2 і значення атрибутів якого належать відповідно доменам A1, A3,

A2, A8, A4.

Таблиця 2.7

36

Визначення. Різницею двох сумісних відношень i і j називається множина i \ j усіх кортежів, кожний з який належить відношенню i і не належить відношенню j.

Приклад. Табл.2.8 задає 5-місне відношення 8 (різниця результатів іспитів), що є різницею двох сумісних відношень 1 і 2 і значення атрибутів якого належать відповідно доменам A1, A3, A2, A8, A4.

Таблиця 2.8

Визначення. Розширеним декартовим добутком двох відношень i і j називається множина i j усіх кортежів, кожний з яких є конкатенацією кортежу a i і кортежу b j.

Тут відома нам конкатенація слів в алфавіті легко поширюється на конкатенацію кортежів: конкатенація кортежів (a1, a2,…,an) і (b1, b2,…,bm) – кортеж (a1, a2,…,an,b1,b2,…,bm).

Приклад. Табл.2.9 задає 7-місне відношення 9, що є розширеним декартовим добутком двох відношень 7 і 4 і значення атрибутів якого належать відповідно доменам A1, A3, A2, A8, A4, A2, A6. Тут варто звернути увагу на повтор домена A2.

Таблиця 2.9

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

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

33. Реляційн лгебр

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

Визначення. Реляційною алгеброю = A, , , \, , Select, Project, Join , називається алгебраїчна система з носієм A, що становить множину відношень, і сигнатурою, що включає такі теоретико-множинні операції: - об'єднання двох сумісних відношень; - перетин двох сумісних відношень; \ - різниця двох сумісних відношень; - розширений декартів добуток двох відношень, а також спеціальні операції Select – вибірка одного відношення з іншого за деякою умовою, Project – проекція одного відношення на інше, Join – з'єднання двох відношень по спільному домену.

37

Спочатку визначимо нові операції.

Визначення. Вибіркою з відношення i за умовою Y називається множина Select i(Y) усіх кортежів відношення i, елементи кожного з яких задовольняють умову Y.

Приклад. Результатом вибірки з відношення 6 за умовою «оцінка = 5» буде відношення 10, наведене в табл.2.10.

Таблиця 2.10

Визначення. Проекцією n-місного відношення i A1 A2 … An, n m, на Ai1,Ai2,…, Aim називається

множина Project I (Ai1,Ai2,…,Aim) усіх кортежів (ai1,ai2,…,aim), де ai1 Ai1, ai2 Ai2,…,aim Aim, елементи кожного з яких є частиною елементів деякого кортежу відношення i.

Приклад. Результатом проекції відношення 6 на атрибути «П.І.Б. студента», «предмет» і «викладач» буде відношення 11, наведене в табл.2.11, значення атрибутів якого належать відповідно

доменам A1, A3, A2.

Таблиця 2.11

Визначення. З'єднанням двох відношень i Ai1 Ai2 … Ain, і j Aj1 Aj2 … Ajm, що мають спільний домен Ai1 = Aj1, називається множина Join ( i, j/Ai1) усіх кортежів (ai1,ai2,…,ain,aj2,…,ajm), де ai1 Ai1 (Aj1), ai2 Ai2,…,ain Ain, aj2 Aj2,…,ajm Ajm, для кожного з яких елементи ai2,…,ain є частиною елементів деякого кортежу a відношення i, елементи aj2,…,ajm є частиною елементів деякого кортежу b відношення j, а елемент ai1 містить спільне значення елемента ai1 кортежу a і елемента aj1 кортежу b.

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

Варто зазначити, що спільний домен може не бути обов'язково першим у відношеннях i і j, він може займати довільне положення в цих відношеннях. Крім того, допускається виконання з'єднання не тільки за умови рівності значень спільного домена, але й за інших умов, зокрема , , , , .

Приклад. Результатом з'єднання відношень 6 (результати двох іспитів) і 4 (звання викладачів), що мають спільний домен A2, буде відношення, наведене в табл.2.12, значення атрибутів якого належать

відповідно доменам A1, A3, A2, A8, A4, A6.

Таблиця 2.12

Використовуючи послідовно операції вибірки і проекції можна одержати унарне відношення, наведене в табл. 2.13, що становить відповідь на запит «Які студенти одержали відмінні оцінки в професорів?».

Таблиця 2.13

Чубарук

Линник

Басанець

34. Н півгруп н тур льних чисел

38

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

По кожній операції визначена на множині N напівгрупа: N,+ , N, . Однак, по операції напівгрупа має одиницю. Тому множина натуральних чисел з операцією і виділеним елементом 1 утворює алгебру, відому нам як моноїд N, ,1 .

Обидві операції комутативні. Розширення множини N шляхом додавання 0 приводить до того, що система N {0},+,0 вже є моноідом, а система N {0}, ,1 , залишаючись моноїдом, здобуває ще і 0.

Цікаво відзначити, що операція віднімання на множини N не визначена, тому що, наприклад, результат віднімання 3 - 4 множині N не належить.

Крім систем N,+ , N, подібними властивостями володіють системи N2,+ , N2, , де: N2 - множина парних додатних цілих чисел. А ось множина N1 непарних додатних цілих чисел по операції + властивістю замкнутості не володіє.

Множина квадратних матриць Mn n розмірності n n, що складаються з елементів множини N має аналогічні властивості щодо операцій додавання і множення матриць + і . Таким чином, Mn n,+, - алгебраїчна система з двома операціями, причому по першій і другій операціях визначені напівгрупи.

Тоді властивості Mn n,+, не цілком збігаються з властивостями системи N,+, . Але властивості системи M n n,+, , де матриці множини M n n складаються з елементів множини N {0} збігаються з властивостями системи N {0},+, , крім комутативності другої операції.

35. Числові кільця

Отже, в системі N,+, не визначена операція віднімання. Іншими словами, немає оберненого елемента для кожного елемента x N. Однак, наявність цієї властивості додала б системі зовсім іншу якість, наприклад уможливила б розв‘язання рівнянь вигляду x + b = c.

Для цього, однак, потрібно доповнити множину N від‘ємними цілими числами і нулем, тобто перейти до множини Z.

Відомо, що операції + і на множини Z комутативні, асоціативні і пов'язані законом дистрибутивності (a + b) c = a c + b c.

Операція віднімання не є цілком незалежною за визначенням. Звичайно її визначають як обернену операції додавання +: елемент d називається різницею елементів a і b, якщо b + d = a. Таким чином, якщо різниця визначена для кожної пари елементів a,b носія, то операція віднімання задана. Але тоді справедлива наступна

Теорема 11. Множина Z має одиницю по операції додавання, причому ця одиниця єдина. Доведення. Позначимо а – а = 0а. За означенням віднімання це означає, що а+0а=а, а в силу комутативності додавання а + 0а = 0а + а = а. Таким чином, елемент 0а виконує роль одиниці. Покажемо, що

ця роль зберігається для будь-якого елемента носія.

Тоді, за означенням різниці, а + (b - а) = b і за властивостями відношення рівності 0а + b = 0а + а + (b

- а) = а + (b - а) = b чи 0а = b - b. Теорема доведена.

Справедлива також наступна

Теорема 12. Множина Z має обернений елемент для будь-якого елемента носія по операції додавання.

Доведення. Обернений елемент повинен задовольняти умові a + a-1 = 0. За означенням різниці таким елементом може бути 0-а. Тому що операція віднімання однозначно визначена, то він однозначний. Далі оберненим для а елементом запишемо елемент -а. Теорема доведена.

Таким чином, система Z,+, - комутативне кільце. Аналогічно, використовуючи тільки ті ж властивості, ми могли б показати, що C,+, , Q,+, , R,+, - також алгебраїчні системи того ж типу. Можна тепер формулювання теорем 11, 12 починати зі слів ―У всякім кільці ...‖.

Для всіх них виконується властивість, що встановлює наступна Теорема 13. В усякім кільці виконується закон дистрибутивності для віднімання.

Доведення. За означенням віднімання b + (а - b) = а. Домножуємо на с обидві частини рівності й одержуємо b c + (a - b) c = a c. Або (a - b) c = a c - b c. Теорема доведена.

Можна тепер формально установити наступні важливі властивості кілець

Теорема 14. В усякім кільці для будь-якого елемента а носія виконується умова a 0 = 0.

Доведення. a 0 = a (b – b) = a b – a b = 0.

Теорема 15. В усякім кільці для будь-яких елементів а, b носія виконується умова (-a) b = - (a b). Доведення. Послідовно застосовуючи аксіоми кільця, одержуємо: a b + (-a) b = (a + (-a)) b –

аксіома дистрибутивності;

(a + (-a)) b = 0 b – аксіома оберненого елемента операції +; 0 b = 0 – теорема 2.4.

Звідси: (-a) b = -a b.

Теорема 16. В усякім кільці для будь-яких елементів a, b носія виконується умова (-a) (-b) = a b.

39

Доведення. Послідовно застосовуючи теорему 14, одержуємо:

(-a) (-b) = -(a (-b)); -(a (-b)) = -(-a b); -(-a b) = a b.

Очевидно всі ці властивості стосуються і комутативних кілець.

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

36. Проблем породження елементів носія лгебри

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

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

1)чи існує так підмножина для кожного носія;

2)чи можна з конкретної підмножини за допомогою операцій одержати всі елементи носія;

3)чи є ефективні критерії для відповідей на ці питання і т.п.

Очевидно, що відповіді на питання мають теоретичне значення.

Проблема встановлення на основі ефективних критеріїв для кожної підмножини носія «чи можна з її елементів одержати за допомогою операцій всі елементи носія» називається проблемою повноти.

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

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

Таким чином, проблема повноти має і практичне значення.

37. Під лгебри

Розпочнемо з визначення центральних понять цієї теми. Домовимося, що далі розглядаємо алгебру

Розглянемо кілька очевидних властивостей замикань і замкнених множин.

40