Немного теории к коллоквиуму по дискретной математике (не все вопросы!!!)

1. Множества. Мощность множества. Операции над множествами. Комбинаторные операции. Правила суммы и правила произведения. Обобщенное правило суммы. Обобщенное правило произведения.

Множество – любое собрание объектов, определённых и хорошо различимых нашей интуицией или интеллектом, мыслимое как единое целое (Георг Кантор, 1872 г.).

Множества обозначаются большими буквами, элементы множества – малыми.

Мощность множества. Для конечных множеств мощность –количество элементов во множестве. Мощность множества S обозначается |S|. Например, S={a, b, c}, |S|=3.

Множества называются равномощными (эквивалентными), если их мощность равны.

Комбинаторные операции:

• Отбор подмножеств;

• Упорядочивание элементов.

Операции над множествами

Пусть заданы множества A и B.

Объединение множеств A и B – множество АВ={x : xA или xB} (объединение содержит элементы, которые есть или в A, или в B, или в том и другом множестве). (нарисовать с помощью кругов Эйлера). АВ= BA.

Пересечение множеств A и B – множество АВ={x : xA и xB} (пересечение содержит элементы, которые есть одновременно и в A, и в B. (нарисовать). АВ= BA.

Дополнение до универсального множества. Если В – универсальное множество, и АВ, то дополнение ={x : xB и xA}. (нарисовать).

Произведение множеств A и B – множество AxB={<x, y> : xA, yB} (множество всех пар, первый элемент которых принадлежит множеству A, второй элемент – множеству B). Мощность произведения AxB равна произведению мощностей A и B (|AxB|=|A|*|B|). Произведение BxA не равно AxB, но их мощности совпадают (BxA  AxB, но |BxA| = |AxB|).

Пример: A={a, b, c}, B={c, d}, |A|=3, |B|=2.

АВ={a, b, c, d}, АВ={c}, AxB={<a,c>, <a,d>, <b,c>, <b,d>, <c,c>, <c,d>}, BxA={<c,a>, <c,b>, <c,c>, <d,a>, <d,b>, <d,c>}, |AxB|=6, |BxA|=6.

Оператор (функция) – правило, определяющее отображение некоторого множества X в некоторое множество Y. Обозначение: F : XY.

Пример: X={a, b, c, d}, Y={▲, ●, ■}. Возможный вариант функции: f(a)=■, f(b)=●, f(c)=■, f(d)=▲.

X Y

a ▲

b ●

c ■

d

Правило суммы

Если объект a можно выбрать p способами, а объект b – другими q способами, то выбор “либо a, либо b” может быть осуществлен p+q способами. При этом выборы a и b являются взаимно исключающими.

Например, в вазе лежит 3 яблока и 5 груш. Тогда взять из вазы либо одно яблоко, либо одну грушу (взаимоисключающие события) можно 3+5 = 8 способами.

Обобщённое правило суммы

Пусть дано r множеств T_i (i=1,…,r), каждое из которых содержит n_i элементов (T_i - n_i‑множество), причём множества взаимно не пересекаются: T_iT_j= при ij. Тогда объединение этих множеств S=T₁ T₂…T_r есть (n₁+…+n_r)-множество. .

Правило произведения

Если объект a можно выбрать p способами, и после каждого из таких выборов объект b можно выбрать q способами, то выбор “a и b” в указанном порядке может быть осуществлен p·q способами. При этом выборы a и b являются независимыми.

Например, в вазе лежит 3 яблока и 5 груш. Тогда взять из вазы одно яблоко и одну грушу (события происходят совместно) можно 3·5 = 15 способами.

Обобщённое правило произведения

Пусть дано r множеств T_i (i=1,…,r), каждое из которых содержит n_i элементов (T_i - n_i‑множество), причем неважно, пересекаются ли T_i или нет. Осуществим выбор элементов последовательно из множеств T_i.

Выбирая из Т₁, получим множество М₁ – множество всех возможных выборок по одному элементу из Т₁. (М₁ – n₁-множество). М₁=Т₁

Выбирая сначала из Т₁, потом из Т₂, получаем множество М₂ упорядоченных пар элементов из Т₁ и Т₂ (М₂ – n₁n₂-множество). М₂=Т₁xТ₂=M₁xТ₂.

Аналогично М₃=Т₁xТ₂xТ₃=M₂xТ₃ – множество упорядоченных троек (n₁n₂n₃-множество); М₄=Т₁xТ₂xТ₃xТ₄=M₃xТ₄ – n₁n₂n₃n₄-множество; … ; М_r= M_r-1xТ_r – n₁n₂…n_r-множество. То есть произведение r множеств есть n₁n₂…n_r-множество.

.

2. Выборка. Виды выборок. Примеры. Упорядоченные выборки. Теоремы о числе упорядоченных выборок без повторений. Доказательства. Следствия.