Лекции.Орг


Поиск:




Способы задания бинарных отношений.

Виды бинарных отношений на множестве A

 

1) Обратное отношение .

 

2) Дополнение .

 

3) Тождественные .

 

4) Универсальные .

 

Композиция отношений

 

Пусть P 1 - отношение из A в C, И P 2 - отношение из C в В,

тогда композицией отношений называется отношение

 

 

ПРИМЕР

 

, , .

 

Пусть ( отношение из А в В). Ядром отношения называется композиция отношения и обратного для него отношения , т.е..

 

 

Основные законы теории множеств

1. Коммутативность операций ∪ и ∩:

а) AB = BA б) AB = BA

2. Ассоциативность операций ∪ и ∩:

а) A ∪(BC)=(AB) ∪ C б) A ∩(BC)=(AB) ∩ C

3. Законы идемпотентности операций ∪ и ∩:

а) AA = A б) AA = A

4. Законы дистрибутивности:

а) A ∪(BC)=(AB) ∩ (A ∪С) б) A ∩(BC)=(AB) ∪ (A ∩С)

5. Законы поглощения:

а) A ∪(AB)= A б) A ∩(AB)= A

6. Законы де Моргана:

а) AB = AB б) AB = AB

7. Законы пустого и универсального множеств: ∅=Æ

A ∪∅= A A ∩∅= ∅ AA =∅

AU = U AU = A AA = U

U =∅ ∅ = U

8. Закон двойного отрицания:

A = A

Пример 4. [, ] Доказать, что относительно данного универсальног

множества U дополнение A любого множества A, если AU, единственно.

4Для доказательства единственности дополнения A множества AU

предположим, что существует два множества B и C, каждое из которы

удовлетворяет требованиям дополнения множества A, т.е. их пересечение с A

пусто, а объединение с A дает U:

а) BA =∅; б) CA =∅; в) BA = U; г) CA = U.

Очевидно, что B = BU. С учетом условия г) B = B ∩(CA). Так ка

B ∩(CA) = (BC)∪(BA), то с учетом условия а) B = (BC) ∪∅ = BC.

Аналогично исходя из условий в), б) получим:

C = CU = C ∩(BA) = (CB)∪(CA) = (CB)∪∅ = CB.

Итак, мы получили, что B = BC и C = CB. Так как CB = BC

(коммутативность операции пересечения), то B = C, что и требовалось доказать.3

 

БИНАРНЫЕ ОТНОШЕНИЯ

2.1. Основные определения

Бинарные отношения используются для определения каких-либ

взаимосвязей, которыми характеризуются пары элементов множества, т.е. есл

отношение P определено на множестве A × B (PA × B), то это значит, что

множество P попадут только те пары множества A × B, между элементами которы

имеет место указанное отношение.

 

Способы задания бинарных отношений.

Так как отношения – это множества, то их можно задавать перечислением ил

характеристическим свойством. Кроме того, для бинарных отношений

определенных на конечных множествах, есть еще несколько способов их задания.

1. Бинарное отношение PA × B, где A={ a 1, a 2, …, an }, B={ b 1, b 2, …, bm } може

быть задано (m, n)-матрицей (таблицей) (m строк, n столбцов), в которой элемен

ij p, стоящей на пересечении i -й строки и j -го столбца, равен 1, если межд

элементами ai и bj имеет место отношение P, или 0 в противном случае.

 

Например, отношение P ={(a, b) | aA, bB и a > b }, где A ={6,7,8}, B ={5,6,7,8,9

задано характеристическим свойством. Это же отношение

может быть определено перечислением P ={(6,5), (7,5),

(7,6), (8,5), (8,6), (8,7)} или матрицей отношения.

2. Если PA × B, A и B – числовые множества,

то отношение P можно изобразить как

множество точек на плоскости, где каждая

точка представляет собой пару из множества P.

Например, P ={(2,1), (1,2), (2,2), (3,2), (4,2), (1,3),

(2,4)}, где A ={1,2,3,4,5}, B ={1,2,3,4}

3. Если PA × B, то отношение P можно

изобразить в виде диаграммы, состоящей из

узлов и стрелок, при этом узлам взаимно

однозначно соответствуют элементы множеств A

и B, а стрелка соединяет элемент a и с элементом

b только в том случае, если (a, b)∈ P. Например,

P ={(a,2), (a,3), (b,1), (c,1)}, A ={ a, b, c }, B ={1, 2,

3}

4. Если PA 2, то бинарное отношение может

быть задано в виде графа, вершины которого –

элементы множества, а дуги направленные от a к

b означают, что (a, b)∈ P. Например, P ={(a, c), (c,

a), (b, a), (b, b),(a, d)}, где A ={ a, b, c, d }.

Способы задания 2–4 иногда называют графическими способам

отображения бинарных отношений.

Пусть P – некоторое бинарное отношение.

Областью определения P называется множество

ä P ={ x |(x, y)∈Ñ для некоторого y }.

Областью значений P называется множество

ñ P ={ y |(x, y)∈Ñ для некоторого x }.

Так как бинарное отношение по сущности есть множество, то для нег

определены все операции, которые определены для множеств: пересечение

объединение, разность, симметрическая разность и дополнение. При этом вс

законы алгебры множеств сохраняют свою силу. Кроме того, определяются други

операции над отношениями, в том числе:

Обратным к P отношением называется множество

P –1={(y, x) |(x, y)∈Ñ }.

Композицией бинарных отношений P 1⊂ A × B и P 2⊂ B × C называется множеств

P 3= 1 2 P _ P, где P 3⊂ A × C и P 3={(x, y) | xA, yC и найдется zB такой, что (x, z)∈ P 1

(z, y)∈ P 2}.

Образом множества X относительно P называется множество

P (X)={ y| (x, y)∈Ñ для некоторого xX }.

Множество P −1(Y)={ x| (x, y)∈Ñ для некоторого yY } называется прообразом

множества Y относительно P.



<== предыдущая лекция | следующая лекция ==>
УПРАЖНЕНИЕ 3 – Работа со списками | База состоит из 3-х модулей.
Поделиться с друзьями:


Дата добавления: 2016-11-12; Мы поможем в написании ваших работ!; просмотров: 1969 | Нарушение авторских прав


Поиск на сайте:

Лучшие изречения:

Лучшая месть – огромный успех. © Фрэнк Синатра
==> читать все изречения...

794 - | 751 -


© 2015-2024 lektsii.org - Контакты - Последнее добавление

Ген: 0.01 с.