Основи дискретної математики

Размещено на http://www.allbest.ru/

1. Теорія множин

1.1 Основні означення теорії множин

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

Множина - це сукупність об'єктів, об'єднаних за певною ознакою.

Приклади:

- множина букв алфавіту;

- множина точок на прямій;

- множина двозначних натуральних чисел;

- множина цілих чисел і т.д.

Множини позначають А, В, С, …

Об'єкти з яких складається множина називаються її елементами: а, в, с, …

Якщо елемент а належить множині А, то позначають: . Якщо елемент d не належить множині А, то позначають: .

Якщо елементами множини є числа, то її називають числовою:

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

- множина цілих чисел: Z

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

- множина дійсних чисел: R

Множина називається скінченною, якщо вона має скінченну кількість елементів.

Множина називається нескінченною, якщо вона має нескінченну кількість елементів.

Кількість елементів множини називається потужністю:

Множина яка не має жодного елемента називається порожньою:

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

Будь - яка множина є підмножиною самої себе. Порожня множина є підмножиною будь - якої множини. Тому у будь - якої множини є дві очевидних підмножини: порожня і сама ця множина.

Приклад: . Підмножини множини А: .

Множина всіх підмножин множини А називається булеаном множини А і позначається: В (А).

Теорема: кожна множина А, яка містить п елементів, має 2^п підмножин.

Теорема: порожня множина є підмножиною будь - якої множини.

Нехай дано дві множини: А і . Доведемо, що .

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

Дві множини А і В називаються рівними, коли кожний елемент множини А є елементом множини В і навпаки: ,

Властивості множин:

§ рефлективність: ;

§ симетричність: ;

§ транзитивність:

Способи завдання множин:

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

1. Довільну скінченну множину можна задати переліком усіх її елементів.

Наприклад:

- множину студентів групи можна задати їх списком у журналі;

- С={червень, липень, серпень} - множина літніх місяців.

Спосіб завдання множини переліком її елементів доцільно використовувати коли ця кількість не дуже велика. Так, множину всіх натуральних чисел, які менші 100000, можна задати переліком її елементів, але це займе дуже багато часу. У таких випадках використовують слідуючий запис: В={1; 2; 3; …; 99998; 99999}. Знак … можна використовувати тоді, коли зрозуміло, які елементи вони замінюють.

2. Завдання множин за допомогою характеристичної властивості.

Нескінченні множини неможливо задати переліком елементів, тому їх задають за допомогою характеристичної властивості

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

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

Для множин, які задаються характеристичною властивістю їх елементів, використовують запис: , де - скорочене позначення речення «елемент х має властивість Р»

Приклади:

1) - множина натуральних чисел, що при діленні на 3 дають остачу 1.

2) - множина всіх раціональних коренів рівняння.

3) - множина натуральних чисел між числами 5 і 10.

1.2 Дії над множинами

1. Об'єднанням множин А і В називається множина, яка складається з усіх тих і тільки тих елементів, які належать хоча б одній з множин А або В.

Позначається:

Об'єднання множин можна виконувати з будь - якою кількістю множин:

Для об'єднання множин справедливі слідуючи властивості:

1) комутативна:

2) асоціативна:

3) =А

4) ідемпотентність:

5) тоді і тільки тоді, коли

Діаграми (круги) Ейлера - Венна - це графічне зображення множин.

Приклад:

2. Перетином множин А і В називається множина, яка складається з усіх тих і тільки тих елементів, які належать як множині А так і множині В (спільні елементи множин).

Позначається:

Дві множини А і В називаються непересічними, якщо .

Дві множини А і В називаються пересічними, якщо .

Перетин множин можна виконувати з будь - якою кількістю множин:

Для перетину множин справедливі слідуючи властивості:

1) комутативна:

2) асоціативна:

3) =

4) ідемпотентність:

5) тоді і тільки тоді, коли

Приклад:

3. Різницею множин А і В називається множина, яка складається з тих і тільки тих елементів, які належать множині А і не належать множині В.

Позначається:

Множина

Приклад:

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

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

Для універсальних множин справедливі слідуючи співвідношення: ,

5. Доповненням множини А до універсальної множини U називається така множина, що визначається співвідношенням

Позначається:

Множини і не мають спільних елементів, тому , . Очевидно, що множина А є доповненням до , а тому .

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

Теорема:

Доведення: так як , то .

1.3 Алгебра множин

Алгебра множин являє собою сукупність тотожностей (рівностей).

