Декартів добуток множин - раздел Математика, Основи Дискретної математики
Упорядкованою Парою Об’Єктів Х Та Y (Поз...
Упорядкованою парою об’єктів х та y (позначається <x,y>) будемо називати сукупність двох об’єктів (не обов’язково різних), які розташовані у певному порядку. Поняття упорядкованої пари можна поширити й розглядати для будь-якого цілого додатного числа n³2 упорядковану n-ку об’єктів х1,…,хn (позначається <х1,…,хn>). Об’єкт хі називається і-м компонентом упорядкованої n-ки. Упорядковані n-ки називають також кортежами.
Декартовим добутком множин А та В (позначається А*В або А´В) називається множина
А´В={<a,b>| aÎA, bÎB},
тобто множина усіх упорядкованих пар, побудованих з елементів множин А та В таким чином, що перший компонент кожної пари – це елемент множини А, а другий – елемент множини В.
Наприклад, декартовим добутком множин А={a,b} та В={1,2,3} є множина A´B={<a,1>,<a,2>,<a,3>,<b,1>,<b,2>,<b,3>}. Побудуємо декартів добуток множин В та А. Маємо: В´А={<1,a>,<2,a>,<3,a>,<1,b>, <2,b>,<3,b>}. Як бачимо, А´В≠В´А, отже, операція ´ не комутативна.
Декартовим добутком множин А1,…,Аn (позначається А1´…´Аn або А1*…*Аn) називається множина
А1´…´Аn={<a1,…,an>| a1ÎA1,…,anÎAn},
тобто множина усіх упорядкованих n-ок, побудованих з елементів множин А1,…,Аn таким чином, що і-й компонент кожної n-ки належить множині Аі (і=1,…,n).
Наприклад, декартовим добутком множин А1={a,b}, A2={b,c}, A3={b,d} є множина А1´А2´А3={<a,b,b>,<a,b,d>,<a,c,b>,<a,c,d>,<b,b,b>, <b,b,d>,<b,c,b>,<b,c,d>}.
Якщо для деякого і (і=1,…,n) Аі=Æ, то А1´…´Аn=Æ.
Якщо А1=…=Аn=А, то А1´…´Аn позначається Аn й називається n-м декартовим степенем множини А.
Наприклад, якщо А={1,2}, то А3={<1,1,1>,<1,1,2>,<1,2,1>,<1,2,2>, <2,1,1>,<2,1,2>,<2,2,1>,<2,2,2>}.
Між операцією декартова добутка та іншими операціями над множинами існують зв’язки. Доведемо, зокрема, що (АÈВ)´С=(А´С)È(В´С).
Для цього покажемо спочатку, що (АÈВ)´СÍ(А´С)È(В´С). Множина (АÈВ)´С є декартовим добутком двох множин ((АÈВ) та С), отже, елементи цієї множини – це упорядковані пари. Таким чином, маємо: <x,y>Î(АÈВ)´С Þ xÎAÈB, yÎC Þ xÎA або xÎB, yÎC Þ xÎA та yÎC або xÎB та yÎC Þ <x,y>ÎA´C або <x,y>ÎB´C, отже, доведено, що (АÈВ)´СÍ(А´С)È(В´С). Тепер покажемо, що (А´С)È(В´С)Í(АÈВ)´С. <x,y>Î(А´С)È(В´С) Þ <x,y>Î(A´C) або <x,y>Î(B´C) Þ (xÎA та yÎC) або (хÎВ та yÎC). Розглянемо випадок xÎA та yÎC. Маємо: xÎA та yÎC Þ хÎАÈВ, yÎC Þ <x,y>Î(AÈB)´C. Якщо хÎВ та yÎC, то маємо: хÎВ та yÎC Þ хÎ(АÈВ), yÎC Þ <x,y>Î(AÈB)´C. Отже, у кожному випадку доведено, що (А´С)È(В´С)Í(АÈВ)´С. Таким чином, рівність виконується.
Все темы данного раздела:
КИЇВ КНУТД 2005
УДК 51.681.3517
Конспект лекцій з курсу “Основи дискретної математики” для студентів спеціальності “Комп’ютерні науки” 6.0402
/ Автор М.К.Мороховец
Лекція 1. Поняття множини. Операції над множинами
Теорія множин як математична дисципліна створена німецьким мате-матиком Г.Кантором. Згідно з його визначенням, множиною є довільне зі-брання певних об’єктів н
Способи подання множин
Множина може бути задана явно або неявно. Якщо об’єктів, що склада-ють множину, небагато, множина задається явно шляхом перерахування цих об’єктів (а точніше, їх імен). На письмі мн
Включення та рівність множин
Нехай А та В – множини. Будемо говорити, що А включається у В, або А є підмножиною В (й позначати АÍВ), якщо кожен елемент множини
Операції над множинами
Об’єднанням множин А та В (позначається АÈВ) називається множина усіх об’єктів, що є елементами множини А або В, тобто
А
Властивості операцій над множинами
Теорема 1. Для будь-яких підмножин А, В, С універсальної множини U наведені нижче рівності є тотожностями (вираз А' слід розуміти як UА
Булеан множини
Кожна непорожня множина Х має принаймні дві різні підмножини: Æ та Х. Крім того, кожен елемент множини Х визначає деяку підмножину множини Х: якщо
Задачі та вправи
І. Описати словами множини:
1) {x| x=2y+1, yÎN}, 2) {x| x=2y-1, yÎN},
Поняття відношення
Термін «відношення» застосовується у математиці для позначення певного зв’язку між об’єктами. Відношенням 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 – м
Новости и инфо для студентов