Взаємні властивості множин, множин та їх

Взаємні властивості множин, множин та їх

елементів.

 

Для позначення взаємних властивостей множин та їх елементів іс-нують спеціальні позначки:

 

b Î M - елемент b належить множині M,

d Ï M - елемент d не належить множині M,

A Ì B - множина A є строга підмножина множини B,

A Ë C - множина A не є строга підмножина множини С,

B É A - множина В є строга надмножина множини А,

C Ê D - множина С є нестрога надмножина множини D,

D Í C - множина D є нестрога підмножина множини С,

A = M - множина A дорівнює множині М.

 

Зазначимо, що стверджувати рівність множин A та M можливо, якщо водночас A Í M та М Í А [2].

 

2.3 Різновиди невпорядкованих множин

 

Множина є скінченна, якщо має скінченну кількість елементів. Множина є нескінченна, якщо має нескінченну кількість елементів. Кількість елементів скінченної множини A є потужність множини A. Вираз |A| = 20 свідчить про те, що потужність множини A дорівнює 20. Порожня множина B має потужність 0. Тобто, |B| = 0 або В = Æ, або

B = {}. “Æ” та “{}” – позначки порожньої множини. Зазначимо, що у випадку B = {Æ} B не є порожня множина, бо має у складі один елемент – порожню множину.

Поняття “ зчисленна (зліченна) множина ” стосується нескінченних множин, для яких можливо запропонувати таку процедуру надання поряд- кових номерів елементам, за якої не можуть бути пропущені елементи, тобто, не залишаться без номерів. Приклад зчисленної нескїнченної множини вузлів прямокутної сітки на площині наведено на рис.2-1. На рис.2-1 нумерацією перших 14-ти вузлів сітки показано процедуру надання порядкових номерів з поступовим розширенням області перелічених вузлів. В середині області немає неперелічених вузлів.

Рівнопотужні множини це такі, що мають однакову кількість eлементів. Це або скінченні, або нескінченні множини, для яких існує така процедура поєднання у пари, коли елемент, що є у парі, в іншій парі не використовується. Зліченна множина рівнопотужна множині

Рис.2-1 Спосіб переліку елементів множини вузлів

Прямокутної сітки.

натуральних чисел N = 1,2,3,... і присутня у складі будь-якої нескінченної множини (як підмножина).

Незліченні множини можуть бути рівнопотужними. Наприклад, множина точок відтинку прямої AE (рис. 2-2) та множина точок відтинку прямої AC є рівнопотужні. Це не очевидно. Доведення таке: будь-яка точка на відтинку AE (наприклад, точка D або E) може бути поєднана з єдиною точкою на відтинку AC (наприклад, D з точкою B або E з точкою C) шляхом опущення перпендикуляру на відтинок AC. Будь-які паровані точки у інших парах, побудованих за такою ж процедурою ніяк у цих парах не можуть бути використані. Тому множини точок відтинків AE та AC рівнопотужні. Якщо голова таке не сприймає, то слід згадати, що наші абстрактні точки не мають геометричного розміру!

Деякі важливі невпорядковані множини (невпорядковані - ті, що розглядаємо) мають такі [16] позначки:

N – множина натуральних чисел,

R – множина дійсних чисел,

Z – множина цілих чисел,

Q – множина раціональних чисел,

C – множина комплексних чисел.

 

2.4 Впорядковані множини

 

Впорядковані множини (також кортежі або вектори) мають іншу форму задання та властивості. У виразах (6) задано кортежі A, B, F

 

A = (a,b.c,d,f), B = (b,a,c,d,f), F = (a,a,a,b,e) (6)

 

(дужки обов’язково круглі) та підкреслено, що переставлення елементів створює інший кортеж, бо порядок розташування елементів у

 

 

 

Рис. 2-2 Рівнопотужність

множин точок.

 

 

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

Над множинами можна виконувати операції.

Між множинами можуть існувати відповідності.

На множинах можуть існувати відношення (між елементами).

 

2.5 Операції над множинами.

 

Назви операцій над невпорядкованими множинами та позначки операцій такі: об’єднання - È, претин (переріз) - Ç, різниця - \, симетрична різниця - Å, прямий (декартів) добуток - ´, проекція множини - Пр, доповнення множини – риска над позначкою множини, розбиття множини – позначки немає.

 

