Лекции для студентов Бурятского филиала фгоу впо сибгути. Раздел 1 Основы теории множеств. Раздел 2 Формулы логики. Раздел 3 Булевы - polpoz.ru o_O
Главная
Поиск по ключевым словам:
Похожие работы
Название работы Кол-во страниц Размер
Раздел Предмет и задачи курса Раздел Глоссарий Раздел Лекционный... 17 3789.86kb.
Раздел I. Общепрофессиональные дисциплины Раздел II. Дисциплины специализации... 2 611.3kb.
Налоговая система Кыргызской Республики раздел II 13 3803.25kb.
Учение, раздел анатомии, изучающий строение органов чувств 2 506.03kb.
Методические указания к контрольной работе Раздел I. Общие положения... 2 361.05kb.
1. Основные понятия теории вероятности 1 308.88kb.
Учебного материала лекции курс. «Экономика» Раздел Введение в экономическую... 3 1580.34kb.
Лекция 33. (13. 06. 06) Недельный раздел 1 261.82kb.
1 Экспериментальный раздел 7 1 Литературный обзор 7 1 13.52kb.
Маркетинговый раздел и мощность предприятия 33 3387.65kb.
Наша работа это раздел программы «Школа здоровья» (руководитель зам... 1 112.54kb.
Проект стандарты управления рисками для негосударственных пенсионных... 22 1709.83kb.
1. На доске выписаны n последовательных натуральных чисел 1 46.11kb.

Лекции для студентов Бурятского филиала фгоу впо сибгути. Раздел 1 Основы теории - страница №1/8

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

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

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

2009 год
Дискретная математика

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


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

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

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

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



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

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

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

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

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

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

знать:

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

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

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

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

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

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

уметь:

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

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

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

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

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

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

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

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

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

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

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

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


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

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

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

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

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


Содержание дисциплины

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

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

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


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

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

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

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

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



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



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



5. Упростите




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

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



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



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



5. Упростите




Раздел 1. ОСНОВЫ ТЕОРИИ МНОЖЕСТВ
Тема 1.1 Основные понятия теории множеств.
Множеством называется совокупность каких-либо объектов, обладающим общим для всех характеристическим свойством. Это определение нельзя считать строгим, так как понятие множества является исходным понятием математики и не может быть определено через другие математические объекты. Один из основателей теории множеств Г. Кантор определял множество так: "Множество есть многое, мыслимое как целое".

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

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

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

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

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

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


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



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

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

Пример:


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

2)

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

, , где М2 – множество, Н2 – мощность множества;
Тема 1.2 Операции над множествами.
Рассмотрим операции над множествами:


  1. операция включения ():

Множество А включается в множество В или множество А является подмножеством множества В (А В), если любой элемент множества А содержится в множестве В.

Используется теоретико-множественные диаграммы или диаграммы Венна, при решении операции включения:


Множество А строго включается в множество В, если во-первых А является подмножеством В и существует элемент bВ, такой что bА.




, где k – количество элементов, т.е. =k, тогда количество подмножеств множества А определяется как 2k.

Свойства подмножеств:

А) Пустое множество является подмножеством любого множества:

Б) Всякое множество является своим собственным подмножеством:


  1. операция объединения:

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


  1. операция пересечения:

Пересечением множеств А и В называется новое множество , которое состоит из элементов, каждый из которых принадлежит и множеству А и множеству В



  1. операция разности:

Разностью множеств А и В называется новое множество , которое содержит элементы, каждый из которых принадлежит множеству А и не принадлежит множеству В.



  1. операция прямого произведения:

