Теория множеств и бинарные отношения

Содержание
Связи между понятиями
Бинарное отношение
Определение функции
Виды функций
Операции
Построение функций
Свойства бинарных отношений

Связи между понятиями

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

Виды бинарных отношений
Обратное отношение
Дополнительное отношение

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

Обратное отношение
Обратное отношение

Дополнительное отношение
Дополнительное отношение

Тождественное отношение
Тождественное отношение

Универсальное отношение
Универсальное отношение

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

Построение функции
Даны множества X={a, b, c, d} и Y={x, y, z}. Построить функцию F: X=> Y таким образом, что
d
y

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

Построение инъекции
Даны множества X={x1, x2, x3} Y={y1, y2}. Построить инъекцию F: X →Y

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

Построение сюръекции
Даны множества X={x1, x2, x3} и Y={y1, y2}. Построить сюрьекцию F: X →Y

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

Построение биекции
Даны множества X={x1, x2, x3} и Y={y1, y2}. Построить биекцию F: X →Y
y3

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

Операция
Дано множество X={x1, x2, x3}. Построить операцию F: X →X
x3

Решение задач
Дано множество натуральных чисел N. Укажите, какие из арифметических действий (сложение, вычитание, умножение, деление) всегда выполнимы на этом множестве?

Решение задач
Дано множество натуральных чисел N. Укажите, какие из арифметических действий (сложение, вычитание, умножение, деление) всегда выполнимы на этом множестве?
Решение
сложение
умножение
Результат операций должен принадлежать множеству натуральных чисел N

Решение задач
На множестве натуральных чисел задана О операция. Какой может быть эта операция?
а) a О b = ab;
б) a О b = a + b;
в) a О b = a – b.

Решение задач
На множестве натуральных чисел задана О операция. Какой может быть эта операция?
а) a О b = ab;
б) a О b = a + b;
в) a О b = a – b.
Решение
возведение в степень
сложение
Результат операций должен принадлежать множеству натуральных чисел N

Решение задач
На множестве рациональных чисел задана О операция . Какой может быть эта операция?
а) a О b = a ^ b;
б) a О b = a + b;
в) a О b = a – b;

Решение задач
На множестве рациональных чисел задана О операция . Какой может быть эта операция?
а) a О b = a ^ b;
б) a О b = a + b;
в) a О b = a – b;
Решение
сложение
вычитание
Результат операций должен принадлежать множеству рациональных чисел N

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

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

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

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

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

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

Другое определение антисимметричности
Бинарное отношение T(M) называется антисимметричным тогда и только тогда, когда из того, что
и следует, что

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

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

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

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

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

Примеры транзитивности
транзитивно
нетранзитивно
интранзитивно

Определение свойств бинарных отношений

Определение свойств бинарных отношений
нерефлексивность (часть вершин имеет петли, часть –нет)
несимметричность (есть симметричные и антисимметричные дуги)
интранзитивность (бинарное отношение обладает несколькими путями длины 2, но нет ни одного транзитивного замыкания)

Определение свойств бинарных отношений

Определение свойств бинарных отношений
иррефлексивность (нет ни одной петли)
антисимметричность (есть только антисимметричные дуги)
нетранзитивность (нет ни одного пути длины 2!!!)

Определение свойств бинарных отношений

Определение свойств бинарных отношений
рефлексивность (все вершины имеют петли)
несимметричность (есть симметричные и антисимметричные дуги)
нетранзитивность (есть пути длины 2 с транзитивными замыканиями, есть без транзитивных замыканий)

Определение свойств бинарных отношений
рефлексивность (число равно a самому себе, a=a ) несимметричность (нет ни одной дуги между различными элементами a и b!!! )
нетранзитивность (нет ни одного пути длины 2!!!)
На множестве натуральных чисел задано отношение равенства (а=b). Какими свойствами (рефлексивность, симметричность, транзитивность) обладает это отношение?
2
n
. . .
. . .