🗊Презентация Математические отношения

ОТНОШЕНИЯ

Введение Когда говорят о родстве двух человек, Ивана и Анны, то подразумевают, что есть некая семья, к членам которой они относятся. Упорядоченная пара (Иван, Анна) отличается от других упорядоченных пар людей тем, что между Иваном и Анной есть некое родство (кузина, отец, и т. д.).

В математике среди всех упорядоченных пар прямого произведения А В двух множеств А и В тоже выделяются некоторые пары в связи с тем, что между их компонентами есть некоторые «родственные» отношения, которых нет у других. В математике среди всех упорядоченных пар прямого произведения А В двух множеств А и В тоже выделяются некоторые пары в связи с тем, что между их компонентами есть некоторые «родственные» отношения, которых нет у других. В качестве примера рассмотрим множество S студентов какого-нибудь института и множество К читаемых там курсов.

В прямом произведении S К можно выделить большое подмножество упорядоченных пар (s, k), обладающих свойством: студент s слушает курс k. Построенное подмножество отражает отношение «... слушает ...», естественно возникающее между множествами студентов и курсов. В прямом произведении S К можно выделить большое подмножество упорядоченных пар (s, k), обладающих свойством: студент s слушает курс k. Построенное подмножество отражает отношение «... слушает ...», естественно возникающее между множествами студентов и курсов.

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

Отношения между элементами нескольких множеств задаются в виде таблиц данных. Такие n-арные отношения применяются, например, для описания систем управления базами данных. Отношения между элементами нескольких множеств задаются в виде таблиц данных. Такие n-арные отношения применяются, например, для описания систем управления базами данных.

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

Пример 4.1. Рассмотрим генеалогическое древо, изображенное на рис. 4.1. Пример 4.1. Рассмотрим генеалогическое древо, изображенное на рис. 4.1. Выпишите упорядоченные пары, находящиеся в следующих отношениях на множестве Р членов этой семьи: (а) R = { (х, у): х — дедушка у }; (б) S = { (х, у): х — сестра у }.

Решение. Решение. (а) R содержит упорядоченные пары: (Фред, Джейн), (Фред, Фиона), (Фред, Алан), (Джон, Джейн), (Джон, Фиона) и (Джон, Алан). (б) S состоит из пар: (Сью, Пенни), (Пенни, Сью), (Джейн, Фиона), (Фиона, Джейн), (Элис, Кен), (Сью, Майк), (Пенни, Майк), (Джейн, Алан) и (Фиона, Алан).

Пример 4.2. Выпишите упорядоченные пары, принадлежащие следующим бинарным отношениям на множествах А = {1, 3, 5, 7} и В = {2, 4, 6}: Пример 4.2. Выпишите упорядоченные пары, принадлежащие следующим бинарным отношениям на множествах А = {1, 3, 5, 7} и В = {2, 4, 6}: (а) U = {(x, у): х + у = 9}; (б) V = {(x, y): x < y}. Решение. (а) U состоит из пар: (3, 6), (5, 4) и (7, 2); (б) V = {(1, 2), (1, 4), (1, 6), (3, 4), (3, 6), (5, 6)}.

Пример 4.3. Множество Пример 4.3. Множество R = {(x, у): х — делитель у} определяет отношение на множестве А = {1, 2, 3, 4, 5, 6}. Найдите все упорядоченные пары, ему принадлежащие. Решение. R состоит из пар: (1, 1), (1, 2), (1, 3), (1, 4), (1, 5), (1, 6), (2, 2), (2, 4), (2, 6), (3, 3), (3, 6), (4, 4), (5, 5) и (6, 6).

Теперь мы познакомимся с двумя более удобными способами перечисления упорядоченных пар, принадлежащих данному отношению. Теперь мы познакомимся с двумя более удобными способами перечисления упорядоченных пар, принадлежащих данному отношению. Первый из них основан на понятии «ориентированный граф», а второй опирается на понятие матрицы.

Пусть А и В — два конечных множества и R — бинарное отношение между ними. Пусть А и В — два конечных множества и R — бинарное отношение между ними. Мы изобразим элементы этих множеств точками на плоскости. Для каждой упорядоченной пары отношения R нарисуем стрелку, соединяющую точки, представляющие компоненты пары. Такой объект называется ориентированным графом или орграфом, точки же, изображающие элементы множеств, принято называть вершинами графа.

В качестве примера рассмотрим отношение V между множествами А = {1, 3, 5, 7} и В = {2, 4, 6} из примера 4.2 (б): V = {(x, y): x < y}. В качестве примера рассмотрим отношение V между множествами А = {1, 3, 5, 7} и В = {2, 4, 6} из примера 4.2 (б): V = {(x, y): x < y}. Соответствующий ориентированный граф показан на рис. 4.2. Для иллюстрации отношения на отдельном множестве А мы чертим орграф, чьи вершины соответствуют одному лишь множеству A, а стрелки, как обычно, соединяют элементы упорядоченных пар, находящихся в отношении.

Пример 4.4. Изобразите граф, представляющий отношение R из примера 4.3: R = {(x, у): х — делитель у} определяет отношение на множестве А = {1, 2, 3, 4, 5, 6}. Пример 4.4. Изобразите граф, представляющий отношение R из примера 4.3: R = {(x, у): х — делитель у} определяет отношение на множестве А = {1, 2, 3, 4, 5, 6}. Решение. Поскольку R — отношение на множестве А = {1, 2, 3, 4, 5, 6}, то ориентированный граф будет иметь шесть вершин. Он приведен на рис. 4.3.

