Программа по формированию навыков безопасного поведения на дорогах и улицах «Добрая дорога детства» 2
Скачать 1.97 Mb.
|
| ДИСКРЕТНАЯ МАТЕМАТИКА (КОНСПЕКТ ЛЕКЦИЙ) Лекции для студентов Бурятского филиала ФГОУ ВПО СибГУТИ. Раздел 1 Основы теории множеств. Раздел 2 Формулы логики. Раздел 3 Булевы функции. Раздел 4 Предикаты и бинарные отношения. Раздел 5 Отображения. Подстановки. Раздел 6 Метод математической индукции. Раздел 7 Основы теории графов. Раздел 8 Элементы теории алгоритмов источник http://www.twirpx.com/file/111042/ 2009 год Дискретная математика ПОЯСНИТЕЛЬНАЯ ЗАПИСКА Программы учебной дисциплины "Дискретная математика" предназначена для реализации государственных требований к минимуму содержания и уровню подготовки выпускников по специальности 2203 Программное обеспечение вычислительной техники и автоматизированных систем. Учебная дисциплина "Дискретная математика" является обще профессиональной, формирующей базовый уровень знаний для освоения других обще профессиональных и специальных дисциплин. Материал данного предмета используется при изучении дисциплин: "Математика и информатика", "Математическая статистика", "Архитектура ЭВМ, систем и сетей", "Основы алгоритмизации и программирование", "Базы данных", "Автоматизированные системы", "Технология разработки программных продуктов". В структуре можно выделить 3 основных раздела:
В результате изучения дисциплины студент должен: Иметь представление:
знать:
уметь:
Программа включает 72 лекционных часов и 20 часов в виде лабораторных работ. Предмет "Дискретная математика" рассчитан на третий и четвертый семестры, проверкой знаний студентов являются обязательные контрольные работы. Итоговый контроль в форме экзамена. В целом программа составлена так, чтобы достичь основных трех целей:
Изложение материала ведется в форме беседы. При этом проблемная ситуация создается постановкой проблемных вопросов или показом противоречивости фактов. Студенты в свою очередь принимают активное участие в обосновании гипотезы и ее доказательств. Организуется самостоятельная работа студентов посредством познавательных проблемных задач и заданий. Содержание дисциплины "Дискретная математика" ВВЕДЕНИЕ Дискретная математика – часть математики, которая зародилась в глубокой древности. В широком смысле этого слова к дискретной математике относятся как классические разделы математики: алгебра, теория чисел, теория множеств, математическая логика и т.д., так и новые разделы, которые возникли в середине нашего столетия в связи с внедрением ЭВМ в практическую жизнь. В узком смысле, а в настоящее время именно в узком смысле слова «дискретная математика» и употребляются, сюда относят только те разделы, которые связаны с анализом сложных управляющих систем. При исследовании, анализе и решении управленческих проблем, моделировании объектов исследования и анализа широко используются дискретные методы формализованного представления, являющиеся предметом рассмотрения в дискретной математике. К ним относятся методы, основанные на теоретико-множественных представлениях, графы, алгоритмы, математическая логика и др. Дискретная математика предлагает:
Сегодня дискретная математика является важным звеном математического образования. Умение проводить анализ, композицию и декомпозицию информационных комплексов и информационных процессов – обязательное квалификационное требование к специалистам в области информатики. Входная контрольная работа 1Вариант 1. Решите уравнение  2. Решите неравенство  3. Найдите производную  4. Решите систему уравнений  5. Упростите  2 Вариант 1. Решите уравнение  2. Решите неравенство  3. Найдите производную  4. Решите систему уравнений  5. Упростите  Раздел 1. ОСНОВЫ ТЕОРИИ МНОЖЕСТВ Тема 1.1 Основные понятия теории множеств. Множеством называется совокупность каких-либо объектов, обладающим общим для всех характеристическим свойством. Это определение нельзя считать строгим, так как понятие множества является исходным понятием математики и не может быть определено через другие математические объекты. Один из основателей теории множеств Г. Кантор определял множество так: "Множество есть многое, мыслимое как целое". Множество – это неопределяемое понятие, которое задается перечислением предметов, входящих (составляющих) в него, либо их свойствами. Всякое множество состоит из элементов. Объекты, сущности или элементы, составляющие множество, обозначаются строчными латинскими буквами: a, b, m, x, y …; множество часто обозначают прописными латинскими буквами А, В, М, Х, У…. Знак обозначает вхождение или принадлежность; х Е читается: «элемент х принадлежит множеству Е», или короче: «х—элемент множества Е». Следует различать «общий элемент» х множества Е, т. е. произвольный элемент, характеризующийся единственным свойством «принадлежать множеству», и конкретные элементы а, b, c,..., каждый из которых отличен от остальных. Если х не принадлежит Е, будем писать х Е, что читается «х не является элементом множества Е» или «х не принадлежит множеству Е». Если каждый элемент множества А является элементом множества В, говорят, что множество А является подмножеством множества В, и записывают А В или В А. Отметим, что по определению само множество А является своим подмножеством, т.е. А А. Множество называется конечным, если оно одержит конечное число элементов. Все остальные множества называются бесконечными. Также необходимо выделить пустые множества. Множества, не содержащие элементы, называются пустыми. Принято считать, что пустое множество является подмножеством любого множества, А, где А – любое множество. Таким образом, всякое множество содержит в качестве своих подмножеств пустое множество и само себя. Существует два способа задания множества:
- Множество М состоит из таких элементов х, обладающих свойством Р.Пример: 1) - перечисление;2) Мощностью множества М называется число элементов в него входящих. , , где М2 – множество, Н2 – мощность множества;Тема 1.2 Операции над множествами. Рассмотрим операции над множествами:
Множество А включается в множество В или множество А является подмножеством множества В (А В), если любой элемент множества А содержится в множестве В.Используется теоретико-множественные диаграммы или диаграммы Венна, при решении операции включения: Множество А строго включается в множество В, если во-первых А является подмножеством В и существует элемент bВ, такой что b А., где k – количество элементов, т.е. =k, тогда количество подмножеств множества А определяется как 2k.Свойства подмножеств: А) Пустое множество является подмножеством любого множества: Б) Всякое множество является своим собственным подмножеством:
Объединением двух множеств А и В называется новое множество , которое содержит элементы, каждый из которых принадлежит хотя бы одному из множеств А или В
Пересечением множеств А и В называется новое множество , которое состоит из элементов, каждый из которых принадлежит и множеству А и множеству В
Разностью множеств А и В называется новое множество  , которое содержит элементы, каждый из которых принадлежит множеству А и не принадлежит множеству В.
Прямым произведением двух множеств А и В, называется новое множество  , такое которое состоит из упорядоченных двоек чисел (а, b), причем таких, что первый элемент из этой двойки , второе .Два множества А и В, называется равными, если множество А является подмножеством множества В, а В является подмножеством множества А. .Самостоятельная работа № 1 Тема 1.3 Свойства операций. Операции над множествами обладают некоторыми свойствами. Эти свойства выражаются совокупностью тождеств, справедливых независимо от конкретного содержания входящих в них множеств. 1. транзитивность операции включения: т.е. если множество А является подмножеством В, а множество В является подмножеством множества С, то множество А является подмножеством множества С. 2. дистрибутивность операции пересечения относительно объединения: т.е. если множество А объединить с множеством В, а потом пересечь с множеством С, то это тоже самое, что А пересечь с С и В пересечь с С, а потом объединить их. 3. дистрибутивность операции объединения относительно пересечения: т.е. если множество А пересечь с множеством В, а потом объединить с множеством С, то это тоже самое, что А объединить с С и В объединить с С, а потом пересечь их. 4. первый закон двойственности: т.е. дополнение множества , есть не что иное, как объединение дополнения множества А и дополнения множества В.5. второй закон двойственности: т.е. дополнение множества , есть пересечение их дополнений.6. ассоциативность операции объединения: 7. ассоциативность операции пересечения: 8. свойства операции объединения:
,
9. свойства операции пересечения:
,
10. свойства операции разности:
11. дополнение к дополнению любого множества есть всегда само множество, т.е. 12. 13. Тест 1. Будет ли пустое множество V каким-либо подмножеством некоторого множества? а) будет собственным подмножеством; б) будет несобственным подмножеством; в) не будет никаким подмножеством. 2. Что есть множество А\В, если А - множество всех книг в библиотеке МЭСИ по различным отделам науки и искусства, а В – множество всех книг во всех библиотеках России? а) множество математических книг в России без математических книг в МЭСИ; б) множество книг по искусству в библиотеке МЭСИ; в) множество книг в библиотеке МЭСИ по искусству и науке, кроме математических. 3. Совпадают ли дистрибутивные законы Булевой алгебры и алгебры действительных чисел; а) оба совпадают; б) оба не совпадают; в) один совпадает, другой - нет. 4. Есть ли законы для дополнений в алгебре действительных чисел? а) да; б) нет; в) некоторые есть, некоторых нет. 5. Справедливы ли законы идемпотентности Булевой алгебры в алгебре действительных чисел? а) справедливы; б) несправедливы; в) один справедлив, другой нет. 6. Обладают ли свойством двойственности формулы поглощения? а) да; б) нет; в) одна обладает, другая нет. 7. Можно ли поставить в соответствие единицу или ноль соответственно универсальному и пустому множеству, исходя из свойств операций? а) можно; б) единицу - можно, ноль - нет; в) ноль - можно, единицу - нет. 8. Обладают ли формулы склеивания свойством двойственности а) нет; б) да; в) одна обладает, другая нет. 9. Будет ли каждое из множеств А, В, С, D подмножеством другого, если А - множество действительных чисел, В - множество рациональных чисел, С - множество целых чисел, D - множество натуральных чисел. а) да; б) нет; в) лишь некоторые из множеств являются подмножествами перечисленных множеств Контрольная работа 1 Вариант 1. А={х | х N : х-однозначное, составное число}В={7,8,13} Определить количество подмножеств у множества А. Выписать все подмножества у множества В. 2. Х={ однозначные натуральные числа, кратные 3} Y={1,3,5,6,8} Найти: Х  Y, X Y, X\Y, Y\X3. А=(-1,8]; В=[0,12] Найти: А\В, В\А, В\(А В), A\(AB)
2 Вариант 1. А={х | x N : х-однозначное простое число}В={0,3,21} Определить количество подмножеств у множества А. Выписать все подмножества у множества В. 2. Х={ Однозначное натуральное число : 4} Y={2,3,4,5,6,8,11} Найти: Х Y, XY, X\Y, Y\X3. А=[2,14]; В=(-3,10] Найти: А\В, В\А, В\(А В), A\(AВ)
Раздел 2. ФОРМУЛЫ ЛОГИКИ. Тема 2.1 Основные логические операции. Высказывание – это предложение которое может быть либо истинным, либо ложным. В математической логике не рассматривается сам смысл высказываний, определяется только его истинность или ложность, что принято обозначать соответственно И или Л. Понятно, что истинные и ложные высказывания образуют соответствующие множества. С помощью простых высказываний можно составлять более сложные, соединяя простые высказывания союзами “и”, “или”. Введем множество  Над высказываниями можно выполнять следующие операции: 1. ┐ (не) – одноместная операция отрицания; 2. (или) – двуместная операция дизъюнкция;3. (и) – двуместная операция конъюнкция;4. (если, то) – двуместная операция импликация;Каждая операция характеризуется своей таблицей истинности: Вводятся следующие логические операции (связки) над высказываниями
Обозначается Р или . Соответствие между высказываниями определяется таблицами истинности. В нашем случае эта таблица имеет вид: P РИЛЛИ2) Конъюнкция. Конъюнкцией (логическим “и”) двух высказываний P и Q называется высказывание, истинное тогда и только тогда, когда истинны оба высказывания. Обозначается P&Q или Р Q.PQP QИИИИЛЛЛИЛЛЛЛ3) Дизъюнкция. Дизъюнкцией (логическим “или”) двух высказываний P и Q называется высказывание, ложное тогда и только тогда, когда оба высказывания ложны. Обозначается P Q.PQP QИИИИЛИЛИИЛЛЛ4) Импликация. Импликацией (логическим следованием) двух высказываний P и Q называется высказывание, истинное тогда и только тогда, когда высказывание Р истинно, а Q – ложно. Обозначается PQ (или Р Q). Высказывание Р называется посылкой импликации, а высказывание Q – следствием.PQP QИИИИЛЛЛИИЛЛИ5) Эквиваленция. Эквиваленцией (логической равносильностью) двух высказываний P и Q называется высказывание, истинное тогда и только тогда, когда истинности высказываний совпадают. Обозначается РQ или РQ. PQPQИИИИЛЛЛИЛЛЛИ С помощью этих основных таблиц истинности можно составлять таблицы истинности сложных формул. Построим истинностную таблицу сложного высказывания: S=(A→B)∧( ┐C)∨(A↔C) Очевидно, истинностная таблица будет содержать 23 = 8 строк. Скобки применяются, если нарушаются естественный порядок операций: отрицание, конъюнкция, дизъюнкция, импликация, двойная импликация. Скобки (А→В) указывают на то, что сначала нужно выполнить импликацию, затем найти (А→В)∧С. Скобки в выражении (A↔C) можно опустить. Заключительной операцией в построении истинностной таблицы для S будет дизъюнкция двух высказываний: (А→В)∧С и (A↔C). Таблица АВСА→В(А→В)∧С┐СA↔CC (A↔C)1 1 1 1 0 0 0 01 1 0 0 1 1 0 01 0 1 0 1 0 1 01 1 0 0 1 1 1 11 0 0 0 1 0 1 00 1 0 1 0 1 0 10 1 0 1 1 0 1 01 0 1 0 0 1 0 11 0 1 0 1 1 1 1Итак, формула S задает высказывание которое истинно на следующих наборах значений элементарных высказываний: А=1 В=1 С=1 (все три элементарных высказывания истинны) А=1 В=0 С=1 (А, С - истинны, В - ложно ) А=0 В=1 С=1 (А - ложно, В и С - истинны) А=0 В=1 С=0 (В - истинно, А и С - ложны) А=0 В=0 С=1 (С - истинно, А и В - ложно) А=0 В=0 С=0 (все три высказывания ложны). Высказывательной формой называется: 1. любая переменная (она в свою очередь называется элементарной (автомарной) высказывательной формой); 2. если и высказывательные формы, то и их отрицания, , , , , также являются высказывательными формами.Тема 2.2 Формулы логики. Алфавитом называется любой непустой набор символов. Элементы этого набора называются символами алфавита. Словом в алфавите называется произвольная конечная (возможно пустая) последовательность символов из . Фиксируем некоторый конечный или счетный алфавит переменных Формула алгебры логики определяется следующим образом (индуктивное определение):
Подформулой формулы называется любое подслово слова , которое само является формулой.Для сокращения записи формул обычно принимаются следующие соглашения:
Принят следующий порядок выполнения операций:
Формула называется тождественно истинной или тавтологией, если она реализует функцию «тождественная единица», и тождественно ложной, если 0. Являются ли формулы тождественно истинными: Формулы логики, принимающие всегда ложное значение, называются тождественно ложными (или противоречиями). Например, формула - противоречие.Формулы алгебры логики, принимающие значение «ложь» хотя бы на одном наборе значений атомов, входящих в формулу называются опровержимыми. Формулы алгебры логики, принимающие значение «истина» хотя бы на одном наборе значений атомов, входящих в формулу называются выполнимыми. Формулы Р и Q называются равносильными, если их истинностные значения совпадают при любом выборе истинностных значений атомов, входящих в эти формулы. Запись Р Q означает, что формулы Р и Q равносильныСамостоятельная работа №2. Тема 2.3 Дизъюнктивная нормальная форма. Отрицание относящиеся к переменной называется тесным (простым). Отрицание, не являющееся тесным, называется сложным. Высказывательная форма называется приведенной, если она не содержит операции импликации и сложного отрицания. Теорема: Для любой высказывательной формы существуют равносильные приведенные формы. Доказательство:
Символическая степень высказывания – это , причем может быть истиной, либо ложной, причем: Свойства символической степени высказывания: Высказывательная форма, состоящая из переменных или отрицания переменных применением только одной операции дизъюнкции, называется элементарной дизъюнкцией. Высказывательная форма, состоящая из элементарных конъюнкций, применением только одной операции дизъюнкции называется дизъюнктивной нормальной формой (ДНФ). Совершенной дизъюнктивной формой формулы алгебры высказываний (СДНФ) называется ДНФ, в которой: |
(В\С)=(А
)U (
В)
= 
U 
Добавить документ в свой блог или на сайт
