Дискретная математика. Бинарные отношения. Соколова С.В. - 5 стр.

UptoLike

ВУЗ: 

ТПУ | Томск

Составители: 

Рубрика: 

5
БИНАРНЫЕ ОТНОШЕНИЯ
1. Декартово произведение множеств
Рене Декарт – французский философ и математик, один из первых
создателей формального языка математики – жил в 17 веке (1596–1659).
Теория множеств появилась спустя 200 лет, т.е. в 19 веке, поэтому Р.
Декарт об этой теории никогда не слышал и заниматься ею не мог. На-
звание операции «декартово произведение» появилось в связи с тем, что
в теории множеств нашел применение метод координат, разработанный
Р. Декартом.
Рассмотрим два непересекающихся множества А={a
1
, а
2
,..., a
n
) и
В={b
1
, b
2
,..., b
m
}. Выберем какой-нибудь элемент из множества А и при-
пишем к нему справа некоторый элемент множества В. Получим упоря-
доченную пару. Элементы, образующие пару, будем записывать в круг-
лых скобках, отделяя один элемент от другого запятой: (а
i
, b
j
), где a
i
∈А;
b
j
∈В; i=1, 2, 3,…, n; j=1, 2, 3,…, m. Множество всех пар (a
i
, b
j
) называют
декартовым произведением множеств. Для обозначения этой операции
используется знак арифметического умножения: А×В.
Формально декартово произведение множеств А и В определяется
следующим образом:
А×В={(x, y) / х∈А ∧ у∈В}.
Читается эта запись так: декартово произведение множеств А и В
– это множество пар (x, у), где х – элемент множества А, у – элемент
множества В.
Точно так же определяется декартово произведение множеств
В×А:
В×А={(у, х) / y∈В ∧ х∈А}.
Рассмотрим пример. Пусть А={1, 2, 3, 4} и В={а, b, с}.
Тогда
А×В={(1, а), (1, b), (1, с), (2, а), (2, b), (2, с),
(3, а), (3, b), (3, с), (4, а), (4, b), (4, с)},
В×А={(a, 1), (b, 1), (с, 1), (а, 2), (b, 2), (с, 2),
(а, 3), (b, 3), (с, 3), (a, 4), (b, 4), (c, 4)}.
Из этих двух выражений следует, что А×В≠В×A, т.е. операция де-
картова произведения некоммутативна. Кроме того, (А×В)∩(В×А)=∅,
поскольку A∩В=∅ и множество А×В содержит те же пары, что и мно-
жество B×A, но порядок элементов в парах другой. Если же А∩В≠∅, то
и (А×В)∩(В×А)≠∅.
Рассмотрим, например, множества А={а, b, с} и B={c, d}. Пересе-

Страницы