Булевы отношения

Декартово произведение
Отношением R множества А и В называется произвольное подмножество А×В.

Пример
A={1, 2, 3}, B={r, s}
A×B= {(1,r), (1,s), (2,r), (2,s), (3,r), (3,s)}
Тогда

Примеры

Определения

Область определения отношения R на А и В есть множество всех

С каждым отношением R на A × B связано отношение R

Примеры

Пусть R={(1, r), (1, s), (3, s)},
тогда R -1 =

Определение

Пусть R⊆A×B – отношение на A×B,
а S⊆B×C – отношение на

Пример

Пусть А={1, 2, 3}, B={x, y}, C=
Пусть отношения R на A

Пример

Пусть R и S – бинарные отношения на множестве положительных целых

Теорема

Композиция отношений ассоциативна: если A, B, C и D – множества

Определения

Отношение R на A×A называется рефлексивным, если (a, a) принадлежит R

Пример

Пусть А = {1, 2, 3, 4, 5, 6} и пусть

Отношение R1 является транзитивным:
Проанализировав каждый возможный случай, когда (a, b)

Пример

Пусть А – множество положительных чисел.
Отношение R: (x, y) R,

Определения

Пусть R – бинарное отношение на множестве А.
Рефлексивное замыкание R

Теорема

Пусть R – отношение на множестве А и I = {x:

Начальные сведения о графах. Подробно в о 2 семестре Граф – наглядное

Конечный граф изображается при помощи диаграммы, в котором вершины представлены точками,

Пример

Граф, в котором множество вершин V={a, b, c, d , e},

Определения

Ориентированный граф, или орграф G состоит из множества V вершин и

В случае ориентированного графа допускается наличие петель. Пример

Орграф с вершинами
V={a, b, c}

Пример

Орграф с вершинами V={a, b, c, d}
и ребрами E={(a, b),

Определение

Отношение R на А есть отношение частичного порядка, если оно рефлексивно,

Пример (*)

Пусть С = {1, 2, 3}, Х – множество всех

Пример

Пусть S – множество действительных чисел,
R1 – отношение, определенное условием

Определение

Два элемента a и b ЧУ-множества (S, ≤) сравнимы, если a

Примеры

Пусть Т – множество положительных делителей числа 30 и ≤1 есть

Пример

Пусть S – множество всех подмножеств множества
{a,b,c} ≤3 есть отношение

Диаграммы Гессе

Для изображения ЧУ-множеств.
Для заданного ЧУ-множества (А, ≤2) диаграмма Гессе состоит

Диаграмма Гессе, соответствующая множеству (Т, ≤1)

Пример

Диаграмма Гессе, соответствующая множеству (S, ≤3)

Пример

Задания для самостоятельной работы

1.
2.

Отношения эквивалентности

Определение

Отношение R на А есть отношение эквивалентности,
если оно рефлексивно, симметрично

Отношение R3 рефлексивно.
Если а – целое число (а ∈ А), то

Отношение R3 транзитивно.
Предположим, a, b, c – целые числа,
(a,

Отношение эквивалентности R на множестве А
разбивает его на подмножества, элементы

Пример

Пусть множество А – набор разноцветных шаров, а отношение R задается

Определение

Пусть a ∈ A, и R - отношение эквивалентности на А

Пример

Отношение R1 есть отношение эквивалентности на множестве А = {1, 2,

Также:

Имеется только три различных класса эквивалентности:
поэтому

Из примера видно, что любой элемент класса эквивалентности порождает класс эквивалентности.

Пример

Рассмотрим отношение эквивалентности R3 и примера (**). Для множества А всех

Определения

Совокупность классов эквивалентности разделяет все множество А на непустые взаимоисключающие, или

Теорема

Непустое множество подмножеств 〈А〉 множества А есть разбиение А тогда и

Пример

Пусть
Рассмотрим разбиение
Необходимо определить R таким образом:
R = {(a, b) : a