Способы задания бинарных отношений

Существует четыре разных способа задания отношений, а преимущества каждого проявляются при разных характеристиках множества X.

Первый, очевидный, способ состоит в 1 непосредственном перечислении таких пар. Ясно, что он приемлем лишь в случае конечного множества R.

Второй удобный способ задания отношения R на конечном множестве — матричный. Все элементы нумеруются, и матрица отношения R определяется своими элементами для всех i и j. Известным примером такого задания отношений являются турнирные таблицы (если ничьи обозначить нулями, как и проигрыш, то матрица изобразит отношение «x_i — победитель y_j»).

Третий способ — задание отношения — 1 графом. Вершинам графа G(R) ставят в соответствия (пронумерованные) элементы множества X, и если x_iRy_j, то от вершины x_i проводят направленную дугу к вершине x_j.

Для определения отношений на бесконечных множествах альтернатив используется четвертый способ — задание отношения R - 1 сечениями. Множество называется верхним сечением отношения, а множество

R^-(x) = {y ∈ X | (y,x) ∈ R}

нижним сечением. Иначе говоря, верхнее сечение — это множество всех y, которые находятся в отношении xRy с заданным элементом x, а нижнее сечение — множество всех y, с которыми заданный элемент x находится в отношении R. Отношение однозначно определяется одним из своих сечений.

Пример: С - множество всех членов семьи. С={a,b,c,d,e}a-отец,b-мать,c,d,e-дети. R={(x,y)/”x есть отец y”, x, y прин. C}, R={(a,c),(a,d),(a,e)}

A={1,2} B={0,3} A*B={(1;0),(1;3),(2;0),(2;3)} a<b R={(a;b)/a<b, a прин А, в прин В} R={(1;3),(2;3)}

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

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

    Yandex.RTB R-A-252273-4