1. Алгебра множеств

1. Свойства операций над множествами. Операции над множествами, сформулированные в (1.2.7), как и операции над числами, обладают некоторыми свойствами (табл. 1). Эти свойства выражаются совокупностью тождеств, справедливых независимо от конкретного содержания входящих в них множеств, являющихся подмножествами некоторого универсума U.

Тождества (1а)-(3а) выражают соответственно коммутативный, ассоциативный и дистрибутивный законы для объединения, а тождества (1б)-(3б) — те же законы для пересечения. Соотношения (4а)-(7а) определяют свойства пустого множества ∅ и универсума U относительно объединения, а соотношения (4б) — (7б) — относительно пересечения.

Выражения (8а) и (8б), называемые законами идемпотентности, позволяют записывать формулы с множества без коэффициентов и показателей степени. Зависимости (9а) и (9б) представляют законы поглощения, а (10а) и (10б) — теоремы де Моргана.

- 82 -

Таблица 1

Основные свойства операций над множествами

1 а) A ∪ B = B ∪ A

1 б) A ∩ B = B ∩ A

2 а) A ∪ (B∪ C)=(A∪ B)∪ C

2 б) A ∩ (B∩ C)=(A∩ B)∩ C

3 а) A∪ (B∩ C)=(A∪ B) ∩ (A∪ C)

3 б) A∩ (B∪ C)=(A∩ B) ∪ (A∩ C)

4 а) A ∪ ∅ = A

4б) A ∩ U = A

5 а) A ∪ A̅ = U

5 б) A ∩ A̅ = ∅

6а) A ∪ U = U

6 б) A ∩ ∅ = ∅

7 а) ∅̅ = U

7 б) U̅ = ∅

8а) A ∪ A = A

8 б) A ∩ A = A

9 а) A ∪ (A ∩ B) = A

9 б) A ∩ (A ∪ B) = A

10 а)

10 б)

11) если A ∪ B =U и A ∩ B = ∅, то B = A̅

12) A̅ = U A

13) A̿ = A

14) A B = A ∩ B̅

15) A + B = (A ∩ B̅) ∪ (A̅ ∩ B)

16) A + B = B + A

17) (A + B) + C = A + (B + C)

18) A + ∅ = ∅ + A = A

19) A ⊂ B, если и только если A ∩ B = A или A ∪ B = B или A ∩ B̅ = ∅

20) A = B, если и только если (A ∩ B̅ ) ∪ (A̅ ∩ B ) = ∅

Соотношения (11)-(20) отражают свойства дополнения, разности, дизъюнктивной суммы, включения равенства.

2. Принцип двойственности. Первые десять свойств в табл. 1 представлены парами двойственных (дуальных) соотношений, одно из которых получается заменой в другом символов: ∪ на ∩ и ∩ на ∪, а также ∅ на U и U на ∅. Соответствующие пары символов ∪, ∩ и ∅, U называются двойственными (дуальными) символами.

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

Принцип дуальности можно распространить на разность и дизьюктивную сумму, если использовать тождества (14) и (15). Аналогично

- 87 -

в соответствии ...........

- !!!!!!!!!!!!!!!!!!!!! -

- Продолжение следует... -

- Содержание продолжения -

...

2. Отношения 97

3. Отображения и функции 106

4. Отношение эквивалентности 115

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

6. Отношение толерантности 129

7. Законы композиции 137

8. Примеры алгебраических систем 145

9. Пространства 157

10. Комбинаторика 169

Список литературы 182

Глава 3. Матрицы 183

1. Действия над матрицами 184

2. Определители 199

3. Обращение матриц 216

4. Линейные уравнения 229

5. Дифференциальные уравнения 248

6. Функции от матриц 276

7. Матричные преобразования 298

8. Пространство переменных состояния 322

Список литературы 342

Глава 4. Графы 344

1. Деревья 345

2. Анатомия графов 362

3. Полюсные графы 380

4. Многополюсные компоненты 397

5. Системы координат 413

6. Неоднородный координатный базис 444

7. Сокращенный координатный базис 475

Список литературы 501