Найти область значений бинарного отношения

Пусть Aотношения title="A"> и B два конечных множества. Декартовым произведением множеств A и B называют множество A\times B,состоящее из всех упорядоченных пар, где  a\in A, b\in B.

Бинарным отношением между элементами множества A и B называется любое подмножество R множества A\times B, то есть  R\subset A\times B.

По определению, бинарным отношением называется множество пар. Если R — бинарное отношение (т.е. множество пар), то говорят, что параметры x и y связаны бинарным отношением R, если пара \langle x,y \rangle является элементом R, т.е. \langle x,y \rangle\in R.

Высказывание: «предметы x и y связаны бинарным отношением R» записывают в виде xRy.Таким образом,  xRy\leftrightarrow\langle x,y\rangle\in R.

Если R\subset A\times A , то говорят, что бинарное отношение определено на множестве A.

Примеры бинарных отношений:

  • на множестве целых чисел Z отношения «делится», «делит», «равно», «больше», «меньше», «взаимно просты»;
  • на множестве прямых пространства отношения «параллельны», «взаимно перпендикулярны», «скрещиваются», «пересекаются», «совпадают»;
  • на множестве окружностей плоскости «пересекаются», «касаются», «концентричны».
  • Областью определения бинарного отношения R называется множество, состоящее из таких x, для которых \langle x,y \rangle\in R хотя бы для одного y.
    Область определения бинарного отношения будем обозначать  \Re R.
    \Re R=\{ x|\exists y(\langle x,y\rangle\in R)\}
    Областью значений бинарного отношения R называется множество, состоящее из таких y, для которых \langle x,y \rangle\in R хотя бы для одного x.
    Область значений бинарного отношения будем обозначать \Im R
    \Im R=\{ y|\exists x(\langle x,y\rangle\in R)\}

    Инверсия (обратное отношение) R — это множество \{\langle x,y\rangle |\langle y,x\rangle\in R\} и обозначается, как {R}^{-1}.

    Композиция (суперпозиция) бинарных отношений R и S — это множество \{\langle x,y\rangle |\exists z\langle xSz\wedge zRy\rangle\} и обозначается, как R\circ S.

    Бинарное отношение R на некотором множестве M может обладать различными свойствами, например:

    • Рефлексивность: \forall x\in M(xRx)
    • Антирефлексивность (иррефлексивность): \forall x\in M\neg (xRx)
    • Корефлексивность: \forall x,y\in M(xRy\Rightarrow x=y)
    • Симметричность: \forall x,y\in M(xRy\Rightarrow yRx)
    • Антисимметричность: \forall x,y\in M(xRy\wedge yRx\Rightarrow x=y)
    • Асимметричность: \forall x,y\in M(xRy\Rightarrow\neg (yRx)). Асимметричность эквивалентна одновременной антирефлексивности и антисимметричности отношения.
    • Транзитивность: \forall x,y,z\in M(xRy\wedge yRz\Rightarrow xRz)
    • Связность: \forall x,y\in M(x\neq y\Rightarrow xRy\lor yRx)
    • Рефлексивное транзитивное отношение называется отношением квазипорядка
    • Рефлексивное симметричное транзитивное отношение называется отношением эквивалентности
    • Рефлексивное антисимметричное транзитивное отношение называется отношением (частичного) порядка
    • Антирефлексивное антисимметричное транзитивное отношение называется отношением строгого порядка
    • Полное антисимметричное (для любых x, y выполняется xRy или yRx) транзитивное отношение называется отношением линейного порядка
    • Над бинарными отношениями можно производить некоторые операции, точно так же, как и над множествами. Не ограничивая общности, будем считать, что следующие операции выполняются на множестве M.

      • Пересечение. Пересечением двух бинарных отношений (Aи B) является отношение, которое определяется пересечением соответствующих подмножеств. Очевидно, что отношение A\cap B выполнимо только в том случае, когда некоторые x и y связаны как первым, так и вторым отношением (xAy и xBy).

        Например, пересечением отношения «не меньше» и «не равно» является отношение «больше».
         xAy\Leftrightarrow x\geq y, xBy\Leftrightarrow x\neq y, тогда A\cap B\Leftrightarrow x>y

      • Объединение. Объединением двух бинарных отношений (A и B) является отношение, которое определяется объединением соответствующих подмножеств. Отношение A\cup B выполнимо только в том случае, когда некоторые x и y связаны хотя бы одним из двух отношений хотя бы одно из отношений (xAy или xBy).

        Например, объединением отношения «больше» и отношения «равно» является отношение «больше, либо равно».

      • Включение. Обозначается A\subseteq B. Первое отношение включено во второе, если все те пары, для которых выполняется первое отношение, являются подмножеством пар, для которых выполняется второе отношение. Если A\subseteq B, то A\neq B. Если A\subseteq B, то, когда любые два элемента из множества, на котором выполняется отношение A, связаны этим отношением, они связаны отношением B.
      • Очевидно, для любого отношения A \varnothing\subseteq A\subseteq U, где \varnothing — пустое, а U— полное отношение.

      Приведём в пример два графических представления бинарных отношений на множстве X = \{a, b, c, d, e\}.
      Первый способ тесно связан с аналитической геометрией. Пусть дана пара взаимно перпендикулярных осей (Ox и Oy). На каждой оси нужно отметить точки которые являются элементами множества X.
      Будем считать, что a, b, c, d, e — координаты точек на горизонтальной и вертикальной осях. Теперь отметим на плоскости точки с координатами (x, y). На рисунке изображена совокупность точек, соответствующих следующему отношению: R=\{(a, b), (a, c), (b, d), (c, e), (e,b), (e, e)\}.
      Image1

      Следующий способ, который мы рассмотрим, заключается в использовании ориентированных графов. Элементы множества X становятся вершинами графа, а элементы \langle x,y\rangle отношения R ребрами, которые соединяют первый член x отношения со вторым членом y. Граф, соответствующий бинарному отношению R, изображен на рисунке.
      Image1

      Задача

      Бинарное отношение R задано на множестве A=\{1,2,3,4\}, определить его свойства.
      R=\{(1,1),(1,2),(2,3),(2,2),(2,4)\}

      ... ^Cпоказать</>

      Проверим все свойства отношения:
      • Рефлексивность
        (\forall x\in A)\langle x,x\rangle\in R – это ложное высказывание.
        Можно привести контрпример: x=3, пара \langle 3,3\rangle не принадлежит множеству R. Бинарное отношение не является рефлексивным.
      • Антирефлексивность
        (\forall x\in A)\langle x,x\rangle\notin R – это ложное высказывание.
        Можно привести контрпример: x=1, пара \langle 1,1\rangle принадлежит множеству R. Бинарное отношение не является антирефлексивным.
      • Корефлексивность
        (\forall x,y\in A)\langle x,y\rangle\notin R – это ложное высказывание.
        Можно привести контрпример: x=1,y=2, пара \langle 1,2\rangle принадлежит множеству R, но x\neq y. Бинарное отношение не является антирефлексивным.
      • Симметричность
         \forall x,y\in A (\langle x,y\rangle\in R): \langle y,x\rangle\in R – это ложное высказывание.
        Можно привести контрпример, x=1,y=2 пара \langle 1,2\rangle принадлежит множеству R, а пара \langle 2,1\rangle не принадлежит множеству R. Бинарное отношение не является симметричным.
      • Антисимметричность
        \forall x,y\in A(xRy\wedge yRx\Rightarrow x=y) – это истинное высказывание
        Контрпример подобрать невозможно. Бинарное отношение является антисимметричным.
      • Асимметричность
        Асимметричность эквивалентна одновременной антирефлексивности и антисимметричности отношения и отношение не является антирефлексивным, отношение не является асимметричным.
      • Транзитивность
        \forall x,y,z\in A(xRy\wedge yRz\Rightarrow xRz)– это ложное высказывание.
        Можно привести контр пример, x=1,y=2,z=3 пара \langle 1,2\rangle принадлежит множеству R и пара \langle 2,3\rangle принадлежит множеству R, а пара \langle 1,3\rangle не принадлежит множеству R. Бинарное отношение не является транзитивным.
      • Связность
        \forall x,y\in A(x\neq y\Rightarrow xRy\lor yRx) – это ложное высказывание.
        Можно привести контрпример, x=3,y=4, 3\neq 4 пара \langle 3,4\rangle не принадлежит множеству R и пара \langle 4,3\rangle не принадлежит множеству R. Бинарное отношение не является связанным.

      Вывод: заданное бинарное отношение обладает только одним свойством антисимметричности.

      Источники:

      • Галушкина, Марьямов, «Задачи и упражнения по дискретной математике», 2007 г., стр.51
      • С.В.Федоровский.Конспект лекций по математической логике
      • Кострикин А.В., «Введение в алгебру», 1977, стр.134
      • А.И. Мальцев, «Алгебраические системы», 1970, стр.16-19
      • Бинарные отношения

        0 из 3 заданий окончено

        Вопросы:

        1. 1
        2. 2
        3. 3

        Информация

        Вопросы для закрепления пройденного материала

        Вы уже проходили тест ранее. Вы не можете запустить его снова.

        Тест загружается...

        Вы должны войти или зарегистрироваться для того, чтобы начать тест.

        Вы должны закончить следующие тесты, чтобы начать этот:

        Правильных ответов: 0 из 3

        Вы набрали 0 из 0 баллов (0)

        Рубрики

        1. Нет рубрики 0%
        2. Алгебра 0%
        Ваш результат был записан в таблицу лидеров

        Загрузка

        Имя: E-Mail:
        Капча: captcha
        1. 1
        2. 2
        3. 3
        1. С ответом
        2. С отметкой о просмотре
        1. Задание 1 из 3

          Пусть A={1}.Запишите хотя бы один элемент декартового произведения A\times A как пару чисел, разделённых запятой. Например: 8,9.

          Правильно

          Неправильно

        2. Задание 2 из 3

          Бинарное отношение xRy\leftrightarrow x^2=y^2 определено на множестве действительных чисел R. Какими свойствами из приведенных ниже оно обладает?

          • Рефлексивность
          • Антирефлексивность
          • Симметричность
          • Антисимметричность
          • Связность
          • Транзитивность

          Правильно

          Неправильно

        3. Задание 3 из 3

          Для бинарного отношения R множество, состоящее из таких x, для которых \langle x,y\rangle\in R хотя бы для одного y называется

          • (областью определения)

          Правильно

          Неправильно

        Таблица лучших: Бинарные отношения

        максимум из 15 баллов Место Имя Записано Баллы Результат
        Таблица загружается
        Нет данных

        Похожее

