1. Множества (1)

Источники
Аляев Ю. А., Тюрин С. Ф. Дискретная математика и математическая логика.
Андерсон Дж. Дискретная математика и комбинаторика.
Кудрявцев Л. Д. Курс математического анализа. Т. 1.
Новиков Ф. А. Дискретная математика для программистов.
Хаггарти Р. Дискретная математика для программистов.

Множество

Условные обозначения

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

Круги Эйлера
1
2
4
5
6
7
3
8

Подмножество

Собственное подмножество

Задачи

Равенство множеств

Задачи

Мощность (конечного) множества

Булеан множества

Действия над множествами

Диаграммы Венна (Эйлера-Венна)
A
B
C
D
1
2
4
5
6
7
3
8

Дополнение множества
A

Дополнение множества
A
B

Пересечение множеств
A
B

Объединение множеств
A
B

Разность множеств
A
B

Симметрическая разность множеств
A
B

Выполняемые тождества

Кортеж

Декартово произведение множеств

Степень множества

Пример

Изображение декартова произведения

Свойства относительно операций над множествами

Комбинаторика

Источники
Андерсон Дж. Дискретная математика и комбинаторика.
Виленкин Н. Я., Виленкин А. Н., Виленкин П. А. Комбинаторика

Дерево (граф) возможных вариантов
Пример: Сколько трехзначных чисел можно составить из цифр 1, 3, 5 и 7, используя в записи числа каждую из них не более одного раза?

Правила суммы и произведения

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

Задача
В группе 24 человека. Из них 15 человек изучают английский язык, 12 – немецкий язык, 7 – оба языка. сколько человек не изучают ни одного языка?
Решение.
По принципу сложения получим количество людей, изучающих английский или немецкий: 15+12-7=20.
Из общего числа студентов вычтем полученное количество людей: 24-20=4. 4 человека не изучает ни одного языка.

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

Выборка

Число перестановок

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

Число сочетаний

Свойства сочетаний

Треугольник Паскаля

Отношения

Отношение

Пример

Пример
1
3
2
3
2
1
4
5
6
7

Обратное отношение

Композиция отношений

Бинарное отношение и его свойства

Виды отношений

Пример

Разбиение множества

Фактор-множество

Отображения (функции)

Отображение (функция)

Инъекция, сюръекция, биекция

Пример

Обратная функция

Композиция функций

Бесконечные множества

Конечные и бесконечные множества
КОНЕЧНОЕ МНОЖЕСТВО
БЕСКОНЕЧНОЕ МНОЖЕСТВО
Множество, не являющееся конечным.
Множество, мощность которого не меньше мощности множества натуральных чисел.
Множество, для которого существует биекция с некоторым его собственным подмножеством.

Равномощность множеств

Бесконечные множества
СЧЁТНОЕ МНОЖЕСТВО
Бесконечное множество, элементы которого возможно пронумеровать натуральными числами.
Множество, для которого можно задать биекцию с множеством натуральных чисел.
Бесконечное множество, равномощное множеству натуральных чисел.
Мощность множества обозначается .
НЕСЧЁТНОЕ МНОЖЕСТВО
КОНТИНУАЛЬНОЕ МНОЖЕСТВО (КОНТИНУУМ)

Мощность множества
Класс эквивалентности по отношению равномощности.

Специальные функции

Бинарная операция

Универсальная алгебра

Полугруппа

Группа

Пример 1

Пример 2

Пример 3

Пример 4

Пример 5

Операции коммутативной группы
АДДИТИВНАЯ
МУЛЬТИПЛИКАТИВНАЯ
Обозначение операции:
Нейтральный элемент:
Противоположный элемент:

Кольцо

Пример 1

Поле
Если кольцо имеет мультипликативный нейтральный элемент (единицу), оно называется кольцом с единицей.
Если операция умножения коммутативна, кольцо называется коммутативным.
Коммутативное кольцо называется полем, если его ненулевые элементы образуют группу, относительно операции умножения.

Примеры