Второй способ задания бинарного отношения на конечных множествах основан на использовании таблиц. Второй способ задания бинарного отношения на конечных множествах основан на использовании таблиц. Предположим, что мы хотим определить бинарное отношение R между множествами А и В. Необходимо обозначить элементы множеств и выписать их в каком-нибудь порядке. Сделаем это так: A = {a1, a2, …, an}, B = {b1, b2, …, bm}.

Для определения отношения R заполним таблицу M с n строками и т столбцами. Для определения отношения R заполним таблицу M с n строками и т столбцами. Строки «перенумеруем» элементами множества А, а столбцы — элементами множества B в соответствии с порядком, в котором мы выписали элементы.

В этих терминах отношение U из примера 4.2(а): А = {1, 3, 5, 7} и В = {2, 4, 6}, U = {(x, у): х + у = 9} (т.е. U состоит из пар: (3, 6), (5, 4) и (7, 2)) В этих терминах отношение U из примера 4.2(а): А = {1, 3, 5, 7} и В = {2, 4, 6}, U = {(x, у): х + у = 9} (т.е. U состоит из пар: (3, 6), (5, 4) и (7, 2)) с помощью матрицы задается следующим образом:

Пример 4.5. Отношение R на множестве А = { а, b, с, d } задается матрицей: Пример 4.5. Отношение R на множестве А = { а, b, с, d } задается матрицей: , порядок строк и столбцов в которой соответствует порядку выписанных элементов множества А. Назовите упорядоченные пары, принадлежащие R. Решение. Отношение R содержит упорядоченные пары: (а, b), (а, с), (b, с), (b, d), (с, b), (d, а), (d, b) и (d, d).

Пример 4.6. Выпишите матрицу, представляющую отношение R из примера 4.3: R = {(x, у): х — делитель у} определяет отношение на множестве А = {1, 2, 3, 4, 5, 6}. R состоит из пар: (1, 1), (1, 2), (1, 3), (1, 4), (1, 5), (1, 6), (2, 2), (2, 4), (2, 6), (3, 3), (3, 6), (4, 4), (5, 5) и (6, 6). Пример 4.6. Выпишите матрицу, представляющую отношение R из примера 4.3: R = {(x, у): х — делитель у} определяет отношение на множестве А = {1, 2, 3, 4, 5, 6}. R состоит из пар: (1, 1), (1, 2), (1, 3), (1, 4), (1, 5), (1, 6), (2, 2), (2, 4), (2, 6), (3, 3), (3, 6), (4, 4), (5, 5) и (6, 6). Решение. Матрица отношения R имеет вид:

Если R — бинарное отношение, то вместо записи (х, у) R можно употреблять обозначение х R y. Например, предикат «х — сестра у» определяет отношение на множестве всех людей. В примере 4.3 предикат «х — делитель у» дает ясное словесное описание еще одного отношения. Если R — бинарное отношение, то вместо записи (х, у) R можно употреблять обозначение х R y. Например, предикат «х — сестра у» определяет отношение на множестве всех людей. В примере 4.3 предикат «х — делитель у» дает ясное словесное описание еще одного отношения.

Подводя итог этой части теории отношений, напомним, что бинарное отношение между конечными множествами может быть задано одним из следующих способов: Подводя итог этой части теории отношений, напомним, что бинарное отношение между конечными множествами может быть задано одним из следующих способов: словами (с помощью подходящих предикатов); как множество упорядоченных пар; как орграф; как матрица.

Пример 4.7. Отношение R на множестве А = { 1, 2, 3, 4 } представлено графом на рис. 4.3. Пример 4.7. Отношение R на множестве А = { 1, 2, 3, 4 } представлено графом на рис. 4.3. Перечислите упорядоченные пары, принадлежащие A, выпишите соответствующую матрицу и определите это отношение с помощью предикатов.

Решение. В терминах упорядоченных пар R = {(2, 1), (3, 2), (4, 3)}. Матрица (относительно данного в условии порядка элементов множества) имеет вид: Решение. В терминах упорядоченных пар R = {(2, 1), (3, 2), (4, 3)}. Матрица (относительно данного в условии порядка элементов множества) имеет вид: С помощью предикатов данное отношение может быть описано как x - у = 1.

Свойства отношений Ограничимся рассмотрением бинарных отношений, заданных на одном множестве и введем некоторый набор их свойств.

Говорят, что отношение R на множестве А Говорят, что отношение R на множестве А рефлексивно, если для всех х A x R x; симметрично, если x R y y R x для каждой пары х и у из A; кососимметрично, если (х R y и y R x x = у) для всех x и у из А; транзитивно, если (х R у и у R z х R z) для любой тройки элементов x, у, z A.

В терминах упорядоченных пар эти свойства определяются следующим образом. Данное отношение R рефлексивно, если (x, х) R для любого возможного значения переменной х; симметрично, если из включения (x, у) R следует, что (у, х) R; кососимметрично, если из предположений: (x, у) R и х у вытекает, что (у, х) R; транзитивно, если включения (x, у) R и (у, z) R влекут (x, z) R. В терминах упорядоченных пар эти свойства определяются следующим образом. Данное отношение R рефлексивно, если (x, х) R для любого возможного значения переменной х; симметрично, если из включения (x, у) R следует, что (у, х) R; кососимметрично, если из предположений: (x, у) R и х у вытекает, что (у, х) R; транзитивно, если включения (x, у) R и (у, z) R влекут (x, z) R.

