Теория множеств. Решение задач. Декартово произведение. (Лекция 6)

1. Теория множеств. Решение задач

2. 1. Вычисление множеств

Дано
U={1;2;3;4;5;6;7;8;9;10;11},
A={1;2;3;7;9},
B={3;4;5;6;10;11},
C={2;3;4;7;8},
D={1;7;11}.
Вычислить множества
1) A B 1;2;3;4;5;6;7;9;10;11
2)( A С ) D
3) ( A \ D) C
1;2;3;4;7;8;9 D 1;7
2;3;9 C 2;3;4;7;8;9
4) ( B
C ) D 2;5;6;7;8;10;11 D 7;11
5)
B \ C (D \ A) 5;6;10;11 ( D \ A) 1;2;3;4;7;8;9 11

3.

2. Выражение множеств
Пусть U={1, 2, 3, 4, 5, 6, 7, 8,9},
A={1, 2, 3, 5},
B={2, 4, 6, 8},
C={1, 3, 5, 7},
D={4, 5, 7, 8}.
Выразить через известные множества A, B, C, D следующие множества.
1) {1,2,3,4,5,7,8}= A D
2) {4,7,8}= D \ A
3) {2,5,6,7}= B
D
4) {2,5}= A \ (C \ D)
5) {5,7,9}= A D ( A B)
6) {4,5}=
Невозможно выразить через данные множества, так как элементы 4 и 8
одновременно принадлежат или не принадлежат данным множествам.

4. 3. Изображение множеств с помощью кругов Эйлера

Изобразить с помощью кругов
Эйлера следующие множества:
A
1)
B
( A B) C
C
A
2)
B
( A B) С
C

5. 3. Изображение множеств с помощью кругов Эйлера

3) B C \ A D
4) A
C D \ A \ C

6. 4. Выражение множеств, заданных с помощью кругов Эйлера

A
B
A C \ B B \ A C
C

7. 4. Выражение множеств, заданных с помощью кругов Эйлера

B C \ D (D \ A \ C)
A \ D C \ B D

8. Декартово произведение

9.

Декартово произведение
Под упорядоченной парой (а; b) мы будем понимать двухэлементное множество,
состоящее из элементов а и b, в котором зафиксирован порядок расположения
элементов.
Упорядоченный набор длины n a1; a2 ;...; an , где a1 A1, a2 A2 ,..., an An ,
называют вектором, кортежем, или упорядоченной n- кой.
Определение 1
Декартовым (прямым) произведением множеств А и В называется множество
A B a; b a A, b B
Пример
Пусть A={1;2}, B={a, b, c}, тогда
A B {(1;a);(1;b);(1;c);(2;a);(2;b);(2;c)};
B A {(a;1);(b;1);(c;1);(a;2);(b;2);(c;2)}.
Вообще говоря,
B A A B

10. Декартово произведение

Определение 2
а) Множество
A1 A2 ... An a1; a2 ;...; an a1 A1, a2 A2 ,..., an An
называется декартовым (прямым) произведением n множеств;
б) An A A ... A - (n cомножителей) – n-aя декартова степень множества
А;
Пример
Пусть
Тогда
A1 1;2;3 ,
A2 *; , A3 ;
A1 A2 A3 (1;*; ), (1;*; ), (1; ; ), (1; ; ), (2;*; ), (2;*; ), (2; ; ), (2; ; ), (3;*; ), (3;*; ), (3; ; ), (3; ; )

11. Декартово произведение

Пример
Очевидно, что
R R R 2, где R- множество действительных чисел,
описывает множество всех точек декартовой плоскости
Задача
Изобразить множество
( 1;3] [0;2)
Решение
y
2
-1
0
3
x

12. Декартово произведение

Теорема 1
Пусть А, В, С – произвольные множества, тогда
A B C A B A C
A B C A B A C
A B \ C A B \ A C

13. Декартово произведение

Доказательство
x, y A B C x A y B C
x A y B x A y C
x; y A B A C
Следовательно
x A y B y C
x; y A B x; y A C
A B C A B A C

14.

Декартово произведение
Доказательство
x; y A B C x A y B C
x A y B y C
x A y B x A y C
x; y A B x; y A C
x; y A B A C
Следовательно
A B C A B A C

15.

Декартово произведение
Доказательство
x; y A B \ A C
x; y A B x; y A C
x A y B x A y C
x A y B x A y C
x A y B x A x A y B y C
x A y B y C
x A y B \ C x; y A B \ C
Следовательно
A B \ A C A B \ C

16. Декартово произведение

Теорема 4
Если множество А состоит из m элементов, а В – из n элементов, тогда
A B
состоит из mn элементов.
Доказательство
ММИ по числу элементов множества B.
1) n=1. B b1 A B a; b1 a A
то есть AB имеет m=m*1 элементов.
2) Допустим, что теорема верна при n=k.
3) И пусть теперь В состоит из к+1 элемента, то есть
где
B' b1 ; b2 ;...; bk
Тогда
B b1 ; b2 ;...; bk ; bk 1 ; B' bk 1
A B A B' bk 1 A B' A bk 1
, где
A B' A bk 1
поэтому множество АВ состоит из mk+m=m(k+1) элементов.