Для будь - яких підмножин А, В і С універсальної множини U дійсними є такі рівності:

1) - комутативний закон

2) - асоціативний закон

3) - дистрибутивний закон

4) =А

5) ()

1'⁾ - комутативний закон

2') - асоціативний закон

3') - дистрибутивний закон

4')

5')

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

Доведемо рівність 3:

Доведення складається з двох частин:

1) Нехай , тоді або

а) якщо , то і , а отже

б) якщо , то і , а отже і , тому

2) Нехай , тоді і , тому або ( і ), а значить .

У загальному вигляді рівності 3 і 3' можна подати у такому вигляді:

Для довільних підмножин А, В універсальної множини U справедливі такі рівності:

1) якщо і , то В=.

2) =U

3) - закон ідемпотентності

4)

5) - закон поглинання

6) - закон де Моргана

7) якщо і , то

1') якщо і , то .

2')

3') - закон ідемпотентності

4') =

5') - закон поглинання

6') - закон де Моргана

7') якщо і , то

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

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

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

Узагальнення операцій над множинами:

1) перетин множин: при ;

2) об'єднання множин: при ;

3) формули де Моргана: , .

2. Вектори, відношення, відображення

2.1 Вектори і прямий добуток множин

Математика вивчає властивості певних множин елементів, відношень між ними. Найбільш поширеними і важливими для математики є відношення між парами і трійками елементів.

Якщо елементи скінченної множини як-небудь перенумеровані, то кажуть, що дана множина упорядкована. Одну і ту ж множину можна упорядкувати різними способами. Наприклад: множину учнів у класі можна впорядкувати

- по алфавіту;

- по росту;

- по вазі і т.д.

Нехай дані множини Х_1, Х₂, …Х_n. Кортежем (вектором) довжини п складеним з елементів цих множин називається скінченна послідовність б = (х₁, х₂, …х_n), де х_і є Х_і; х_і називається координатою кортежу б.

Кортеж - це упорядкований набір елементів.

Координати нумерують зліва направо.

Довжиною кортежу називається кількість його координат.

Кортеж позначають (А, В), де на першому місці елемент множини А, на другому місці елемент множини В.

Приклад: А={а, b, с}, В={1,2}

б ={(а; 1), (а; 2), (b; 1), (b; 2), (с; 1), (с; 2)}

Будь-яке слово є кортеж складений з літер. Будь-яке натуральне число - це кортеж складений з цифр.

Кортежі довжини 2 (2 елементи) називаються парами; довжини 3 - трійками; довжини n - енками.

Два кортежі рівні, якщо вони мають однакову довжину і їх відповідні координати рівні: , якщо

Приклади: а) (1; 2; 3)=(; ; )

б) (1; 2; 3)?(3; 1; 2)

Порожній кортеж - це кортеж, що не має жодної координати, його довжина дорівнює нулю.

Чим відрізняється кортеж від множини:

1) у множині порядок елементів може бути різний, а кортежі різні якщо не співпадає порядок; {а; b; с}={b; а; с}

(а; b; с)?(а; с; b)

2) у множині всі елементи різні, а у кортежі вони можуть повторюватись: {а; b; с}, (а; b; с; b)

Приклади: 1) слово «підручник» - це кортеж довжини 9: (п;і; д; р; у; ч; н; и; к)

2) число 134 - це кортеж довжини 3: (1; 3; 4)

Утворення впорядкованих m-ок (кортежів довжини m) пов'язане з операцією над множинами, яку називають знаходженням прямого або декартового добутку множин.

Розглянемо випадок, коли m=2.

Прямим (декартовим) добутком двох множин А і В називається множина всіх пар (а; b) таких, що а є А, b є В:

А Ч В ={(а; b)¦ а є А, b є В}

АЧВ =Ш, якщо А =Ш, або В = Ш, або А =В = Ш

Прямим добутком множин називається множина всіх кортежів довжини n виду , таких, що .

Прямий добуток АЧА позначають А² і називають прямим квадратом множини А.

Зауваження: АЧВ ? ВЧА.

Прямим добутком трьох множин А, В, С називається множина всіх кортежів (а, b, с) таких, що а є А, b є В, с є С.

АЧ В ЧС = {(а, b, с)| а є А, b є В, с є С}.

А Ч А Ч А =А³ - прямий куб множини А.

Якщо множини А, В, С мають потужність m, n, k, то потужність множини АЧВЧС дорівнює добутку потужностей цих множин.

