Материал: 4553

11

отображении f2 : Y X является элемент a множества X, поэтому последнее отображение не является сюръективным.

1.3. Индивидуальные задания

Задача №1. Пусть U = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10}, множества A, B, C, D

заданы в табл. 1. Перечислить все элементы множества D.

Таблица 1

12

13

Задача № 2. Преобразовать выражение, заданное в табл. 2.

Таблица 2

Окончание таблицы 2

2. Бинарные отношения 2.1. Теоретическая часть

Понятие бинарного отношения и связанные с ним понятия

Всякое подмножество P декартова произведения A B непустых множеств A и B называется бинарным отношением между элементами множеств A и B. Если (u, v) P, то говорят, что элементы u и v находятся в отношении P (говорят также, что элемент u находится в отношении P к элементу v). Всякое подмножество множества A A называется бинарным отношением на A.

Вместо «отношение между элементами множеств A и B» можно сказать «отношение на паре множеств A, B». Указать на принадлежность пары (a, b) отношению P можно несколькими способами:

(a, b) P, P(a, b), aPb.

Последний способ может показаться странным, однако, на самом деле им часто пользуются: 2 < 7, 5 =5.

Задать бинарное отношение можно различными способами. Можно перечислить все пары, принадлежащие отношению, или указать какое – то свойство, специфичное именно для этих пар. Иногда полезно задать отношение матрицей.

Пусть P – бинарное отношение между элементами конечных множеств

столбцов, называется матрицей отношения P, если ее элементы удовлетворяют следующему условию:

1, если (ai , b j ) P, pij 0, если (ai , b j ) P.

15

Произведением (или композицией) отношений P1 A B и P2 B C

называется отношение P1 P2 A C, образованное следующим образом: пара (x, y) A C принадлежит P1 P2 тогда и только тогда, когда в B существует

умножаются по обычному правилу умножения матриц, но произведение элементов матриц и сумма таких произведений при перемножении матриц находятся по правилам 0 0 = 1 0 = 0 1 = 0, 1 1 = 1, 0 + 0 = 0, 1 + 1 = 1, 1 + 0 = 0 + 1 = 1.

Обратным отношением для бинарного отношения P называется множество P 1, состоящее из тех пар (a, b), для которых (b, a) P.

Укажем особенно часто встречающиеся виды бинарных отношений. Бинарное отношение P на множестве A называется

а) рефлексивным, если (x, x) P для каждого x A;

б) антирефлексивным, если (x, x) P для каждого x A;

в) симметричным, если для любых x, y A из (x, y) P следует, что и

(y, x) P;

г) антисимметричным, если для любых x, y A из (x, y) P и x y следует, что (y, x) P;

д) транзитивным, если для любых x, y, z A из (x, y) P и (y, z) P следует, что (x, z) P.

По свойствам матрицы бинарного отношения можно судить о некоторых свойствах самого отношения. Пусть P (pij ) – матрица бинарного отношения

P на некотором множестве. Это отношение является

1)рефлексивным, если на главной диагонали матрицы P нет нулей;

2)антирефлексивным, если на главной диагонали матрицы P нет

единиц;

3) симметричным, если матрица P симметрическая: pij p ji для любых

i и j;