У ориентированного графа, изображающего рефлексивное отношение, каждая вершина снабжена петлей, т.е. стрелкой, начинающейся и заканчивающейся в одной и той же вершине. У ориентированного графа, изображающего рефлексивное отношение, каждая вершина снабжена петлей, т.е. стрелкой, начинающейся и заканчивающейся в одной и той же вершине. Орграф симметричного отношения вместе с каждой стрелкой из вершины х в вершину у имеет стрелку, направленную в обратную сторону: из у в х.

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

Перечислим свойства матриц, задающих отношения. Перечислим свойства матриц, задающих отношения. Прежде всего заметим, что матрица отношения на отдельном множестве А будет квадратной, т.е. количество ее строк будет равно количеству столбцов.

Матрица М, задающая рефлексивное отношение, отличается от других тем, что каждый ее элемент, стоящий на главной диагонали (М(i, i)), равен И; матрица М симметричного отношения будет симметричной, т.е. M(i, j) = M(j, i); в матрице кососимметричного отношения выполнено условие: Матрица М, задающая рефлексивное отношение, отличается от других тем, что каждый ее элемент, стоящий на главной диагонали (М(i, i)), равен И; матрица М симметричного отношения будет симметричной, т.е. M(i, j) = M(j, i); в матрице кососимметричного отношения выполнено условие: (M(i, j) = И и i j ) M(j, i) = Л. Отличительное свойство матрицы транзитивного отношения довольно трудно сформулировать четко и наглядно.

Пример 4.8. Что можно сказать о свойствах (рефлексивности, симметричности, кососимметричности и транзитивности) следующих отношений: Пример 4.8. Что можно сказать о свойствах (рефлексивности, симметричности, кососимметричности и транзитивности) следующих отношений: (а) « х делит у » на множестве натуральных чисел; (б) « x у » на множестве целых чисел; (в) « количество лет х совпадает с возрастом у » на множестве всех людей.

Решение. Решение. (а) Поскольку х всегда делит сам себя, то это отношение рефлексивно. Оно, конечно, не симметрично, поскольку, например, 2 является делителем 6, но не наоборот: 6 не делит 2. Проверим, что отношение делимости транзитивно. Предположим, что х делит у, а у в свою очередь делит z. Тогда из первого предположения вытекает, что у = mx для некоторого натурального числа m, а из второго z = nу, где n — натуральное число.

Следовательно, z = nу = (nт)х, т. е. х делит z. Следовательно, z = nу = (nт)х, т. е. х делит z. Значит, данное отношение транзитивно. Наконец, наше отношение кососимметрично, поскольку из предположений: х делит у и у делит х немедленно вытекает, что у = х.

Решение. Решение. (б) Так как высказывание «x х» ложно, то это отношение не рефлексивно. Оно симметрично, поскольку х у тогда и только тогда, когда у х. Наше отношение не обладает свойством транзитивности, так как, например, 2 3 и 3 2, но, тем не менее, 2 = 2. Наше отношение не кососимметрично, поскольку из условий х у и у х нельзя заключить, что х = у.

Решение. Решение. (в) Отношение этого пункта рефлексивно, так как возраст любого человека х совпадает с количеством прожитых им лет. Оно симметрично, поскольку высказывание «количество лет х совпадает с возрастом у» равносильно высказыванию «количество лет у совпадает с возрастом x»

Отношение и транзитивно, так как, если найдутся такие три человека x, у и z, что «количество лет х совпадает с возрастом у», а «количество лет у совпадает с возрастом z», то все трое будут одинакового возраста. Отношение и транзитивно, так как, если найдутся такие три человека x, у и z, что «количество лет х совпадает с возрастом у», а «количество лет у совпадает с возрастом z», то все трое будут одинакового возраста. Так как мы можем найти много ровесников, то данное отношение не кососимметрично.

Если отношение R на множестве А не обладает тем или иным свойством, то его стоит попытаться продолжить до отношения R*, которое будет иметь нужное свойство. Под «продолжением» мы понимаем присоединение некоторых упорядоченных пар к подмножеству R А А так, что новое полученное множество R* уже будет обладать требуемым свойством. Если отношение R на множестве А не обладает тем или иным свойством, то его стоит попытаться продолжить до отношения R*, которое будет иметь нужное свойство. Под «продолжением» мы понимаем присоединение некоторых упорядоченных пар к подмножеству R А А так, что новое полученное множество R* уже будет обладать требуемым свойством.

Ясно, что исходное множество R будет подмножеством в R*. Ясно, что исходное множество R будет подмножеством в R*. В том случае, если вновь построенное множество R* будет минимальным среди всех расширений R с выделенным свойством, то говорят, что R* является замыканием R относительно данного свойства.

Более строго, R* называется замыканием отношения R относительно свойства Р, если Более строго, R* называется замыканием отношения R относительно свойства Р, если R* обладает свойством Р; R R*; R* является подмножеством любого другого отношения, содержащего R и обладающего свойством Р.

