Способы задания множеств

Вопросы для самостоятельного изучения

(по курсу «Дискретная математика», первый семестр)

1. Множества: определения, примеры.

2. Способы задания множеств: порождающая процедура, разрешающая процедура.

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

4. Векторы и прямые произведения, определения, примеры.

5. Теорема о мощности прямого произведения множеств.

6. Проекции векторов и векторных множеств на оси.

7. Элементы комбинаторики: правило произведения, размещения без повторений, размещения с повторениями.

8. Элементы комбинаторики: перестановки без повторений, перестановки с повторениями.

9. Элементы комбинаторики: сочетания без повторений, правило суммы.

10. Соответствия: определения, свойства.

11. Взаимно однозначные соответствия и мощность множеств: утверждение о взаимно однозначном соответствии равномощных множеств, теорема о числе подмножеств конечного множества.

12. Взаимно однозначные соответствия и мощность множеств: семь утверждений о счетных множествах.

13. Взаимно однозначные соответствия и мощность множеств: теорема Кантора, теорема о числе подмножеств счетного множества.

14. Бинарные отношения и их свойства.

15. Отношения эквивалентности, отношения порядка. Лексико-графический порядок.

16. Понятие операции. Основные свойства бинарных операций.

17. Алгебры: определения и примеры.

18. Гомоморфизм и изоморфизм алгебр.

19. Булева алгебра и теория множеств: теорема 1 об изоморфизме булевых алгебр.

20. Булева алгебра и теория множеств: теорема 2 об изоморфизме булевых алгебр.

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

Множества. Определения, примеры.

Способы задания множеств

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

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

Например:

- множество всех станций Московского метро;

- множество левых ботинок;

- множество натуральных чисел: 1, 2, 3, 4 и т. д.;

- множество символов, доступных специальному печатающему устройству;

- множество кодов операций конкретного компьютера.

Для большинства примеров мы будем использовать некоторые абстрактные множества, такие как множества чисел.

Множества обычно обозначают прописными буквами, например, А. Если число принадлежит множеству, то будем говорить, что “оно является элементом множества”. Например, если а является элементом множества А, то это утверждение может быть записано следующим образом:

“ ”.

Утверждение “ b не является элементом А” будем обозначать

“ ”.

Символ происходит от греческой буквы .

Пример:

- множество всех натуральных чисел: 1, 2, 3,... Обозначим N. Часто 0 считают натуральным числом. Множество N с добавлением 0 обозначается .

- множество всех натуральных чисел, не превосходящих 100.

- множество всех решений уравнения (элементы множества - числа, являющиеся решением).

- множество всех чисел вида , где .

Определение: Множество А называется подмножеством множества В (обозначается ), если всякий элемент А является элементом В.

Говорят: В содержит Аили покрывает А.

Определение1: Множества А и В равны, если их элементы совпадают или если это два множества, имеющие одинаковые элементы.

Определение2: Множества А и В равны, если и . Определение 2 указывает на наиболее типичный метод доказательства (сначала доказывается , затем обратное .

Пример:

Тригонометрическая теорема: :

а) всякое решение уравнения имеет вид ;

б) всякое число вида является решением уравнения sin x = 1 .

Определение: Если и , то А называется строгим подмножеством множества В (обозначается , - строгое включение).