2.5.1 Об’єднання множин

Результат об’єднання двох множин є третя множина, яка cкла-дається з усіх тих і лише з тих елементів, які належать хоча б одній з об’єднуваних множин. Наприклад, якщо X = {a,b,c,d},Y = {d,c,m}. то

A = XÈY = {a,b,c,d,m}. Сутність операцій добре пояснюють діаграми Ейлера-Венна, на яких множини зображені, як множини точок у внутрішній області кругів або прямокутників, як на рис.2-3.

 

Рис.2-3 Об’єднання множин: A=XÈY

 

2.5.2 Перетин множин

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

тинаються. Наприклад, якщо X = {a,b,c,d},Y = {d,c,m}, то A = XÇY = ={c,d}. Сутність операції пояснює діаграма на рис.2-4.

 

Рис.2-4 Перетин множин: A=XÇY

 

2.5.3 Теорема про п’ять можливостей

Для будь-яких двох множин А та В можливо таке:

A = B або,

A Ì B або,

A É B або,

A Ç B = Æ або,

A Ç B ¹ Æ, A ¹ B, тобто, множини перебувають у загальному

розташуванні.

 

2.5.4 Різниця множин (віднімання)

Результат операції над множинами X та У є множина, яка cкла-дається з тих елементів множини X, які не є спільні для обох множин. Наприклад, якщо X = {a,b,c,d}, Y = {d,c,m}, то A = X\Y== {a,b}. Сутність операції пояснює діаграма на рис.2-5.

Рис.2-5 Різниця множин: A=X\Y

 

2.5.5 Симетрична різниця

Результат операції над множинами X та У є множина, яка cкла-дається з тих елементів об’єднання множин, які не є спільні для обох множин. Наприклад, якщо X = {a,b,c,d}, Y = {d,c,m}, то A = XÅY= ={a,b,m}. Сутність операції пояснює діаграма на рис.2-6.

 

2.5.6 Прямий добуток множин

Результат операції над невпорядкованими множинами X та Y є невпорядкована множина кортежів довжини 2, у яких перший елемент належить множині X, другий - множині Y. У загальному

 

Рис.2-6. Симетрична різниця множин: A=XÅY

 

