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

Содержание

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

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

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

1.3 Свойства операций

1.4 Тождества и их доказательство

1.5 Отношения на множествах

1.6 Свойства отношений

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

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

2 МАТЕМАТИЧЕСКАЯ ЛОГИКА. АЛГЕБРА ЛОГИКИ

3. БУЛЕВА АЛГЕБРА

3.1

Совершенные нормальные формы

3.1.1 Совершенная дизъюнктивная нормальная форма

3.1.2 Разложение по переменным

3.1.3 Алгоритм преобразования формулы в СДНФ

3.2 Совершенная конъюнктивная нормальная форма (СКНФ)

3.2.1 Алгоритм преобразования формулы в СКНФ

4 ИСЧИСЛЕНИЕ ВЫСКАЗЫВАНИЙ

4.1 Равносильные формулы и их доказательство

4.2 Равносильные формулы

4.3 Доказательство равносильностей

5. БУЛЕВЫ ФУНКЦИИ

5.1 Полнота системы булевых функций

6. ЛОГИКА ПРЕДИКАТОВ

5.1 Операции над предикатами

5.2 Кванторы

5.3 Формулы

6. ТЕОРИЯ ГРАФОВ

6.1 Понятие смежности

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

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

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

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

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

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

Приложение I

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

АВ

Пример:

Объединением множеств А и В (аддитивная операция) называется новое множество С, состоящее из элементов множества А и из элементов множества В.

АВ

Пример:

Разностью множеств А и В называется новое множество С, состоящее из элементов, принадлежащих множеству А и не принадлежащих множеству В.

А\ В из А вычесть В

Пример:

.

Кроме рассмотренных двухместных операций существует одна одноместная операция – дополнение. Дополнением множества М является множество (не М) = .

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

1.3 Свойства операций

1. Ассоциативность;

2. Коммутативность;

3. Дистрибутивность.

Операция называется ассоциативной, если выполняется равенство:

.

Выполнение этого условия (свойства ассоциативности) означает, что скобки в выражении можно не расставлять. Сложение и умножение чисел - ассоциативные операции, что и позволяет не ставить скобки (пример: a+b+c; abc) пример неассоциативной операции: возведение в степень (ab)c здесь скобки необходимы.

Операция называется коммутативной, если выполняется условие: . Сложение и умножение являются коммутативными (от перемены мест слагаемых сумма не меняется). Вычисление и деление – некоммутативные, некоммутативной так же является операция умножения матриц.

Операция называется дистрибутивной, если выполняется условие: .

1.4 Тождества и их доказательство

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

Доказать, что M=N, где M и N – выражения с множествами.

 Скачать реферат