Прямое произведение множеств. Бинарные отношения. Способы задания бинарных отношений.

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

Если А = В, то А В =А² и называется декартовым квадратом.

Прямое произведение множеств А₁ , А₂ , …, А_n есть множество всех векторов (а₁ , а₂ , а₃ ,…, а_n) длины n таких , что а₁ А₁ , а₂ А₂ , …, а_n А_n .

Если А₁ = А₂ = … = А_n , то А₁ А₂ … А_n = А_n и называется декартовой степенью.

N-местным отношением или n-местным предикатом Р на множествах А₁ , А₂ , …, А_n называется

любое подмножество прямого произведения А₁ А₂ … А_n. Другими словами, элементы

х₁,х₂,…,х_n (где х₁ А_1,…, х_n А_n) связаны соотношением Р(обозначается Р(х₁,х₂,…,х_n)) тогда и только

тогда, когда (х₁,х₂,…,х_n) Р.

Наиболее часто встречаются двухместные отношения (n=2). В этом случае они называются

бинарными отношениями или соответствиями.

Отношения на конечных множествах обычно задаются:

1. Перечислением пар, для которых выполняется это отношение.

2. Матрицей бинарного отношения.

3. Словесным описанием (больше, меньше и т.д.)

4. Графически (на плоскости)

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

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

   Yandex.RTB R-A-252273-4