Дискретная математика: Конспект лекций (Описание основных понятий и методов решения задач дискретной математики, относящихся к теории множеств, отношениям на множествах, теории графов и комбинаторике)

Страницы работы

42 страницы (Word-файл)

Содержание работы

Министерство образования Российской Федерации

НОВОСИБИРСКИЙ ГОСУДАРСТВЕННЫЙ ТЕХНИЧЕСКИЙ УНИВЕРСИТЕТ

______________________________________________________________________

С.В. РЕНИН

ДИСКРЕТНАЯ МАТЕМАТИКА

Конспект лекций для студентов II курса

Института социальной реабилитации

Новосибирск

2002


УДК 51 (076.1)

Рецензент ………………………………………………..

Работа выполнена на кафедре
автоматизированных систем управления
для студентов II курса Института социальной реабилитации

Ренин С.В.

Дискретная математика. Конспект лекций. – Новосибирск:
Изд-во НГТУ, 2000.

Конспект лекций содержит описание основных понятий и методов решения задач дискретной математики, относящихся к теории множеств, отношениям на множествах, теории графов и комбинаторике и предназначается студентам Института социальной реабилитации НГТУ , обучающимся по направлению 5528 "Информатика и вычислительная техника", для использования при подготовке к практическим занятиям и при самостоятельной работе над курсом.

УДК 51 (076.1)

© Новосибирский государственный
технический университет, 2000 г.


ОГЛАВЛЕНИЕ

1. МНОЖЕСТВА. ОТНОШЕНИЯ НА МНОЖЕСТВАХ

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

Множество – совокупность объектов любой природы, называемых элементами данного множества.

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

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

Примеры.       1) Множество Х, состоящее из элементов х1, х2, х3, обозначают:

Х = {х1, х2, х3}

              2) Множество простых чисел Х = {x|x - простое число}.

Принадлежность элемента х множеству Х записывается как хÎХ.

Если элемент х не принадлежит Х, то пишут хÏХ.

Множество называется конечным, если оно состоит из конечного числа элемен­тов. Например, множество жителей г. Новосибирска, множество студентов группы ВИ-51.

Множество называется бесконечным, если число его элементов бесконечно. Например, множество натуральных чисел N = {1,2,3,...}.

Бесконечное множество называется счетным, если его элементы можно перечислять. Например, множество натуральных чисел N, множество целых чисел
Z = {...,-3,-2,-1,0,1,2,3,...}.

В противном случае оно называется несчетным. Например, множество точек плоскости, множество вещественных чисел.

Если множество не содержит ни одного элемента, то оно называется пустым и обозначается Æ. Например, пусто множество людей, имеющих рост выше 3 метров. Пусто множество студентов группы ВИ-51, имеющих диплом о высшем образовании.

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

АÌВ. Например, множество студентов группы ВИ-51 есть подмножество множества студентов ИСР и НГТУ.

Если множество А является подмножеством множества В и при этом может совпадать с В, то знак Ì подчеркивают: Í.

Множество называется универсальным, если все другие рассматриваемые в данной задаче множества являются его подмножествами. Обозначается такое множество латинской буквой I. Например, если в задаче рассматриваются множество вещественных чисел R, множество целых чисел Z, множество натуральных чисел N и множество рациональных чисел F, то для всех этих множеств множество R является универсальным, так как ZÌR, NÌR и FÌR. Т.е. в данном случае I=R.

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

1.2.1. Объединение

Обозначение:

Определение. Объединением двух множеств А и В называется множество, состоящее из всех тех и только тех элементов, которые входят во множество А или во множество В или в оба вместе, причем элементы, принадлежащие обоим множествам одновременно, входят в объединение только один раз.

   Если С = А В, то С = {c| cÎА или сÎВ или сÎА и В одно­временно}.

Операции над множествами можно наглядно изобразить с помощью диаграмм Эйлера-Венна. На этих диаграммах универсальное множество изображается в виде прямоугольника, а множества, участвующие в операции - кругами.

Представление объединения на диаграмме Эйлера-Венна (результат объединения закрашен):

Примеры:

1) А = {a, b, c, d}, B = {c, d, e, f}, C=A B={a, b, c, d, e, f}

2) Z+ – множество целых положительных чисел;

  Z- – множество целых отрицательных чисел;

  О = {0};

  C = Z+ Z- O = Z – множество всех целых чисел.

3) А – множество студентов гр. ВИ-51, учащихся на отлично;

  В – множество студентов гр. ВИ-51, учащихся без троек;

  С – множество студентов гр. ВИ-51, имеющих удовлетворительные оценки;

  D – множество студентов гр. ВИ-51, имеющих неудовлетворительные оценки;

  E = A B C D - множество всех студентов группы ВИ-51.

Свойства: 1) коммутативность (переместительный закон)

               А В = В А

     2) ассоциативность (сочетательный закон)

           А В С = (А В) С = А С)

     3) если АÌВ, то А В=В;

Похожие материалы

Информация о работе

Тип:
Конспекты лекций
Размер файла:
452 Kb
Скачали:
0