🗊Презентация Дискретная математика. Периоды развития математики

Дискретная математика Введение

Периоды развития математики В истории цивилизации можно выделить три крупных периода: сельскохозяйственный, или аграрный — до XVII в.; индустриальный — с XVII по XX в.; информационный — с XX в. Эти периоды определялись научно-техническими революциями и, следовательно, характером тех систем и явлений природы, которые вовлекались в сферу главных производственных интересов и потребностей людей. В каждый период создавались новые технологии производства, новая картина реального мира, новые системы знаний (науки) и, в частности, новая математика.

Периоды развития математики

Новый период развития математики Дискретной математикой называют совокупность математических дисциплин, изучающих свойства абстрактных дискретных объектов. Фундаментом дискретной математики являются: Теория множеств; Математическая логика; Теория графов; Теория кодирования; Теория автоматов.

Новый период развития математики Стимулы развития дискретной математики: растущий поток информации и проблемы ее передачи, обработки и хранения привели к возникновению и развитию теории кодирования; различные экономические задачи, задачи электротехники стимулировали создание и развитие теории графов; связь релейно-контактных схем с формулами алгебры логики и их использование для описания функционирования автоматов дали начало развитию и применению математической логики и теории автоматов.

Обозначения Кванторы: Квантор общности:  - «любой», «всякий», «каждый»; Квантор существования:  - «существует», «найдется», «можно найти»;  «тогда и только тогда», «необходимо и достаточно»;  «следует», «выполняется»; : или  «такой, что» Пример:

Дискретная математика Теория множеств

Основные понятия «Под многообразием, или множеством, я понимаю вообще всякое многое, которое можно мыслить как единое, то есть всякую совокупность определённых элементов, которая может быть связана в одно целое с помощью некоторого закона…» Георг Кантор

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

Пустое множество Примеры множеств: Множество решений уравнения; Множество студентов в группе; Множество предметов мебели в кабинете; Множество натуральных чисел.

Универсальное множество Множество U, содержащее все возможные элементы, обладающие некоторым признаком, называется универсальным (универсумом).

Основные понятия Множества обозначают большими буквами латинского алфавита. Элементы множества – строчными буквами.

Диаграммы Эйлера-Венна Множества удобно изображать с помощью кругов Эйлера (диаграмм Венна).

Равные множества Определение равенства множеств 1. Два множества называются равными (А=В) в том и только в том случае, когда они состоят из одних и тех же элементов. Примеры: Множества решений уравнений 4х-8=16 и х/15=2/5 равны, так как их решением является одно и то же число 6. Равны множества букв, из которых составлены слова «навес» и «весна».

Подмножество Множество A называют подмножеством множества B (обозначается A  B ), если всякий элемент множества A является элементом множества B:

Конечные и бесконечные Множество, состоящее из конечного числа элементов называется конечным множеством. Бесконечное множество- непустое множество, не являющееся конечным. Мощностью конечного множества называется число его элементов. Обозначение: А , В .   = 0

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

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

Способы задания множеств Задание множеств порождающей процедурой, которая описывает способ получения элементов множества из уже полученных элементов либо других объектов. Например: a) (1)1 N; (2) если nN, то n+1N. Графическое задание множеств с помощью диаграмм Эйлера-Венна. Например,

Способы задания множеств Задание множеств порождающей процедурой, которая описывает способ получения элементов множества из уже полученных элементов либо других объектов. Например:  a) 2 M2n; б) если mM2n , то 2mM2n. а) 1 N; б) если nN, то n+1N. Графическое задание множеств с помощью диаграмм Эйлера-Венна. Например,

Способы задания множеств Задайте списком множество: 1) букв в слове «алгебра»; 2) четных однозначных натуральных чисел; 3) нечетных однозначных натуральных чисел; 4) однозначных простых чисел. Запишите множество описанием характеристических свойств : а) натуральных делителей числа 12; б) натуральных делителей числа 30; в) целых делителей числа 6; г) простых делителей числа 12.

Способы задания множеств По какому характеристическому свойству записаны такие множества: {понедельник, вторник, среда, четверг, пятница, суббота, воскресенье}; {январь, февраль, март, апрель, май, июнь, июль, август, сентябрь, октябрь, ноябрь, декабрь}; {до, ре, ми, фа, соль, ля, си}; {0, 1, 2, 3, 4, 5, 6, 7, 8, 9}. А — множество четных натуральных чисел, расположенных между числами 25 и 35. Задайте это множество списком, характеристическим свойством, порождающей процедурой.

Операции над множествами

Операции над множествами Пересечением множеств A и В называется множество (АВ), состоящее из тех и только тех элементов, которые принадлежат множествам А и В одновременно.

Операции над множествами

Операции над множествами Разностью множеств B и A (B\A) называется множество всех элементов множества B, которые не содержатся в A.

Операции над множествами

Операции над множествами

