Основные положения дискретной математики (стр. 1 из 11)
Содержание
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 – выражения с множествами.
Доказательство производится в два этапа: 1) «в одну сторону», 2) «в обратную сторону».
1) Сначала предположим, что некий элемент х принадлежит левой части равенства:
эта запись звучит следующим образом:«если
, то 
».2) На втором этапе предполагается, что элемент х принадлежит правой части равенства:
.Пример №1
Доказать тождество:
.Решение:
1)
;2)
.1.5 Отношения на множествах
Отношения бывают одноместными, двуместными (бинарными) и n-местными. Одноместное отношение– это просто подмножество. Мы остановимся на бинарных отношениях.
1. упорядоченная пара (x, y) есть совокупность двух элементов записанных в определенном порядке.
2. Две пары (x, y) и (x1, y1) считаются равными тогда и только тогда x1 = х, y1 = y.
3. Прямым произведением x
y называется совокупность пар (x,y)таких, что 
.Можно привести следующие примеры бинарных отношений:
· Отношение «иметь общий делитель отличный от 1» выполняется для пар (6,9); (4,2); (2,4); (4,4), но не выполняется для пар (7,9); (4,7).
· Отношение «быть делителем», т. е. x делит y выполняется для пар (2,4); (4,4), но не выполняется для пар (4,2); (7,9).
· Отношение
выполняется для пар (7,9); (7,7), но не выполняется для пары (9,7).1.6 Свойства отношений
1. Рефлексивность;
2. Симметричность;
3. Транзитивность.
Отношение обозначается R и записывается так: xRy (x и y находятся в отношении R).