Декартово произведение на множества. Индексиране на множества

📞 Онлайн уроци по математика за цялата страна◆ гл.ас. д-р Атанас Илчев◆ Индивидуални и групови уроци • Тел: 0883 375 433◆ ISEE Upper Level • Подготовка за американски колеж◆ 📞 Онлайн уроци по математика за цялата страна◆ гл.ас. д-р Атанас Илчев◆ Индивидуални и групови уроци • Тел: 0883 375 433◆ ISEE Upper Level • Подготовка за американски колеж◆

Математика › Теория на множествата › Декартово произведение

Декартово произведение на множества
Разбивания и бит-вектори

Пълен урок с определения, примери, задачи за самостоятелна работа и интерактивен тест

Теория на множествата Декартово произведение Разбивания Бит-вектори 15 въпроса тест

Наредена двойка, декартово произведение, \(n\)-кратно произведение, разбивания и бит-вектори

До момента се запознахме с основните операции с множества — сечение, обединение и разлика (вж. тук). Сега ще разгледаме декартовото произведение на две множества \(A\) и \(B\), означавано с \(A\times B\).

Определения

Определение 1: Нека \(a\) и \(b\) са произволни елементи. Множеството \(\{\{a\},\{a,b\}\}\) се нарича наредена двойка от елементите \(a\) и \(b\).

Вместо този запис ще използваме \((a,b)\), като изрично споменем, че \((a,b)\neq(b,a)\). Тук \(a\) е първи елемент, а \(b\) — втори елемент.

Определение 2: Нека \(A\) и \(B\) са множества. Множеството \[A\times B=\{(a,b):a\in A,\; b\in B\}\] се нарича декартово произведение на множествата \(A\) и \(B\).

Пример 1 — координатна равнина: Евклидовата равнина с въведена правоъгълна координатна система е декартово произведение \(O_x\times O_y\). Всяка точка се определя еднозначно от наредената двойка \((x,y)\), където \(x\) е проекцията върху \(O_x\), а \(y\) — върху \(O_y\).

Пример 2: Нека \(A=\{2,8,9\}\) и \(B=\{1,3,7\}\). Тогава: \[A\times B=\{(2,1),(2,3),(2,7),(8,1),(8,3),(8,7),(9,1),(9,3),(9,7)\},\] \[B\times A=\{(1,2),(1,8),(1,9),(3,2),(3,8),(3,9),(7,2),(7,8),(7,9)\}.\] Очевидно \(A\times B\neq B\times A\) — двете множества съдържат различни елементи.

Определение 3: Декартовото произведение \[A_1\times A_2\times\cdots\times A_n=\{(a_1,a_2,\ldots,a_n):a_i\in A_i\},\] където \((a_1,a_2,\ldots,a_n)\) е наредена \(n\)-орка, се нарича \(n\)-кратно декартово произведение.

Индексно множество: Нека \(I_n=\{i:i\in\mathbb{N},\; 1\leq i\leq n\}\). Използваме елементите на \(I_n\), за да означим елементите на множеството \(A=\{a_i:i\in I_n\}\). Тогава \(I_n\) е индексно множество на \(A\) и \(|A|=n\).

Определение 4 — Обединение на \(n\) множества: \[A_1\cup A_2\cup\cdots\cup A_n=\bigcup_{i\in I_n}A_i=\{a:\exists\, i\in I_n,\; a\in A_i\}.\]

Определение 5 — Сечение на \(n\) множества: \[A_1\cap A_2\cap\cdots\cap A_n=\bigcap_{i\in I_n}A_i=\{a:\forall\, i\in I_n,\; a\in A_i\}.\]

Операциите обединение и сечение са асоциативни — затова можем да ги дефинираме за произволен брой множества. Разликата на множества не е асоциативна, поради което не може да се дефинира за повече от две множества.

Определение 6 — Разбиване: Фамилията \(F=\{A_i:i\in I,\; A_i\subseteq A\}\) се нарича разбиване на \(A\), ако са изпълнени три условия:

1) \(A_i\neq\emptyset\) за всяко \(i\in I\);
2) \(A_i\cap A_j=\emptyset\) за всеки \(i\neq j\)  (множествата са по двойки непресичащи се);
3) \(\bigcup_{i\in I}A_i=A\)  (обединението им е цялото \(A\)).

Пример: Нека \(A=\{a,b,c,d,e,f,g,h,i,j,k\}\).

\(B=\{\{a,b,c\},\{d,e,f,g,h\},\{i,j,k\}\}\) е разбиване на \(A\) — трите подмножества са непразни, попарно непресичащи се и обединението им е \(A\).

\(C=\{\{a,b,c\},\{d,f,g,h\},\{i,j,k\}\}\) не е разбиване на \(A\), защото \(e\in A\), но \(e\) не принадлежи на никое подмножество — условие 3 не е изпълнено.

Определение 7 — Бит-вектор: Нека \(A\subseteq U\). За множеството \(A\) дефинираме бит-вектор по следния начин: \[b_i=1,\text{ ако }a_i\in A;\qquad b_i=0,\text{ ако }a_i\notin A,\quad i=1,2,\ldots,n.\]

Пример: Нека \(U=\{a,b,c,d,e,f,h,i,j,k\}\) и \(A=\{a,b,d,h,i,k\}\). Бит-векторът, съответстващ на \(A\): \[1\;1\;0\;1\;0\;0\;1\;1\;0\;1.\] Единиците са на позициите на \(a, b, d, h, i, k\) — елементите, принадлежащи на \(A\).

