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

УКД 51.658.01

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

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

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

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

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

Содержание:

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Ú – и

Ù – или

Þ – следует

Глава 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.