Теория языков программирования методов трансляции (стр. 2 )

Один из способов определения множества – определение с помощью предиката. Предикат –это утверждение, состоящее из нескольких переменных и принимающее значение 0 или 1 («ложь» или «истина»). Множество, определяемое с помощью предиката, состоит из тех элементов, для которых предикат истинен.

Говорят, что множество содержится во множестве , и пишут , если каждый элемент из является элементом из . Если содержит элемент, не принадлежащий и , говорят, что , собственно содержится в (рис. 1.1).

Рис. 1.1. Диаграмма Венна для включения множеств

1.2.  Операции над множествами

Объединение множеств

-

это множество, содержащее все элементы А и В (рис. 1.2).

Рис. 1.2. Диаграмма для объединения множеств

Пересечение множеств

-

это множество, состоящее из всех тех элементов, которые принадлежат обоим множествам А и В (рис. 1.3).

Рис. 1.3. Диаграмма Венна для пересечений множеств

Разность множеств

А – В -

это множество элементов А, не принадлежащих В (рис. 1.4).

Рис. 1.4. Диаграмма Венна для разности множеств

Универсальное множество: множество всех элементов, рассматриваемых в данной ситуации, обозначается через U.

Разность U - В =`В – дополнение В.

Æ - А и В не пересекаются.

Определение.

Пусть I – некоторое множество, элементы которого используются как индексы, и для каждого iÎ I множество Ai известно. Через обозначим множество {X | существует такое , что } - это обобщенное понятие объединения.

Если I определено с помощью предиката, то иногда пишут вместо .

Пример. означает

Определение.

Множество всех подмножеств А обозначается через R(А) или 2А т. е.

Пример. , т. е., если А конечное множество из m элементов, то R(А) состоит из 2m элементов.

В общем случае элементы множества не упорядочены.

Определение.

Пусть a и b объекты. Через (a, b) обозначим упорядоченную пару объектов, взятых именно в этом порядке.

Упорядоченные пары (a, b) и (c, d) называются равными, если a=c и b=d. Упорядоченные пары можно рассматривать как множество (a, b) - {a, {a, b}}.

Декартово произведение А и В

.

Пример. Ессли А={1,2}, B={2,3,4}, то A´B={(1,2), (1,3), (1,4), (2,2), (2,3), (2,4)}

Отношения

Пусть А и В – множества. Отношением из А в В называется любое подмножество множеств А´В.

Если А=В, то отношение задано (определено) на А.

Если R отношение из А в В и (a, b)ÎR, то пишут aRb. Множество А называют областью определения, В - множеством значений.

Пример.

А – множество целых чисел. Отношение L представляет множество {(a, b) | a меньше b} aLb.

Определение.

Отношение {(b, а) | (a, b)ÎR} называют обратным к отношению R, т. е. R-1.

Определение.

Пусть А – множество, R – отношение на А.

Тогда R называют:

1)  рефлексивным, если aRa для всех пар из А;

2)  симметричным, если aRb влечет bRa для всех a и b из А;

3)  транзитивным, если aRb и bRс влекут aRс для a, b, с из А.

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

Отношение эквивалентности, определенное на А, заключается в том, что оно разбивает множество А на непересекающиеся подмножества, называемые классами эквивалентности.

Пример.

Отношение сравнения по модулю N, определенное на множестве неотрицательных чисел. а сравнимо с b по модулю N. , т. е. a-b=kN (k - целое).

Пусть N=3, тогда множество {0, 3, 6,…, 3n,…} будет одним из классов эквивалентности, т. к. 3n=3m(mod3) для целых n и m. Обозначим его через [0]. Другие два:

[1]={1, 4, 7,…, 3n+1,…};

[2]={2, 5, 8,…, 3n+2,…}.

Объединение этих трех множеств дает множество неотрицательных целых чисел (рис. 1.5).

Рис. 1.5. Классы эквивалентности отношения сравнения по модулю 3

Число классов, на которые разбивается множество отношением эквивалентности, называется индексом этого отношения.

Замыкание отношений

Задача.

Для данного отношения R найти другое R¢, обладающее дополнительными свойствами (например, транзитивностью). Более того, желательно, чтобы R¢ было как можно «меньше», т. е., чтобы оно было подмножеством R.

Задача в общем случае не определена, однако для частных случаев имеет решение.

Определение.

k – степень отношения R на А определяется:

1)  aR1b тогда и только тогда, когда aRb;

2)  для i>1 тогда и только тогда, когда существует такое cÎA, что aRc и

Это пример рекурсивного определения

.

Транзитивное замыкание отношения множества R на А (R+) определяется так: аR+b тогда и только тогда, когда для некоторого i³1.

Расшифровка понятия: аR+b, если существует последовательность , состоящая из 0 или более элементов принадлежащих А, такая, что . Если n=0, то aRb.

Рефлексивное и транзитивное замыкание отношения R (R*) на множестве А определяется следующим образом:

1)  aR*a для всех аÎА;

2)  aR*b, если aR+b;

3)  в R* нет ничего другого, кроме того, что содержится в 1) и 2).

Если определить R0, сказав, что aR0b тогда и только тогда, когда a=b, то aR*b тогда и только тогда, когда для некоторого i³0.

Единственное различие между R+ и R* состоит в том, что aR*a истинно для всех аÎА, но aR+а может быть, а может и не быть истинным.

Отношения порядка

Отношения порядка играют важную роль при изучении алгоритмов, особенно специальный вид порядков – частичный порядок.

Определение.

Частичным порядком на множестве А называют отношение R на А такое, что:

1)  R – транзитивно;

2)  для всех аÎА утверждение aRa ложно, т. е. отношение R иррефлексивно.

Пример.

- множество, состоящее из n элементов, и пусть А=P(S). Положим aRb для любых a и b из А тогда и только тогда, когда aËb. Отношение R называется частичным порядком.

Для случая S={0, 1, 2} имеем (рис. 1.6).