Лекция 2. Бинарные отношения и свойства 2008 г. Дискретная математика. Математическая логика ИОПИОПИОПИОП МИФИ Проф., д.т.н. Гусева А.И., доцент Порешин П.П., аспирант Цыплаков А.C.

Бинарное отношение Бинарным отношением Т(М) на множестве М называется подмножество, Инфиксная форма записи бинарного отношения a T b =.

Виды бинарных отношений Обратное отношение Дополнительное отношение Тождественное отношение Универсальное отношение

Способы задания бинарных отношений Перечислением, как множество пар Графически, когда каждый элемент х множества М представляется вершиной, а пара представляется дугой из х в у Матричным способом, с помощью матрицы смежности или матрицы инциденций Фактор-множеством

Пример Матрица смежности Графическое задание

Фактор-множество R/M множества М по отношению к R называется множество окрестностей единичного радиуса для всех элементов М при заданном R Фактор-множество {1}{1, 2}{1, 3}{1, 2, 4}{1, 5} R/M =R/M =

Функция называется функцией, если для каждого элемента х найдется не более одного элемента у такого, что, т.е. выполняется свойство однозначности полученного результата Множество X - область определения функции, и множество Y - область значений функции Х и У могут не иметь общих элементов

Инъекция Функция F: X Y называется инъективной, или инъекцией, или вложением, если она переводит разные элементы Х в разные У, то есть

Сюръекция Функция F: X Y называется сюръективной, или сюръекцией, или наложением, если множество ее значений есть все Y, т.е.

Биекция Функция F: X Y называется биекцией или взаимно однозначным соответствием, если она одновременно является инъекцией и сюръекцией (вложением и наложением)

Операция Частным случаем функции является операция О В этом случае область значения Х и область определения У совпадают, т.е

Бинарное отношение T(M) называется рефлексивным тогда и только тогда, когда для каждого элемента пара (х, х) принадлежит этому бинарному отношению, т.е. Бинарное отношение T(M) называется иррефлексивным тогда и только тогда, когда для каждого элемента пара (х, х) не принадлежит этому бинарному отношению, т.е. Рефлексивность

Если бинарное отношение T(M) не обладает ни свойством рефлексивности, ни свойством рефлексивности, то оно является нерефлексивным Рефлексивность

Симметричность Бинарное отношение T(M) называется симметричным тогда и только тогда, когда для каждой пары (х, у)из Т, обратная пара (у, х) также принадлежит этому бинарному отношению, т.е. Бинарное отношение T(M) называется антисимметричным тогда и только тогда, когда для каждой пары различных элементов (х, у) из Т пара (у, х) не принадлежит этому бинарному отношению, т.е.

Если бинарное отношение T(M) не обладает ни свойством симметричности, ни свойством анти симметричности, то оно является несимметричным Симметричность

Транзитивность Бинарное отношение T(M) называется транзитивным тогда и только тогда, когда для каждых двух пар элементов (х, у) и (у, z), принадлежащих бинарному отношению, пара (x, z) также принадлежит этому бинарному отношению, т.е.

Бинарное отношение T(M) называется интранзитивным тогда и только тогда, когда для каждых двух пар элементов (х, у) и (у,z), принадлежащих бинарному отношению, пара (x, z) не принадлежит этому бинарному отношению, т.е. Транзитивность

Если бинарное отношение T(M) не обладает ни свойством транзитивности, ни свойством интранзитивности, то оно является нетранзитивным Транзитивность

Примеры рефлексивности

Примеры симметричности a c b d a c b d a c b d

Примеры транзитивности a c b d a c b d a c b d

Пример свойств бинарных отношений b f a cd e не рефлексивность (часть вершин имеет петли, часть –нет) несимметричность (есть симметричные и антисимметричные дуги) интранзитивность (бинарное отношение обладает несколькими путями длины два, но ни на один из них нет транзитивного замыкания)