Пример 4.9. Пусть А = { 1, 2, 3 }, а отношение R на A задано упорядоченными парами: Пример 4.9. Пусть А = { 1, 2, 3 }, а отношение R на A задано упорядоченными парами: R = {(1, 1), (1, 2), (1, 3), (3, 1), (2, 3)}. Оно не рефлексивно, не симметрично и не транзитивно. Найдите соответствующие замыкания.

Решение. Замыкание относительно рефлексивности должно содержать все пары вида (х, х). Поэтому, искомое замыкание имеет вид: Решение. Замыкание относительно рефлексивности должно содержать все пары вида (х, х). Поэтому, искомое замыкание имеет вид: R* = {(1, 1), (1, 2), (1, 3), (3, 1), (2, 3); (2, 2), (3, 3)}, где добавленные пары отделены от исходных точкой с запятой. Замыкание относительно симметричности должно содержать все пары, симметричные исходным. Значит, R* = {(1, 1), (1, 2), (1, 3), (3, 1), (2, 3); (2, 1), (3, 2)}.

Чтобы найти замыкание относительно транзитивности, необходимо выполнить несколько шагов. Так как R содержит пары (3, 1) и (1, 2), замыкание обязано включать в себя и пару (3, 2). Аналогично, пары (2, 3) и (3, 1) добавляют пару (2, 1), а пары (3, 1) и (1, 3) — пару (3, 3). Добавим сначала эти пары: Чтобы найти замыкание относительно транзитивности, необходимо выполнить несколько шагов. Так как R содержит пары (3, 1) и (1, 2), замыкание обязано включать в себя и пару (3, 2). Аналогично, пары (2, 3) и (3, 1) добавляют пару (2, 1), а пары (3, 1) и (1, 3) — пару (3, 3). Добавим сначала эти пары: R* {(1, 1), (1, 2), (1, 3), (3, 1), (2, 3); (3, 2), (2, 1), (3, 3)}.

Теперь у нас возникло сочетание (2, 1) и (1, 2). Стало быть, замыкание R* должно содержать пару (2, 2). Теперь можно увидеть, что все необходимые пары мы добавили (хотя бы потому, что перебрали все пары из А2). Следовательно, Теперь у нас возникло сочетание (2, 1) и (1, 2). Стало быть, замыкание R* должно содержать пару (2, 2). Теперь можно увидеть, что все необходимые пары мы добавили (хотя бы потому, что перебрали все пары из А2). Следовательно, R* = {(1, 1), (1, 2), (1, 3), (3, 1), (2, 3); (3, 2), (2, 1), (3, 3), (2, 2)}.

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

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

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

Эквивалентные элементы (т.е. находящиеся в отношении эквивалентности), как правило, обладают какими-то общими признаками. Эквивалентные элементы (т.е. находящиеся в отношении эквивалентности), как правило, обладают какими-то общими признаками.

Приведем примеры отношения эквивалентности: Приведем примеры отношения эквивалентности: Отношение «... имеет те же углы, что и ...» на множестве всех треугольников. Очевидно, что треугольники эквивалентны относительно этого отношения тогда и только тогда, когда они подобны.

Отношение R, заданное условием: х R y, если и только если ху > 0 на множестве ненулевых целых чисел является отношением эквивалентности. При этом эквивалентные числа имеют одинаковый знак. Отношение R, заданное условием: х R y, если и только если ху > 0 на множестве ненулевых целых чисел является отношением эквивалентности. При этом эквивалентные числа имеют одинаковый знак. Отношение «... имеет тот же возраст, что и ...» на множестве всех людей. «Эквивалентные» люди принадлежат к одной и той же возрастной группе.

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

Разбиением множества А называется совокупность непустых подмножеств A1, А2, …, Аn множества A, удовлетворяющих следующим требованиям: Разбиением множества А называется совокупность непустых подмножеств A1, А2, …, Аn множества A, удовлетворяющих следующим требованиям: А = A1 А2 … Аn; Ai Aj = Ø при i j. Подмножества Ai называются блоками разбиения.

Диаграмма Венна разбиения множества А на пять блоков показана на рис. 4.4. Диаграмма Венна разбиения множества А на пять блоков показана на рис. 4.4. Заметим, что блоки изображены как лоскуты, не заходящие один на другой. Это связано с тем, что блоки разбиения не могут иметь общих элементов.

Как мы уже говорили, отношение эквивалентности R на множестве А задает на нем разбиение. Блоки разбиения при этом состоят из эквивалентных друг другу элементов. Мы сейчас докажем это утверждение. Но прежде определим класс эквивалентности Еx произвольного элемента х А как подмножество Еx = {z А: z R x }. Как мы уже говорили, отношение эквивалентности R на множестве А задает на нем разбиение. Блоки разбиения при этом состоят из эквивалентных друг другу элементов. Мы сейчас докажем это утверждение. Но прежде определим класс эквивалентности Еx произвольного элемента х А как подмножество Еx = {z А: z R x }. Докажем теорему.

Теорема. Пусть R — отношение эквивалентности на непустом множестве А. Тогда различные классы эквивалентности определяют разбиение А. Теорема. Пусть R — отношение эквивалентности на непустом множестве А. Тогда различные классы эквивалентности определяют разбиение А. Доказательство. Доказательство состоит из четырех частей. 1) Сначала покажем, что классы эквивалентности являются непустыми подмножествами в А. По определению, Еx — подмножество в А. Кроме того, R — рефлексивное отношение, т.е. x R x. Следовательно, х Еx и Еx не пусто.

