Реферат: Основные положения дискретной математики

6.2 Матрица инцидентности и списки ребер

6.3 Матрица смежности графа

6.4 Операции над членами графов

7 ОСНОВНЫЕ ТРЕБОВАНИЯ К ВЫПОЛНЕНИЮ КОНТРОЛЬНОЙ РАБОТЫ

8. ЭКЗАМЕНАЦИОННЫЕ ВОПРОСЫ

9. ЛИТЕРАТУРА

Приложение I

1. ТЕОРИЯ МНОЖЕСТВ

1.1 Понятие множества и подмножества

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

Множество – совокупность объектов, различаемых нашей интуицией.

Объекты, составляющие множество называются элементами этого множества.

Множества обозначаются большими латинскими буквами, а элементы – маленькими латинскими буквами.

Если элемент а принадлежит множеству А, то будем использовать запись , в противном случае используется запись .

Множество, содержащее конечное число элементов называется конечным. Если множество не содержит ни одного элемента, оно называется пустым. Если множество содержит все элементы, присутствующие в задаче, то оно называется универсальным и обозначается Е.

Множество можно задать различными способами. Самые распространенные это: перечисление элементов: ; указание свойств элементов: , (после двоеточия указаны свойства х).

Множество А называется подмножеством множества В только тогда, когда любой элемент множества А принадлежит множеству В. записывается это так: если .

- знак нестрогого включения (говорят В содержит или покрывает А).

- знак строгого включения.

- не включение.

Очевидно: если и , то эти множества состоят из одних и тех же элементов и А=В.

1.2 Графическая интерпретация множеств и операций над ними

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

Над множествами выполняются три двуместные операции:

· Пересечение;

· Объединение;

· Разность множеств.

Пересечением множеств А и В (мультипликативная операция) называется новое множество С , которое включает в себя элементы принадлежащие и множеству А и множеству В.

АВ