Главная страница 1



Лекция 2

    1. Декартово произведение множеств

Обозначим упорядоченную последовательность из n элементов x1, x2, …, xn через (x1x2, …, xn). Круглые скобки используются для того, чтобы указать на порядок в котором следуют элементы. Назовем такую упорядоченную последовательность набором длины n или n-кой.

Пусть имеются n множеств A1, A2, …, An, тогда декартовым (прямым) произведением множеств A1, A2, …, An называют множество всех наборов (x1x2, …, xn) таких, что x1A1, x2A2, …, xnAn. Декартово произведение обозначают A1A2  …  An. Если одним из множителей является , то декартово произведение равно . Если A1 = A2 = … = An = A, то декартово произведение называется n-ой степенью A и обозначается An = AA  …  A. Положим по определению, что A0 = {}.



Пример 1.7. Пусть A = {1, 2, 3}, B = {2,3}. Тогда, AB = {(1, 2), (1, 3), (2, 2), (2, 3), (3, 2), (3,3)}, B2 = {(2, 2), (2, 3), (3, 2), (3, 3)}.

Теорема 4. | AB| = |A||B|.

Следствие. |An | = |A|n.

    1. Бинарные отношения на множествах

Бинарным отношением R на множествах А и В называется любое подмножество декартова произведения множеств А и В.

Если элементы x и y множеств А и В находятся в отношении R, то пишут (x,y)R или xRy. Если А=В, то R называется бинарным отношением на А.

Бинарное отношение можно задать указанием всех пар, для которых это отношение выполняется, или графически. Основу графического представления бинарного отношения составляет прямоугольная система координат, где по одной оси отмечаются точки, представляющие элементы множества А, а по другой – точки, представляющие элементы множества В. Точки, первая координата которых – элемент множества А, а вторая – элемент множества В, обозначают элементы декартова произведения.

Пример 1.6. Рассмотрим множества A={1,2,3,4,5,6}, B={1,2,3}. Определим на этих множествах отношение RAB.

R={(x,y) | x делится на y}.

R можно представить графически следующим образом:

С
вяжем с каждым бинарным отношением R между множествами A и B два множества – область определения R и множество значений R. Они определяются следующим образом:

R={x| (x,y)R для некоторого y},

R={y| (x,y)R для некоторого x}.



Пример 1.7. Пусть на множестве A={1,2,3,4,5} задано отношение R: R={(x,y) | остаток от деления y на x равен 1}.

Тогда R={(5,1), (4,1), (3,1), (2,1), (2,3), (2,5), (3,4), (4,5)},

R={2,3,4,5}, R={1,3,4,5}.

Пусть имеются множества A, B, C и отношения RAB, PBC. Определим отношение SAC следующим образом: оно действует из A в B посредством R, а затем из B в C посредством P. Такое отношение называется составным (композицией) и обозначается S=PR.



S={(x,y) | zB, для которого выполнено (x,z)R, (z,y)P}.

П
ример 1.8.
Пусть A={1,2,3,4}, на множестве A определим два отношения: R={(x,y) | 2xy} и P={(x,y) | x+3y делится на 2}. Найдем графические представления отношений R, P, S = PR.

Найдем области определения и области значений для всех отношений.

R={1,2}, R={2,3,4}, P={1,2,3,4}, P={1,2,3,4}, S={1,2}, S={1,2,3,4}.

Бинарное отношение R на множестве А называется рефлексивным, если для всякого выполняется .

Бинарное отношение R на множестве А называется антирефлексивным, если для любых x и y, для которых выполнено xRy следует, что xy.

Бинарное отношение R на множестве А называется симметричным, если из того, что выполняется xRy следует выполнение yRx.

Бинарное отношение R на множестве А называется антисимметричным, если из выполнения xRy и yRx следует, что x=y.

Бинарное отношение R на множестве А называется транзитивным, если из выполнения xRy и yRz следует выполнение xRz.

Рефлексивное, симметричное и транзитивное отношение R на множестве A называется отношением эквивалентности.

Рефлексивное, антисимметричное и транзитивное отношение R на множестве А называется частичным порядком.