|А| =m, |В| =n, |С| = k, то |А ЧВЧ С|= m · n · k.

Якщо R - множина дійсних чисел, то R² =RЧR. Геометричною ілюстрацією прямого квадрата є множина точок прямокутної системи координат на площині (х; у)

RЧRЧR=R³, геометрична ілюстрація - це множина точок тривимірного простору.

2.2 Відношення

Поняття «відношення» поширене як в математиці так і за її межами.

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

Основну ідею поняття «відношення» можна розглянути на таких прикладах:

А={3; 5; 8}, В={1; 4; 11}

Побудуємо множини правильних висловлень:

М₁={«3:1», «5:1», «8:1», «8:4»}

М₂={«3>1», «5>1», «8>1», «5>4», «8>4»}

Кожний елемент з множини М₁ є висловлення про відношення подільності, а кожний елемент з множини М₂ є висловлення про відношення «більше».

Кожне з висловлень множини М₁ можна замінити відповідною парою (а; b), в якій аА, bВ, тоді матимемо множину таких пар: ={(3; 1), (8; 1), (5; 1), (8; 4)}, яка є підмножиною прямого добутку множин А і В: (АЧВ). Отже, замість множини , яка характеризує відношення подільності в множинах А і В, можна розглядати множину відповідних пар.

Відношення «більше» в множинах А і В можна зобразити відповідною множиною пар (а; b), в яких перша компонента аА більша другої компоненти bМ, тобто є підмножиною прямого добутку множин А і В:

={(3; 1), (5; 1), (8; 1), (5; 4), (8; 4)}.

Бінарним відношенням, визначеним у множинах А і В називається кожна підмножина прямого добутку множин А і В.

Позначають: б, в, г,… С, М, Н…

Якщо А=В, то кажуть, що бінарне відношення визначене у множині А.

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

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

Якщо елементи а і b пари (а; в) перебувають у відношенні б, то позначають так: (а; в)б або а б в.

В утворенні пар бінарного відношення можуть брати участь не всі елементи множин А і В.

Способи завдання відношень.

1) переліком всіх своїх елементів;

2) характеристичною властивістю:

Множина всіх bВ, які відповідають елементу а, називаються образом а в В при відповідності Р. Множина всіх а А, яким відповідають елементи bВ називаються прообразом b в А.

Відношенням оберненим до Р (РАЧВ) називається відношення Р^-1, що є підмножиною прямого добутку ВЧА і складається з тих і тільки тих пар (b; а), для яких (а; b)Р.

Позначають: Р^-1, б -¹: (b; а)Р (а; b)Р

Приклад: А={3; 4; 6; 7}, В={2; 3; 4}. Задати Р^-1, де Р - відношення подільності.

Р={(3; 3), (4; 4), (4; 2), (6; 2), (6; 3)}, Р^-1= {(3; 3), (4; 4), (2; 4), (2; 6), (3; 6)}

З означення випливає, що обернене до відношення Р^-1 буде відношення Р: (Р ^-1)^-1 = Р

Щоб дістати стрілкове відношення Р^-1, треба стрілки відношення Р поміняти на протилежні.

Композицією відношень називається послідовне застосування двох відношень.

Композиція відношень - це операція з трьома множинами Ч, Х, Ж на яких визначені дві відповідності Р і Q: (Х; Y; Р) і (Y; Z; Q), де РXЧY, QYЧZ

Композицію позначають Р п Q, при цьому композицію відношень записують: (X, Z, P п Q), P п Q X Ч Z.

Властивості відношень.

1) рефлексивність: аА; а R а (елемент а знаходиться у відношенні R сам до себе).

Якщо властивість рефлексивності не виконується, то відношення називається антирефлексивним: аА; .

2) симетричність:а, вА, а R в в R а

Якщо властивість симетричності не виконується, то відношення називається антисиметричним:

Асиметричне відношення:

3) транзитивність:а, в, с А, а R b і b R с а R с.

Якщо властивість транзитивності не виконується, то відношення називається антитранзитивним: а, в, с А, а R b і b R с .

4) властивість повноти:а, b А, а ? b, то а R b або b R а.

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

Відношення строгого порядку, якщо воно асиметричне і транзитивне одночасно.

Відношення нестрогого порядку, якщо воно асиметричне, транзитивне і рефлексивне.

дискретний множина симетричність вектор

2.3 Відображення

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

Елемент b множини В називається образом елемента a множини А, в свою чергу елемент a називається прообразом елемента b.

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

