1.5.Упорядоченные множества

1.5.1Понятие вектора

Под вектором понимается упорядоченный набор элементов. Определение является не строгим (интуитивным), так же как и определение множества.

Элементы, образующие вектор, называются координатами или компонентами вектора. Число координат вектора называется его длиной или размерностью. Синонимом понятия «вектор» является «кортеж».

Для обозначения вектора обычно используются скобки, например (1, 2, 1, 3). Иногда скобки и даже запятые в обозначении вектора опускаются.

Примером векторов могут служить целые числа, при этом отдельные цифры числа являются координатами этого вектора.

Замечание. В отличие от элементов множеств, некоторые координаты вектора могут совпадать.

Векторы длины два называются упорядоченными парами (или просто парами), длины три – тройками, …, длины n – n-ками и т.д.

Два вектора равны, если они имеют одинаковую длину и соответствующие их координаты равны, т.е.

(а₁, а₂, …, а_m)=(b₁, b₂,…,b_n), если m=n и a₁=b₁, a₂=b₂, …, a_m=b_m.

Векторы (кортежи) образуют особый класс множеств, называемых упорядоченными. В отличии от множеств, элементы которых могут быть перечислены в произвольном порядке, для элементов (координат) вектора существенным является их положение внутри вектора. В связи с этим множества, содержащие одинаковые элементы, но в различном порядке, равны {a, b}={b, a}, а вектора – не равны (a, b)  ( b, a).

1.5.2Прямое (декартово) произведение множеств

Прямым (декартовым) произведением множеств А и В называется множество всех пар (а,b), таких, что аА и bВ.

Прямое произведение множеств А и В обозначается в виде АВ:

АВ={(a,b)aA и bB}.

П ример 1.10

А={a,b,c}; B={b,c}.

AB={(a,b), (a,c), (b,b), (b,c), (c,b), (c,c)};

BA={(b,a}, (b,b), (b,c), (c,a), (c,b), (c,c)}.

Замечание. Из рассмотренного примера видно, что АВВА, т.е. коммутативный закон для прямого произведения множеств не действует.

Пример 1.11

Х – множество точек отрезка [0;1];

Y – множество точек отрезка [1;2].

Тогда ХY – множество точек квадрата с вершинами в точках (0,1), (0,2), (1,1), (1,2).

1.5.3 Декартова степень множества

Прямое (декартово) произведение одинаковых множеств называется декартовой степенью множества:

если В=А, то АВ=АА=А².

Точка на плоскости может быть задана упорядоченной парой координат, т.е. двумя точками на координатных осях. Та как координаты представляются множеством действительных чисел R, то прямое произведение RR=R² представляет собой множество координат точек плоскости.

Замечание. Метод координат ввел в употребление Рене Декарт, отсюда и название «декартово произведение».

Прямым (декартовым) произведением множеств А₁, А₂, …, А_n называется совокупность всех упорядоченных n-ок (векторов длиной n) (a₁, a₂, …, a_n) таких, что a_iAi (i=1,2,…,n). В случае, если А₁=А₂=…=А_n=А, то А₁А₂…А_n = Аⁿ - n-ая декартова степень множества А.

Пример 1.12

Х – множество точек отрезка [0;1];

Y – множество точек отрезка [1;2];

Z – множество точек отрезка [0;0,5].

XYZ – множество точек пространства, ограниченного параллелепипедом.

Замечание. Декартово произведение RRR= R³ представляет собой множество координат точек пространства.

1.5.4 Мощность прямого произведения множеств

Теорема. Пусть А₁, А₂, …, А_n – конечные множества мощностью m₁, m₂, …, m_n. соответственно, т.е. А₁=m₁,A₂=m₂, …,A_n=m_n.. Тогда мощность их прямого произведения равна произведению мощностей множеств – сомножителей, т.е.

А₁А₂…А_n=m₁*m₂*…*m_n

Следствие: Мощность n-ой декартовой степени множества А равна n-ой степени мощности этого множества Аⁿ=Aⁿ

1.5.3Основные тождества для операции

прямого произведения множеств

1. (АВ)  (CD) = (АC)  (BD);

2. (АВ)  C = (АC) (BC);

3. (А\В)  C = (АC) \(BC);

4. А(В\C) = (АB) \(AC).

Литература

1. Новиков Ф.А. Дискретная математика для программистов. 3-е изд. СПб.:Питер, 2009.–383 с.

2. Тюрин С.Ф. Дискретная математика: Практическая дискретная математика и математическая логика: учеб. пособие. /С.Ф.Тюрин, Ю.А. Аляев. – М.:Финансы и статистика, 2010. – 384 с.

3. Гладков Л.А., Курейчик В.В., Курейчик В.М.: Дискретная математика: теория множеств, алгоритмом, алгебры логики: Учебное пособие / Под ред. В.М.Курейчика. – Таганрог: изд-во ТТИ ЮФУ, 2009. – 312 с.

4. Нефедов В.Н., Осипова В.А. Курс дискретной информатики: Учеб. пособие. – М.:изд-во МАИ, 1992. – 264 с.

5. Кузнецов О.П. Адельсон-Вельский Г.М. Дискретная математика для инженеров. 2-е изд., перераб. и доп. – М.: Энергоатомиздат, 1988. – 480с.