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

Міністерство освіти та науки України

 

Київський національний університет технологій та дизайну

 

 

М.К.МОРОХОВЕЦЬ

 

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

 

МНОЖИНИ ТА ВІДНОШЕННЯ

Конспект лекцій

Для студентів напрямку “Комп’ютерні науки” 6.0402

 

 

КИЇВ КНУТД 2005

УДК 51.681.3517   Конспект лекцій з курсу “Основи дискретної математики” для студентів спеціальності “Комп’ютерні науки” 6.0402

Лекція 1. Поняття множини. Операції над множинами

  Теорія множин як математична дисципліна створена німецьким мате-матиком…  

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

Множина може бути задана явно або неявно. Якщо об’єктів, що склада-ють множину, небагато, множина задається явно шляхом перерахування цих об’єктів… Щойно описана форма подання множин не є зручною, коли треба задати множину, що… Наведемо приклади множин, заданих неявно: {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