2) Далее проверим, что из x R y вытекает равенство Еx = Еy. Предположим, что x R y и возьмем произвольный z Еx. Тогда z R x и x R y. Поскольку R — транзитивное отношение, мы получаем, что z R y. Иными словами, z Еy. Следовательно, Еx Еy. Аналогично можно показать, что Еy Еx, откуда Еx = Еy, что и требовалось. 2) Далее проверим, что из x R y вытекает равенство Еx = Еy. Предположим, что x R y и возьмем произвольный z Еx. Тогда z R x и x R y. Поскольку R — транзитивное отношение, мы получаем, что z R y. Иными словами, z Еy. Следовательно, Еx Еy. Аналогично можно показать, что Еy Еx, откуда Еx = Еy, что и требовалось.

3) Теперь мы покажем, что классы эквивалентности удовлетворяют первому свойству разбиения, а именно, что А является объединением всех классов эквивалентности. Как уже отмечалось в первой части нашего доказательства, Еx — подмножество в A и поэтому объединение всех классов эквивалентности тоже будет подмножеством в A. 3) Теперь мы покажем, что классы эквивалентности удовлетворяют первому свойству разбиения, а именно, что А является объединением всех классов эквивалентности. Как уже отмечалось в первой части нашего доказательства, Еx — подмножество в A и поэтому объединение всех классов эквивалентности тоже будет подмножеством в A.

В обратную сторону, если х А, то х Еx. В частности, х принадлежит объединению классов эквивалентности. Значит, и А является подмножеством нашего объединения. Следовательно, А совпадает с объединением классов эквивалентности. В обратную сторону, если х А, то х Еx. В частности, х принадлежит объединению классов эквивалентности. Значит, и А является подмножеством нашего объединения. Следовательно, А совпадает с объединением классов эквивалентности.

4) И, наконец, в последней части мы покажем, что два разных класса эквивалентности не пересекаются. Этим мы проверим, что классы удовлетворяют второму свойству разбиения. Воспользуемся методом «от противного». Допустим, что Еx Еy Ø. Тогда найдется элемент z в A принадлежащий пересечению Еx Еy. Следовательно, z R x и z R y. Так как R — симметричное отношение, можно утверждать, что х R z и z R y. Ввиду транзитивности R, это влечет х R y. Значит, по второй части доказательства, Еx = Еy. 4) И, наконец, в последней части мы покажем, что два разных класса эквивалентности не пересекаются. Этим мы проверим, что классы удовлетворяют второму свойству разбиения. Воспользуемся методом «от противного». Допустим, что Еx Еy Ø. Тогда найдется элемент z в A принадлежащий пересечению Еx Еy. Следовательно, z R x и z R y. Так как R — симметричное отношение, можно утверждать, что х R z и z R y. Ввиду транзитивности R, это влечет х R y. Значит, по второй части доказательства, Еx = Еy.

Итак, мы предположили, что разные классы эквивалентности Еx и Еy пересекаются и доказали, что они на самом деле совпадают. Полученное противоречие доказывает последнюю часть наших рассуждений. Теорема доказана. Итак, мы предположили, что разные классы эквивалентности Еx и Еy пересекаются и доказали, что они на самом деле совпадают. Полученное противоречие доказывает последнюю часть наших рассуждений. Теорема доказана.

Заметим, чтобы показать, что классы эквивалентности служат блоками разбиения множества А, мы использовали все определяющие свойства отношения эквивалентности: рефлексивность, симметричность и транзитивность. Заметим, чтобы показать, что классы эквивалентности служат блоками разбиения множества А, мы использовали все определяющие свойства отношения эквивалентности: рефлексивность, симметричность и транзитивность.

Пример 4.10. Отношение R на вещественной прямой  задано условием: x R y, если и только если х - у — целое число. Докажите, что R — отношение эквивалентности и опишите классы эквивалентности, содержащие 0, и . Пример 4.10. Отношение R на вещественной прямой  задано условием: x R y, если и только если х - у — целое число. Докажите, что R — отношение эквивалентности и опишите классы эквивалентности, содержащие 0, и . Решение. Так как х - х = 0  для любого вещественного числа х, отношение R рефлексивно. Если х - у число целое, то и противоположное к нему у - х = -(х - у) является целым.

Следовательно, R — симметричное отношение. Следовательно, R — симметричное отношение. Пусть х - у и у - z — целые числа. Тогда х - z = (х - у) + (у - z) — сумма целых чисел, т. е. целое число. Это означает, что R транзитивно. Итак, мы показали, что R рефлексивно, симметрично и транзитивно. Следовательно, R — отношение эквивалентности.

Ранее были введены обозначения множеств: Ранее были введены обозначения множеств:  = { все десятичные дроби } — множество вещественных чисел;  = { 0, ±1, ±2, ±3, ... } — множество целых чисел.

Класс эквивалентности Еx произвольного вещественного числа х определяется по формуле: Класс эквивалентности Еx произвольного вещественного числа х определяется по формуле: Еx = {z : z - x — целое число }. Поэтому, Е0 = ; Е½ = { z : z - ½ — целое число } = = Е = { z : z - — целое число }=

