Подякувати Студентському архіву довільною сумою
Admin
26.02.2023 12:38
Дякуємо, що користуєтесь нашим архівом!
Інформація про навчальний заклад
ВУЗ:
Національний університет Львівська політехніка
Інститут:
Не вказано
Факультет:
Комп'ютерна інженерія
Кафедра:
Кафедра ЕОМ
Інформація про роботу
Рік:
2007
Тип роботи:
Конспект лекцій
Предмет:
Дискретна математика
Частина тексту файла (без зображень, графіків і формул):
Міністерство Освіти і Науки України
Національний Університет “Львівська Політехніка”
Кафедра ЕОМ
Конспект лекцій
з курсу “Дискретна математика” для студентів базового напрямку 6.0915 “Комп’ютерна інженерія”
Затверджено на засіданні кафедри Електронних Обчислювальних Машин Протокол № від
Львів – 2007
Конспект лекцій з курсу “Дискретна математика” для студентів базового напрямку 6.0915 “Комп’ютерна інженерія” / Укладач: Р. Попович – Львів: Національний університет “Львівська політехніка”, 2007, с.
Укладач: Р. Попович, к.т.н., доцент
Відповідальний за випуск: Мельник А. О., професор, завідувач кафедри ЕОМ
Рецензенти:
Елементи теорії множин
Вступ
Дискретна математика є розділом математики, що зародилася в давні часи. Її головною відмінністю є дискретність, тобто антипод неперервності. Дискретна математика включає традиційні розділи математики, які вже сформувалися (математичну логіку, алгебру, теорію чисел), і нові, що інтенсивно розвиваються.
У більш як двотисячорічній історії дискретної математики сучасний період є одним із найінтенсивніших періодів її розвитку: дуже швидко розширюється сфера застосування, інтенсивно зростають обсяги нової інформації та кількість нових результатів. Якщо ще порівняно недавно ця наука була сферою інтересів лише вузького кола фахівців, то тепер вона перетворюється на наукову дисципліну, дуже важливу й потрібну для багатьох, а у сфері сучасної освіти – для всіх.
Масове використання обчислювальної техніки та інформаційних технологій значно розширює сферу прикладних досліджень, у яких все більше застосовується апарат дискретної математики.
Базовим розділом як дискретної математики, так і взагалі всієї математики, є теорія множин.
Коротка історична довідка
Основи теорії множин були закладені відомим німецьким математиком Георгом Кантором у другій половині минулого століття. Поява теорії множин була зустрінута з ентузіазмом багатьма авторитетними математиками. Вони побачили в ній можливість створення метамови математики, тобто формальної одностайної системи понять і принципів, за допомогою якої можна було б викласти з єдиних позицій зміст різноманітних традиційно далеких один від одного розділів математики. Перші такі досить успішні спроби були виконані вже незабаром після виникнення канторівської теорії множин.
Однак пізніші дослідники виявили в теорії Кантора чимало суперечностей: так званих парадоксів або антиномій теорії множин. Виникла кризова ситуація. Одна частина математиків, посилаючись на штучність сформульованих антиномій, вважала за краще не помічати ці суперечності або не надавати їм великого значення. У той час як інша (скажімо, відповідальніша) група математиків зосередила свої зусилля на пошуках більш обгрунтованих та точних принципів і концепцій, на яких могла б бути побудована несуперечлива теорія множин.
У результаті було запропоновано кілька формальних (або аксіоматичних) систем, які служать фундаментом сучасної теорії множин, а значить, фундаментом всієї класичної математики. Важливість цих досліджень серед іншого підкреслює той факт, що значний внесок у становлення аксіоматичної теорії множин зробили такі видатні математики і мислителі XX століття, як Б.Рассел, Д.Гільберт, К.Гедель та ін.
Сьогодні теорія множин - це математична теорія, на якій грунтується більшість розділів сучасної математики, як неперервної, так і дискретної.
Поняття множини. Способи задання множин
Для наших цілей достатньо буде викладення основ так званої інтуїтивної або наївної теорії множин, яка в головних своїх положеннях зберігає ідеї та результати засновника теорії Г.Кантора.
В інтуїтивній теорії множин поняття "множина" належить до первинних невизначальних понять, тобто воно не може бути означено через інші більш прості терміни або об’єкти, а пояснюється на прикладах, апелюючи до нашої уяви та інтуіції. Такими поняттями в математиці є також поняття "число", "пряма", "точка", "площина" тощо.
Канторівський вираз: "Множина - це зібрання в єдине ціле визначених об’єктів, які чітко розрізняються нашою інтуіцією або нашою думкою" - безумовно не може вважатися строгим математичним означенням, а є скоріше поясненням поняття множини, яке заміняє термін "множина" на термін "зібрання". Іншими синонімами основного слова "множина" є "сукупність", "набір", "колекція", "об’єднання" тощо.
Прикладами множин можуть служити: множина десяткових цифр, множина літер українського алфавіту, множина мешканців Києва, множина парних чисел, множина розв’язків деякого рівняння та ін.
На письмі множини позначаються, як правило, великими літерами. Для деяких множин у математиці вживаються сталі позначення. Наприклад, N - множина натуральних чисел, Z - множина цілих чисел, Q - множина раціональних чисел, R - множина дійсних чисел, C - множина комплексних чисел тощо.
Об’єкти, з яких складається задана множина, називають її елементами. Елементи множин позначатимемо малими літерами латинського алфавіту. Той факт, що об’єкт a є елементом множини M записується так: a(M (читається: "a належить M" або"a є елемент M"). Для того, щоб підкреслити, що деякий елемент a не належить множині M, вживають позначення a(M.
Запис a,b,c,...(M використовують для скорочення запису a(M, b(M, c(M,....
Множину називають скінченною, якщо кількість її елементів скінченна, тобто існує натуральне число k, що є числом елементів цієї множини. В іншому разі множина є нескінченною.
Множина є визначеною, коли можна встановити, чи є будь-який об’єкт її членом чи ні.
Для задання множини, утвореної з будь-яких елементів, будемо використовувати два такі способи. В основі обох із них лежить позначення множини за допомогою фігурних дужок.
1. Якщо a1,a2,...,an - деякі об’єкти, то множина цих об’єктів позначається через {a1,a2,...,an}, де у фігурних дужках міститься перелік усіх елементів відповідної множини. З останнього зауваження випливає, що в такий спосіб можуть бути задані тільки скінченні множини. Порядок запису елементів множини при цьому позначенні є неістотним.
Так, множина десяткових цифр записується {0,1,2,3,4,5,6,7,8,9}, множина основних арифметичних операцій - {+,-,*,/} або {*,/,+,-}, множина розв’язків нерівності (x-1)2 ( 0 - {1}.
Слід пікреслити, що однією з основних ідей канторівської теорії множин був розгляд множини як нового самостійного об’єкта математичного дослідження. Тому необхідно розрізняти такі два різні об’єкти, як елемент a і множина {a}, яка складається з єдиного елемента a. Зокрема, множини можуть виступати в ролі елементів якоїсь іншої множини. Наприклад, множина всіх можливих невпорядкованих пар з елементів a, b і c (елементи в парі не співпадають) D = {{a,b},{a,c},{b,c}} складається з трьох елементів і задана цілком коректно.
2. Другий спосіб задання множин грунтується на зазначенні загальної властивості або породжувальної процедури для всіх об’єктів, що утворюють описувану множину.
У загальному випадку задання множини M має вигляд: M = {a | P(a)}.
Цей вираз читається так: "множина M - це множина всіх таких елементів a, для яких виконується властивість P", де через P(a) позначено властивість, яку мають елементи множини M і тільки вони.
S = { n | n - непарне число } або S = { n | n = 2k+1, k(Z },
X = { x | x = (k, k(Z },
F = { fi | fi+2 = fi+1 + fi, i(N, f1 = f2 = 1 }.
Другий спосіб є більш загальним способом задання множин. Наприклад, введену вище множину D всіх невпорядкованих пар з елементів a, b і c можна задати так
D = { {x,y} | x({a,b,c}, y({a,b,c} і x ( y}. (1.1)
У теорії множин використовується поняття порожньої множини. Вона позначається символом (.
Множина може взагалі не містити елементів, наприклад
S = {x | x – непарне число, що ділиться на 2} = (;
K = {x | x ( R, x2 + 1 = 0} = (.
Для позначення цього факту вводиться поняття порожньої множини.
Це поняття відіграє дуже важливу роль при заданні множин за допомогою опису. Так, без поняття порожньої множини не можна говорити про множину відмінників студентської групи або про множину дійсних коренів квадратного рівняння, не пересвідчившись заздалегідь, чи є в студентській групі відмінники або чи має задане рівняння дійсні корені. Поняття порожньої множини дає змогу оперувати множиною відмінників групи, не турбуючись про те, чи є відмінники в групі, яка розглядається. Порожню множину умовно відносять до скінченних множин. Число елементів у ній рівне 0.
Таким чином, уведення порожньої множини дає можливість оперувати будь-якою множиною без попереднього застереження, існує вона чи ні.
Операції над множинами
Розглянемо дві множини А і В та введемо низку операцій над ними. Для графічної ілюстрації використовують діаграми (кола) Ейлера. Для зображення множини на площині креслять замкнену лінію із заштрихованою внутрішньою областю (найчастіше – це коло, звідси й назва відповідного інструмента, що широко застосовується в теорії множин).
Об’єднання А і В – множина, що складається з усіх елементів множини А, всіх елементів множини В і не містить ніяких інших елементів (рис. 1), тобто
А ( В = {x | x ( А або x ( В}.
Рис. 1
Переріз А і В – множина, що складається з тих і тільки з тих елементів, які належать одночасно множині А та множині В (рис. 2), тобто
А ( В = {x | x ( А і x ( В}.
Рис. 2
Різниця А і В (відносне доповнення) – множина, що складається з тих і тільки тих елементів, які належать множині А й не належать множині В (рис. 3), тобто
А \ В = {x | x ( А і x ( В}.
Рис. 3
Диз’юнктивна сума А і В (симетрична різниця) – множина, що складається усіх елементів А, які не належать множині В, й усіх елементів В, які не належать множині А, та яка не містить ніяких інших елементів (рис. 4), тобто
А ( В = {x | (x ( А і x ( В) або (x ( В і x ( А)}.
Рис. 4
Доповнення множини.
Звичайно, вже в означенні конкретної множини явно або неявно обмежується сукупність об’єктів, що є допустимими. (Слони – серед тварин, натуральні числа – серед цілих або дійсних залежно від контексту). Зручно сукупність допустимих об’єктів зафіксувати явно та вважати, що множини, які розглядаються, складаються з елементів цієї сукупності. Її називають основною множиною (універсумом) і позначають U. Універсум U арифметики – числа, універсум U зоології – тварини і т.д. Будь-яку множину розглядатимемо у зв’язку з універсумом, який на діаграмах Ейлера асоціюватимемо з прямокутником на площині, всередині якого зображатимемо множини (рис. 5).
Рис. 5
Доповнення множини А – це множина, що містить усі елементи універсуму, за винятком елементів А (рис. 6), тобто .
Рис.6
Множина А називається підмножиною множини В, якщо кожен елемент А є елементом В. Для позначення цього факту вводиться знак ( - символ строгого включення (або ( - символ нестрогого включення) (рис. 7). Якщо необхідно підкреслити, що множина В містить також інші елементи, крім елементів множини А, то використовують символ строгого включення А ( В.
Дві множини рівні, якщо вони складаються з одних і тих самих елементів. Справджується таке: А = В тоді і тільки тоді, коли А ( В і В ( А.
Рис. 7
Окремо розглянемо ще одну дуже важливу операцію над множинами.
Декартовим (прямим) добутком множин A і B (записується A(B) називається множина всіх пар (a,b), в яких перша компонента належить множині A (a(A), а друга - множині B (b(B).
Тобто
A(B = {(a,b) | a(A і b(B }
Декартовий добуток природно узагальнюється на випадок довільної скінченної сукупності множин. Якщо A1, A2,..., An - множини, то їхнім декартовим добутком називається множина
D = { (a1,a2,...,an) | a1(A1, a2(A2,..., an(An },
яка складається з усіх наборів (a1,a2,...,an), в кожному з яких i-й член, що називається i-ю координатою або i-ю компонентою набору, належить множині Ai, i=1,2,...,n. Декартовий добуток позначається через A1( A2(...( An.
Набір (a1,a2,...,an), щоб відрізнити його від множини, яка складається з елементів a1,a2,...,an, записують не у фігурних, а в круглих дужках і називають кортежем, вектором або впорядкованим набором. Довжиною кортежу називають кількість його координат. Два кортежі (a1,a2,...,an) і (b1,b2,...,bn) однакової довжини вважаються рівними тоді і тільки тоді, коли рівні їхні відповідні координати, тобто ai=bi, i=1,2,...,n. Отже, набори (a,b,c) і (a,c,b) вважаються різними, в той час як множини {a,b,c} і {a,c,b} - рівні між собою.
Декартовий добуток множини A на себе n разів, тобто множину A(A(...(A називають n-м декартовим (або прямим) степенем множини A і позначають An.
Прийнято вважати, що A0 = ( (n=0) і A1 = A (n=1).
Наприклад, якщо A = {a,b} і B = {b,c,d}, то
A(B = {(a,b),(a,c),(a,d),(b,b),(b,c),(b,d)},
A2 = {(a,a),(a,b),(b,a),(b,b)}.
Якщо R - множина дійсних чисел або множина точок координатної прямої, то R2 - це множина пар (a,b), де a,b(R, або множина точок координатної площини.
Координатне зображення точок площини вперше було запропоновано французьким математиком і філософом Рене Декартом, тому введена теоретико-множинна операція і називається декартовим добутком.
Множину, елементами якої є всі підмножини множини А, називають множиною підмножин множини А і позначають Р(А). Так, для триелементної множини А = {a, b, c} маємо P(A)={(, {a}, {b}, {c}, {a, b},{b, c}, {a, c}, {a, b, c}}. У разі скінченної множини А з n елементів, множина підмножин Р(А) містить 2n елементів.
Алгебра множин
Операції над множинами, як і операції над числами, мають деякі властивості (табл.). Останні виражаються сукупністю тотожностей незалежно від конкретного вмісту множин, що входять у ці тотожності та є підмножинами деякого універсуму U.
Таблиця
Комутативний закон
1а) А ( В = В ( А
1б) А ( В = В ( А
Асоціативний закон
2а) А ( (В ( С) = (А ( В) ( С
2б) А ( (В ( С) = (А ( В) ( С
Дистрибутивний закон
3а) А ( (В ( С) = (А ( В) ( (А ( С)
3б) А ( (В ( С) = (А ( В) ( (А ( С)
Властивості ( та U
4а) А ( ( = A
4б) А ( U = A
5а)
5б)
6а) А ( U = U
6б) А ( ( = (
7а)
7б)
Закон самопоглинання
8а) А ( A = A
8б) А ( A = A
Закон поглинання
9а) А ( (А ( В) = А
9б) А ( (А ( В) = А
Правило де Моргана
10а)
10б)
Властивості доповнення, різниці та рівності
11) А ( В = U і А ( В = ( (
12)
13)
14)
15) А ( В = В ( А
16) А ( (В ( С) = (А ( В) ( С
17) А ( ( = ( ( A = A
18) А ( В ( А ( В = А ( А ( В = В (
19)
Основний метод доведення тотожностей в алгебрі множин ґрунтується на згаданому раніше факті: А = В тоді і тільки тоді, коли А ( В і В ( А. Доведемо, наприклад, тотожність 3а) А ( (В ( С) = (А ( В) ( (А ( С).
Доведемо, що А ( (В ( С) ( (А ( В) ( (А ( С). Для цього візьмемо будь-яке x ( А ( (В ( С), тоді за означенням операцій ( та ( маємо x ( А або (x ( В і x ( С). За законом дистрибутивності “або” відносно “і” (x ( А або x ( В) і (x ( А або x ( С), тобто x ( А ( В і x ( А ( С. Це рівносильно x ( ( А ( В) ( (А ( С), що й треба було довести.
Доведемо тепер, що (А ( В) ( (А ( С) ( А ( (В ( С). Для цього візьмемо будь-яке x ( (А ( В) ( (А ( С). Звідси (x ( А або x ( В) і (x ( А або x ( С). Це рівносильно x ( А або (x ( В і x ( С), тобто x ( А ( (В ( С), що й потрібно було довести.
Таким чином, А ( (В ( С) = (А ( В) ( (А ( С).
Із властивості асоціативності операції об’єднання множин випливає, що об’єднання кількох множин можна виконати, послідовно об’єднуючи їх, причому порядок входження множин не впливає на результат: А ( (В ( С) = (А ( В) ( С = А ( В ( С. Отже, об’єднання сукупності множин можна подати співвідношенням: .
Аналогічно на n множин узагальнюється операція перерізу: .
Використовуючи узагальнення операцій об’єднання та перерізу на n множин, можна узагальнити також інші співвідношення, наприклад закон де Моргана, який в узагальненому вигляді записується так: і .
Зауважимо, що операція декартового добутку неасоціативна і некомутативна, тобто множини (A(B)(C і A((B(C), а також множини A(B і B(A, взагалі кажучи, не рівні між собою.
Зв’язок декартового добутку з іншими теоретико-множинними операціями встановлюється такими тотожностями:
(A ( B) ( C = (A(C) ( (B(C),
(A(B) ( C = (A(C)((B(C),
A ( (B ( C) =(A(B) ( (A(C),
A ( (B(C) =(A(B)((A(C).
Сукупність підмножин A1, A2, …, An множини A називається розбиттям множини A, якщо:
1. ;
2. Ai ( Aj = (, i ( j.
Парадокси теорії множин
Слово "парадокс" грецького походження і перекладається українською мовою - несподіваний, дивний. Вживають це слово у відношенні до висловлювання (положення, ідеї), яке суттєво різниться від загальноприйнятого традиційного уявлення з даного приводу. Вживання терміна "парадокс" стосовно до тих суперечностей, які були виявлені різними математиками в теорії множин Г.Кантора, є наївною спробою зменшити їхнє значення і надати їм характеру логічних курйозів, штучних, неприродних конструкцій. Більш точно суть явища передає назва, "антиномії теорії множин", оскільки термін антиномія є синонімом терміна суперечність. Але за традицією, будемо називати сформульовані нижче положення парадоксами.
Парадокс Б.Рассела. Для будь-якої множини M коректним є питання: чи множина M належить собі як окремий елемент, тобто чи є множина M елементом самої себе, чи ні? Наприклад, множина всіх множин є множиною і тому належить сама собі, а множина всіх будинків у місті не є будинком, множина студентів в аудиторії не є студентом.
Отже коректно поставити сформульоване питання і щодо множини всіх множин, які не будуть власними елементами. Нехай M - множина всіх тих множин, що не є елементами самих себе. Розглянемо питання: а сама множина M є елементом самої себе чи ні? Якщо припустити, що M(M, то з означення множини M випливає M(M. Якщо ж припустимо, що M(M, то з того ж таки означення дістанемо M(M.
Близьким до парадокса Рассела є так званий "парадокс цирульника": цирульник - це мешканець міста, який голить тих і тільки тих мешканців міста, які не голять самі себе. Проводячи міркування, аналогічні тим, що були зроблені в парадоксі Рассела, дійдемо висновку, що цирульник голить себе в тому і тільки в тому випадку, коли цирульник не голить сам себе.
Багато хто з математиків на початку ХХ ст. не надавали цим парадоксам особливого значення, оскільки в той час теорія множин була відносно новою галуззю математики і не зачіпала інтересів більшості математиків. Однак їхні більш відповідальні та проникливі колеги зрозуміли, що виявлені парадокси стосуються не тільки теорії множин і побудованих на ній розділів класичної математики, але мають безпосереднс відношення до логіки взагалі, тобто до головного інструменту математики.
Зокрема, парадокс Рассела може бути переформульований в термінах логіки і таким чином доданий до відомих з давніх часів логічних парадоксів (парадокса брехуна, парадокса всемогутньої істоти тощо).
Якщо проаналізувати всі парадокси теорії множин, то можна зробити висновок, що всі вони обумовлені необмеженим застосуванням так званого принципу абстракції (або принципу згортання), згідно з яким для будь-якої властивості P(x) існує відповідна множина елементів x, які мають властивість P(x). Якщо відкинути це припущення, то всі відомі парадокси теорії множин стають неможливими.
В усіх існуючих аксіоматичних теоріях множин неможливість антиномій ґрунтується на обмеженнях принципу згортання.
Відображення
Визначення і приклади
Нехай задано дві множини Х і Y. Відображення f з областю визначення Х та областю значень Y кожному елементу х з множини Х ставить у відповідність деякий (але єдиний) елемент f (х) з множини Y. Елемент f (х) називають образом елемента х при відображенні f. Символічно відображення записується наступним чином: f : Х ( Y чи XY. У випадку Y = Х кажуть ще про відображення f множини Х в (на) себе.
Варто розрізняти відображення f і елемент f (x), що відповідає елементу х при цьому відображенні. Наприклад, неправильно (але зручно) казати „функція sin х”, правильно – „функція sin”. Цю неточність звичайно виправляють, вказуючи, що задано функцію x ( sin x, чи, що функція f визначена рівністю f (х) = sin x.
Множина f -1(у) = {x | f (x) = y, x ( X} називається (повним) прообразом елемента y при відображенні f.
Якщо Х = {x1, x2, …, xn} тo відображення f : Х → Y, можна задати записом з двох рядків f = , де f (хi) ( Y, i = 1, 2, …, n.
Наприклад, f : Х → Y, Х = {l, 2, 3, 4, 5}, Y = {а, b, c}, f = . Тоді повні прообрази - це f -1(a) = {1, 2, 5}, f -1(b) = {3}, f -1(c) = {4}.
Відображення часто ілюструють за допомогою діаграм (Рис. 8), де відповідність між елементами показують стрілками. Відображення задане в попередньому прикладі зображене на рис. 8.а. Відповідності рис. 8.б та рис. 8.в відображеннями не будуть, оскільки на рис. 8.б елемент 1 ( X не має образу в множині Y, а на рис. 8.в елементу 3 ( X ставиться у відповідність два елементи з множини Y, h (3) = b та h (3) = c.
Приклади відображень:
1) f (x) = є відображенням множини відмінних від нуля елементів множини дійсних чисел R в R. Було б неточно казати, що область визначення відображення співпадає з множиною R, оскільки х не може приймати всі дійсні значення. Але цілком можна розглядати відображення з R в R типу: g(x) = для x ≠ 0 і g(0) = 2 або відображення з R в R1 : h(x) = для x ≠ 0 і h(0) = +∞, де множина R1 утворена об’єднанням R i деякого додаткового елемента +∞.
Рис. 8
2) Якщо, Х - множина дійсних функцій φ(х), визначених та інтегрованих на інтервалі [a, b], то інтеграл є відображенням з Х в множину дійсних чисел R.
3) Якщо X - множина кривих скінченної довжини на площині, то можна визначити відображення з Х в множину R+ додатних дійсних чисел, яке кожній кривій ставить у відповідність її довжину.
Деякі часткові випадки
1. Відображення f множини Х в множину Х, визначене рівністю f (х) = х, називається тотожним.
2. Якщо Х є підмножиною Y, то відображення Х в Y , визначене рівністю f (х) = х, називається канонічною ін’єкцією Х в Y.
3. Відображення з прямого добутку множин Х ( Y в X, що ставить у відповідність кожній парі (x, y) ( Х ( Y елемент х ( Х, називається проекцією на множину X. Аналогічно визначається проекція на множину Y .
4. Нехай Х, Y, Z - три множини. Відображення f множини Х ( Y в множину Z кожній парі (x, y) ( Х ( Y ставить у відповідність деякий елемент із Z, що позначається через f (z) = f (x, y). Кажуть, що f є функцією двох змінних. Наприклад, якщо Х є множиною дійсних функцій дійсної змінної, інтегровних на будь-якому скінченному інтервалі з фіксованим початком а, то інтеграл визначає деяке відображення Х ( R в R, оскільки це відображення є функцією двох змінних: φ ( Х і b ( R.
5. Якщо розглядати відображення з X в Y ( Z, то воно має вигляд х → (f (x), g(x)), де f (відповідно g) є відображенням з X в Y (відповідно в Z ). Задання такого відображення еквівалентне заданню системи двох функцій.
6. У загальному випадку задання відображення деякого декартового добутку Х1 ( Х2 ( ... ( Хn у декартовий добуток Y1 (Y2 ( ... ( Ym рівносильне завданню системи m функцій від n змінних.
7. Відображення f множини X в множину Y називають постійним, якщо для всіх х ( Х елемент f (х) рівний тому самому елементу з множини Y.
Ін’єктивні, сюр’єктивні та бієктивні відображення
Відображення f множини Х в множину Y називають ін’єктивним, чи ін’єкцією, якщо два різних елементи з Х мають образами при відображенні f два різних елементи з Y (Рис. 9 а) та в)). Канонічна ін’єкція деякої підмножини в саму множину є ін’єктивним відображенням.
Відображення f називають сюр’єктивним, чи сюр’єкцією, якщо кожен елемент з Y є образом при відображенні f принаймні одного елемента з X (Рис. 9 б) та в)).
Відображення f називається бієктивним, чи бієкцією, якщо кожен елемент із Y є образом при відображенні f деякого, і при тому єдиного, елемента з X (Рис. 9 в). Відображення бієктивне тоді і тільки тоді, коли воно одночасно ін’єктивнe й сюр’єктивнe. Бієкція множини на себе називається також перестановкою чи перетворенням.
Визначивши поняття ін’єкції, сюр’єкції та бієкції, введемо поняття образу і прообразу підмножини, а потім ще раз повернемося до властивостей ін’єкції, сюр’єкції та бієкції.
Образ і прообраз підмножини
Нехай маємо відображення f : X → Y та A – підмножина множини Х. Позначимо через f (A) підмножинy множини Y, утворену зі всіх елементів f (x), x ( A, тобто f (A) = {f (x) | x ( A}.
Підмножина f (A) називається образом підмножини А при відображенні f.
Наприклад: для відображення f = з множини Х={l, 2, 3, 4} у множину Y = {y1, y2, y3} маємо f ({1, 3, 4}) = {y1, y3}.
Очевидно, що f (Ø) = Ø. Виходячи з відображення f, ми тим самим визначаємо деяке відображення A → f (A) множини Р(Х) у множину Р(Y). Це відображення зберігає символи (, ( у тому сенсі, що коли А ( B, то f (A) ( f (B), f (A ( B) = f (A) ( f (B). Однак символ ( при цьому відображенні не зберігається, бо має місце лише включення, тобто f (A ( B) ( f (A) ( f (B). Дійсно, нехай f - постійне відображення, тобто f (x) = b для всіх x ( X, A i B – підмножини множини Х, що не перетинаються. Оскільки A ( B = Ø, то f (A ( B) = Ø і це не збігається з f (A) ( f (B) = {b}.
Нехай тепер В є деякою підмножиною множини Y. Будемо позначати через f -1(В) підмножину множини Х, утворену з усіх таких елементів х, що f (х) ( В, тобто f -1(B) = {x | x ( Х, f (x) ( B}.
Підмножина f -1(B) називається прообразом підмножини В при відображенні f.
Очевидно, f -1(Ø) = Ø. Може виявитися, що f -1(B) = Ø при B ≠ Ø. Наприклад, f : х → х2 відображення множини R в R, тоді f -1({-1}) = Ø. Тим самим ми зв’язали з відображенням f відображення B → f -1(B) множини Р(Y) в множину Р(X). Це відображення зберігає символи (, (, ( у тому сенсі, що коли А ( В, то f -1(A) ( f -1(B), f -1(A ( B) = f -1(A) ( f -1(B), f 1(A) ( f 1(B) = f 1(A) ( f 1(B).
Рис. 9
Визначення прообразу підмножини зовсім не припускає бієктивності відображення f. У всякому разі, якщо y ( Y, тo можна говорити про f 1({y}), але це деяка підмножина множини Х, а не елемент множини X. Ця підмножина може містити більше одного елемента, а може виявитися і порожньою.
Тепер повернемося знову до властивостей ін’єктивності, сюр’єктивності та бієктивності відображень, враховуючи при цьому введені раніше визначення образу і прообразу підмножини.
Розглядаємо відображення f : Х → Y. Можна сказати, що це відображення сюр’єктивне, якщо для будь-якого елемента y ( Y його прообраз f 1({y}) відносно цього відображення не порожній. Іншими словами, для будь-якого елемента y ( Y існує такий елемент x ( Х, щоy = f (х). Тоді f (Х) = Y і для довільного y ( Y справедлива умова f 1({y}) ≠ Ø.
Для скінченних множин Х и Y сюр’єктивнiсть відображення f : X → Y означає, що | Х | ≥ | Y |. Наприклад; f : {1, 2, 3, 4} → {y1, y2, y3}, f = - сюр’єктивне, a f = - не сюр’єктивнe.
Відображення f : X → Y ін’єктивне, якщо для будь-якого елемента y ( Y його прообраз f 1({y}) містить не більш одного елемента (порівняйте з раніше сказаним). Іншими словамиf : X → Y ін’єктивне, якщо для будь-яких x ≠ x1, x, x1 ( Х, f (x) ≠ f (x1). Якщо Х і Y скінченні, то ін’єктивність відображення означає, що | Х | ≤ | Y |.
Наприклад, нехай Х = {l, 2, 3}, Y = {y1, y2, y3, y4}. Якщо f (1) = y1, f (2) = y2, f (3) = y3, то f : X → Y ін’єктивнe.
Бієктивне відображення f : X → Y є одночасно ін’єктивним та сюр’єктивним. Із сюр’єктивності випливає, що | f 1({y}) | ≥ 1 для будь-якого y ( Y, а з ін’єктивності випливає, що | f 1({y}) | ≤ 1 для кожного y ( Y. Отже, бієктивність f означає, що | f 1({y}) | = 1 для будь-якого y ( Y, тобто умова y = f (x) для кожного y ( Y однозначно визначає єдине значення x ( Х. Кажуть, що бієктивне відображення встановлює взаємно однозначну відповідність між множинами X та Y. При скінченних X та Y в цьому випадку | X | = | Y |.
Наприклад, X = (1, 2, 3), Y = {y1, y2, y3}, відображення f = - бієктивне.
Множина відображень
Якщо Х та Y довільні множини, то можна говорити про деяку нову множину - множину відображень з множини X в множину Y. Наприклад, якщо Х = {x1, x2}, то множина відображень X в Y може бути бієктивно відображена в декартовий добуток Y2, бо кожне відображення X в Y повністю визначається парою (y1, y2) ( Y2 образів y1, y2 елементів x1, x2 з множини Х.
Далі, якщо Х = {x1, x2, …, xk} тo множину відображень X в Y можна бієктивно відобразити в декартовий добуток Yk, оскільки кожне таке відображення рівносильне заданню набору (у1, y2, ..., уk) ( Yk образів елементів x1, x2, …, xk при цьому відображенні.
Тому множину відображень Х в Y прийнято позначати YХ. Далі наведемо різні підмножини множини YХ.
1) множина неперервних відображень Х в Y, якщо Х та Y метричні простори;
2) множина лінійних відображень Х в Y, якщо X і Y векторні простори;
3) сім’ю (xj)j ( J елементів з X, помічених індексами з множини J, можна розглядати як відображення з множини J в множину Х. Множина сімей елементів з X, помічених індексами з J, є не чим іншим, як множиною ХJ відображень з J в X;
4) послідовність елементів з множини Х можна визначити як сім’ю елементів з X, помічених індексами з множини N натуральних чисел, або ж як відображення з N в Х. Множина всіх послідовностей елементів з Х є множиною ХN;
5) можна говорити про послідовність з індексами з множини Z цілих чисел чи про скінченну послідовність, помічену індексами із скінченної множини цілих чисел 1, 2, ..., k. Завжди слід уточнювати зміст виразу „послідовність” при неспівпаданні множини індексів з множиною натуральних чисел.
Композиція відображень
Нехай задано два відображення: f : X → Y та g: Y → Z. Тоді композицією відображень f і g (позначаємо символом g ○ f) будемо називати відображення з множини X в множину Z, визначене виразом g ○ f (x) = g(f (x)) для всіх елементів x з множини X. Прийняте правило, згідно з яким у композиції g ○ f треба починати з відображення f, розташованого праворуч.
Нехай A ( X, тоді g ○ f (А) = g(f (A)), де f (А) – образ підмножини A при відображенні f. Якщо B ( Z, тo (g ○ f ) -1(B) = f -1(g-1(B)).
Композиція відображень асоціативна, тобто якщо маємо три відображення f : X → Y, g: Y → Z, h: Z → U, то (h ○ g) ○ f = h ○ (g ○ f) = h ○ g ○ f.
Відображення g: Y → X називається оберненим до відображення f : X → Y, якщо виконуються такі умови f -1 ○ f = IX (IX - тотожне відображення на множині X), f ○ f -1 = IY (IY - тотожне відображення на множині Y). Для відображення f існує обернене відображення f -1 тоді і тільки тоді, коли це відображення f є бієктивним. Обернене відображення f -1 також є бієктивним.
Якщо f :X → Y - бієкція й g: Y → Z - бієкція, то g ○ f - бієкція з Х в Z, а її обернена бієкція дорівнює f -1 ○ g -1.
Нехай маємо відображення f : X → Y та підмножину A ( X. Тоді відображення fA: A → Y, визначене виразом fA(х) = f (x) для x ( А, називається звуженням f на А и позначається f | А. Кажуть також, що f є продовженням на X відображення fA множини А в множину Y. Найчастіше в цьому випадку продовжують писати f замість fA. Аналогічно, якщо f : X → Y i f (X) ( В, то f визначає деяке відображення fB: Х → B, що задається виразом fB(х) = f(х). Практично завжди замість fB пишуть f.
Приклади розв’язання задач
1. Використавши метод подвійного включення, перевірити справедливість твердження A \ (B ( C) = (A \ B) ( (A \ C).
Розв’язування: Спочатку доведемо, що (A \ B) ( (A \ C) ( A \ (B ( C). Нехай довільне x ( (A \ B) ( (A \ C), тоді, відповідно до означення перетину x ( (A \ B) і x ( (A \ C). За означенням різниці множин запишемо x ( A і x ( B і x ( A і x ( C. Використавши властивості комутативності, асоціативності та ідемпотентності логічної зв’язки „і” останнє перепишемо як x ( A і x ( B і x ( C. Звідси x ( A і x ( (B ( C), а отже x ( A \ (B ( C). З останнього робимо висновок: якщо x ( (A \ B) ( (A \ C), то x ( A \ (B ( C), що не відповідає лівій частині заданого твердження, а отже твердження не є справедливим.
Перевірка зворотнього включення не має змісту, тому що навіть пряме не справдилося.
2. Використавши метод еквівалентних перетворень довести, що A ( (B ( C) = = (A ( B) ( (A ( C).
Розв’язування: Аналізуючи праву та ліву частину твердження можна інтуїтивно відчути, що перетворення правої частини тотожності до лівої буде простішим. Отже:
(A ( B) ( (A ( C) = = = = = = = = = = = = = = A ( (B ( C) \ (B ( C) = = A ( (B ( C).
Тотожність доведено.
3. Дослідити властивості (ін’єктивність, сюр’єктивність та бієктивніть) відображення f : X → Y, де X = { прямокутники }, Y ( R+, f (x) = площа (x).
Розв’язування: Введемо такі позначення. Довільний прямокутник x можна подати як впорядковану пару довжин його сторін (ax, bx) де ax та bx – додатні дійсні числа, тоді відображення f (x) = площа (x) визначатиметься виразом f (x) = sx = ax(bx.
a) ін’єктивність. Візьмемо довільне s ( Y та виберемо прямокутник зі сторонами ax і bx =. Тоді для довільного ax, площа f (x) == s. Отже, довільне число прямокутників матимуть один образ s, тому задане відображення не є ін’єктивним;
б) сюр’єктивність. Подібно до наведених вище міркувань візьмемо довільне y ( Y та зафіксуємо одну із сторін прямокутника ax = 1. Тоді bx = y і для кожного додатнього цілого числа y ( Y у множині X знайдеться прямокутник зі сторонами (1, y). Значить, відображення сюр’єктивне;
б) бієктивність. Оскільки задане відображення не ін’єктивне, то за означенням воно не є бієктивне.
Відношення
Розглянемо декартовий добуток к-го степеня множини Х: Хк = Х ( Х ( ... ( Х. Довільну підмножину R множини Хк (R ( Хк) будемо називати к-арним відношенням, заданим на множині Х. Вважатимемо, що впорядковані елементи x1, x2, …, xn ( Х знаходяться між собою у відношенні R, коли (x1, x2, …, xn) ( R. Одномісні відношення, які ще називаються унарними, відповідають підмножинам множини X. Надалі особливу увагу будемо приділяти бінарним відношенням (k = 2), які для стислості будемо називати просто відношеннями, якщо не обумовлено противного. Якщо на Х задано відношення R ( X 2, то запис x R х' означає, що x і х' знаходяться у відношенні R, тобто (x, х') ( R.
Областю визначення відношення R називаємо множину (R = {x | (( y : (x, y) ( R}, а областю значень - множину (R = {x | (( y : (y, x) ( R}. Для відношень звичайним чином визначені теоретико-множинні операції об’єднання, перетину і т.д. Доповненням відношення R ( X 2 вважаємо множину . Оберненим відношенням до відношення R називається відношення, задане множиною R-1 = {(x, y) | (y, x) ( R}. Образом множини Х відносно R називається множина R(Х) = {y | існує таке х ( Х, що (х, у) ( R} прообразом Х відносно R - множина R-1(Х) = {х | існує таке y ( Х, що (х, у) ( R}.
Розглянемо кілька прикладів найпростіших відношень:
1) на множині N відношення ( . Ясно, що впорядковані пари (3, 7) і (5, 5) належать цьому відношенню, а пара (4, 1) не належить;
2) на множині Р(Х) всіх підмножин множини Х = {1, 3, 5, 7, 9} відношення (. Пари підмножин ({1, 3}, {1, 3, 9}) і ({5, 7, 9}, {5, 7, 9}) належать цьому відношенню, а пара підмножин ({1, 5, 7}, {3, 5, 9}) не належить.
Кожному відношенню R на скінченній множині з n елементів X = {x1, x2, …, xn} можна поставити у відповідність матрицю А = (аij), i,j = де aij = 1, якщо xi R xj , і aij = 0 у протилежному випадку. Матриця А, яка складається з елементів 0 та 1, називається матрицею інцидентності відношення R.
Ця матриця однозначно задає відношення на скінченних множинах. Наприклад, - одинична матриця задає відношення рівності; - якщо в матриці на головній діагоналі знаходяться 0, а інші елементи рівні 1, то вона задає відношення нерівності. Якщо Х = {1, 2, 3, 4} і R – відношення (, то матриця інцидентності матиме вигляд
Відношення R на множині X називається:
1) рефлективним, якщо довільний елемент множини знаходиться у відношенні сам з собою, тобто для будь-якого х ( Х виконується х R х. Прикладами рефлективних відношень можуть бути ≤, ≥, = на множині натуральних чисел;
2) антирефлективним, якщо для будь-якого х ( Х пара (х, х) не належить до відношення R. Прикладами антирефлективних відношень можуть бути <, >, ≠ на множині раціональних чисел;
3) симетричним, якщо для довільних x, х' ( Х з того, що x R x випливає х' R x;
4) антисиметричним, якщо для довільних x, х' ( Х з того, що x R х' і х' R x, випливає x = х' (наприклад, ( на N, тому що з x ( х' і х' ( x випливає х' = x);
5) транзитивним, якщо для довільних x, х', х'' ( Х з того, що x R х' і х' R х'', випливає x R х'' (наприклад, відношення ( на множині Р(Х) чи відношення ( на множині N).
Наведемо деякі приклади відношень:
1) рефлективне, симетричне, не транзитивне
R = {(x, х') | x, х' ( R, | x - х' | ( 1};
2) рефлективне, антисиметричне, не транзитивне
R = {(x, х') | x, х' ( Z, x ( х' ( x2};
3) рефлективне, антисиметричне, транзитивне
R = {(x, х') | x, х' ( Q, x ( х'};
4) нерефлективне, антисиметричне, транзитивне
R = {(x, х') | x, х' ( R, x = х' = 0};
5) нерефлективне, симетричне, транзитивне
R = {(x, х') | x, х' ( R, x, х' > 0}.
Будь-якому відношенню R на множині Х можна поставити у відповідність відношення , що визначається так: x х' для x, х' ( X, якщо існують такі x1, x2, …, x( ( X, що x R x1, x1 R x2, ..., x( R x'. Відношення називається транзитивним замиканням відношення R. Якщо R транзитивне, то = R.
Розглянемо далі відношення, які мають особливе значення.
Відношення еквівалентності
Відношення R називається відношенням еквівалентності, якщо воно має наступні властивості:
а) рефлективності: (x, х) ( R при будь-якому х ( Х;
б) симетричності: з (x1, х2) ( R випливає (x2, х1) ( R;
в) транзитивності: якщо (x1, х2) ( R і (x2, х3) ( R, то (x1, х3) ( R;
Замість того, щоб писати (x1, х2) ( R, часто пишуть x1 ~ x2 або x1 ( x2(mod R) (читається так: x1 конгруентно x2 за модулем R) чи, простіше, (x1 ~ x2 або x1 ( x2, якщо немає необхідності ще раз вказувати, що мова йде про одне й те саме відношення R).
Приклади: 1) Беремо множину Z цілих чисел. Будуємо множину X = {(p, q) ( Z(Z | q ( 0} Відношення еквівалентності задаємо наступним чином: (p, q) ( (р', q') якщо рq' - р'q = 0.
2)(Визначимо на множині цілих чисел Z відношення еквівалентності так, що р(q, тоді і тільки тоді, коли p - q ділиться без остачі на деяке наперед задане число m. У теорії чисел таке відношення записується у вигляді р ( q(mod т).
3)(Нехай Х - множина прямих на площині. Визначимо відношення еквівалентності для прямих x1 і x2, покладаючи x1 ( x2, коли ці прямі паралельні чи співпадають.
4)(Х – множина всіх векторів на площині. Визначимо на X відношення еквівалентності ~, якщо ці вектори паралельні, однаково напрямлені й мають однакову довжину.
5)(У тій же множині Х (див.4) встановимо відношення еквівалентності ~, якщо і лежать на одній прямій, однаково напрямлені й мають однакову довжину.
6) Нехай Х – множина всіх студентів, які присутні на лекції з дискретної математики. Два студенти еквівалентні, якщо вони народилися в тому самому місяці року.
Відношення еквівалентності на множині Х породжує деяке розбиття цієї множини, блоки якого називаються класами еквівалентності. Будь-які два елементи з одного класу зв’язані відношенням еквівалентності, тобто еквівалентні; з різних класів - не еквівалентні.
Побудуємо розбиття множини Х, яке відповідає заданому відношенню еквівалентності на цій множині. Для x ( X позначимо через K(x) підмножину, що складається з елементів, еквівалентних x, тобто K(x) = {y | y ( X; y ~ x}.
Справедлива наступна теорема:
Теорема I. Два класи еквівалентності не перетинаються або співпадають.
Доведення. Припустимо, що перетин множин K(x) і K(х') непорожній, і візьмемо z ( K(x) ( K(х'). Клас еквівалентності K(x) утворений з елементів, еквівалентних одному зі своїх елементів x. Оскільки x і z еквівалентні, то за властивістю транзитивності отримуємо, що K(x) утворений також з елементів, еквівалентних z. Аналогічно K(х') утворений з елементів, еквівалентних z. Таким чином, K(х) і K(х') співпадають.
З наведеного доведення бачимо, що клас еквівалентності є множиною всіх елементів, еквівалентних довільному елементу з цього класу. Таким чином, клас еквівалентності визначає деяке розбиття множини Х, тобто деяку сім’ю непорожніх підмножин множини X, які попарно не перетинаються, а їх об’єднання рівне X. Якщо відомі ці підмножини, то відоме й відношення еквівалентності, бо х і х' еквівалентні тоді і тільки тоді, коли вони належать одному класу еквівалентності.
Навпаки, будь-яке розбиття множини X: Х =, де Xj непорожні і попарно не перетинаються, визначає деяке відношення еквівалентності, а саме x ( х', якщо існує такий індекс j ( J, що x ( Xj, х' ( Xj. У цьому випадку підмножини Xj є класами еквівале...
Ділись своїми роботами та отримуй миттєві бонуси!
0%
Оголошення від адміністратора