Министерство образования российской федерации
МОСКОВСКИЙ ГОСУДАРСТВЕННЫЙ УНИВЕРСИТЕТ ТЕХНОЛОГИЙ И УПРАВЛЕНИЯ
(образован в 1953 году)
Кафедра физики и высшей математики
|
Дистанционное обучение |
Физ.мат.-8.22.2202 зчн.скр. Физ.мат.-8.22.2202 очн.плн. Физ.мат.-8.22.2202 зчн.плн. Физ.мат.-11.22.2713 зчн.скр. Физ.мат.-11.22.2713 очн.плн. |
Физ.мат.-11.22.2713 зчн.плн. Физ.мат.-7.22.2202 зчн.скр. Физ.мат.-7.22.2202 очн.плн. Физ.мат.-7.22.2202 зчн.плн. |
Ю.А. Зуев
А.Р. Садыкова
Математическая логика и теория алгоритмов. Теория множеств. Дискретная математика
Учебное – практическое пособие
для студентов специальностей 2202 и 2713
всех форм обучения
www.msta.ru
Москва – 2004 4092
УДК 519.6
3-93
Зуев Ю.А., Садыкова А.Р. Дискретная математика. Математическая логика и теория алгоритмов. Теория множеств. Учебно – практическое пособие М.,МГуТу, 2004.
В учебно – практическом пособии доктора физико – математических наук, профессора Зуева Ю.А. и старшего преподавателя Садыковой А.Р. в кратком и систематическом виде изложены основные понятия теории множеств, математической логики и теории алгоритмов. Каждую тему заключают контрольные вопросы и тесты, позволяющие контролировать степень усвоения материала. Тесты снабжены ответами. В конце пособия даны более трудные задачи для самостоятельного решения и словарь основных терминов.
Пособие предназначено для студентов специальностей 2202 и 2713 всех форм обучения.
Авторы: Зуев Юрий Анатольевич,
Садыкова Альбина Рифовна
Рецензенты: к.т.н. доцент кафедры Электронных приборов МЭИ
Обидин Г.Н.,
К.Т.Н. доцент кафедры ЭП ЭТФ МЭИ Бодров В.Н.
Редактор: Свешникова Н.И.
Московский Государственный Университет Технологий и Управления 2004.
109004, Москва, Земляной вал, 73.
Содержание.
ВведениеСтр.
Глава I. Множества 4
1.1. Определения и обозначения 4
1.2. Операции над множествами 5
1.3.
Свойства операций
5
1.4. Мощность множества 6
1.5. Прямое произведение множеств 7
Вопросы для самоконтроля по теме. 8
Тест по теме. 8
Глава II. Отношения, функции, алгебраические 9
структуры, морфизмы
2.1. Бинарные отношения 9
2.2.Функции 10
2.3.Алгебраические структуры и морфизмы 11
Вопросы для самоконтроля по теме. 13
Тест по теме. 13
Глава III. Булевы функции 14
3.1. Определение и основные свойства 14
3.2. Дизъюнктивная и конъюнктивная нормальные формы 15 3.3. Упрощение д.н.ф. 16
Вопросы для самоконтроля по теме. 19
Тест по теме. 19
Глава IV. Элементы математической логики 20
4.1. Исчисление высказываний 20
4.2. Логическое следствие 20
4.3. Предикаты и кванторы 22
Вопросы для самоконтроля по теме. 23
Тест по теме. 23
Глава V. Алгоритмы и машина Тьюринга 24
5.1. Понятие алгоритма 24
5.2.Алгоритм Евклида 25
5.3. Машина Тьюринга 27
5.4.Алгоритмически неразрешимые проблемы 29
Вопросы для самоконтроля по теме. 30
Тест по теме. 31
Задачи для самостоятельного решения 31
Итоговый тест 33
Рекомендуемая литература 34
Словарь 34
Ответы к тестам 35
Введение.
Целью курса является получение студентом представления о фундаментальных основах современной математики, базирующейся на теоретико-множественной, логико-алгебраической и алгоритмической концепциях, а также повышение у студента общей математической культуры, необходимой при дальнейшем изучении математики, в частности, дискретной математики и программирования. Для этого в рамках курса предусмотрено:
изучение множеств и операций над ними;
знакомство с канторовой теорией множеств и понятием мощности;
изучение алгебраических операций и морфизмов алгебраических структур;
знакомство с основными понятиями математической логики, приобретение навыков в математических рассуждениях и доказательствах;
развитие на примере машины Тьюринга необходимого будущим программистам алгоритмического мышления, получение представления об алгоритмически неразрешимых проблемах.
Предполагается, что приступая к изучению данного курса, студент уже знаком с такими основными понятиями алгебры как группы, кольца, поля и линейные пространства. Примеры этих алгебраических структур неоднократно встречаются на протяжении курса.