Судопланов. Судоплатов С.В., Овчинникова Е.В. Дискретная математика 2016. Редакционная коллегия серии учебники нгту
 Скачать 2.01 Mb.
|
|
X счетно. Нетрудно заметить, что множество X эквивалентно множеству ∪ n∈ω ω n , по- скольку каждая функция f ∈ X однозначно определяется кортежем цифр (f (0), . . . , f (k)), где f (k) 6= 9 и f (n) = 9 для всех n > k. Теперь из предло- жения 1.4.4 получаем X ∼ ∪ n∈ω ω n ∼ ω, т. е. |X| = ω. ¤ § 1.5. Матрица бинарного отношения. Специальные бинарные отношения Рассмотрим два конечных множества A = {a 1 , a 2 , . . ., a m }, B = {b 1 , b 2 , . . . , b n } и бинарное отношение P ⊆ A × B. Определим матрицу [P ] = (p ij ) размера m × n бинарного отношения P по следующему правилу: p ij = ( 1, если (a i , b j ) ∈ P, 0, если (a i , b j ) / ∈ P. 1.5. МАТРИЦА БИНАРНОГО ОТНОШЕНИЯ 35 Полученная матрица содержит полную информацию о связях между эле- ментами и позволяет представлять эту информацию на компьютере. Заме- тим, что любая матрица, состоящая из нулей и единиц, является матрицей некоторого бинарного отношения. Пример 1.5.1. Матрица бинарного отношения P ⊆ A 2 , A = {1, 2, 3}, заданного на рис. 1.9, имеет вид [P ] = 1 1 1 0 0 1 1 0 0 . ¤ Отметим основные свойства матриц бинарных отношений. 1. Если P, Q ⊆ A × B, [P ] = (p ij ), [Q] = (q ij ), то [P ∪ Q] = (p ij + q ij ) и [P ∩ Q] = (p ij · q ij ), где сложение осуществля- • • • - ¡ ¡ ¡ ¡ ¡ ¡ ª @ @ @ @ @ @ I@ @ @ @ @ @ R ¹¸ º· ¾ 1 2 3 Рис. 1.9 ется по правилам 0 + 0 0, 1 + 1 1 + 0 0 + 1 1, а умножение — обычным образом. Итак, [P ∪ Q] = [P ] + [Q], а матрица [P ∩ Q] по- лучается перемножением соответствующих эле- ментов из [P ] и [Q]: [P ∩ Q] = [P ] ∗ [Q]. Пример 1.5.2. Пусть [P ] = µ 1 0 1 0 1 1 ¶ , [Q] = µ 0 1 1 0 0 1 ¶ — матрицы отношений P и Q. Тогда [P ∪ Q] = [P ] + [Q] = µ 1 0 1 0 1 1 ¶ + µ 0 1 1 0 0 1 ¶ = µ 1 1 1 0 1 1 ¶ , [P ∩ Q] = [P ] ∗ [Q] = µ 1 0 1 0 1 1 ¶ ∗ µ 0 1 1 0 0 1 ¶ = µ 0 0 1 0 0 1 ¶ . ¤ 2. Если P ⊆ A × B, Q ⊆ B × C, то [P ◦ Q] = [P ] · [Q], где умножение матриц [P ] и [Q] производится по обычному правилу умножения матриц, но произведение и сумма элементов из [P ] и [Q] — по определенным в п. 1 правилам. 36 Глава 1. ЭЛЕМЕНТЫ ТЕОРИИ МНОЖЕСТВ Пример 1.5.3. Если [P ] = µ 0 1 0 1 1 0 ¶ , [Q] = 0 1 1 0 1 1 , то [P ◦ Q] = µ 0 1 0 1 1 0 ¶ · 0 1 1 0 1 1 = µ 1 0 1 1 ¶ . ¤ 3. Матрица обратного отношения P −1 равна транспонированной матрице отношения P : [P −1 ] = [P ] T 4. Если P ⊆ Q, [P ] = (p ij ), [Q] = (q ij ), то p ij 6 q ij 5. Матрица тождественного отношения id A единична: [id A ] = 1 0 · · · 0 0 1 · · · 0 0 0 · · · 1 . Пусть P — бинарное отношение на множестве A: P ⊆ A 2 . Отношение P называется рефлексивным, если (x, x) ∈ P для всех x ∈ A, т. е. id A ⊆ P , [P ] = 1 1 ∗ ∗ 1 . Если P ∩ id A = ∅, то отношение P называется антирефлексивным или ирре- флексивным. Отношение P называется симметричным, если для любых x, y ∈ A из (x, y) ∈ P следует (y, x) ∈ P , т. е. P −1 = P , или [P ] T = [P ]. Если P ∩ P −1 = ∅, то отношение P называется асимметричным. Отношение P называется антисимметричным, если из (x, y) ∈ P и (y, x) ∈ P следует, что x = y, т. е. P ∩ P −1 ⊆ id A . На языке матриц это означает, что в матрице [P ∩ P −1 ] = [P ]∗[P ] T все элементы вне главной диагонали являются нулевы- ми. Отношение P называется транзитивным, если из (x, y) ∈ P и (y, z) ∈ P следует (x, z) ∈ P , т. е. P ◦ P ⊆ P . 1.5. МАТРИЦА БИНАРНОГО ОТНОШЕНИЯ 37 Отметим, что антисимметричность не совпадает с несимметрично- стью. Действительно, отношение P = {(1, 2), (2, 3), (3, 2)} на множестве A = {1, 2, 3} не симметрично (так как (1, 2) ∈ P , а (2, 1) / ∈ P ) и не анти- симметрично (поскольку 2 6= 3, но (2, 3) ∈ P и (3, 2) ∈ P ). Тождественное отношение id A является одновременно симметричным и антисимметричным. Пример 1.5.4. Проверим, какими свойствами обла- • • • 6 ¡ ¡ ¡ ¡ ¡ ¡ µ - ±° ²¯ j 2 3 1 Рис. 1.10 дает отношение P ⊆ A 2 , A = {1, 2, 3}, изображенное на рис. 1.10. Составим матрицу отношения P : [P ] = 0 1 1 0 1 1 0 0 0 . Так как в матрице [P ] на главной диагонали имеются ну- левые элементы, отношение P не рефлексивно. Несиммет- ричность матрицы [P ] означает, что отношение P не симметрично. Для проверки антисимметричности вычислим матрицу [P ∩ P −1 ] = [P ] ∗ [P ] T Имеем [P ] ∗ [P ] T = 0 1 1 0 1 1 0 0 0 ∗ 0 0 0 1 1 0 1 1 0 = 0 0 0 0 1 0 0 0 0 . Поскольку в полученной матрице все элементы, стоящие вне главной диа- гонали, нулевые, отношение P антисимметрично. Так как [P ◦ P ] = [P ] (проверьте!), то P ◦ P ⊆ P , т. е. P является транзитивным отношением. ¤ Пример 1.5.5. Отношение < {(x, y) | x, y ∈ Q и x < y} на множестве рациональных чисел Q не рефлексивно, не симметрично, антисимметрично и транзитивно. ¤ Пример 1.5.6. Рассмотрим отношение P = {(x, y) | x, y ∈ Z и x − y < 1} на множестве целых чисел Z. Так как x − x = 0 < 1 для любого x ∈ Z, отношение P рефлексивно. Поскольку (2, 4) ∈ P , а (4, 2) / ∈ P , отношение P не симметрично. Заметим, что если x − y < 1 и y − x < 1, то x = y, так как из x 6= y следует |x − y| > 1. Таким образом, отношение P антисимметрично. Предположим теперь, что (x, y), (y, z) ∈ P , т. е. x − y < 1 и y − z < 1. Имеем x 6 y и y 6 z, тогда x 6 z, значит, x − z < 1, т. е. (x, z) ∈ P . Следовательно, отношение P транзитивно. ¤ 38 Глава 1. ЭЛЕМЕНТЫ ТЕОРИИ МНОЖЕСТВ § 1.6. Отношения эквивалентности и разбиения. Фактор-множества Отношение P называется отношением эквивалентности (эквивалентно- стью), если P рефлексивно, симметрично и транзитивно. Эквивалентности часто обозначают символами E и ∼ (тильда): x E y, x ∼ y. Пример 1.6.1. 1. Отношение равенства x = y является эквивалентно- стью на любом множестве A, так как оно рефлексивно (x = x), симметрично (x = y ⇒ y = x) и транзитивно (x = y, y = z ⇒ x = z). 2. Отношение подобия на множестве треугольников есть отношение эк- вивалентности. 3. На любом множестве P(U) отношение равномощности |A| = |B| является отношением эквивалентности (см. § 1.4). 4. Отношение принадлежности к одной студенческой группе на множе- стве студентов НГТУ — отношение эквивалентности. 5. Рассмотрим множество M программ, вычисляющих некоторые функ- ции. Отношение E = {(x, y) | программы x и y вычисляют одну и ту же функцию} является эквивалентностью. ¤ Пусть E — эквивалентность на множестве A. Классом эквивалентно- сти элемента x ∈ A называется множество E(x) {y | x E y}. Клас- сы эквивалентности E будут также называться E-классами. Множество A/E {E(x) | x ∈ A} называется фактор-множеством множества A по от- ношению E. Пример 1.6.2. 1. Для отношения равенства = на множестве A каждый =-класс состоит только из одного элемента: =(x) = {x} для любого x ∈ A. Таким образом, фактор-множество A/= имеет вид {{x} | x ∈ A} и, следова- тельно, биективно множеству A. 2. Для отношения принадлежности к одной студенческой груп- пе классом эквивалентности является множество студентов одной группы. Фактор-множество множества студентов НГТУ по этому отношению экви- валентности представляет собой множество студенческих групп НГТУ. ¤ Предложение 1.6.1. Множество A/E является разбиением множе- ства A. Обратно, если R = {A i } — некоторое разбиение множества A, то можно задать соответствующее ему отношение эквивалентности E по следующему правилу: x E y ⇔ x, y ∈ A i для некоторого i. 1.6. ОТНОШЕНИЯ ЭКВИВАЛЕНТНОСТИ И РАЗБИЕНИЯ 39 Доказательство. Пусть E — отношение эквивалентности на множе- стве A; A/E — фактор-множество множества A по E. Так как в силу ре- флексивности отношения E выполнимо x ∈ E(x) для любого x ∈ A, то каждое множество из A/E непусто и ∪ x∈A E(x) = A. Чтобы установить, что A/E — разбиение множества A, осталось показать, что если E(x)∩E(y) 6= ∅, то E(x) = E(y). Пусть z ∈ E(x) ∩ E(y) и u ∈ E(x), т. е. (x, z), (y, z), (x, u) ∈ E. Так как отношение E симметрично, (z, x) ∈ E. Тогда из транзитивности отношения E следует (y, u) ∈ E, т. е. u ∈ E(y). Таким образом, E(x) ⊆ E(y). Включение E(y) ⊆ E(x) доказывается аналогично. Предположим, что E — отношение на множестве A, соответствующее разбиению R = {A i }. Рефлексивность и симметричность E очевидны. Пусть теперь x E y и y E z. Тогда x, y ∈ A i , y, z ∈ A j , где A i , A j ∈ R. Поскольку y ∈ A i и y ∈ A j , то A i = A j . Следовательно, x, z ∈ A i и x E z. ¤ Таким образом, существует биекция между множеством всех отноше- ний эквивалентности на множестве A и множеством всех разбиений мно- жества A. В любом классе E(x) эквивалентности E каждый элемент y ∈ E(x) свя- зан отношением E с любым элементом z ∈ E(x). Поэтому если E — эк- вивалентность на конечном множестве A, A/E = {E(x 1 ), . . . , E(x n )}, E(x i ) = {b i 1 , . . . , b i m i }, i = 1, . . . , n, и множество A перенумеровано в следу- ющем порядке: b 1 1 , . . . , b 1 m 1 , b 2 1 , . . . , b 2 m 2 , . . . , b n 1 , . . . , b n m n , то матрица [E] имеет блочно-диагональный вид: [E] = m 1 m 2 m n z}|{ z}|{ z}|{ m 1 n m 2 n m n n 1 0 1 0 1 , где блоки 1 состоят из единиц, а остальные элементы равны 0. Если же множество A перенумеровано произвольным образом: A = {a 1 , . . . , a n }, E — отношение эквивалентности на A, то матрица [E] = (e ij ) приводится к блочно-диагональному виду некоторыми одновре- 40 Глава 1. ЭЛЕМЕНТЫ ТЕОРИИ МНОЖЕСТВ менными перестановками строк и столбцов. Элементы a i и a j эквивалентны по отношению E тогда и только тогда, когда i-я и j-я строки (а также столб- цы) матрицы [E] совпадают. Класс эквивалентности E(a i ) состоит из элемен- тов a j , для которых e ij = 1. Пример 1.6.3. Рассмотрим множество A = {1, 2, 3, 4, 5} с разбиением R = {{1, 3, 5}, {2, 4}}, задающим отношение эквивалентности E с двумя E- классами {1, 3, 5} и {2, 4}. Матрица [E] имеет вид 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 . По этой матрице легко определить, что класс E(3) равен {1, 3, 5}, так как в 3-й строке только e 31 , e 33 и e 35 равны 1. ¤ Пример 1.6.4. Рассмотрим геометрическое векторное пространство E 3 и множество направленных отрезков в нем. Направленные отрезки −−−→ A 1 B 1 и −−−→ A 2 B 2 называются эквивалентными: −−−→ A 1 B 1 ∼ −−−→ A 2 B 2 , если они имеют одина- ковые длину и направление. Отношение ∼ — это отношение эквивалентно- сти. Вектором (геометрическим вектором) − → a в E 3 называется класс экви- валентности направленных отрезков ∼ ( −→ AB) для некоторого −→ AB. Фактор- множество множества направленных отрезков по отношению ∼ образует множество векторов пространства E 3 . ¤ § 1.7. Отношения порядка Отношение эквивалентности является обобщением отношения равенства: эквивалентные элементы считаются “равными”. Обобщением обычного отно- шения 6 служат отношения порядка. Отношение P ⊆ A 2 называется предпорядком или квазипорядком, если P рефлексивно и транзитивно. Пример 1.7.1. Отношение P = {(1, 1), (2, 2), (3, 3), (1, 2), (2, 1), (2, 3), (1, 3)} на множестве {1, 2, 3} является предпорядком (рис. 1.11). ¤ 1.7. ОТНОШЕНИЯ ПОРЯДКА 41 Отметим, что симметричный предпорядок является отношением эквива- лентности. Отношение P ⊆ A 2 называется частичным по- • • • @ @ @ @ R - * ¼ m ¼ m ¸ m K 2 1 3 Рис. 1.11 рядком, если P рефлексивно, транзитивно и анти- симметрично. Таким образом, частичный порядок — это антисимметричный предпорядок. Частичный по- рядок обычно обозначается символом 6, а обратное ему отношение 6 −1 — символом >. Отношение > так- же является частичным порядком и называется двой- ственным порядку 6. Используя отношение 6, определим отношение <, называемое строгим порядком, по следующему правилу: x < y ⇔ x 6 y и x 6= y. Заметим, что отношение строгого порядка не является частичным порядком, так как не выполняется условие рефлексивности (неверно, что x < x). Пример 1.7.2. Частичным порядком является • • • - j j j ¼ ¼ ¼ a b c Рис. 1.12 обычное отношение 6 на множестве N. Действитель- но, это отношение рефлексивно (x 6 x), транзитив- но (x 6 y, y 6 z ⇒ x 6 z) и антисимметрично (x 6 y, y 6 x ⇒ x = y). ¤ Пример 1.7.3. Отношение, изображенное на рис. 1.12, является частичным порядком, а отношение из примера 1.7.1 — нет. ¤ Пример 1.7.4. Отношение включения |