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

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

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

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

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

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

,

 

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

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

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

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

 

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

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

2А = 2cardА

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. Что такое перестановка с повторением и их число? + задача

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

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

 

 

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

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

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

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

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

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

 

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

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

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

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

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

0011 € Bin4; но числа мы умеем сравнивать (по первому биту, разряду). Получим отношение < на Binn для a, b € Binn – a < b, если a1 < b1 (1-й бит), либо, если a1 = b1, то a2 < b2 и т.д. Любые два набора можно сравнить (либо они равны, либо одни из них меньше)

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