КИЇВ КНУТД 2005 - раздел Математика, Основи Дискретної математики
Удк 51.681.3517
Конспект Лекцій З Ку...
УДК 51.681.3517
Конспект лекцій з курсу “Основи дискретної математики” для студентів спеціальності “Комп’ютерні науки” 6.0402
/ Автор М.К.Мороховець. – К.: КНУТД, 2005. – 52 с. Укр.мовою.
У даному матеріалі викладено основні відомості з теорії множин, розглядаються поняття відношення, відображення. Наводяться приклади розв’язання задач. До кожного розділу подаються задачі та вправи.
Матеріал призначено для студентів, що починають вивчати основи дискретної математики.
Київський національний університет технологій та дизайну... М К МОРОХОВЕЦЬ...
Если Вам нужно дополнительный материал на эту тему, или Вы не нашли то, что искали, рекомендуем воспользоваться поиском по нашей базе работ:
КИЇВ КНУТД 2005
Что будем делать с полученным материалом:
Если этот материал оказался полезным ля Вас, Вы можете сохранить его на свою страничку в социальных сетях:
Лекція 1. Поняття множини. Операції над множинами
Теорія множин як математична дисципліна створена німецьким мате-матиком Г.Кантором. Згідно з його визначенням, множиною є довільне зі-брання певних об’єктів н
Способи подання множин
Множина може бути задана явно або неявно. Якщо об’єктів, що склада-ють множину, небагато, множина задається явно шляхом перерахування цих об’єктів (а точніше, їх імен). На письмі мн
Включення та рівність множин
Нехай А та В – множини. Будемо говорити, що А включається у В, або А є підмножиною В (й позначати АÍВ), якщо кожен елемент множини
Операції над множинами
Об’єднанням множин А та В (позначається АÈВ) називається множина усіх об’єктів, що є елементами множини А або В, тобто
А
Властивості операцій над множинами
Теорема 1. Для будь-яких підмножин А, В, С універсальної множини U наведені нижче рівності є тотожностями (вираз А' слід розуміти як UА
Булеан множини
Кожна непорожня множина Х має принаймні дві різні підмножини: Æ та Х. Крім того, кожен елемент множини Х визначає деяку підмножину множини Х: якщо
Задачі та вправи
І. Описати словами множини:
1) {x| x=2y+1, yÎN}, 2) {x| x=2y-1, yÎN},
Декартів добуток множин
Упорядкованою парою об’єктів х та y (позначається <x,y>) будемо називати сукупність двох об’єктів (не обов’язково різних), які розташовані у
Поняття відношення
Термін «відношення» застосовується у математиці для позначення певного зв’язку між об’єктами. Відношенням R, заданим на множинах А та В, називається довільна підмножина декар
Операції над відношеннями
Нехай R1, R2 – відношення, задані на множинах A1,…,An. Об’єднанням відношень R1 та R2
Види бінарних відношень
Бінарне відношення R на множині А називається симетричним, якщо <x,y>ÎR Þ <y,x>ÎR. Пару
Відношення еквівалентності
Рефлексивне, симетричне та транзитивне відношення на множині А називається відношенням еквівалентності на А.
Прикладом відношення еквівалентності на мн
Фактор-множина
Нехай R – відношення еквівалентності на А. Тоді, як відомо, існує розбиття множини А, яке визначається відношенням R. Позначимо це розбиття через А
Замикання відношень
Рефлексивним замиканням бінарного відношення R, заданого на множині А (позначається Rr), називається відношення Rr=i
Задачі та вправи
І. Чи існують на множині {1,2,3,4} такі два різні відношення R та S, що: 1) Rr=Sr; 2) Rs=Ss; 3)
Відношення часткового порядку
Бінарне відношення R, задане на множині А, називається відношенням часткового порядку (частковим порядком на А), якщо R рефлексивне, антиси
Відношення лінійного та повного порядку
Відношенням лінійного порядку (лінійним порядком) на множині А називається такий частковий порядок на множині А, відносно якого порівнюються будь-які еле
Задачі та вправи
І. Які з відношень завдань XXVIІ-XXІX до попереднього розділу є відношен-нями: 1) часткового порядку, 2) строгого порядку, 3) передпорядку, 4) лінійного порядку, 5) повного порядку.
Поняття відображення
Відношення R, задане на множинах А та В, називається функціональним, якщо для кожного елемента xÎА існує не більше одного елемента
Види відображень
Відображення F множини А у множину В називається відображенням А на В (або сюр’єктивним відображенням, або сюр’єкцією), як
Задачі та вправи
І. Визначити, які з відображень є: а) частковими, б) сюр’єктивними,
в) ін’єктивними, г) взаємно однозначними. А={a,b,c,d}, B={b
Рівнопотужні множини
Множини А та В називаються рівнопотужними (еквівалентними), якщо існує взаємно однозначне відображення А на В.
Наприклад, множини
Потужність множини
Визначимо відношення ~ на множині усіх множин U: A~В Û А та В рівнопотужні. Дане відношення рефлексивне (А~А), симетричне (якщ
Трансфінітна індукція
Твердження, що стосуються елементів деякої повністю упорядкованої множини, можна доводити, використовуючи метод трансфінітної індукції, який є узагальненням методу математичної інду
Задачі та вправи
І. Навести приклад множини Y, еквівалентної множині X={1,2,3,4,5}. Скільки взаємно однозначних відображень існує між Х та Y?
ІІ. Чи рівнопотужні
СПИСОК ВИКОРИСТАНОЇ ТА РЕКОМЕНДОВАНОЇ ЛІТЕРАТУРИ
1. Биркгоф Г., Барти Т. Современная прикладная алгебра. – М.: Мир, 1976. – 400 с.
2. Глушков В.М., Цейтлин Г.Е., Ющенко Е.Л. Алгебра, языки, программировани
СИМВОЛИ ТА ПОЗНАЧЕННЯ
N – множина усіх невід’ємних цілих чисел
N+ – множина усіх додатних цілих чисел
Z – м
Хотите получать на электронную почту самые свежие новости?
Подпишитесь на Нашу рассылку
Наша политика приватности обеспечивает 100% безопасность и анонимность Ваших E-Mail
Новости и инфо для студентов