Подякувати Студентському архіву довільною сумою
Admin
26.02.2023 12:38
Дякуємо, що користуєтесь нашим архівом!
Звіт про виконання лабораторної роботи №1
Інформація про навчальний заклад
ВУЗ:
Національний університет Львівська політехніка
Інститут:
Не вказано
Факультет:
КН
Кафедра:
Кафедра СКС
Інформація про роботу
Рік:
2015
Тип роботи:
Звіт про виконання лабораторної роботи
Предмет:
Дискретна математика
Частина тексту файла (без зображень, графіків і формул):
Міністерство освіти і науки, молоді та спорту України
Національний університет „Львівська політехніка”
Кафедра СКС
Звіт про виконання лабораторної роботи №1
"Дискретна математика"
Львів - 2015
Тема: Множини. Операції над множинами. Алгебраїчні операції. Групи.
Мета:
Розробити програмне забезпечення, яке перевіряє властивості відображення (ін’єктивність)
Теоретична частина:
1.1. Множини
Множини є основними об’єктами вивчення у дискретній математиці. Множина - це невпорядкована сукупність об’єктів, які називають елементами множини. Елементами можна вважати довільні об’єкти, які можуть бути названі або означені за допомогою правила, що задає належність до множини.
Як правило, множини позначають великими буквами.
Прикладе множин:
множина всіх трамвайних зупинок міста Львова;
множина символів клавіатури ЕОМ;
множина зарезервованих слів мови Паскаль;
А = {х ǀ х - ціле число і 7 < х < 13};
N = {1, 2, 5, 9, 14, 13} - множина задана перечисленням її елементів.
Для будь-якого елемента можна встановити, чи належить він множині . Запис означає приналежність елемента до множини , а символ «» - це знак приналежності деякого елемента до множини .
Запис означає, що елемент не належить до множини .
1.2. Операції над множинами
Об’єднанням множин і (позначається ) називається множина
.
Перетином множин і (позначається ) називається множина
.
Різницею множин і (позначається ) називається множина
.
Симетрична різниця множин і (позначається ) задається як
Порожня множина (позначається Ø) - це множина, яка володіє властивістю для будь-якого .
Означення 1. Множина є підмножиною множини ) тоді і тільки тоді, якщо для будь-якого випливає, що .
Означення 2. Відношення називається:
рефлексивним, якщо для всіх ;
симетричним, якщо з випливає для всіх;
антисиметричним, якщо з і випливає, що для всіх ;
транзитивним, якщо з і випливає для всіх .
Означення 3. Рефлексивне, симетричне і транзитивне відношення на множині називається відношенням еквівалентності. Рефлексивне, антисиметричне і транзитивне відношення на множині називається відношенням часткового порядку.
Означення 4.
тоді і тільки тоді, коли;
для тоді і тільки тоді, коли існує таке, що і для .
Як для заданого на деякій множині відношення можна визначити відношення таке, що володіє додатковими властивостями, зокрема - транзитивністю? Таким буде відношення тоді і тільки тоді і якщо знайдеться таке , що для, які належать даній множині.
Відношення називається транзитивним замиканням відношення на множині .
Для транзитивного замикання Має місце теорема:
Теорема 1. Транзитивне замикання деякого відношення є відношення транзитивне. Якщо - будь-яке транзитивне відношення, таке, що, тоді і тобто - найменше транзитивне відношення, яке включає .
Для знаходження матриці транзитивного замикання відношення на множині зі скінченою кількістю елементів можна скористуватись теоремою:
Теорема 2. Нехай - матриця, що задає відношення на множині , яка містить елементів. Тоді матриця
задає транзитивне замикання відношення .
1.1. Об’єднання А і В – множина, що складається з усіх елементів множини А, всіх елементів множини В і не містить ніяких інших елементів (рис. 1), тобто
А ( В = {x | x ( А або x ( В}.
Рис. 1
1.2. Перетин А і В – множина, що складається з тих і тільки з тих елементів, які належать одночасно множині А та множині В (рис. 2), тобто
А ( В = {x | x ( А і x ( В}.
Рис. 2
1.3. Різниця А і В (відносне доповнення) – множина, що складається з тих і тільки тих елементів, які належать множині А й не належать множині В (рис. 3), тобто
А \ В = {x | x ( А і x ( В}.
Рис. 3
1.4. Диз’юнктивна сума А і В (симетрична різниця) – множина, що складається усіх елементів А, які не належать множині В, й усіх елементів В, які не належать множині А, та яка не містить ніяких інших елементів (рис. 4), тобто
А ( В = {x | (x ( А і x ( В) або (x ( В і x ( А)}.
Рис. 4
1.5. Доповнення множини.
Звичайно, вже в означенні конкретної множини явно або неявно обмежується сукупність об’єктів, що є допустимими (слони – серед тварин, натуральні числа – серед цілих або дійсних залежно від контексту). Зручно сукупність допустимих об’єктів зафіксувати явно та вважати, що множини, які розглядаються, складаються з елементів цієї сукупності. Її називають основною множиною (універсумом) і позначають U. Універсум U арифметики – числа, універсум U зоології – тварини і т.д. Будь-яку множину розглядатимемо у зв’язку з універсумом, який на діаграмах Ейлера асоціюватимемо з прямокутником на площині, всередині якого зображатимемо множини (рис. 5).
Рис. 5
Доповнення множини А – це множина, що містить усі елементи універсуму, за винятком елементів А (рис. 6), тобто .
Рис.6
1.8. Множина А називається підмножиною множини В, якщо кожен елемент А є елементом В. Для позначення цього факту вводиться знак ( - символ строгого включення (або ( - символ нестрогого включення) (рис. 7). Якщо необхідно підкреслити, що множина В містить також інші елементи, крім елементів множини А, то використовують символ строгого включення А ( В.
Дві множини рівні, якщо вони складаються з одних і тих самих елементів. Справджується таке: А = В тоді і тільки тоді, коли А ( В і В ( А.
Рис. 7
1.6. Декартовим (прямим) добутком множин 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.
Множину, елементами якої є всі підмножини множини А, називають множиною підмножин множини А (або булеаном множини А) і позначають Р(А).
Результат виконання роботи:
Висновок:
На лабораторній роботі я розробив програмне забезпечення, яке знаходить диз’юктивну суму двох множин.
21.03.2016 01:03-
Ділись своїми роботами та отримуй миттєві бонуси!
0%
Оголошення від адміністратора