МГАПИ

МОСКОВСКАЯ ГОСУДАРСТВЕННАЯ АКАДЕМИЯ ПРИБОРОСТРОЕНИЯ И ИНФОРМАТИКИ Кафедра «высшей математики» Галенко А.Н. Кокшаров О.М. Шоркин В.С. Руководство к решению задач по дискретной математике Учебное пособие Москва, 2006

УКД 51.658.01

Руководство к решению задач по дискретной математике. Учебное пособие.

/А.Н. Галенко, О.М. Кокшаров, В.С. Шоркин – М.:МГАПИ, 2006. – 55с.:ил.

Настоящее пособие предназначено для подготовки студентов различных форм обучения по специальностям: 230101 и 010502.

Пособие предназначено для студентов 3 курса изучающих курс «Дискретная математика». Содержит 15 вариантов двух аудиторных контрольных работ, а также билеты для письменного зачета или экзамена.

Работа рассмотрена и одобрена на заседании кафедры ИТ-1 «Высшей математики».

© Галенко А.Н., Кокшаров О.М., Шоркин В.С., 2006

© МГАПИ, 2006

Содержание:

МГАПИ 1

МОСКОВСКАЯ ГОСУДАРСТВЕННАЯ АКАДЕМИЯ 1

УКД 51.658.01 2

Содержание: 3

Глава 1 Множества 5

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

1.2 Способы задания множеств 6

1. Перечислением, списком своих элементов. 6

2.Порождающей процедурой. 6

3.Описанием характеристических свойств, которыми обладают элементы. 6

1.3 Операции над множествами 7

1.4 Графическое представление множеств 8

Упражнения 10

Глава 2 Векторы 12

2.1 Основные понятия 12

2.2 Операции над векторами 12

Упражнения 14

Глава 3 Отношения 15

3.1 Бинарные отношения. Основные понятия 15

Способы задания бинарных отношений: 15

3.2 Свойства бинарных отношений. 16

3.3. Отношения эквивалентности и порядка. 18

3.4 Правила построения матриц отношений , R-1, R(2), R0, R*. 18

Упражнения 21

Глава 4 Соответствия 24

4.1 Свойства соответствий 24

Упражнения 25

Глава 5 Функции и отображения 27

Упражнения 28

Глава 6 Графы 30

Теория графов. Основные понятия 30

Способы задания графов 30

Упражнения 36

Глава 7 Логические представления. Логика высказываний 37

Основные логические связки логики высказываний: 37

Логические функции 39

Метод установления эквивалентности двух формул: 40

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

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

Эквивалентные преобразования. 42

Основные эквивалентные соотношения (законы) в булевой алгебре. 43

Упражнения 44

Приложение 1 47

Контрольная работа №1 47

Разбор решений контрольной работы №1 48

Приложение 2 52

Контрольная работа №2 52

Разбор решений контрольной работы №2 54

Предметом рассмотрения данного методического пособия являются теоретико-множественные, логические и графические представления, т.к. знакомство с ними и их освоение – есть основная задача курса «Дискретная математика».

В пособии использованы обозначения:

 – тогда и только тогда

 – любой, для любого

 – и

 – или

 – следует

Глава 1 Множества

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

Множество – совокупность объектов, рассматриваемых как одно целое. Множества обозначаются заглавными буквами А, В, С… или заглавными буквами с индексами А₁, А₂, А₃….А_n.

Отдельные объекты, из которых состоит множество, - называются элементами (обозначают: a, b, c… или a₁, a₂…).

Принадлежность элемента а множеству А обозначается аА (а принадлежит А), непринадлежность – а  А. Множества делятся на конечные и бесконечные.

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

Множество не содержащее ни одного элемента, называется пустым (обозначается ).

Два множества А и В называются равными (А=В), если они состоят из одних и тех же элементов ( каждый элемент множества А является элементом множества В и наоборот).

Множество А называется подмножеством множества В (А В), если всякий элемент из А является элементом В.

(А В х A x B)

Пример:

N – множество натуральных чисел.

R – множество действительных чисел.

N R.

Число элементов в конечном множестве А называется мощностью множества (обозначается |А| ). Мощность пустого множества равна 0.

Пример:

Мощность множества В={4, 6, 7, 9} равна 4.

Пример:

Пусть U={1, 2, 3}. Определить В(U) – множество всех подмножеств, состоящих из элементов множества U. Какова мощность В(U).

Решение:

В(U) = {(), (1), (2), (3), (1, 2), (1, 3), (2, 3), (1, 2, 3)}.

|В(U)| = 8.