Читать онлайн «Дискретная математика. Учебник и практикум»

Министерство образования и науки Российской Федерации НОВОСИБИРСКИЙ ГОСУДАРСТВЕННЫЙ ТЕХНИЧЕСКИЙ УНИВЕРСИТЕТ С. В. СУДОПЛАТОВ, Е. В. ОВЧИННИКОВА ДИСКРЕТНАЯ МАТЕМАТИКА УЧЕБНИК для дистанционного образования НОВОСИБИРСК 2011  Рецензенты: А. Г. Пинус — д-р физ. -мат. наук, проф. ; В. М. Зыбарев — канд. техн. наук, доц. Сергей Владимирович Судоплатов Елена Викторовна Овчинникова Дискретная математика В книге излагаются основы теории множеств, алгебраических си- стем, теории графов и алгебры логики, которые образуют курс дис- кретной математики. Книга предназначена для студентов технических вузов, изучающих дискретную математику в рамках дистанционного образования. c Судоплатов С. В. , Овчинникова Е. В. , 2006, 2011 ° Оглавление Предисловие 5 Г л а в а 1. Элементы теории множеств 6 § 1. 1. Множества и основные операции над ними . . . . . . . . . . . . . . . . . . . 6 § 1. 2. Отношения. Функции. Взаимно однозначные соответствия . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 11 § 1. 3. Натуральные числа. Принцип математической индукции . . . . . . . . . . . . . . . . . . . . . . . 17 § 1. 4. Мощность множества. Конечные и бесконечные множества . . . . . . . . . . . . . . . . . . . . . . . 19 § 1. 5. Матрица бинарного отношения. Специальные бинарные отношения . . . . . . . . . . . . . . . . . . . . . . . . 24 § 1. 6. Отношения эквивалентности и разбиения. Фактор-множества . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 26 § 1. 7. Отношения порядка . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 28 § 1. 8. Задачи и упражнения . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 32 Г л а в а 2. Алгебраические системы 35 § 2. 1. Определения и примеры . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 35 § 2. 2. Морфизмы . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 37 § 2. 3.