Операции над множествами Кортежем длины n (n-кой) называется упорядоченная последовательность из n элементов. Элемент, занимающий первое место, называется первой компонентой n-ки, элемент, занимающий второе место, называется второй компонентой n-ки и т.д. Обозначение: (а1, а2, … аn) или а1, а2, … аn. Кортеж длины 2 называют двойкой или парой. Прямым произведением двух множеств А и В называется множество всевозможных пар (a,b), таких, что: a А, bВ. Символическая запись: АВ = {(a,b): aА, bВ}

Операции над множествами Известно, что M = {1;2;5}, N = {1;4;5;7;9}, K = {4;7;9}. Найдите: 1) пересечение M и N; 2) пересечение M и K; 3) пересечение N и K; 4) объединение M и K; 10) дополнение M, N, K до универсума, если U –все цифры. 11) Прямое произведение K и N, N и K; 12) Симметрическую разность M и K, M и N, K и N

Операции над множествами т

Операции над множествами Найти булеан множества М={a,b,c}. (М)={, {a}, {b}, {c}, {a,b}, {a,c}, {b,c}, {a,b,c}}. Найти булеан множества М={1,3,5,7}

Домашнее задание Дано: U={1, 2, 3, 4, 5, 6, 7}, A={1, 2, 3, 4, 5}, В={2, 4, 6}, С={1,3,7}. Найти: а) АС; б) В\(СА); в) АВ; г) (СВ)(А\В); д) (АВ)\С. Выписать булеан множества А, если А – множество нечетных однозначных чисел.

Свойства операций над множествами Пусть U — универсальное множество; A, B,C— его подмножества. Тогда имеют место следующие тождественные равенства:

Свойства операций над множествами

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

Проиллюстрируем с помощью диаграмм Эйлера-Венна равенство А \ В = Проиллюстрируем с помощью диаграмм Эйлера-Венна равенство А \ В =

Докажем равенство А∪(В∩С) = (А∪В)∩(А∪С). Докажем равенство А∪(В∩С) = (А∪В)∩(А∪С).

Доказательства с помощью диаграмм Эйлера-Венна Докажите тождество, используя диаграммы Венна. А\(В\С) = (А\В) ∪ (А∩С).

Доказать, что: Доказать, что: A\(BC)=(A\B)(A\C), A\(BC)=(A\B)(A\C), A\(A\B)=AB, A\B=A\(AB), A(B\C)=(AB)\(AC)=(AB)\C, (A\B)\C=(A\C)\(B\C), AB=A(B\A), (AB)(A )=A, (AB)(A )=A, ( B)A=AB, (AB)\C=(A\C)(B\C), A\(B\C)=(A\B)(AC), A\(BC)=(A\B)\C.

Доказательства (аналитически) Справедливость законов алгебры множеств доказывается на основе определения равенства: Х = Y, если 1) Х  Y:  x  X  x  Y; 2) Y  Х:  y  Y  y  X. Сформулированный принцип называют интуитивным принципом объемности

Доказательства Используя отношения принадлежности, доказать тождество (A  B) \ C = (A \ C)  (B \ C).

Доказательства 2) Если y  Y  y  (A \ C)  (B \ C) 

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

1) Если 1) Если

Докажем включение в обратную сторону: Докажем включение в обратную сторону:

Операции над множествами Тест

Вставьте слово или фразу Пересечением множеств A и В называется множество, состоящее из тех и только тех элементов, которые_________ принадлежат множествам А и В одновременно; принадлежат хотя бы одному из множеств A или B; которые принадлежат множеству А, но не содержатся в B; принадлежат одному из множеств: либо А, либо В, но не являются общими элементами.

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

Вставьте слово или фразу Объединением множеств A и B называется множество, состоящее из всех тех элементов, которые_________________ принадлежат множествам А и В одновременно; принадлежат хотя бы одному из множеств A или B; не принадлежат множеству А, но принадлежат универсальному множеству; которые принадлежат множеству А, но не содержатся в В.

Вставьте слово или фразу Симметрической разностью множеств А и В называется множество, содержащее те и только те элементы, которые____ принадлежат множествам А и В одновременно; принадлежат хотя бы одному из множеств A или B; которые не содержатся в B; принадлежат одному из множеств: либо А, либо В, но не являются общими элементами;

5.Установите соответствие Объединение Пересечение Разность В/А Симметрическая разность Разность А/В Дополнение

6.Выбрать верное утверждение

7.

8.

9.

10.

11.

15.Установите соответствие

Операции над множествами Решение задач

Даны множества K={а,б,д}, L={б,в,д}, M={а,в,г}, U={а,б,в,г,д}. Найти множества: Даны множества K={а,б,д}, L={б,в,д}, M={а,в,г}, U={а,б,в,г,д}. Найти множества: (KM) \L L(K M) M×L

Построить диаграмму Эйлера-Венна для множества (A\C)(B\C) Построить диаграмму Эйлера-Венна для множества (A\C)(B\C)

Доказать равенство множеств (СB)(AC)=(AB)\C Доказать равенство множеств (СB)(AC)=(AB)\C с помощью диаграммы Эйлера – Венна; аналитически

Доказать равенство множеств (СB)(AC)=(AB)\C Доказать равенство множеств (СB)(AC)=(AB)\C б) аналитически