ц: А>В або А>В.

Образ елемента a позначається: (a)ц.

Способи відображення однієї множини в іншу: 1) графічний; 2) стрілковий; 3) табличний.

ц: А>В-це відображення, яке кожному числу з множини А ставить у відповідність найменше спільне кратне цього числа і числа 4, яке входить до множини В.

(3)ц= 12 12 - образ 3, 3 - прообраз 12

(6)ц=12 12 - образ 6, 6 - прообраз 12.

(2)ц= 4 4 - образ 2, 2 - прообраз 4.

Стрілкова схема:

Табличний спосіб завдання

a	2	3	6	7
	4	12	12	28

Приклад 2. А={г; а; и; л}, В={1; 2; 3; 4; 5; 6; 7}

ц: А>В-це відображення, за яким кожній літері з множини А ставиться у відповідність її порядковий номер у слові «логарифм».

Види відображень:

Сюр'єкція - це відображення множини А в множину В, при якому для кожного елемента b з множини В знайдеться елемент a з множини А такий, що (a)ц = b.

А={2; 3; 6; 7}, В={4; 12; 28}

Стрілкове завдання: а) А={2; 3; 6; 7}

В={4; 12; 28}

Табличне завдання

a	2	3	6	7
	4	12	12	28

Якщо множини А і В скінченні, то в нижньому ряду таблиці знаходяться всі елементи множини В, хоча можливо і не один раз.

В стрілковому зображенні в кожний елемент множини В входить хоча б одна стрілка.

Сюр'єкція скінченної множини на скінченну множину існує не завжди. Щоб відображення ц: А>В було сюр'єкцією необхідно, щоб виконувалась умова ¦А¦?¦В¦.

Ін'єкція.

Відображення множини A на множину B називається ін'єкцією, якщо різним елементам множини А відповідають різні елементи множини В:

a₁?a₂ (a₁)ц ? (a₂)ц

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

Ін'єкція можлива, якщо ¦А¦?¦В¦.

А={1; 2; 3; 4}

В={10; 15; 20; 25; 30; 35; 40; 45}

Бієкція.

Якщо відображення множини А на множину В є одноразово сюрєктивним та інєктивним, то воно називається взаємно-однозначним або бієкцією множини А на множину В.

Бієкція можлива, якщо виконується рівність ¦А¦=¦В¦.

Схематично бієктивне відображення позначається так: АВ.

2.4 Функції

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

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

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

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

Символ функції використовується у двох розуміннях:

1) - це множина, елементами якої є пари , які беруть участь у відношенні між множинами та .

2) - це означення для , що відповідає .

Формальне означення функції: .

Способи задання функції:

1) перерахуванням всіх пар у вигляді таблиці

х
у

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

Якщо і , то .

Вираз, що містить функціональні знаки і символи аргументів називають формулою.

Якщо у виразі , , то будемо мати функцію від двох змінних і , яка позначається , де

Якщо і - дві функції: , , то оберненими до них є функції ,

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

Композиція функцій і : о: , для кожного визначає

Більш загальним поняттям, ніж функція є поняття функціоналу.

Функціонал встановлює залежність між деякою множиною чисел і деякою множиною функцій (залежність числа від функції).

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

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

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

2.5 Перетворення

Перетворення - це відображення множини самої на себе.

Табличний вигляд перетворення має вигляд де .

Приклад. Нехай задана множина

Для множини М можуть бути такі перетворення

а) б) в) та інші.

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

1) Тотожне перетворення - це перетворення множини М, при якому всі елементи з М залишаються на місці .

2) Постійне перетворення - це перетворення, при якому кожному елементу з множини М ставиться у відповідність деякий фіксований елемент цієї множини: .

3) Підстановка - це бієкція множини М на себе. , де , ,

Композицією перетворень ц і ш називається таке перетворення щ, який кожний елемент перетворює в образ , а потім в : :

Приклад. Нехай ц: х>х+3 - перетворення множини дійсних чисел R, яке числу х ставить у відповідність число х+3, а ш: х > х+2, тоді перетворення ю є композиція , яка кожне число х переводить у х+5: х > х+5.

ц: х > х+3

ш: х > х+2

щ: ц ? ш: x > x+5

Якщо х=3, то ц ? ш: 3 > 8

2.6 Сукупність підстановок множини М: S(М)

Розглянемо множину . Підстановками на множині М будуть

