Что называется объединением, пересечением, разностью, симметрической разностью множества, дополнение множества до универсального множества?

· Объединение множеств А и В - это множество АUВ, состоящее из всех элементов множества А и всех элементов множества В.

· Пересечение множеств А и В - это множество А∩В, состоящее из тех элементов, которые одновременно принадлежат и А и В.

· Разность множеств А и В- это множество А\В, состоящее из тех элементов множества А, которые не принадлежат множеству В.

· Симметрическая разность множеств А и В - это множество:

· Дополнение множества А до универсального Ω, это множество:

,

2. Что такое биективное, сюрьективное, инъективное отображение множеств? (с примерами) + задача

· Отображение f:A→B называется инъективным, если различные элементы множества А переходят в различные элементы множества В.

· Отображение f:A→B называется сюръективным, если каждый элемент множества В имеет свой прообраз в А.

· Отображение f:A→B называется биективным, если оно инъективно и сюръективно.

3. Что вы знаете о мощности множества двоичных наборов и о мощности всех подмножеств данного множества? (с примером)

· Дано множество А. Множество всех его подмножеств включая само А и Ø, обозначается 2^А.

2^А = 2^cardА

4. Что такое правило произведения? (с примером)

· Декартово произведение множеств А и В - это множество АхВ, состоящее из всех пар (а, b), где а принадлежит А, b принадлежит В.

· Правило произведения: cardAxB = cardA * cardB.

· Пример: A={1,2}; B={a, b, c}

AxB = {1a, 1b, 1c, 2a, 2b, 2c}, следовательно card AxB=6.

5. Что такое перестановки и число перестановок? + задача

· Перестановки: пусть имеются n различных объектов, которые можно переставить между собой. Сколькими способами это можно сделать?

· Число перестановок из n различных объектов равно:

6. Что такое размещение и число размещений? + задача

· Размещения: пусть из n-различных предметов нужно выбрать k-штук (k <= n), причем порядок выбора существенен. Это и есть размещения.

· Число размещений равно:

7. Что такое сочетание и число сочетаний? + задача

· Пусть из n-различных предметов выбираем k-штук, причем порядок выбора не существенен. Это и есть число сочетаний.

· Число сочетаний равно:

8. Что такое перестановка с повторением и их число? + задача

· Перестановка с повторениями: пусть имеется k₁ предметов 1-го типа, k₂ предметов второго типа …, k_m предметов m-го типа. Всего k₁ + k₂ + … k_m = n.

· Число различных перестановок равно:

9. Что такое рефлексивное, симметричное, транзитивное отношение, отношение эквивалентности и его основное свойство? + задача

· Отношение Г называется рефлексивным, если (a;a) € Г для всех a € A (без скобок аГа, аГb; Отношение называется антирефлексивным, если аГа никогда не выполняется).

· Отношение Г симметрично, если аГb → bГа; Отношение называется ассиметричным, если аГb и bГа → b = а; Отношение называется антисимметричным, если аГb и bГа невозможно.

· Отношение Г называется транзитивным, если аГb и bГc → аГс.

· Если отношение рефлексивно, симметрично и транзитивно, то оно называется отношением эквивалентности.

· Основное свойство отношения эквивалентности: если на множестве А задано отношение эквивалентности, то множество распадается, на объединение пересекающихся классовых множеств, в каждом из которых все элементы эквивалентны друг другу.

10. Что такое отношение строгого и нестрогого порядка? + задача

· Отношение Г называется отношением строгого порядка, если оно антирефлексивно, антисимметрично и транзитивно.

· Отношение Г называется отношением нестрого порядка, если оно рефлексивно, асимметрично и транзитивно.

11. В чем состоит числовое сравнение двоичных наборов и как их сравнить по правилу Парето? + задача

· Набор из Bin_n мы можем рассматривать, как двоичные числа, иногда с незначащими нулями слева,

0011 € Bin₄; но числа мы умеем сравнивать (по первому биту, разряду). Получим отношение < на Bin_n для a, b € Bin_n – a < b, если a₁ < b₁ (1-й бит), либо, если a₁ = b₁, то a₂ < b₂ и т.д. Любые два набора можно сравнить (либо они равны, либо одни из них меньше)

· a <= b, если a_i <= b_i для всех i от 1 до n