Подмножества и их свойства.

Множество А называется подмножеством В, если любой элемент, принадлежащий А, принадлежит В.

АᴄВ<=> . Если АᴄВ, то будем также говорить, что множество А содержится в В, или имеется включение А в В. Множества А и В называются равными или совпадающими (обозначается А=В), если они состоят из одних и тех же элементов, т.е. если АᴄВ и ВᴄА. Таким образом, чтобы доказать равенство множеств, требуется установить два включения.

Свойства подмножеств:

1. A, AcA

2. A, cA

3. A,B,C: { АᴄВ, BᴄC => A ᴄC - транзитивность

4. A,B: А=В { АᴄВ, ВᴄА

На свойстве 4 основано доказательство равенства множеств А и В, т.е. для того чтобы доказать, что А=В, нужно доказать два включения АᴄВ(x A,x B), ВᴄА(y B,y A). Этот способ доказательства позволяет проверить равенство множеств, не прибегая к сравнению всех элементов, что актуально для бесконечных множеств.

3. Yandex.RTB R-A-252273-3
   Содержание

   • Множества. Элементы множеств. Интуитивный принцип объемности. Способы задания множества. Мощность множества.
   • Подмножества и их свойства.
   • Операции над множествами: объединение, пересечение, разность, дополнение. Диаграммы Эйлера-Венна.
   • Свойства операций над множествами (с доказательством).
   • Прямое произведение множеств. Бинарные отношения. Способы задания бинарных отношений.
   • Операции над бинарными отношениями: композиция отношений, степень отношения, обратное отношение, дополнение отношения, объединение, пересечение, разность отношений.
   • Свойства бинарных отношений: рефлексивность, антирефлексивность, симметричность, антисимметричность, транзитивность, связность.
   • Замыкания отношений. Транзитивное замыкание, рефлексивное транзитивное замыкание. Теоремы о транзитивном и рефлексивном транзитивном замыкании.
   • Операции над бинарными отношениями, заданными в матричной форме.
   • Алгоритм определения матрицы транзитивного замыкания бинарного отношения.
   • Отношение эквивалентности. Классы эквивалентности и их свойства. Разбиения множеств. Связь эквивалентности с разбиением (теоремы с доказательством).
   • Отношение порядка. Строгий и нестрогий порядок. Частичный и полный порядок. Упорядоченные множества.
   • Соответствия. Образ и прообраз. Свойства соответствий: всюду определенные, инъективные, сюръективные, функциональные, взаимнооднозначные соответствия.
   • Функции и отображения. Виды отображений. Обратные соответствия и функции. Способы задания функций.
   • Алгебраические операции. Примеры операций. Арность операции. Способы задания.
   • Свойства бинарных алгебраических операций: коммутативность, ассоциативность, дистрибутивность, поглощение, идемпотентность. Нейтральный и симметричный элементы.
   • Комбинаторные правила суммы и произведения. Выборки (упорядоченные, неупорядоченные, с повторениями и без).
   • Операции над графами.
   • Способы представления графов и орграфов на эвм: матрица смежности, матрица инцидентности, список смежности, массив ребер (дуг).
   • Маршруты в графах. Виды маршрутов: замкнутые и незамкнутые. Цепь. Простая цепь. Цикл. Простой цикл. Длина маршрута. Расстояние между вершинами. Диаметр графа.
   • Орграфы и бинарные отношения. Отношение достижимости вершин орграфа. Матрица достижимости. Связь между отношениями достижимости и смежности.
   • Определение матрицы достижимости орграфа как матрицы рефлексивного и транзитивного замыкания отношения смежности.
   • Алгоритм выделения компонент связности (сильной связности)
   • Нагруженные орграфы Длина пути в нагруженном орграфе. Минимальные пути в нагруженных орграфах.
   • Нагруженные орграфы. Алгоритм Форда-Беллмана выделения минимального пути в нагруженном орграфе.

   Yandex.RTB R-A-252273-4