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

(КОНСПЕКТ ЛЕКЦИЙ)

Лекции для студентов Бурятского филиала ФГОУ ВПО СибГУТИ. Раздел 1 Основы теории множеств. Раздел 2 Формулы логики. Раздел 3 Булевы функции. Раздел 4 Предикаты и бинарные отношения. Раздел 5 Отображения. Подстановки. Раздел 6 Метод математической индукции. Раздел 7 Основы теории графов. Раздел 8 Элементы теории алгоритмов

источник http://www.twirpx.com/file/111042/

2009 год

Дискретная математика

ПОЯСНИТЕЛЬНАЯ ЗАПИСКА

Программы учебной дисциплины "Дискретная математика" предназначена для реализации государственных требований к минимуму содержания и уровню подготовки выпускников по специальности 2203 Программное обеспечение вычислительной техники и автоматизированных систем.

Учебная дисциплина "Дискретная математика" является обще профессиональной, формирующей базовый уровень знаний для освоения других обще профессиональных и специальных дисциплин.

Материал данного предмета используется при изучении дисциплин: "Математика и информатика", "Математическая статистика", "Архитектура ЭВМ, систем и сетей", "Основы алгоритмизации и программирование", "Базы данных", "Автоматизированные системы", "Технология разработки программных продуктов".

В структуре можно выделить 3 основных раздела:

• основы теории множеств, формулы логики и булевы функции;

• предикаты, бинарные отношения, отображения, метод математической индукции;

• основы теории графов и теории алгоритмов.

В результате изучения дисциплины студент должен:

Иметь представление:

• о значении и областях применения дисциплины;

знать:

• основы теории множеств;

• аппарат формул логики и теорию булевых функций;

• логику предикатов и бинарных отношений;

• метод математической индукции;

• основы теории графов;

• основа теории автоматов и алгоритмов.

уметь:

• выполнять операции над множествами, применять аппарат теории множеств для решения задач;

• строить таблицы истинности для формул логики и упрощать формулы логики;

• представлять булевы функции в виде формул заданного типа. Определять возможность выражения одних булевых функций через другие;

• выполнять операции над предикатами, записывать области истинности предикатов;

• исследовать бинарные отношения на заданные свойства;

• выполнять операции над отображениями;

• доказывать утверждения с помощью метода мат. индукции;

• находить характеристики графов, выделять структурные особенности графов, исследовать графы на заданные свойства;

• применять аппарат учебной дисциплины "Дискретная математика" для решения прикладных задач.

Программа включает 72 лекционных часов и 20 часов в виде лабораторных работ.

Предмет "Дискретная математика" рассчитан на третий и четвертый семестры, проверкой знаний студентов являются обязательные контрольные работы. Итоговый контроль в форме экзамена.

В целом программа составлена так, чтобы достичь основных трех целей:

1. Сообщить студенту необходимые конкретные сведения из дискретной математики, предусмотренные стандартной программой технических высших учебных заведений. Выполнение практических заданий и разбор доказательств позволят студенту овладеть методами, наиболее употребительными с практической стороны.

2. Познакомить студента с широким кругом понятий, специальных терминов, тем самым, сформировать у студента терминологический запас, необходимый для самостоятельного изучения специальной математической и технико-программистской литературы.

1. Пополнить запас примеров нетривиальных алгоритмов.

Изложение материала ведется в форме беседы. При этом проблемная ситуация создается постановкой проблемных вопросов или показом противоречивости фактов. Студенты в свою очередь принимают активное участие в обосновании гипотезы и ее доказательств.

Организуется самостоятельная работа студентов посредством познавательных проблемных задач и заданий.

Содержание дисциплины "Дискретная математика" введение

Дискретная математика – часть математики, которая зародилась в глубокой древности. В широком смысле этого слова к дискретной математике относятся как классические разделы математики: алгебра, теория чисел, теория множеств, математическая логика и т.д., так и новые разделы, которые возникли в середине нашего столетия в связи с внедрением ЭВМ в практическую жизнь. В узком смысле, а в настоящее время именно в узком смысле слова «дискретная математика» и употребляются, сюда относят только те разделы, которые связаны с анализом сложных управляющих систем.

При исследовании, анализе и решении управленческих проблем, моделировании объектов исследования и анализа широко используются дискретные методы формализованного представления, являющиеся предметом рассмотрения в дискретной математике. К ним относятся методы, основанные на теоретико-множественных представлениях, графы, алгоритмы, математическая логика и др.

Дискретная математика предлагает:

• универсальные средства (языки) формализованного представления;

• способы корректной переработки информации, представленной на этих языках;

• возможности и условия перехода с одного языка описания явлений на другой с сохранением содержательной ценности моделей.

Сегодня дискретная математика является важным звеном математического образования. Умение проводить анализ, композицию и декомпозицию информационных комплексов и информационных процессов – обязательное квалификационное требование к специалистам в области информатики.

Входная контрольная работа

1Вариант

1. Решите уравнение

2. Решите неравенство

3. Найдите производную

4. Решите систему уравнений

5. Упростите

2 Вариант

1. Решите уравнение

2. Решите неравенство

3. Найдите производную

4. Решите систему уравнений

5. Упростите

Раздел 1. Основы теории множеств

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

Множеством называется совокупность каких-либо объектов, обладающим общим для всех характеристическим свойством. Это определение нельзя считать строгим, так как понятие множества является исходным понятием математики и не может быть определено через другие математические объекты. Один из основателей теории множеств Г. Кантор определял множество так: "Множество есть многое, мыслимое как целое".

Множество – это неопределяемое понятие, которое задается перечислением предметов, входящих (составляющих) в него, либо их свойствами.

Всякое множество состоит из элементов. Объекты, сущности или элементы, составляющие мно­жество, обозначаются строчными латинскими буквами: a, b, m, x, y …; множество часто обозначают прописными ла­тинскими буквами А, В, М, Х, У…. Знак  обозначает вхож­дение или принадлежность; х  Е читается: «элемент х принадлежит множеству Е», или короче: «х—элемент множества Е». Следует различать «общий элемент» х множества Е, т. е. произвольный элемент, характеризую­щийся единственным свойством «принадлежать множест­ву», и конкретные элементы а, b, c,..., каждый из ко­торых отличен от остальных. Если х не принадлежит Е, будем писать х  Е, что читается «х не является элемен­том множества Е» или «х не принадлежит множеству Е».

Если каждый элемент множества А является элементом множества В, говорят, что множество А является подмножеством множества В, и записывают А  В или В  А. Отметим, что по определению само множество А является своим подмножеством, т.е. А  А.

Множество называется конечным, если оно одержит конечное число элементов. Все остальные множества называются бесконечными.

Также необходимо выделить пустые множества. Множества, не содержащие элементы, называются пустыми. Принято считать, что пустое множество является подмножеством любого множества,   А, где А – любое множество. Таким образом, всякое множество содержит в качестве своих подмножеств пустое множество и само себя.

Существует два способа задания множества:

1. перечисление элементов (только для конечных множеств):

2. указание свойств:

- Множество М состоит из таких элементов х, обладающих свойством Р.

Пример:

1) - перечисление;

2)

Мощностью множества М называется число элементов в него входящих.

, , где М₂ – множество, Н₂ – мощность множества;