вигдяді A = X´Y = {(x,y)| (xÎX)Ù(yÎY)}. Наприклад, якщо X = {a,b,c}, Y = {d,c}, то A = X´Y== {(a,d),(a,c),(b,d(,(b,c),(c,d),(c,c)}. Якщо множини X та Y є множини точок відтинків числової вісі, а cаме:

X1={x| (x³2)Ù(x£6)}, Y1={y|(y³1)Ù(y£ 5)}, то геометрична інтерпретація результата – множина точок прямокутника на площині XY

(див. рисунок 2-7).

 

Рис.2-7 Прямий добуток множин: A=X1´Y1

 

2.5.7 Універсальна множина та доповнення множини

 

Множина, яка є об’єднанням всіх множин, має позначку “ I ” та назву – “ універсальна ”. Властивості універсальної множини:

 

XÇI = X, XÈI = I (7)

 

Результат операції доповнення множини X є = I \ X. До складу доповнення потрапляють будь-які елементи універсальної множини за виключенням елементів множини-операнда цієї операції. Сутність операції пояснюється на рисунку 2-8.

 

 

Рис.2-8. Операція доповнення множини X.

 

2.5.8 Проекція множини

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

A = {(b,c,d.k),(b,b,d,k),(a,b,c,d),(f,c,d,m)}, то

Пр1A={b,a,f}, Пр2A={c,b}, Пр3A={d,c}, Пр4A={k,d,m},

Пр1,2A={(b,c),(b,b),(a,b),(f,c)}, Пр2,3A={(c,d),(b,d),(b,c)},

Пр2,3,4A={(c,d,k),(b.d,k),(b,c,d),(c,d,m)} та таке інше.

 

2.5.9 Розбиття множини

Це подання множини об’єднанням підмножин, які не мають взаєм-них перетинів. Умови визнання системи підмножин розбиттям множини A такі:

A = A1ÈA2ÈA3ÈA4È…ÈÇAn,

AiÇAj = Æ, i ¹ j.

 

 

2.6 Властивості операцій над множинами

 

Властивості операцій над множинами виграють суттєву роль у виз-наченні алгебраїчних систем та під час перетворень математичних виразів. Назви властивостей та ілюстрація їх наявністі у деяких операцій над множинами наведені у таблиці 2-1.

 

 

(Увага далі файл dmc3-9 з таблицею)

 

2.7 Відповідності на множинах

 

2.7.1 Визначення та задання відповідності

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

- множину X, елементи якої складають область відбуття відповідності,

- множину Y, елементи якої складають область прибуття

відповідності,

множину Q (QÍX´Y), яка визначає сутність відповідності. Множина Q містить кортежі довжини 2, які поєднують тільки ті лементи двох множин, що перебувають у відповідності.

Формальний запис q=(X,Y,Q) означає задану відповідність з позначкою q, яка має у якості множини відбуття множину Х (бо вона розташована на першому місці у кортежі формального запису), яка має у якості множини прибуття множину Y (бо вона розташована на другому місці) і яка має множину кортежів Q (бо така позначка розташована на третьому місці). Очевидним є те, що Пр1Q=X та Пр2Q=Y. Якщо кортеж (x,y)ÎQ, то кажуть, що “y” відповідає “x”. Геометрична ілюстрація кортежа (x,y) є стрілка, що виходить з точки “x” і потрапляє вістрям у точку “y”.

 

2.7.2 Обернена відповідність

Для кожної відповідності q=(X,Y,Q), QÍX´Y можна побудувати обернену відповідність q-1=(Y,X,Q1), де Q1ÍY´X. Елементи множини Q1 побудовані з елементів множини Q шляхом переставлення елемен-тів у кортежах. Якщо кортеж (x1,y1)ÎQ, то кортеж (y1,x1)ÎQ1. Двора-зове обернення дає вихідну відповідність.

Приклад. Задано відповідність q1=(A,B,F), A={a,b,c,k}, B={2,1,5},

F={(a,1),(a,5),(c,5),(k,1),(b,2)}. Обернена відповідність q1-1=(B,A,F1),

де F1={(1,a),(5,a),(5,c),(l,k),(2,b)}.

 

2.7.3 Композиція відповідностей

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

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

Прикдад. Треба визначити композицію відповідностей

q1=(A,B,Q) та q2=(B,F,Q1),

де A={a,b,c,d}, B={k,l,m,n}, F={f,g,h},

Q={(a,l),(a,n),(c,k),(b,k),(d,m)},

Q1={(k,f),(l,g),(m,h),(m,g)}

Результат операції q=q1°q2=(A,F,Q2) (позначку операції °будемо надалі використовувати у випадках, коли загальновживані позначки операцій відсутні), Q2={(a,g),(c,f),(b,f),(d,h),(d,g)}, всі елементи результату, а саме A,F,Q2, тепер відомі.

 

2.7.4 Різновиди відповідностей

Задано відповідність q=(A,B,G), GÍA´B.

Відповідність має назву всюди визначена або відображення, якщо Пр1G=A, Пр2GÍB.

Відповідність має назву сюр’єктивна, якщо Пр1GÍA, Пр2G=B.

Відповідність має назву ін’єктивна, якщо Пр1G=A, Пр2GÍB, та між A та Пр2G існує взаємно однозначна (бієктивна) відповідність.

Відповідність має назву функціональна, якщо Пр1G=A, та кожен елемент множини A має один елемент - образ в множині B.

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

Функціональна відповідність між числовими множинами є функція.

Функціональна відповідність, де область відбуття є множина функ-цій, а область прибуття є числова множина, має назву функціонал. Наприклад, функціонал “середнє значення функції f(x) на інтервалі 0-Т “ встановлює відповідність за допомогою виразу

 

(8)

 

 

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

оператор (використовують для перетворення функцій).

2.7.5 Деякі терміни та символіка при відображеннях

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

 

4 Елементи математичної логіки

 

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

 

4.1 Предикати

 

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

значення “істинний” або “хибний”. Формально предикат як відображення

може бути визначений так:

Р: Мn®B, (10)

де В={істиний, хибний};

n- показник степеня (тут декартів добуток).

Наприклад, предикат P1(x1,x2)=(x1³x2) має значення “істинний”, якщо x1

не менше ніж x2. Область істиності цього предикату має геометричну

інтерпретацію. На рис.4-1 частина площини, що не віще лінії, де

x1=x2(затемнена), може бути описана кортежами (x1,x2), у якиx x1³xЗатемнена частина є область істиності предиката P1(x1,x2).

Рис.4-1 Геометрична інтерпретація області істиності предиката P1(x1,x2)

Інший приклад. Розглянемо предикат

 

P(x,y,z,n) = (xn+yn=zn), (11)

де x,y,z,n – натуральні числа. Цей предикат при n=2 істинний на всіх єги-

петських трикутниках (прямокутних трикутниках з цілочисельними сторо-

нами)

P(3,4,5,2)= “істинний”,

P(5,12,13,2)= “істинний”,

P(8,15,17,2)= “істинний”,

P(9,12,15,2)= “істинний”.

Цей предикат при n>2 є частина формулювання відомої теореми

Ферма, відносно якої якої є різні думки (щодо існування хоча б одного

прикладу істиності предиката).

Ще приклад. Умова закінчення циклічних операцій у програмі може

виглядати, як предикат P(x,y,i) = (x=y)Ù(i >100)

 

4.2 Квантори

4.2.1 Умовні позначки та квантифікація

Висловлювання “для всіх x з множини М предикат P(x) є істин-

ний” позначають так:

"(xÎM)P(x) або "xP(x).

Тут позначка " має назву квантор загальності (рос.- квантор общности, англ. – universal generalization) і походить від першої (перевернутої) літе-

ри англійського слова All – все, всі.

Висловлювання “існує такий x у множині М, для якого предикат P(x) є істинний” позначають так:

$(xÎM)P(x) або $xP(x).

Тут позначка $ має назву квантор істування (рос.- квантор существования, англ. – existential generalization) і походить від першої (повернутої) літери англійського слова Exist – існувати.

З використанням кванторів твердження теореми Ферма виглядає

так

$(nÎN)$(xÎN)$(yÎN)$(zÎN)((xn+yn+zn)Ù(n>2)) (12)

або так

$n$x$y$z((xn+yn+zn)Ù(n>2)). (13)

У звичайного предиката P(x,y) змінні не є зв’язані умовами, є

вільні. У предиката з квантором "P(x,y) (або $P(x,y)) змінна x є зв’я-

зана, а змінна y є вільна. Операція надання кванторів має назву -

квантифікація.

 

4.2.2 Ситуації щодо істинності формул логіки предикатів

Формулювання теорем або умов за допомогою предикатів з кван-

торами є формули логіки предикатів.

Формула логіки предикатів може бути [1]

 

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

- тотожно істинною в області М, якщо вона набуває значення “істин-ний” при будь-яких підстановках з М, як, наприклад, формула

___

"x(P(x)ÚP(x)), (14)

- тотожно хибною в області М, якщо вона набуває значення “хибний” при будь-яких підстановках з М, як, наприклад, формула

___

$x(P(x)ÙP(x)). (15)

4.2.3 Деякі властивості кванторів

Квантор загальності "x має властивість дистрибутивності відносно

кон’юнкції, тобто,

"x(P1(x)ÙP2(x)) = "xP1(x)Ù"xP2(x), (16)

 

а квантор існування має властивість дистрибутивності відносно диз’ юнк-

ції -

$x(P1(x)ÚP2(x)) = $xP1(x)Ú$xP2(x). (17)

 

Формулу, яка не має зв’язаних змінних, можна виносити за межі дії квантора -

"x(P(x)ÚP1(x,z)ÚP(y)) = "x(P(x)Ú P1(x,z))ÚP(y) (18)

 

Для перетворень кванторних виразів можна скористатись аналогами

формул де-Моргана _____ ___ _____ ___

$xP(x) = "xP(x), "xP(x) = $xP(x). (19)

 

4.2.4 Зв’язок кванторів з функціями алгебри логіки

Якщо множина Х є скінченна, а саме, Х={x₁,x₂,x₃,…,x_n}, тоді

 

"xP(x) = P(x₁)ÙP(x₂)ÙP(x₃)Ù…ÙP(x_n), (20)

$xP(x) = P(x₁)ÚP(x₂)ÚP(x₃)Ú…ÚP(x_n). (21)

 

Ці вирази дають можливість позбутися кванторів у формулах логіки

предикатів, після чого доведення, скажімо, тотожної істиності формул

полягає в перевірці істиності їх для скінченної кількості підстановок

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

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

Результати аналізу істинності формул на скінченних множинах не зав-

жди можуть бути поширені на ситуацію з нескінченними множинами, бо

 

 

існують формули, здійсненні на нескінченних множинах, але хибні на

скінченних множинах.

4.2.5. Про формалізацію доведень та неповноту аксіоматичних си-

стем.

Німецький філософ Кант стверджував: аксіоми евклідової геометрії

апріорно (одвічно, до накопичення досвіду) задані людскій інтуіції.

Така позиція похитнулася у XIX сторіччі завдяки математикам

Ріману, Больяі, Лобачевському. Вони створили геометричні системи, які не є евклідові, бо замість аксіоми Евкліда про паралельні прямі використали свої варіанти цієї аксіоми. Ріман показав, якщо евклідова геометрія несуперечлива, то і його ріманова геометрія теж несупереч-лива, бо теж послідовно побудована на аксіомах [7]. Якщо взя-

ти до уваги те, що повсюдно визнана теорія відносності Ейнштейна ба-

зується на рімановій геометрії, то можна погодитись з думкою, що й

іншим геометричним системам не уникнути застосування. Але важливо

було і те, що не тільки несуперечливість евклідової геометрії перестає

бути апріорно очевидною, а ще й тягне за собою несуперечливість

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

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

На початку ХХ сторіччя німецьким математиком Гільбертом була

створена група математиків-формалістів, які створили математичну ло-

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

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

не дійти) до тотожно істинних формул, що й має означати успішне

доведення теореми. Випробувати такий метод доведення теорем форма-

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

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

Намагання формалістів припинились, а програма була зруйнована тео-

ремою німецького математика Гьоделя про неповноту. Теорема стверд-

жує, що будь-яка несуперечлива арифметична логіка є неповною, що

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

цієї логіки. Але можна довести засобами іншої логіки, яка більш загаль-

на і обіймає цю. Філософи вбачають у цьому нескінченність пізнання,

бо система, що обіймає, теж неповна. Так розроблений математиками-

формалістами математичний апарат для формалізації доведень допоміг

виявити важливу властивість у відносинах людини і реального світу.

4.2.6 Про теорії алгоритмів та цифрових автоматів

Теорія алгоритмів (алгорифмів) з’явилась за 30 років до появи

ЕОМ і ставила за мету визначення можливості ефективно обчислити

задачу (тобто за скінченну кількість елементарних кроків дійти результату). Ця теорія також має назву - теорія обчислюваності. Щоб теорія мала ознаку строгої математичної теорії, потрібно було визначити

поняття

машина (абстрактна),

алгоритм.

Така абстрактна машина (машина Поста[8], машина Т’юрінга) має

мінімальну кількість команд (Аж 6 команд у Поста! Це вкрай мало на-

віть у порівняння з сучасними RISC-мікроконтролерами, де 30 – 36

команд) та найпростішу пам’ять - нумеровані комірки для зберігання

1 биту інформації в кожній. Така мінімізація спрощувала доведення

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

(загальнорекурсивні функції, частково рекурсивні функції та т. ін.)

дозволяє чипати такі питання, як, скажімо, “Чи може машина бути

розумніше її творця?” або “Чи може машина самовідтворюватись?”[7].

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

вити послідовністю переходів від одного кортежа до іншого, що є об’єк-

том вивчення у “Теорії цифрових автоматів”. Щодо алгоритмізації

конкретних задач теорія алгоритмів зараз мало що може додати.

 

5 Комбінаторна математика

 

Комбінаторна математика або комбінаторика чипає області бага-

тьох розділів математики і ця обставина утруднює її формальне визна-

чення. В основному вона має справу з розташуванням елементів у мно-

жинах. У типових випадках кількість елементів скінченна, а їх розта-

шування зумовлене певними обмежувальними умовами, що витікають

з умов конкретної задачи.

Розглядаються 2 типи проблем:

- проблема існування певних конфігурацій на множинах та

- проблема визначення кількості конфігурацій, їх класифікація

(перелічувальна задача).

Приклад проблеми (задачи) першого типу. Є множина підмножи-на цілих додатних чисел від 1 до 16. Чи можливо розташувати ці чис-

ла у квадратній матриці 4´4 елементи так, щоб сума чисел у кожному

рядку та у кожному стовпцю була та ж сама. Така конфігуруція

(розташування елементів) має назву - латинський квадрат. Колись слу-

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

В задачах другого типу комбінаторній ситуації або комбінаторній

моделі треба поставити у відповідність формулу для обчислення кіль-

кості конфігурацій (потужності множини конфігурацій). Далі розгляда-

тимемо відомі конфігурації, деякі правила та виведемо формули для обчислення їх кількості [5].

 

5.1 Правило суми

Якщо потужність множини S |S|=m, а потужність множини T

|T|=n, то потужність множини SÈT за умови SÇT=Æ можна

обчислити як

|SÈT|=|S|+|T|=m+n (22)

 

5.2 Узагальнене правило суми

Якщо |Ti|=ni, то за умови TiÇTj=Æ, i¹j

|T1ÈT2ÈT3È…ÈTk|=n1+n2+n3+…+nk(23)

 

5.3 Правило добутку

Якщо потужність множини S |S|=m, а потужність множини T

|T|=n, то потужність множини

|S´T|=m×n (24)

 

5.4 Узагальнене правило добутку

Якщо |Ti|=ni, то

|T1´T2´T3´…´Tk|=n1×n2×n3×…×nk(25)

Потужність декартового добутку дорівнює добутку потужностей множин

-співмножників.

 

5.5 Розміщення с повтореннями або вибірки

Конфігурації можна побудувати наступним чином. Задано множину

S потужності ½S½=m. З елементів множини S, розмножуючи їх при

потребі, формуємо кортежі довжини n

 

(s4,s1,s2,sm,s1,…,s4,s3,s5) це варіант конфігурації

n елементів

Кожен такий кортеж може мати деякі елементи множини S, при-

пустимі повторення елементів у кортежі. Такі конфігурації (у цьому

випадку – кортежі) мають назву “розміщення з повтореннями” (деякі елементи розмістили у кортежі, можливо повторюючи їх) або “вибірки”.

Формулу для визначення кількості можливих (різних) кортежів за таких

умов формування виведемо, враховуючи наступне. Кортежі довжини

n, побудовані з елементів множини S, належать декартовому добутку

 

 

S´S´…´S,

 

n разів

 

а їх кількість згідно з узагальненим правилом добутку дорівнює

 

m×m×…×m=mn

n разів

Тобто, кількість розміщень з повтореннями

N=mn, (26)

Нями

 

(31)

Приклад застосування.

Задача. Маємо три гральні кістки (гральна кістка – кубічної форми, на

кожній грані кількістю крапок позначено число. Числа – 1, 2, 3, 4, 5, 6.

Три гральні кістки водночас кидають на стіл - три числа на верхній грані

кісток складають конфігурацію. Скільки існує таких конфігурацій?

Розв’язок. Кількість елементів у конфігурації m=3, розташування елементів у конфігурації значення не має; потужність множини, з еле-ментів якої побудовано конфігурації n=6; за всіма ознаками ці конфігу-рації є комбінації з повтореннями, тому

 

5.10 Переставлення з повтореннями та поліноміальні коефіцієнти

 

Поліном на відміну від бінома має у доданках більш ніж два спів-

множника окрім коефіцієнтів, бо є результатом обчислення виразу

 

(32)

m елементів

Результат обчислення можна вважати сумою кортежів довжини n, серед

яких є еквівалентні, бо (для n=7)

Еквівалентні кортежі утворюються шляхом переставлення елементів, тому

це переставлення з наявністю повторень елементів у кортежі.

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

Припустимо, що треба знайти кількість еквівалентних доданків у (32), у складі яких є множник xayb(степені інших складових нас не цікавлять). Кількість варіантів кортежів довжини n, у яких x розташо-

вано на a місцях складатиме. Для кожного такого варіанту з решти місць (у кількості n-a) на частині місць у кількості b буде розташовано елемент y. Кількість варіантів такого розташування дорівнюватиме кіль-

комбінацій з n-a по b, що дає загальну кількість варіантів у відповідно-

сті з виразом

Зауважимо, що сума показників степеня у знаменнику, тобто,

a+b+(n-a-b) дорівнює n. Аналогічно у загальному випадку, якщо відомі степені всіх співмножників конкретного доданку з виразу (32), поліноміальний коефіцієнт для цього доданку обчислюють за виразом

, (33)

де

Приклад застосування.

Залача. Який буде поліноміальний коефіціент для доданку, що містить

 

при обчисленні?

Розв’язок.

 

 

Ще задача. Скільки буде варіантів розбиття множини потужності n=9 на

три підмножини, якщо

у першій підмножині - 2 елементи,

у другій підмножині - 4 елементи,

у третій підмножині - 3 елементи?

Розв’язок. Припустимо, що є кортеж довжини 9, у якому місця мають

номери від 1 до 9. Номери місць у кортежі складають множину потуж-ності n=9. Будь-який кортеж довжини 9, у якому дворазово присутній елемент x, триразово присутній елемент z та чотириразово елемент y,

є розбиття множини номерів місць у кортежі на підмножини, де

перша підмножина місць містить x, друга підмножина місць містить y

і третя підмножина місць містить z. Кількість варіантів такого розбит-тя дорівнює кількості переставлень з повтореннями або поліноміально-

му коефіцієнту з попередньої задачи, їх буде 1260.

 

5.11 Як розпізнати конфігурацію.

 

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

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

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

запропоновано алгоритм, за яким можна провести аналіз і одержати від-

повідь на запитання - до якої з розглянутих класичних конфігурацій

належить та, що є у вашій задачі. (Зрозуміло, що конкретна задача не обо-

в’язково закінчується розпізнаванням конфігурації та використанням від-

повідної формули).

Ви маєте підрахувати кількість якихось конфігурацій …

 

Якщо ви міняєте місцями елементи у конфігурації,

чи буде то

вже інша конфігурація серед та ж сама конфігурація серед

тих, які вам треба підраху- тих, які вам треба підраху-

вати? вати?

Чи є повторення елементів

Рис.5-1 у складі конфігуруції?

ні так

Конфігурація Конфігурація Конфігурація не є кортеж

є кортеж є підмножина і не є підмножина

 

Конфігурація Конфігурація Конфігурація не є кортеж

є кортеж є підмножина і не є підмножина

Якщо потужність Конфігурації мають назву

всіх підмножин “ комбінації з

Чи є повто - однакова, конфі- повтореннями ”.

рення елемен- гурації мають наз-

тів у кортежі? ву “ комбінації ”.

 

ні так

Чи однакова кількість Чи є обмеження

елементів у кортежі та на кількість однако -

у множині, з елемен- вих елементів у

тів якої побудовано складі кортежа

кортеж?

 

так ні

так ні Конфігурації

мають назву

Конфігурації Конфігурації “ переставлення

мають назву мають назву з повтореннями “,

“ переставлення ” “ розміщення ” кількість є поліно -

Міальний коефіцієнт

 

 

Конфігурації мають назву

“ розміщення з повтореннями “

Рис.5-1 (продовження) або “ вибірки ”.

 

 

6 Групи. Застосування у кодах.

 

6.1 Визначення

Група – алгебраїчна система з однією визначальною операцією.

Загальний запис

де A – множина,

°- позначка операції (тут абстрактної) над елементами множини. Відносно операції та множини є низка вимог:

 

1) результат операції над елементами множини має належати цій

множині; кажуть – множина є замкнена відносно операції; якщо ця ви-

мога виконана, алгебраїчна система має назву – групоїд;

2) операція має бути асоціативною; якщо ця вимога виконується

разом з вимогою п.1, алгебраїчна система має назву – півгрупа;

3) множині має належати нейтральний елемент для операції

(позначимо літерою “е”), такий, що