Декартово произведение множеств. Среди студентов группы присутствуют следующие три студента-прогульщика: Иванов (И), Петров (П) и Сидоров (С)

Пример 3.

Пример 2.

Среди студентов группы присутствуют следующие три студента-прогульщика: Иванов (И), Петров (П) и Сидоров (С). Хотя все они часто прогуливают занятия, И умудряется учиться на отлично, П является хорошистом, а С – троечником.

Преподаватель, желая наказать студентов за прогулы, решил в течение всего занятия вызывать их к доске. При этом он составил для себя такую последовательность вызова студентов:

< С, И, П, С, П, С, И, С, П, С, П, И, С, П, С, П, И, П, С, П, С, И, С >

Данная последовательность составлена таким образом, чтобы чаще других к доске ходил С, а реже других – И. Очевидно, что в данной последовательности объекты повторяются, а порядок следования объектов важен и без вмешательства преподавателя не может меняться. Поэтому данная последовательность является кортежем.

В Украине ежегодно проводится независимое тестирование выпускников школ. При этом в Министерстве образования составляется порядок следования предметов на текущий год. Например, порядок может быть таким:

< укр. язык, математика, история, география, иностр. язык, биология >

В данном списке важен порядок следования предметов, который определяет порядок подготовки учащихся к тестированию. Хотя в данном случае предметы не повторяются, данная последовательность является кортежем. Одновременно последовательность может рассматриваться и как множество – в этом случае порядок следования предметов не имеет значения и может быть произвольным.

Декартовым (прямым) произведением множеств A и B называется множество всех упорядоченных пар (кортежей) < a, b > таких, что a Î A и b Î B. Декартово произведение обозначается A ´ B:

A ´ B = { < a, b > | a Î A, b Î B }.

Если A и B – конечные множества мощности m и n соответственно, то их декартово произведение также будет конечным множеством, и его мощность будет составлять m × n. Если A и B – не более, чем счетные множества, то их декартово произведение также будет не более, чем счетным. Если одно из множеств пустое, то и A ´ 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>; <a, 2>; <b, 1>; <b, 2>; <c, 1>; <c, 2>}

Обратим внимание, что речь идет об упорядоченных парах (кортежах), т.е., в отличии от множеств, <1, a> ¹ <a, 1>.

Понятие прямого произведения допускает обобщение.

Декартово произведение множеств A ₁, A ₂, …, A_n – это множество кортежей:

A ₁´ A ₂´…´ A _n={< a ₁, a ₂, …, a _n> | a ₁Î A ₁ Ù a ₂Î A ₂ Ù … Ù a _nÎ A _n}.

Понятно, что мощность результирующего множества равна произведению мощностей перемножаемых множеств.

Пример. Пусть A ={ a ₁, a ₂}, B ={ b ₁, b ₂}, C ={ c ₁, c ₂}. Описать множество D = A ´ B ´ C.

D = {a₁, a₂}´{b₁, b₂}´{c₁, c₂} = {< a ₁, b ₁, c ₁>, < a ₁, b ₁, c ₂>, < a ₁, b ₂, c ₁>, < a ₁, b ₂, c ₂>, < a ₂, b ₁, c ₁>, < a ₂, b ₁, c ₂>, < a ₂, b ₂, c ₁>, < a ₂, b ₂, c ₂>}.

В данном примере |D| = 2*2*2 = 8.

В декартовом произведении множества A _i не обязательно различны.

Декартовой степенью n множества A называется его декартово произведение самого на себя n раз:

Aⁿ = A ´ A ´…´ A.

При этом |Aⁿ| = |A|ⁿ.

Считается, что A ⁰=Æ, A ¹= A, A ²= A ´ A, или в общем случае Aⁿ = A ´ A^{n -1}.

Пример 1. Пусть A ={a, b, c}. Описать множество A ².

A ² = A ´ A = {a, b, c}´{a, b, c} = {<a, a>, <a, b>, <a, c>, <b, a>, <b, b>, <b, c>,
<c, a>, <c, b>, <c, c>}.

Пример 2. Пусть A ={0, 1}. Описать множество A³.

A ³ = A ´ A ´ A = {0, 1}´{0, 1}´{0, 1} = {<0, 0, 0>, <0, 0, 1>, <0, 1, 0>, <0, 1, 1>, <1, 0, 0>, <1, 0, 1>, <1, 1, 0>, <1, 1, 1>}.

Отметим, что в каждом из перечисленных кортежей первой компонентой является элемент первого из перемножаемых множеств, второй компонентой – элемент второго множества, третьей компонентой – элемент третьего множества.

Лекция 4.

Дата добавления: 2014-01-06