Основи Дискретної математики
Міністерство освіти та науки України
Київський національний університет технологій та дизайну
М.К.МОРОХОВЕЦЬ
Основи Дискретної математики
МНОЖИНИ ТА ВІДНОШЕННЯ
Конспект лекцій
Для студентів напрямку “Комп’ютерні науки” 6.0402
УДК 51.681.3517
Конспект лекцій з курсу “Основи дискретної математики” для студентів спеціальності “Комп’ютерні науки” 6.0402
Теорія множин як математична дисципліна створена німецьким мате-матиком…
Множина може бути задана явно або неявно. Якщо об’єктів, що склада-ють множину, небагато, множина задається явно шляхом перерахування цих об’єктів… Щойно описана форма подання множин не є зручною, коли треба задати множину, що… Наведемо приклади множин, заданих неявно: {x| x – зірка Всесвіту} – множина, елементами якої є ті й тільки ті об’єкти,…
Очевидно, що для будь-якої множини Х виконується ХÍХ. Доведемо, що для будь-яких множин X,Y,Z XÍY, YÍZ Þ XÍZ. Для… Назвемо множини X та Y рівними (й позначимо Х=Y), якщо XÍY та… Множина Х називається власною підмножиною множини Y, або Х строго включається в Y (позначається ХÌY), якщо…
Об’єднанням множин А та В (позначається АÈВ) називається множина усіх об’єктів, що є елементами множини А або В, тобто
АÈВ = {х| хÎА або хÎВ}.
Тут сполучник «або» використовується у тому розумінні, що елемент множини АÈВ може належати обом множинам (А та…
1) АÈ(ВÈС)=(АÈВ)ÈС, 1') АÇ(ВÇС)=(АÇВ)ÇС,
2) АÈВ=ВÈА, 2') АÇВ=ВÇА,
3) АÈ(ВÇС)=(АÈВ)Ç(АÈС), 3')…
Кожна непорожня множина Х має принаймні дві різні підмножини: Æ та Х. Крім того, кожен елемент множини Х визначає деяку підмножину множини Х:… Теорема 4.Нехай множина Х складається з n елементів. Тоді P(Х) містить 2n… Доведення. Нехай Х={х1,…,хn}. Розглянемо такий спосіб подання підмножини Y множини Х. Нехай lY=l1…ln – послідовність n…
І. Описати словами множини:
1) {x| x=2y+1, yÎN}, 2) {x| x=2y-1, yÎN},
3) {x| 10<x<100, x=5y, yÎN}, 4) {x| x=2y, yÎN},
ЛЕКЦІЯ 2. Декартів добуток множин. ВІДНОШЕННЯ
Упорядкованою парою об’єктів х та y (позначається <x,y>) будемо називати сукупність двох об’єктів (не обов’язково різних), які розташовані у… Декартовим добутком множин А та В (позначається А*В або А´В) називається… А´В={<a,b>| aÎA, bÎB},
Термін «відношення» застосовується у математиці для позначення певного зв’язку між об’єктами. Відношенням R, заданим на множинах А та В, називається… Наприклад, множина R={<1,2>,<1,3>,<3,1>,<3,5>} є… У випадку рівних множин А та В відношення, задане на А та В, називають бінарним відношенням, заданим на множині А (або…
Нехай R1, R2 – відношення, задані на множинах A1,…,An. Об’єднанням відношень R1 та R2 (позначається R1ÈR2) називається множина… Нехай, наприклад, A1={1,2,3}, A2={a,b,c}, R1, R2 – відношення, задані на… R1ÈR2={<1,a>,<1,b>,<2,b>,<3,c>,<3,a>},
Бінарне відношення R на множині А називається симетричним, якщо <x,y>ÎR Þ <y,x>ÎR. Пару виду <y,x> назвемо… Наприклад, нехай на множині А={a,b,c,d} задано відношення… Бінарне відношення R на множині А назвемо антисиметричним, якщо <x,y>ÎR, <y,x>ÎR Þ x=y,…
Рефлексивне, симетричне та транзитивне відношення на множині А називається відношенням еквівалентності на А.
Прикладом відношення еквівалентності на множині А={a,b,c,d} є відношення… Теорема 7. Бінарне відношення R на множині А є відношенням еквівалентності тоді й тільки тоді, коли існує розбиття Р…
Нехай R – відношення еквівалентності на А. Тоді, як відомо, існує розбиття множини А, яке визначається відношенням R. Позначимо це розбиття через… Наприклад, множина N з відношенням еквівалентності R, заданим умовою xRy…
Рефлексивним замиканням бінарного відношення R, заданого на множині А (позначається Rr), називається відношення Rr=iAÈR.
Симетричним замиканням бінарного відношення R, заданого на множині А… Нехай, наприклад, на множині А={1,2,3,4} задано відношення R={<2,3>,<3,3>, <2,1>,<1,3>}.…
І. Чи існують на множині {1,2,3,4} такі два різні відношення R та S, що: 1) Rr=Sr; 2) Rs=Ss; 3) Rt=St? Відповіді обгрунтувати.
ІІ. Побудувати декартів добуток множин
1) {1,2,Æ} та {2,4}, 2) {а,с,е}, {с,а},
Лекція 3. Відношення порядку
Бінарне відношення R, задане на множині А, називається відношенням часткового порядку (частковим порядком на А), якщо R рефлексивне, антисиметричне,… Наприклад, відношення… Теорема 9. Нехай R та R1 – часткові порядки на А. Довести, що:
Відношенням лінійного порядку (лінійним порядком) на множині А називається такий частковий порядок на множині А, відносно якого порівнюються… Наприклад, лінійно упорядкованою є множина А={1,2,3}, на якій задано частковий… Нехай R – частковий порядок на множині А. Елемент х множини А називається мінімальним (максимальним) елементом…
І. Які з відношень завдань XXVIІ-XXІX до попереднього розділу є відношен-нями: 1) часткового порядку, 2) строгого порядку, 3) передпорядку, 4)… ІІ. Побудувати частково упорядковану множину, яка має:
1) найменший елемент, максимальний елемент й не має найбільшого елементу;
ЛЕкція 4. Відображення
Відношення R, задане на множинах А та В, називається функціональним, якщо для кожного елемента xÎА існує не більше одного елемента yÎВ… Наприклад, відношення R={<1,b>,<3,a>,<4,b>}, задане на… Нехай R – відношення, задане на множинах А та В. Назвемо областю визначення відношення R (позначається D(R)) множину…
Відображення F множини А у множину В називається відображенням А на В (або сюр’єктивним відображенням, або сюр’єкцією), якщо F-1(b)¹Æ для… Нехай, наприклад, А={1,2,3,4}, B={a,b,c}, F:A®B,… F-1(a)={3,4}, F-1(b)={1}, F-1(c)={2}.
І. Визначити, які з відображень є: а) частковими, б) сюр’єктивними,
в) ін’єктивними, г) взаємно однозначними. А={a,b,c,d}, B={b,c,d,f}.
1) F:A®B, F={<a,b>,<c,f>,<d,d>};
ЛЕКЦІЯ 5. Потужність множини. Трансфінітна індукція
Множини А та В називаються рівнопотужними (еквівалентними), якщо існує взаємно однозначне відображення А на В.
Наприклад, множини А={a,b,c} та В={1,2,3} рівнопотужні, оскільки існує взаємно… Зауважимо, що рівні множини є рівнопотужними, але рівнопотужні множини не обов’язково рівні.
Визначимо відношення ~ на множині усіх множин U: A~В Û А та В рівнопотужні. Дане відношення рефлексивне (А~А), симетричне (якщо А~В, то існує… Множина, еквівалентна множині N+, називається зліченною. Кардинальне число… Прикладом зліченної множини є множина Р усіх додатних парних чисел. Дійсно функція f(n)=2n задає взаємно однозначне…
Твердження, що стосуються елементів деякої повністю упорядкованої множини, можна доводити, використовуючи метод трансфінітної індукції, який є… Теорема 14 (теорема про трансфінітну індукцію). Нехай <А,£>–… Доведення. Припустимо, що твердження теореми не правильне. Тоді існує така непорожня підмножина В множини А…
І. Навести приклад множини Y, еквівалентної множині X={1,2,3,4,5}. Скільки взаємно однозначних відображень існує між Х та Y?
ІІ. Чи рівнопотужні множини: 1) N+ та N-, 2) N- та N+, 3) N та Z, 4) N+ та Q,… III. Нехай А – незліченна множина й В – деяка зліченна підмножина множини А. Довести, що множина ВА незліченна.
1. Биркгоф Г., Барти Т. Современная прикладная алгебра. – М.: Мир, 1976. – 400… 2. Глушков В.М., Цейтлин Г.Е., Ющенко Е.Л. Алгебра, языки, программирование. – К.: Наукова думка, 1989. – 328 с.
N – множина усіх невід’ємних цілих чисел
N+ – множина усіх додатних цілих чисел
Мороховець Марина Костянтинівна
Основи Дискретної математики
МНОЖИНИ ТА ВІДНОШЕННЯ
Конспект лекцій
з дисципліни “Основи дискретної математики”
Для студентів напрямку “Комп’ютерні науки” 6.0402