Нахождение мощности объединения множеств Мощность объединения двух множеств равна сумме мощностей этих множеств баз мощности их пересечения:

Нахождение мощности объединения множеств Мощность объединения трех множеств:

Нахождение мощности объединения множеств Пример. На потоке из 100 студентов 28 человек изучают английский язык, 30 человек - немецкий язык, 42 человека - французский язык. Причем 8 человек изучают два языка - английский и немецкий, 10 человек изучает английский и французский языки, 5 человек - немецкий и французский языки. 3 человека изучают все 3 языка. Сколько студентов не изучает ни один из перечисленных языков?

H- мн-во студентов, изучающих нем. язык , H=30; H- мн-во студентов, изучающих нем. язык , H=30; Ф- мн-во студентов, изучающих фр. язык, Ф=42. Соответственно множества студентов, изучающих по 2 или 3 ин. языка:

Задача. На вступительном экзамене по математике были предложены три задачи: по алгебре, планиметрии и стереометрии. Из 1000 абитуриентов задачу по алгебре решили 800, по планиметрии — 700, а по стереометрии — 600 абитуриентов. При этом задачи по алгебре и планиметрии решили 600 абитуриен­тов, по алгебре и стереометрии — 500, по планиметрии и стерео­метрии — 400. Все три задачи решили 300 абитуриентов. Суще­ствуют ли абитуриенты, не решившие ни одной задачи, и если да, то сколько их? Задача. На вступительном экзамене по математике были предложены три задачи: по алгебре, планиметрии и стереометрии. Из 1000 абитуриентов задачу по алгебре решили 800, по планиметрии — 700, а по стереометрии — 600 абитуриентов. При этом задачи по алгебре и планиметрии решили 600 абитуриен­тов, по алгебре и стереометрии — 500, по планиметрии и стерео­метрии — 400. Все три задачи решили 300 абитуриентов. Суще­ствуют ли абитуриенты, не решившие ни одной задачи, и если да, то сколько их?

Задача. В студенческой группе 25 человек. Во время летних каникул 9 из них выезжали в турпоездки за границу, 12 – путешествовали по России, 15 – отдыхали в Сочи, 6 – путешествовали за границей и по России, Задача. В студенческой группе 25 человек. Во время летних каникул 9 из них выезжали в турпоездки за границу, 12 – путешествовали по России, 15 – отдыхали в Сочи, 6 – путешествовали за границей и по России, 7 – были и за границей и в Сочи, 8 – и путешествовали по России и были в Сочи и 3 – участвовали во всех трех поездках. Сколько студентов никуда не выезжало?

Задача. Из 220 школьников 163 умеют играть в хоккей, 175 – в футбол, 24 не умеют играть в эти игры. Сколько школьников одновременно умеет играть в хоккей и футбол? Задача. Из 220 школьников 163 умеют играть в хоккей, 175 – в футбол, 24 не умеют играть в эти игры. Сколько школьников одновременно умеет играть в хоккей и футбол?

Задача. По итогам экзаменов из 37 студентов отличную оценку по математике имели 15 студентов, по физике – 16, по химии – 19, по математике и физике – 7, по математике и химии – 9, по физике и химии – 6, по всем трем предметам – 4. Сколько студентов получили хотя бы по одной отличной оценке? Задача. По итогам экзаменов из 37 студентов отличную оценку по математике имели 15 студентов, по физике – 16, по химии – 19, по математике и физике – 7, по математике и химии – 9, по физике и химии – 6, по всем трем предметам – 4. Сколько студентов получили хотя бы по одной отличной оценке?

Задача. Староста курса представил следующий отчет о физкультурной работе: Всего – 45 студентов. Футбольная секция – 25 человек, баскетбольная секция – 30 человек, шахматная секция – 28 человек, футбольная и баскетбольная – 16, футбольная и шахматная – 18, баскетбольная и шахматная – 17. В трех секциях одновременно занимаются 15 человек. Объясните, почему отчет не был принят? Задача. Староста курса представил следующий отчет о физкультурной работе: Всего – 45 студентов. Футбольная секция – 25 человек, баскетбольная секция – 30 человек, шахматная секция – 28 человек, футбольная и баскетбольная – 16, футбольная и шахматная – 18, баскетбольная и шахматная – 17. В трех секциях одновременно занимаются 15 человек. Объясните, почему отчет не был принят?

Домашняя работа В течение 30 дней сентября было 12 дождливых, 8 ветреных, 4 холодных, 5 дождливых и ветреных, 3 дождливых и холодных, 2 ветреных и холодных, а один день был и дождливый, и ветреный, и холодный. В течение скольких дней в сентябре была хорошая погода? В классе 35 учащихся. Из них 20 посещают математический кружок, 11 – физический, 10 учеников не посещают ни одного из этих кружков. Сколько учеников посещают и математический, и физический кружок? Сколько учащихся посещают только математический кружок?

Подготовка к контрольной работе Подготовка к контрольной работе

3. Докажите, что 3. Докажите, что

Контрольная работа Продолжительность 45 минут Критерии оценки: На «3»- 2 и 3 задания На «4» - 1, 2, 3, 4а) На «5» - все! (и правильно)