Прямым произведением двух множеств А и В, называется новое множество , такое которое состоит из упорядоченных двоек чисел (а, 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, XY, X\Y, Y\X

3. А=(-1,8]; В=[0,12]

Найти: А\В, В\А, В\(АВ), A\(AB)



  1. Доказать: А (В\С)=(АВ)\(АС)

  2. Упростить: (АВ)()U (В)

2 Вариант


1. А={х | xN : х-однозначное простое число}
В={0,3,21}

Определить количество подмножеств у множества А. Выписать все подмножества у множества В.

2. Х={ Однозначное натуральное число : 4}
Y={2,3,4,5,6,8,11}

Найти: ХY, XY, X\Y, Y\X

3. А=[2,14]; В=(-3,10]

Найти: А\В, В\А, В\(АВ), A\(AВ)



  1. Доказать: =  U 

  2. Упростить: (АВ)()( В)


Раздел 2. ФОРМУЛЫ ЛОГИКИ.
Тема 2.1 Основные логические операции.
Высказывание – это предложение которое может быть либо истинным, либо ложным.

В математической логике не рассматривается сам смысл высказываний, определяется только его истинность или ложность, что принято обозначать соответственно И или Л.

Понятно, что истинные и ложные высказывания образуют соответствующие множества. С помощью простых высказываний можно составлять более сложные, соединяя простые высказывания союзами “и”, “или”.

Введем множество

Над высказываниями можно выполнять следующие операции:

1. (не) – одноместная операция отрицания;

2. (или) – двуместная операция дизъюнкция;

3. (и) – двуместная операция конъюнкция;

4. (если, то) – двуместная операция импликация;

Каждая операция характеризуется своей таблицей истинности:

Вводятся следующие логические операции (связки) над высказываниями


  1. Отрицание. Отрицанием (логическим “не”) высказывания Р называется высказывание, которое истинно только тогда, когда высказывание Р ложно.

Обозначается Р или .

Соответствие между высказываниями определяется таблицами истинности. В нашем случае эта таблица имеет вид:


PРИЛЛИ

2) Конъюнкция. Конъюнкцией (логическим “и”) двух высказываний P и Q называется высказывание, истинное тогда и только тогда, когда истинны оба высказывания.

Обозначается P&Q или РQ.

PQPQИИИИЛЛЛИЛЛЛЛ

3) Дизъюнкция. Дизъюнкцией (логическим “или”) двух высказываний P и Q называется высказывание, ложное тогда и только тогда, когда оба высказывания ложны.

Обозначается PQ.

PQPQИИИИЛИЛИИЛЛЛ

4) Импликация. Импликацией (логическим следованием) двух высказываний P и Q называется высказывание, истинное тогда и только тогда, когда высказывание Р истинно, а Q – ложно.

Обозначается PQ (или РQ). Высказывание Р называется посылкой импликации, а высказывание Q – следствием.

PQPQИИИИЛЛЛИИЛЛИ

5) Эквиваленция. Эквиваленцией (логической равносильностью) двух высказываний P и Q называется высказывание, истинное тогда и только тогда, когда истинности высказываний совпадают.

Обозначается РQ или РQ.


PQPQИИИИЛЛЛИЛЛЛИ

С помощью этих основных таблиц истинности можно составлять таблицы истинности сложных формул.


Построим истинностную таблицу сложного высказывания:

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 Дизъюнктивная нормальная форма.
Отрицание относящиеся к переменной называется тесным (простым). Отрицание, не являющееся тесным, называется сложным.

Высказывательная форма называется приведенной, если она не содержит операции импликации и сложного отрицания.

Теорема: Для любой высказывательной формы существуют равносильные приведенные формы.

Доказательство:



  1. Пусть высказывательная форма Ы есть переменная (тривиально);

  2. Пусть Ы - = L и для L теорема 1 выполняется, т.е. существует L*, которое является приведенной формой: L* L, тогда рассмотрим L* применяя нужное число раз законы Моргана, получим, что внешнее отрицание перенесется внутрь либо на отрицание переменной, либо на отрицание отрицания переменной, таким образом L является приведенной высказывательной формой.

  3. Пусть , причем для теорема 1 выполняется, т.е. для них существуют равносильные приведенные высказывательные формы, т.к. они не содержат операции импликации и сложного отрицания.

  4. Пусть , аналогично п.3

  5. Пусть , для теорема 1 выполняется, применяем закон импликации:

Символическая степень высказывания – это , причем может быть истиной, либо ложной, причем:

Свойства символической степени высказывания:








Высказывательная форма, состоящая из переменных или отрицания переменных применением только одной операции дизъюнкции, называется элементарной дизъюнкцией.

Высказывательная форма, состоящая из элементарных конъюнкций, применением только одной операции дизъюнкции называется дизъюнктивной нормальной формой (ДНФ).

Совершенной дизъюнктивной формой формулы алгебры высказываний (СДНФ) называется ДНФ, в которой:


  1. следующая страница >>


izumzum.ru