МИНИСТЕРСТВО ОБРАЗОВАНИЯ РОССИЙСКОЙ ФЕДЕРАЦИИ МГУПИ

УТВЕРЖДАЮ

Проректор по УР

____________ Соколов В.В.

«___» ___________ 2002 г.

МЕТОДИЧЕСКИЕ УКАЗАНИЯ

К выполнению контрольных заданий

и лабораторных работ по дисциплине

«Дискретная математика

Рекомендуется для направления подготовки

дипломированного специалиста

654600 – «Информатика и вычислительная техника»

специальности – 22.02.00.

Автоматизированные системы обработки

информации и управления.

Москва 2002

АННОТАЦИЯ

Методические указания соответствуют программе курса “Дискретная математика” для студентов специальности 22.02.03. Рассматриваются следующие понятия: множества, отношения, функции, графы, булевы (переключательные) функции. Эти понятия иллюстрируются многочисленными примерами. Целью методических указаний является помощь студентам при выпол­нении лабораторных и контрольных работ.

Авторы: Казаков С.А., Правоторова Н.А.

Научный редактор: проф. Петров О.М.

Рецензент:____________________________________ О.М. Петров

Рассмотрено и одобрено на заседании кафедры ИТ-7

"__"____________2002 г. Зав. кафедрой __________О.М. Петров

Ответственный от кафедры за выпуск учебно-методических материалов

доц. Правоторова Н.А.

ТЕМА 1. МНОЖЕСТВА 5

1.1.Основные понятия 5

1.2. Операции над множествами 6

1.3. Геометрическое моделирование множеств. Диаграммы Венна 7

1.4. Алгебра множеств. Основные тождества алгебры множеств 8

Основные тождества алгебры множеств 8

1.5. Эквивалентность множеств 10

1.6. Счетные множества 13

1.7. Множества мощности континуума 14

ТЕМА 2. ОТНОШЕНИЯ. ФУНКЦИИ 15

2.1. Отношения. Основные понятия и определения 15

2.2. Операции над отношениями 17

2.3. Свойства отношений 18

2.4. Функции. Основные понятия и определения 20

Тема 3. ГРАФЫ 23

3.1. Основные характеристики графов 23

3.2. Матричные способы задания графов 25

3.3. Изоморфизм графов 26

3.4. Маршруты, циклы в неориентированном графе 27

3.5. Пути, контуры в ориентированном графе 27

3.6. Связность графа 28

3.7. Экстремальные пути в нагруженных ориентированных графах 29

3.8 Алгоритм Форда – Беллмана нахождения минимального пути 30

3.9. Алгоритм нахождения максимального пути 33

3.10. Деревья.. Основные определения 36

3.11. Минимальные остовные деревья нагруженных графов 36

ТЕМА 4. БУЛЕВЫ ФУНКЦИИ 39

4.1. Определение булевой функции 39

4.2. Формулы логики булевых функций 40

4.3. Равносильные преобразования формул 41

Основные равносильности булевых формул. 42

4.4. Двойственность. Принцип двойственности. 43

4.5. Булева алгебра (алгебра логики). Полные системы булевых функций 43

4.6. Нормальные формы 44

4.7. Разложение булевой функции по переменным 47

4.8. Минимизация формул булевых функций в классе дизъюнктивных 49

нормальных форм 49

4.9. Применение алгебры булевых функций к релейно-контактным схемам 55

Ответы на контрольные вопросы 57

Тема 1 57

Тема 2. 57

Тема 3. 57

Тема 4. 57

Указания к выполнению лабораторных работ 58

Лабораторная работа №1. Основные понятия. Ориентированные графы 58

Лабораторная работа №2. Основные понятия. Неориентированные графы 58

Лабораторная работа №3. Экстремальные пути в графах 58

Контрольные задания по курсу "Дискретная математика". 58

1. Раздел «Множества» 58

2. Раздел «Отношения. Функции» 64

3. Раздел «Графы» 69

4. Раздел «Булевы функции» 73

Список рекомендованной литературы 75

СОДЕРЖАНИЕ

Введение

Тема 1. Множества

1.1. Основные понятия

1.2. Операции над множествами

1.3. Геометрическое моделирование множеств. Диаграммы Эйлера – Венна.

1.4. Алгебра множеств. Основные тождества алгебры множеств

1.5. Эквивалентность множеств

1.6. Счетные множества

1.7. Множества мощности континуума

Контрольные вопросы к теме 1

Тема 2. Отношения. Функции.

2.1. Отношения. Основные понятия и определения

2.2. Операции над отношениями

2.3. Свойства отношений

2.4. Функции. Основные понятия и определения

Контрольные вопросы к теме 2

Тема 3. Графы.

3.1. Основные характеристики графов

3.2. Матричные способы задания графов

3.3. Изоморфизм графов

3.4. Маршруты, циклы в неориентированном графе

3.5. Пути, контуры в ориентированном графе

3.6. Связность графа

3.7. Экстремальные пути в нагруженных ориентированных графах

3.8. Алгоритм Форда – Беллмана нахождения минимального пути

3.9. Алгоритм нахождения максимального пути

3.10. Деревья. Основные определения

3.11. Минимальные остовные деревья нагруженных графов

Контрольные вопросы к теме 3

Тема 4. Булевы функции

4.1. Определение булевой функции

4.2. Формулы логики булевых функций

4.3. Равносильные преобразования формул

4.4. Двойственность. Принцип двойственности.

4.5. Булева алгебра (алгебра логики). Полные системы булевых функций

4.6. Нормальные формы

4.7. Разложение булевой функции по переменным

4.8. Минимизация формул булевых функций в классе дизъюнктивных

нормальных форм

4.9. Применение алгебры булевых функций к релейно-контактным схемам

Контрольные вопросы к теме 4