Рефлексивное, транзитивное, но косо- симметричное отношение R на множестве А называется частичным порядком. Частичный порядок важен в тех ситуациях, когда мы хотим как-то охарактеризовать старшинство. Иными словами, решить - при каких условиях считать, что один элемент множества превосходит другой. Рефлексивное, транзитивное, но косо- симметричное отношение R на множестве А называется частичным порядком. Частичный порядок важен в тех ситуациях, когда мы хотим как-то охарактеризовать старшинство. Иными словами, решить - при каких условиях считать, что один элемент множества превосходит другой.

( Отношение R на множестве А кососимметрично, если (х R y и y R x x = у) для всех x и у из А ). ( Отношение R на множестве А кососимметрично, если (х R y и y R x x = у) для всех x и у из А ). Примеры частичных порядков: « ≤ » на множестве вещественных чисел; « » на подмножествах универсального множества; «...делит...» на множестве натуральных чисел.

Множества с частичным порядком принято называть частично упорядоченными множествами. Множества с частичным порядком принято называть частично упорядоченными множествами.

Если R — отношение частичного порядка на множестве А, то при х у и x R y мы называем х предшествующим элементом или предшественником, а у — последующим. У произвольно взятого элемента у может быть много предшествующих элементов. Однако если х предшествует у, и не существует таких элементов z, для которых x R z и z R y, мы называем х непосредственным предшественником у и пишем х у (иногда говорят, что y покрывает x).

Непосредственных предшественников можно условно изобразить с помощью графа, известного как диаграмма Хассе. Вершины графа изображают элементы частично упорядоченного множества А, и если х у, то вершина х помещается ниже вершины у и соединяется с ней ребром. Непосредственных предшественников можно условно изобразить с помощью графа, известного как диаграмма Хассе. Вершины графа изображают элементы частично упорядоченного множества А, и если х у, то вершина х помещается ниже вершины у и соединяется с ней ребром. Диаграмма Хассе выдает полную информацию об исходном частичном порядке, если мы “поднимемся” по всем цепочкам ребер.

Пример 4.11. Дано, что отношение «... делитель ...» определяет частичный порядок на множестве А = {1, 2, 3, 6, 12, 18}. Составьте таблицу предшественников и непосредственных предшественников, после чего постройте соответствующую диаграмму Хассе. Пример 4.11. Дано, что отношение «... делитель ...» определяет частичный порядок на множестве А = {1, 2, 3, 6, 12, 18}. Составьте таблицу предшественников и непосредственных предшественников, после чего постройте соответствующую диаграмму Хассе. Решение. Таблица и диаграмма приведены ниже.

Таблица 4.1 Таблица 4.1

Рисунок 4.5. Диаграмма Хассе

Линейным порядком на множестве А называется отношение частичного порядка, при котором из любой пары элементов можно выделить предшествующий и последующий. Линейным порядком на множестве А называется отношение частичного порядка, при котором из любой пары элементов можно выделить предшествующий и последующий. Примеры линейного порядка: « ≤ » на множестве вещественных чисел; лексикографическое упорядочение слов в словаре.

Различные сортирующие процедуры в информатике требуют, чтобы элементы сортируемых множеств были линейно упорядочены. В этом случае они могут выдавать упорядоченный список. Другие приложения используют частичный порядок, предполагая, что в любом частично упорядоченном множестве найдется минимальный элемент (не имеющий предшественников) и максимальный (не имеющий последующих элементов). Различные сортирующие процедуры в информатике требуют, чтобы элементы сортируемых множеств были линейно упорядочены. В этом случае они могут выдавать упорядоченный список. Другие приложения используют частичный порядок, предполагая, что в любом частично упорядоченном множестве найдется минимальный элемент (не имеющий предшественников) и максимальный (не имеющий последующих элементов).

Частично упорядоченное множество из примера 4.11 обладает одним минимальным элементом, а именно, числом 1. С другой стороны, в нем есть два максимальных: 12 и 18. В этом множестве содержится несколько линейно упорядоченных подмножеств. Каждое из них соответствует цепочке ребер на диаграмме Хассе. Например, множество { 1, 2, 6, 18 } линейно упорядочено относительно отношения «...делитель...». Частично упорядоченное множество из примера 4.11 обладает одним минимальным элементом, а именно, числом 1. С другой стороны, в нем есть два максимальных: 12 и 18. В этом множестве содержится несколько линейно упорядоченных подмножеств. Каждое из них соответствует цепочке ребер на диаграмме Хассе. Например, множество { 1, 2, 6, 18 } линейно упорядочено относительно отношения «...делитель...».

Краткое содержание главы Бинарным отношением между множествами А и В называется подмножество R в А В. Если А = В, то говорят, что R — отношение на А. Бинарное отношение между конечными множествами может быть описано на словах (при помощи подходящих предикатов), как множество упорядоченных пар, как орграф и с помощью матрицы.

Отношение R на множестве А называется Отношение R на множестве А называется рефлексивным, если х R x для всех х А; симметричным, если x R y у R x для всех х, у А; кососимметричным, если (х R y и у R x х = у) для всех x, y A; транзитивным, если (x R y и y R z) x R z для всех x, у, z А.

Отношение R* называют замыканием отношения R относительно свойства Р, если Отношение R* называют замыканием отношения R относительно свойства Р, если R* обладает свойством Р; R R*: R* — подмножество любого другого отношения, содержащего R и обладающего свойством Р.