Підстановки і - рівні, бо в них область визначення (елементи 1,2,3) одна і та ж, і кожний елемент з області визначення ці підстановки переводить в одні і ті ж елементи: 1>1, 2>3, 3>2.

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

1) Покажемо, що добуток підстановок належить сукупності підстановок

Отже, якщо і , то

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

?

а)

б)

Отже, асоціативний закон виконується.

3) Перевіримо що буде, якщо множити на будь-яку підстановку з множини М.

Висновок: - виступає одиничним елементом в сукупності підстановок множини .

4) Знайдемо добуток:

Отже

2.7 Алгебраїчні операції та системи

Операцією на множині М називається відповідність, при якій з кожною парою елементів з множини М зіставлений певний елемент цієї ж множини.

Означена таким способом операція може бути множенням або додаванням і записують. а ·b= c, а + b = c.

Приклад: Дія додавання ставить у відповідність парі чисел 2 і 3 число 5.

(2; 3) > 5

Операція називається асоціативною для множення і додавання, якщо для будь-яких а, b, c є М виконується співвідношення.

Якщо операція довільна і парі елементів з М вона ставить у відповідність елемент с, то коротко це записують так: . Елемент с називають композицією.

Напівгрупа.

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

1) для кожних , композиція теж належить М;

2) дія ?, задана на М, асоціативна: тобто для кожних елементів виконується рівність ;

3) існує такий елемент , що для кожного маємо

Елемент e - називається нейтральним для дії ?; для «+» е - називається нульовим; для «·» - е називається одиничним елементом.

Приклади.

1) Множина Z - цілих чисел, відносно дії «+» - напівтрупа.

2) Множина Z цілих чисел, відносно дії множення є напівтрупа.

3) Сукупність підстановок множини М: S(M) - є напівгрупою відносно множення.

4) Множина Z⁺ додатних цілих чисел із заданою операцією не є напівгрупою.

Група.

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

1) для будь-яких , композиція

2) дія ? задана на М - асоціативна:

3) існує нейтральний елемент е:

4) для кожного існує такий елемент , що

Зауваження:

1) , то для дії «+» - b називається протилежним: а і - а (бо а+(-а)=0), бо їх сума дорівнює нейтральному елементу - 0.

2) для дії «·» b називається оберненим елементом , бо - одиничному елементу.

Приклади:

1) Множина Z усіх цілих чисел є група.

2) Множина R⁺ додатних дійсних чисел відносно множення є група.

3) S(M) - сукупність підстановок множини М є група.

4) Числа -1 і 1 утворюють групу з операцією множення.

Кожна група є напівгрупою, але не навпаки.

Дії «+» і «·» чисел мають властивості комутативності. Але вимога комутативності не входить до означення групи і напівгрупи. Це пояснюється тим, що дія множення перетворень не комутативна, а історичне поняття групи виникло саме на основі вивчення властивості дії множення підстановок.

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

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

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

Множина М називається кільцем, якщо на ній визначені одразу дві операції «+» і «·», причому

1) операція «+» - комутативна

2) операції «+» і «?» зв'язані дистрибутивними законами: ,

У кільці може не бути одиниці і обернених елементів.

Приклади:

1) Множина Z цілих чисел кільце відносно «+» і «·»

2) Множина раціональних чисел Q - кільце відносно «+» і «·».

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

Кільця раціональних чисел Q та дійсних чисел R є полями, бо для будь-якого і будь-якого знайдеться таке число , що .

, тоді

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

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

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

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

При цьому обов'язково зазначають який елемент перший, а який другий. групову операцію позначають +, · або ?.

Групою називається пара < G; f >, яка складається з множини елементів G і двомісної операції f над ними, якщо ця операція задовольняє умовам:

1) операція f асоціативна:

2) існує нейтральний елемент (елемент е множини G, що для будь-яких : )

3) існує зворотній елемент (тобто для будь-яких можна знайти свій такий, що )

Елементи множини G називаються елементами групи.

Умови 1, 2, 3 - називаються аксіомами (первинними істинами).

Якщо у групі визначена групова операція «·», то вона називається мультиплікативною.

Якщо у групі визначена групова операція «+», то така група називається адитивною.

Група називається скінченною, якщо у ній скінченна кількість елементів.

Група називається нескінченною, якщо у ній нескінченна кількість елементів.

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

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

Приклади груп:

§ число 0 утворює групу за множенням і додаванням: G = {0; +; ·}

§ число 1 утворює групу за множенням G = {1; ·}.

Размещено на Allbest.ru