Виталий Сигорский - Математический аппарат инженера

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

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

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

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

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

- 82 -

Таблица 1

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

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. Отношения

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

1. Деревья

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

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

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

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

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

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

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

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

Аппарат математической логики в значительной степени сложился под влиянием прикладных проблем, в рамках которых развились его специфические особенности. Пробным камнем среди технических приложений была задача анализа и синтеза контактных схем. Успехи в этой области послужили стимулом для использования аппарата математической логики и в других областях.

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

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