|
|
ОглавлениеГлава 4. Логика и исчисление высказываний Для бесплатного чтения доступна только часть главы! Для чтения полной версии необходимо приобрести книгуГлава 2.ОТНОШЕНИЯ2.1. ВведениеИзучение множеств обычно осуществляется с точки зрения операций, производимых над элементами этих множеств, т.е. как из одних множеств строить другие множества. Однако часто приходится сравнивать сами множества. Приходится говорить о таких сравнениях, как «меньше чем», «параллельно» и т.п. Сравнения такого рода не являются операциями, они в определенном смысле рассматривают существование или отсутствие некоторой связи между парами объектов, взятых в фиксированном порядке. Такие связи называют отношениями, и они обычно определяются в терминах упорядоченных пар. Имеется три вида отношений, которые играют важную роль в дискретной математике: 1) отношения эквивалентности; 2) отношения порядка; 3) функции. Обычно отношения определяются в терминах упорядоченных пар (a, b). Именно пары являются элементами отношений, но и каждая такая пара (a, b), в свою очередь, сама состоит из элементов, где a является первым элементом пары, а b – вторым элементом. В частности, (a, b) = (c, d) тогда и только тогда, когда a = c и b = d. Поэтому (a, b) ≠ (b, a) при a ≠ b. Для множеств, которые рассматривались в главе 1, это было не так, поскольку список {a, b} и список {b, a} определяли одно и то же множество, т.е. {a, b} = {b, a} при любых a и b. 2.2. Декартово произведение множествПусть имеется два произвольных множества А и В. Множество всех упорядоченных пар (a, b), где a ∈ A и b ∈ B называется произведением или декартовым произведением множеств А и В и обозначается А × В. По определению А × B = {(a, b) : a ∈ A и b ∈ B}. Вместо А × А можно записать А2. Пример 2.1. Поскольку R — это множество вещественных чисел, то R2 = R × R является множеством упорядоченных пар вещественных чисел. Геометрическим представлением декартова произведения R2 являются точки плоскости, как на рис. 2.1. Рис. 2.1 Каждая точка плоскости является упорядоченной парой (a, b) и наоборот. Иногда R2 называют декартовой плоскостью. Рассмотрим пример с конечными множествами. Пример 2.2. Пусть А = {1, 2} и B = {a, b, c, d}. Тогда А × В = {(1, a), (1, b), (1, c), (1, d), (2, a), (2, b), (2, c), (2,d) }, В × А = {(a, 1), (a, 2), (b, 1), (b, 2), (c, 1), (c, 2), (d, 1), (d, 2) }. Также можно найти произведение А на себя. А × A = {(1, 1), (1, 2), (2, 1), (2, 2) }. Декартово произведение не коммутативно, т.е. А × В ≠ В × А, и это следует из того что декартово произведение образуется из упорядоченных пар. Если обозначить через n(A × B) количество элементов, то для любых конечных множеств А и В количество элементов n(A × B) = n(A) · n(B). Такое произведение получается потому, что с каждым из n(A) элементов множества А можно образовать n(B) пар (a, b) для A × B. Можно распространить произведение множеств на любое число конечных множеств. Так, для множеств А1, А2, …, Аn множество всех упорядоченных наборов элементов (a1, a2, …, an), где a1 ∈ А1, a2 ∈ А2, …, an ∈ Аn, называется декартовым произведением этих множеств (или прямым произведением) и обозначается Вместо записи А1 × А2 × … × Аn можно записать An. Так, например, запись R × R × R = R3 используется для описания трехмерного пространства. 2.3. ОтношенияОпределение. Пусть имеются множества А и В. Бинарным отношением R или просто отношением R между двумя множествами А и В называется любое подмножество декартова произведения A × B, т.е. R ⊆ A × B. Отношение R представляет собой множество упорядоченных пар, где каждый первый элемент пары входит в множество А, а второй в множество В. Для каждой пары a ∈ A и b ∈ B истинно точно одно из следующих утверждений: 1)(a, b) ∈ R, т.е. a находится в отношении R к b (иногда это пишут как aRb); 2)(a, b) ∉ R, т.е. не находится в отношении R к b (или можно записать ab). Если R является отношением на множестве А с самим собой, т.е. R является подмножеством А2 = А × А, то говорят, что R является отношением на А. Областью определения отношения R называется множество всех первых элементов упорядоченных пар R, и областью значений R называется множество вторых элементов пар R. Если отношение образовано более чем из двух множеств, то при n множествах его называют n-арным отношением. Сечением по элементу a ∈ A отношения R называется множество элементов b ∈ B, для которых (a, b) ∈ R. Множество всех сечений отношения R называется фактормножеством множества В по отношению R, и оно однозначно задает отношение R. Пример 2.3. Пусть А = {1, 2, 3} и В = {1, 2, 3, 4, 5, 6}. Пусть (a, b) ∈ R означает, что элемент b ∈ В является делителем элемента a ∈ А. Для того чтобы найти отношение R, выпишем сначала все пары декартова произведения A × B: Выберем из них те пары, в которых второе число является делителем первого R = {(1, 1), (2, 1), (2, 2), (3, 1), (3, 3)}. Найдем для всех элементов множества А их сечения 1 2 3 {{1} {1, 2} {1, 3}} фактормножество множества В по отношению R. Пример 2.4 (a) Пусть имеется отношение R, означающее «быть соседними» для любых двух стран, которые имеют общую границу. Поэтому (Италия, Швейцария) ∈ R. (Италия, Германия) ∉ R. (Италия, Россия) ∉ R. (Франция, Германия) ∈ R. (b) Пусть имеются множества А = {лыжи, коньки, ласты}, В = {снег, лед, вода}. Определим отношение R между А и В как (a, b) ∈ R, если a используется на b, т.е. R = {(лыжи, снег), (коньки, лед), (ласты, вода)}. Можно прочитать «лыжи используются на снегу», или лыжи R снег, «коньки используются на льду», или коньки R лед и т.д. (с) Множество, порождаемое включением ⊆, является отношением на любом семействе множеств. (d) Для множества прямых на плоскости свойства параллельности и перпендикулярности являются отношениями. Для любой пары прямых на плоскости a и b всегда можно определить, параллельны они или нет либо перпендикулярны или нет. (е) Пусть А произвольное множество. Тогда A × А и Ø будут подмножествами произведения A × А и, следовательно, отношениями на А. Они называются соответственно универсальное отношение и пустое отношение. Обратное отношение Пусть R любое отношении между множествами А и В. Тогда обратное отношение для R обозначается как R-1 и является отношением между В и А и состоит из пар отношения R, элементы которых меняются местами. R-1 = {(b, a): (a, b) ∈ R}. Пусть, например, A = {1, 2, 3}, B = {x, y, z}. Тогда, если R = {(1, x), (2, x), (2, y), (3, y), (3, z)}, то обратное для него R-1 = {(x, 1), (x, 2), (y, 2), (y, 3), (z, 3)}. Для любого отношения R выполняется (R-1)-1 = R. Область определения R-1 равна области значений R, а область значений равна области определения R. Если R некоторое отношение на А, то его обратное также всегда будет отношением на А. 2.4. Представление отношенийКак и множества, отношения можно изображать графически. Самый известный пример отношений дают уравнения. Рассмотрим отношение Р на множестве вещественных чисел R, т.е. Р является подмножеством множества R × R. Поскольку R2 представляет собой множество точек плоскости, то можно выразить Р через те точки плоскости, которые принадлежат Р. Обычно отношение Р состоит из всех пар вещественных чисел, которые обращают уравнение в ноль. Рассмотрим следующий пример. Пример 2.5 Пусть имеется отношение Р, определяемое уравнением 2 x + y = 4. Р содержит все пары (x, y), которые удовлетворяют уравнению. Графиком этого уравнения является прямая (рис. 2.2). Рис. 2.2 Представление отношений для конечных множеств Пусть А и В два конечных множества. Отношение R между этими множествами можно представить: 1) в виде прямоугольной матрицы из 0 и 1 — строки матрицы размечены элементами из А, а столбцы — элементами из В: 2) в виде двух непересекающихся дисков — один для множества А и другой для В. Если имеется отношение из А в В, то стрелка направлена от a к b, если (a, b) ∈ R. Например, если A = {a1, a2, a3}, B = {b1, b2, b3, b4} и R = {(a1, b2), (a1, b4), (a2, b3), (a3, b4)}, то матрица отношений и стрелочная диаграмма для R показаны на рис. 2.3. Рис. 2.3 Представление отношения в виде ориентированного графа Имеется еще один способ представления отношений. Он используется, когда имеется отношение R для некоторого конечного множества А с самим собой. Пусть на множестве А = (1, 2, 3, 4, 5} имеется отношение R = {(1, 2), (2, 3), (3, 1), (3, 3), (3, 4), (4, 5), (5, 2), (5, 4)}. Поставим в соответствие каждому элементу множества А вершину графа, а каждой паре отношения — ориентированное ребро (дугу), при этом стрелка направлена от вершины, соответствующей первой паре, к вершине второй пары (рис. 2.4). Рис. 2.4 2.5. Композиция отношенийПусть имеются множества А, В и С, и пусть R отношение из А в В, а S отношение из В в С. Тогда R будет подмножеством А × В и S будет подмножеством В × С. Отношения R и S позволяют построить новое отношение из А в С, которое обозначается R ○ S и которое определяется как Внимание! Авторские права на книгу "Дискретная математика. Краткий курс. Учебное пособие" (Казанский А.А.) охраняются законодательством! |
||||||||||||||||||||||