Рефлексивное, симметричное и транзитивное отношение R на множестве А называется отношением эквивалентности. Классом эквивалентности элемента х А является подмножество Рефлексивное, симметричное и транзитивное отношение R на множестве А называется отношением эквивалентности. Классом эквивалентности элемента х А является подмножество Еx = {z A: z R x}.

Разбиение множества А представляет собой совокупность подмножеств А1, А2, ..., Аn в A, удовлетворяющих требованиям: Разбиение множества А представляет собой совокупность подмножеств А1, А2, ..., Аn в A, удовлетворяющих требованиям: А = А1 A2 … Аn и Ai Aj = Ø при i j. Подмножества Ai из предыдущего определения называются блоками разбиения. Если R — отношение эквивалентности на А, то различные классы эквивалентности образуют разбиение А.

Рефлексивное, кососимметричное и транзитивное отношение R на множестве А называется частичным порядком. Множества, на которых определено такое отношение, в свою очередь, называются частично упорядоченными множествами. Рефлексивное, кососимметричное и транзитивное отношение R на множестве А называется частичным порядком. Множества, на которых определено такое отношение, в свою очередь, называются частично упорядоченными множествами. Линейный порядок на множестве — это такой частичный порядок, при котором можно сравнить любую пару элементов.

Если R — отношение частичного порядка на множестве А и x R y, х у, то х называется предшественником у. В том случае, когда х предшествует у и нет такого элемента z, для которого х R z и z R у, то говорят, что х — непосредственный предшественник у. Последний факт обозначают так: х у. Если R — отношение частичного порядка на множестве А и x R y, х у, то х называется предшественником у. В том случае, когда х предшествует у и нет такого элемента z, для которого х R z и z R у, то говорят, что х — непосредственный предшественник у. Последний факт обозначают так: х у. Диаграмма Хассе представляет собой граф, чьи вершины изображают элементы частично упорядоченного множества. В том случае, когда х у, вершина х располагается непосредственно под вершиной у и соединяется с ней ребром.

Системы управления базами данных Данные, хранящиеся в компьютере, называются базой данных. Программы, с помощью которых пользователь извлекает информацию из базы данных или вносит в нее изменения, называются системами управления базами данных (СУБД).

Данные в компьютере, как правило, организованы в виде таблиц. Например, табл. 4.2 содержит информацию о группе студентов: личный номер студента, фамилию, пол, дату рождения, семейное положение и адрес. В табл. 4.3 занесена информация об успеваемости некоторых студентов по отдельным курсам. Данные в компьютере, как правило, организованы в виде таблиц. Например, табл. 4.2 содержит информацию о группе студентов: личный номер студента, фамилию, пол, дату рождения, семейное положение и адрес. В табл. 4.3 занесена информация об успеваемости некоторых студентов по отдельным курсам.

Таблица 4.2. Т1 = Персональные данные Таблица 4.2. Т1 = Персональные данные

Таблица 4.3. Т2 = Успеваемость Таблица 4.3. Т2 = Успеваемость

Эти таблицы составят основу для наших обсуждений, хотя и не представляют практического интереса. Например, проблемы при работе с табл. 4.2 могут возникнуть при попытке извлечь информацию о двух различных Смитах, а в табл. 4.2 отсутствует детальная информация о некоторых из студентов, появляющихся в табл. 4.3. Эти таблицы составят основу для наших обсуждений, хотя и не представляют практического интереса. Например, проблемы при работе с табл. 4.2 могут возникнуть при попытке извлечь информацию о двух различных Смитах, а в табл. 4.2 отсутствует детальная информация о некоторых из студентов, появляющихся в табл. 4.3.

Строки таблицы с n колонками, помеченными множествами А1, А2, ..., Аn можно представить как подмножество в прямом произведении А1 А2 ... Аn. Строки образуют список из n элементов, по одному из каждого Аi а вся таблица представляет собой парное отношение. Строки таблицы с n колонками, помеченными множествами А1, А2, ..., Аn можно представить как подмножество в прямом произведении А1 А2 ... Аn. Строки образуют список из n элементов, по одному из каждого Аi а вся таблица представляет собой парное отношение.

Например, табл. 4.3 можно рассматривать как подмножество Т2 в А1 А2 А3 А4 А5, где А1 — множество фамилий студентов, а А2 = А3 = А4 = А5 = {отл, хор, удовл, неуд}. Один из элементов этого пятинарного отношения — строка (Джонс, хор, удовл, хор, неуд), в которой записаны оценки Джонса, полученные им за четыре предмета. Например, табл. 4.3 можно рассматривать как подмножество Т2 в А1 А2 А3 А4 А5, где А1 — множество фамилий студентов, а А2 = А3 = А4 = А5 = {отл, хор, удовл, неуд}. Один из элементов этого пятинарного отношения — строка (Джонс, хор, удовл, хор, неуд), в которой записаны оценки Джонса, полученные им за четыре предмета.

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

Операция проект формирует новую таблицу из определенных столбцов старой. Например, проект(Т1, {Фамилия, Адрес}) создает табл. 4.4. Операция проект формирует новую таблицу из определенных столбцов старой. Например, проект(Т1, {Фамилия, Адрес}) создает табл. 4.4.

Таблица 4.4. ТЗ = проект(Т1, {Фамилия, Адрес}) Таблица 4.4. ТЗ = проект(Т1, {Фамилия, Адрес})