Пример 1.9. Определим отношение R на множестве натуральных чисел следующим образом: (a+2делится на 3).

Это отношение является рефлексивным, т.к.

Отношение R симметрично.

. Для того чтобы проверить выполнение bRa, необходимо показать, что

,

выполнено.

Отношение R не является антисимметричным, т.к. 6R3, 3R6, но .

Проверим, что R – транзитивно.
,

. Для того, чтобы проверить выполнение aRc, необходимо показать, что .



aRc выполнено.

Заметим, что отношение R является отношением эквивалентности.

Удобным способом представления отношений в ЭВМ является матричная форма. Рассмотрим два множества A={a1,a2,…,am}, B={b1,b2,…,bn} и бинарное отношение . Определим матрицу [R] = (rij) бинарного отношения по следующему правилу:

Полученная матрица содержит полную информацию о связях между элементами и позволяет представлять эту информацию на компьютере.



Основные свойства матриц бинарных отношений:

Пусть R – бинарное отношение на A2. Тогда отношение R является



    1. рефлексивным, если на главной диагонали R стоят единицы;

    2. антирефлексивным, если на главной диагонали R стоят нули;

    3. симметричным, если [R]=[R]T (матрица симметрична относительно главной диагонали);

    4. антисимметричным, если в матрице отсутствуют единицы, симметричные относительно главной диагонали;

    5. транзитивным, если RR  R. Матрица композиции [RR] = [R]  [R], где умножение матриц [R] и [R] выполняется обычным способом, но при этом, умножение элементов соответствует логическому «и» (00=10=01=0, 11=1), а сложение элементов – логическому «или» (0+0=0, 1+0=0+1=1+1=1).

Пример 1.10. Рассмотрим отношения Р, R, S из Примера 1.8. Определим свойства этих отношений.

Запишем матрицы отношений:



Отношение P является рефлексивным, а отношения R и S не являются рефлексивными (в матрицах отношений на главной диагонали имеются нули).

Отношение R является антирефлексивным, а отношения P и S не являются антирефлексивными (в матрицах отношений на главной диагонали имеются единицы).

Найдем транспонированные матрицы отношений.



Из сравнения матриц отношений с транспонированными матрицами этих отношений, находим, что отношение P является симметричным, а отношения R и S не являются симметричными. Отношения R и S являются антисимметричными (у матриц [R] и [R]T, [S] и [S]T нет совпадающих единиц вне главной диагонали), а отношение P не является антисимметричным (например, p13=p31=1).



Для определения транзитивности отношений найдем произведения каждой матрицы на саму себя.

, следовательно, R является транзитивным.

, следовательно, P -транзитивно.

, следовательно, S -транзитивно.






Смотрите также:
Круглые скобки используются для того, чтобы указать на порядок в котором следуют элементы
54.15kb.
Вводное литофильные элементы. Признаки, по которым химические элементы относятся к литофильным, сидерофильным или халькофильным. Собственные минералы и минералы-концентраторы того или иного химического элемента. Литий
42.42kb.
Порядок (правила)
68.4kb.
Обзор книг серии «Детям о праве»
29.3kb.
Достижение успеха в некоторых видах деятельности неред­ко связано с риском. Например, в сфере бизнеса для того, чтобы выиграть, иногда нужно поставить на карту слиш­ком многое
73.72kb.
Средства индивидуальной защиты органов дыхания (сизод)
152.56kb.
Мало кто её видел. Но, говорили, что это был изумительный экземпляр. Лучший в колонии. Совершенное тело, созданное лишь для того, чтобы сводить с ума. Других функций, до прилета «Эвакуатора», у пунит не было
167.53kb.
Урок главная составная часть учебного процесса. Учебная деятельность учителя и учащихся в значительной мере сосредоточивается на уроке
841.29kb.
Методические указания для студентов фак. Иу по "Инженерной графике" Москва 2002 Геометрические построения
105.86kb.
Доставить почту
123.42kb.
Памятка для клиента системы Интернет Банкинг
74.58kb.
Квашение капусты 12 Соление огурцов 13
447kb.