---

Задачи за самостоятелна работа

Задача 1 Намерете \(A\times B\) и \(B\times A\), ако \(A=\{a,b,c\}\) и \(B=\{d,e\}\).

Задача 2 Намерете всички възможни разбивания на множеството \(A=\{a,b,c,\{a,b,c\}\}\).

---

Онлайн тест

15 въпроса • 4 точки за верен отговор • максимум 60 точки

Тест: Декартово произведение, разбивания и бит-вектори

Изберете верния отговор за всеки въпрос, след което натиснете КРАЙ.

1Вярно ли е, че \((a,b)=(b,a)\)?

Да, винаги Не — наредените двойки зависят от реда Само ако \(a=b\) → не Зависи от множествата

2Колко елемента има \(A\times B\), ако \(|A|=2\) и \(|B|=3\)?

2 5 6 8

3За произволни множества \(A\) и \(B\) е вярно, че:

\(A\times B=B\times A\) \(A\times B\neq B\times A\) по принцип \(A\times B\) е винаги празно \(|A\times B|\neq|B\times A|\)

4Евклидовата равнина с правоъгълна координатна система представлява:

\(O_x\cup O_y\) \(O_x\cap O_y\) \(O_x\times O_y\) \(O_x\setminus O_y\)

5Елементите на \(n\)-кратното декартово произведение \(A_1\times\cdots\times A_n\) са:

обикновени множества наредени \(n\)-орки \((a_1,\ldots,a_n)\) неупорядочени двойки само реални числа

6Второто условие за разбиване на множество изисква:

\(A_i\cap A_j\neq\emptyset\) за \(i\neq j\) \(A_i\cap A_j=\emptyset\) за \(i\neq j\) \(A_i=A_j\) за всички \(i,j\) \(A_i\subseteq A_j\) за \(i<j\)

7Третото условие за разбиване изисква обединението на частите да е:

\(\emptyset\) цялото множество \(A\) само едно подмножество универсумът \(U\)

8В бит-вектора на множеството \(A\), \(b_i=1\) означава:

\(a_i\notin A\) \(a_i\in A\) \(a_i=1\) \(|A|=1\)

9Колко наредени двойки съдържа \(A\times B\), ако \(A=\{a,b,c\}\) и \(B=\{d,e\}\)?

3 5 6 9

10Първото условие за разбиване изисква:

\(A_i=\emptyset\) за поне едно \(i\) \(A_i\neq\emptyset\) за всяко \(i\) \(|A_i|=1\) за всяко \(i\) \(A_i\cap A=\emptyset\)

11\(a\in\bigcup_{i\in I_n}A_i\) означава:

\(a\in A_i\) за всяко \(i\) съществува \(i\) такова, че \(a\in A_i\) \(a\notin A_i\) за нито едно \(i\) \(a\in A_1\) само

12\(a\in\bigcap_{i\in I_n}A_i\) означава:

съществува \(i\) такова, че \(a\in A_i\) \(a\in A_i\) за всяко \(i\in I_n\) \(a\notin A_i\) за всяко \(i\) \(a\in A_n\) само

13Защо разликата на множества не може да се дефинира за повече от две множества?

Защото не е комутативна Защото не е асоциативна Защото резултатът е винаги празен Защото изисква три аргумента

14Мощността \(|I_n|\) на индексното множество \(I_n=\{i:i\in\mathbb{N},\; 1\leq i\leq n\}\) е:

\(n-1\) \(n\) \(n+1\) \(2n\)

15За \(U=\{a,b,c,d,e\}\) и \(A=\{a,c,e\}\) бит-векторът на \(A\) е:

\(0\; 1\; 0\; 1\; 0\) \(1\; 0\; 1\; 0\; 1\) \(1\; 1\; 1\; 0\; 0\) \(0\; 0\; 1\; 1\; 1\)

---

Използвана литература

1. 1.Дискретна математика, Светла Бойчева, Стефка Толева-Стоименова, изд. Сиела 2018 г.
2. 2.Увод в дискретната математика, Красимир Манев, изд. КЛМН 2012 г.
3. 3.Въведение в дискретната математика, Христо Кискинов, Пловдивско университетско издателство

Запишете урок

Индивидуални и групови онлайн уроци по математика за цялата страна

🎓 Подготовка за изпити

• ›НВО по математика след 7 клас
• ›НВО по математика след 10 клас
• ›Кандидатстудентски изпити по математика
• ›Прием в университети в чужбина (ISEE, SAT, A-Level)

📚 Текущо обучение и студенти

• ›Усвояване на текущия учебен материал (всички класове)
• ›Студенти: Мат. анализ, Линейна алгебра, Аналитична геометрия, Диф. уравнения, Теория на вероятностите, Статистика и др.

✆ 0883 375 433 ☎ Viber

Харесва ли ви съдържанието?

Ако този урок ви е бил полезен, можете да подкрепите създаването на нови безплатни материали.

📞 Онлайн уроци по математика за цялата страна◆ гл.ас. д-р Атанас Илчев◆ Индивидуални и групови уроци • Тел: 0883 375 433◆ ISEE Upper Level • Подготовка за американски колеж◆ 📞 Онлайн уроци по математика за цялата страна◆ гл.ас. д-р Атанас Илчев◆ Индивидуални и групови уроци • Тел: 0883 375 433◆ ISEE Upper Level • Подготовка за американски колеж◆