Задача 1. Найти проект (Т2, {Фамилия, Основы матем., Дискр. матем.}). Задача 1. Найти проект (Т2, {Фамилия, Основы матем., Дискр. матем.}). Решение. Смотри табл. 4.5 Таблица 4.5

Операция соединение объединяет две таблицы в большую, выписывая в одну строку информацию, соответствующую общему атрибуту. Предположим, что R и S — отношения, представленные двумя таблицами, причем R — подмножество в прямом произведении А1 … Аm В1 … Вn, a S — в прямом произведении А1 … Аm С1 … Ср. Операция соединение объединяет две таблицы в большую, выписывая в одну строку информацию, соответствующую общему атрибуту. Предположим, что R и S — отношения, представленные двумя таблицами, причем R — подмножество в прямом произведении А1 … Аm В1 … Вn, a S — в прямом произведении А1 … Аm С1 … Ср.

В этом случае общие атрибуты представлены множествами А1, А2,…, Аm. Соединение R и S — это подмножество в А1 … Аm В1 … Вn С1 … Ср, состоящее из элементов вида (a1, a2, …, аm, b1, b2, …, bm, c1, c2, ..., ср), где (a1, ..., аm, b1, ..., bm) лежит в R, а (a1, ..., аm, c1, ..., ср) — в подмножестве S. В этом случае общие атрибуты представлены множествами А1, А2,…, Аm. Соединение R и S — это подмножество в А1 … Аm В1 … Вn С1 … Ср, состоящее из элементов вида (a1, a2, …, аm, b1, b2, …, bm, c1, c2, ..., ср), где (a1, ..., аm, b1, ..., bm) лежит в R, а (a1, ..., аm, c1, ..., ср) — в подмножестве S.

Например, соединение(ТЗ, Т2) дает табл. 4.6. Например, соединение(ТЗ, Т2) дает табл. 4.6. Таблица 4.6

Операция выбор отбирает строки таблицы, удовлетворяющие подходящему критерию. Например, выбор(Т1, Пол = М и Семейное положение = Женат) верстает табл. 4.7. Операция выбор отбирает строки таблицы, удовлетворяющие подходящему критерию. Например, выбор(Т1, Пол = М и Семейное положение = Женат) верстает табл. 4.7. Таблица 4.7.

Задача 2. Найдите выбор(Т2, Дискр. матем. = отл). Задача 2. Найдите выбор(Т2, Дискр. матем. = отл). Решение. В новую таблицу (табл. 4.8) войдут только те строки таблицы Т2, у которых в столбце, помеченном Дискр. математика будет стоять «отл». Таблица 4.8

Как иллюстрируют следующие задачи, комбинация всех трех операций позволит нам извлекать различную информацию из баз данных. Как иллюстрируют следующие задачи, комбинация всех трех операций позволит нам извлекать различную информацию из баз данных. Задача 3. Найдите таблицу, которая получится в результате операций: R1 = проект(Т2, {Фамилия, Прогр., Вычисл. системы}); R2 = выбор(R1, Вычисл. системы=отл или Прогр.=отл);

Решение. Во-первых, все столбцы таблицы Т2, отличные от Фамилия, Прогр. и Вычисл. системы, удаляются. В результате получится таблица R1. Затем, в новой таблице нужно оставить только те строки, в которых есть хотя бы одна оценка «отл», а остальные отбросить. Это даст нам требуемую таблицу R2 (табл. 4.9). Решение. Во-первых, все столбцы таблицы Т2, отличные от Фамилия, Прогр. и Вычисл. системы, удаляются. В результате получится таблица R1. Затем, в новой таблице нужно оставить только те строки, в которых есть хотя бы одна оценка «отл», а остальные отбросить. Это даст нам требуемую таблицу R2 (табл. 4.9). Таблица 4.9

Задача 4. Найдите результат действий следующих операций: Задача 4. Найдите результат действий следующих операций: R1 = выбор(Т1, пол = Ж); R2 = проект(Т2,{Фамилия, Дискр. матем.}); R3 = соединение(R1, R2). Решение. Прежде всего выберем из таблицы Т1 строки, соответствующие студенткам, и составим из них таблицу R1. Затем удалим из Т2 все столбцы, кроме двух выбранных, и получим таблицу R2. Общим атрибутом таблиц R1 и R2 является Фамилия. Соединив R1 и R2, получим искомую таблицу (табл. 4.10).

Таблица 4.10. Таблица 4.10.

Задача 5. Выпишите последовательность операций (выбор, проект и соединение) для определения имен и адресов всех тех студенток, которые получили оценку не ниже «хор» по обоим предметам: основы математики и дискретная математика. Задача 5. Выпишите последовательность операций (выбор, проект и соединение) для определения имен и адресов всех тех студенток, которые получили оценку не ниже «хор» по обоим предметам: основы математики и дискретная математика.

Решение. Одна из последовательностей операций выглядит следующим образом. Решение. Одна из последовательностей операций выглядит следующим образом. R1 = выбор(Т1, пол = Ж); R2 = выбор(Т2, Дискр. матем. = «отл» или Дискр. матем. = «хор»); R3 = выбор (R2, Основы матем. = «отл» или Основы матем. = «хор»); R4 = соединение(R1, R3); R = проект(R4,{Фамилия, Адрес}).