© 2012-2016: Нохум-Даниэль Блиндер (11), Анастасия Лозинская (10), Юлия Стерлянко (8), Денис Стехун (8), Игорь Любинский (8), Олег Шпинарев (7), Александр Базан (7), Валентин Малявко (7), Анна Чалапчий (7), Константин Берков (7), Татьяна Корнилова (6), Влад Радзивил (6), Максим Швандт (6), Людмила Рыбальченко (6), Марина Чайковская (5), Екатерина Шибаева (5), Мария Корень (5), Анна Семененко (5), Мария Илларионова (5), Сергей Черкес (5), Валерия Заверюха (5), Елизавета Снежинская (5), Вадим Покровский (5), Даниил Радковский (5), Влад Недомовный (5), Александр Онищенко (5), Денис Базанов (5), Александр Ковальский (5), Александр Земсков (5), Святослав Волков (4), Алёна Гирняк (4), Николай Царев (4), Роман Бронфен-Бова (4), Артём Романча (4), Анна Шохина (4), Никита Савко (4), Кондрат Воронов (4), Иван Чеповский (4), Игорь Чернега (4), Даниил Кубаренко (4), Ольга Денисова (4), Яков Юсипенко (4), Ольга Слободянюк (4), Руслан Авсенин (4), Екатерина Фесенко (4), Дмитрий Заславский (4), Полина Сорокина (4), Кирилл Демиденко (4), Дмитрий Стеценко (4), Илья Бровко (3), Максим Носов (3), Филип Марченко (3), Станислав Чмиленко (3), Катя Писова (3), Дмитрий Дудник (3), Дарья Кваша (3), Игорь Стеблинский (3), Виктор Булгаков (3), Игорь Вустянюк (3), Андрей Яроцкий (3), Екатерина Мальчик (3), Анатолий Осецимский (3), Дмитрий Робакидзе (3), Вячеслав Зелинский (3), Стефания Амамджян (3), Валерия Сиренко (3), Вячеслав Иванов (3), Андрей Бойко (3), Милан Карагяур (3), Александр Димитриев (3), Стас Коциевский (3), Павел Бакалин (3), Антон Локтев (3), Константин Грешилов (3), Марина Кривошеева (3), Денис Куленюк (3), Константин Мысов (3), Мария Карьева (3), Колаев Демьян (3), Станислав Бондаренко (3), Ильдар Сабиров (3), Кирилл Сплошнов (3), Дмитрий Козачков (3), Алёна Янишевская (3), Дмитрий Байков (3), Павел Загинайло (3), Надежда Кибакова (2), Майк Евгеньев (2), Евгений Колодин (2), Денис Карташов (2), Роман Гайдей (2), Гасан Мурадов (2), Алексей Никифоров (2), Настя Филипчук (2), Михаил Абабин (2), Бриткариу Ирина (2), Юрий Олейник (2), Татьяна Таран (2), Настя Кондратюк (2), Сергей Запорожченко (2), Георгий Луценко (2), Настя Панько (2), Дэвид Ли (2), Александр Коломеец (2), Евгения Максимова (2), Алексей Пожиленков (2), Юрий Молоканов (2), Александр Гутовский (2), Таня Спичак (2), Радомир Сиденко (2), Алина Гончарова (2), Андрей Сидоренко (2), Юлия Стоева (2), Юрий Холодков (1), Марк Носуленко (1), Артак Григорян (1),


Закрыть ... [X]

Лекция 3. Отношения на множествах. Свойства Как сделать игрушечного кролика своими руками

Найти область значений бинарного отношения Найти область значений бинарного отношения Найти область значений бинарного отношения Найти область значений бинарного отношения Найти область значений бинарного отношения Найти область значений бинарного отношения