Ответы на контрольные вопросы

Указания к выполнению лабораторных работ

Вопросы к экзамену по дисциплине «Дискретная математика»

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

Краткие сведения о математиках

ТЕМА 1. МНОЖЕСТВА

1.1.Основные понятия

Определение 1.1. Множеством называется совокупность каких-либо объектов, обладающим общим для всех характеристическим свойством. Это определение нельзя считать строгим, так как понятие множества является исходным понятием математики и не может быть определено через другие математические объекты. Один из основателей теории множеств Г. Кантор определял множество так: "Множество есть многое, мыслимое как целое".

Пример 1.1.

Следующие совокупности объектов являются множествами: множество деревьев в лесу, множество целых чисел, множество корней уравнения e^xsinx = 0.5.

Всякое множество состоит из элементов. Множества обозначают большими буквами, например А. В, С, а элементы – маленькими буквами, например, а, b, c.

Множество и его элементы обозначаются следующим образом:

А = {a₁, a₂, a₃} – множество, состоящее из трех элементов;

А = {a₁, a₂, …} – множество, состоящее из бесконечного числа элементов.

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

Пример 1.2.

Множество А = {1, 2} состоит из двух элементов 1, 2; но множество {А} состоит из одного элемента А.

Если элемент a принадлежит множеству А, это записывается следующим образом:

a  А. Если элемент a не принадлежит множеству А, то записывают так: a  А.

Пример 1.3.

Пусть А₁ – множество простых чисел, А₂ – множество целых чисел, a = 4. Тогда

a  А₂, a  А₁.

Если все элементы множества А являются элементами множества В и наоборот, т. е. множества А и В совпадают, то говорят, что А = В.

Если каждый элемент множества А является элементом множества В, говорят, что множество А является подмножеством множества В, и записывают А  В или В  А. Отметим, что по определению само множество А является своим подмножеством, т.е. А  А.

Если А  В и В  А, то по ранее введенному определению А = В.

Если А  В и А  В, то А есть собственное подмножество В, А  В. Если А не является собственным подмножеством В, то записывают А  В.

Пример 1.4.

Пусть А – множество четных чисел, В – множество целых чисел, С – множество нечетных чисел. Тогда

А  В, С  В, А  С, В  А.

Не надо смешивать отношение принадлежности () и отношение включения ().

Пример 1.5.

Пусть А = {2} – множество, состоящее из одного элемента, В = {{2}, {4}} – множество, состоящее из двух элементов, каждое из которых является одноэлементным множеством. Тогда имеют место следующие соотношения:

2  {2};

{2}  {{2}, {4}};

2  {{2}, {4}}.

Множество, не содержащее ни одного элемента, называется пустым множеством и обозначается . Принято считать, что пустое множество является подмножеством любого множества,   А, где А – любое множество. Таким образом, всякое множество содержит в качестве своих подмножеств пустое множество и само себя.

Пример 1.6.

Множество корней уравнения sinx = 2 является пустым.

Множество всех подмножеств данного множества А называется множеством-степенью и обозначается P(A). Множество P(A) состоит из 2ⁿ элементов (доказать самостоятельно).

Пример 1.7.

Пусть множество А = {1, 2} состоит из двух элементов 1, 2. Тогда множество P(A) включает в себя пустое множество , два одноэлементных множества {1} и {2} и само множество А = {1, 2}, т. е.

P(A) = {, {1}, {2}, {1, 2}}.

Мы видим, что множество P(A) состоит из четырех элементов (4 = 2²).

Существуют следующие способы задания множеств.

1. Перечислением элементов множества. Например:

A = {1, 3, 5, 7, 9} – конечное множество;

B = {1, 2, …, n, …} – бесконечное множество.

2. Указанием свойств элементов множества. Для этого способа пользуются следующим форматом записи: A = {aуказание свойства элементов}. Здесь a является элементом множества A, a  А. Например:

A = {a a – простое число} – множество простых чисел;

B = {b b² – 1 = 0, b – действительное число} – множество, состоящее из двух элементов, B = {– 1, 1};

Z = {x  = 1}– множество, состоящее из одного числа, x = 0.

1.2. Операции над множествами

Рассмотрим основные операции над множествами.

Объединением множеств А и В называется множество АВ, все элементы которого являются элементами хотя бы одного из множеств А или В:

АВ = {x  x А или xВ}.

Из определения следует, что А  АВ и В  АВ.

Аналогично определяется объединение нескольких множеств

Пример 1.8.

а) Пусть А = {4, 5, 6}, В = {2, 4, 6}.

Тогда АВ = {2, 4, 5, 6}.

б) Пусть А – множество чисел, которые делятся на 2, а В – множество чисел, которые делятся на 3:

А = {2, 4, 6, …}, В = {3, 6, 9, …}.

Тогда АВ множество чисел, которые делятся на 2 или на 3:

АВ = {2, 3, 4, 6, 8, 9, 10, …}.

Пересечением множеств А и В называется множество АВ, все элементы которого являются элементами обоих множеств А и В:

АВ = {x  x А и xВ}.

Из определения следует, что АВ  А, АВ  В и АВ  АВ.

Аналогично определяется пересечение нескольких множеств.

Пример 1.9.

Рассмотрим данные из примера 1.8.

а) Пусть А = {4, 5, 6}, В = {2, 4, 6}.

Тогда АВ = {4, 6}.

б) Пусть А – множество чисел, которые делятся на 2, а В – множество чисел, которые делятся на 3:

А = {2, 4, 6, …}, В = {3, 6, 9, …}.

Тогда АВ множество чисел, которые делятся и на 2 и на 3:

АВ = {6, 12, 18, …}.

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

Пример 1.10.

Пусть А = {1, 2}, В = {2, 3}, C = {3, 4}.