множества. Множества. Дискретная математика Введение Периоды развития математики
 Скачать 2 Mb.
|
Дискретная математикаВведениеПериоды развития математикиВ истории цивилизации можно выделить три крупных периода:
Периоды развития математикиАграрный период Индустриальный период Материальная картина мира Информационный период Энергетическая картина мира Информационная картина мира Элементарная математика Высшая математика Дискретная математика Дискретной математикой называют совокупность математических дисциплин, изучающих свойства абстрактных дискретных объектов.Фундаментом дискретной математики являются:
Стимулы развития дискретной математики:
ОбозначенияКванторы:
(хМ) (yN: у х) «для любого х из множества М существует у из множества N такой что у меньше, чем х» Дискретная математикаТеория множествОсновные понятия«Под многообразием, или множеством, я понимаю вообще всякое многое, которое можно мыслить как единое, то есть всякую совокупность определённых элементов, которая может быть связана в одно целое с помощью некоторого закона…»Георг КанторОсновные понятияПонятие множества является одним из наиболее общих и наиболее важных математических понятий. Оно было введено в математику немецким ученым Георгом Кантором.Множество, элементы множества – первичные базисные неопределяемые понятия, на которых строится теория множеств.Объекты, составляющие множество, называются элементами множества.Георг Кантор (1845-1918) Пустое множествоПримеры множеств:
Среди множеств выделяют особое множество - пустое множество. Пустое множество - множество, не содержащее ни одного элемента. Примеры неочевидных пустых множеств:
Универсальное множествоМножество U, содержащее все возможные элементы, обладающие некоторым признаком, называется универсальным (универсумом).. Пример: В математическом анализе:
В алгебре: Основные понятияМножества обозначают большими буквами латинского алфавита. Элементы множества – строчными буквами.«элемент, а принадлежит множеству М» «а является элементом множества М» «элемент, а содержится во множестве М». а М а M «элемент а не принадлежит множеству М» Диаграммы Эйлера-ВеннаМножества удобно изображать с помощью кругов Эйлера (диаграмм Венна).Леонард Эйлер (1707 – 1783г.) Диаграммы Эйлера-Венна – геометрические представления множеств, где множества изображаются в виде совокупностей точек на плоскости ограниченных некоторой замкнутой кривой, а универсум – в виде большого прямоугольника. a, b A d, e A Равные множестваОпределение равенства множеств 1.Два множества называются равными (А=В) в том и только в том случае, когда они состоят из одних и тех же элементов.Примеры:
ПодмножествоМножество A называют подмножеством множества B (обозначается A B ), если всякий элемент множества A является элементом множества B:. (A B) (aA aB) Множество A называется собственным подмножеством множества B, если A B и АВ. Обозначение: А В. Пустое множество является подмножеством любого множества. Все рассматриваемые в задаче множества являются подмножествами универсального множества. Определение равенства множеств 2. Множества A и B равны ( A=B ) тогда и только тогда, когда A B , и B A, т. е. элементы множеств A и B совпадают. Равные множества Булеаном множества М называется множество (М), элементами которого являются все возможные подмножества множества М. Булеан множества Конечные и бесконечныеМножество, состоящее из конечного числа элементов называется конечным множеством.Бесконечное множество- непустое множество, не являющееся конечным.Мощностью конечного множества называется число его элементов. Обозначение: А , В . = 0Способы задания множествМножества могут быть заданы
Способы задания множеств
Например: Например: Способы задания множеств
Например:a)Например,Следовательно, A={a,b,c}, B={b,d,e,f} Способы задания множеств
Например,Следовательно, A={a,b,c}, B={b,d,e,f} Способы задания множеств
Способы задания множеств
Операции над множествамиОбъединением множеств A и B (AB) называется множество, состоящее из всех тех элементов, которые принадлежат хотя бы одному из множеств A или B. Пример. {1,2,3} {2,3,4} = {1,2,3,4}. Пример. Даны два множества А={1,2,4,6} B={0,3,4,6}. Найти С=АB. C={0,1,2,3,4,6} AB = {x| xA или xB} Операции над множествамиПересечением множеств A и В называется множество (АВ), состоящее из тех и только тех элементов, которые принадлежат множествам А и В одновременно.Пример. {1,2,3} {2,3,4} = {2,3} Пример. Даны два множества А={1,2,4,6} B={0,3,4,6}. Найти С=А B. С={4,6} АВ = {x| xA и xB} Операции над множествамиРазностью множеств A и B (A\B) называется множество всех элементов множества A, которые не содержатся в B. Пример. {1,2,3} \ {2,3,4} = {1}. Пример. Даны два множества А={1,2,4,6} и B={0,3,4,6}. Найти С=А \ B. C={1,2} A\B= {x| xA и xB} Операции над множествамиРазностью множеств B и A (B\A) называется множество всех элементов множества B, которые не содержатся в A.B\A= {x| xB и xA} Пример. {2,3,4} \{1,2,3} = {4}. Пример. Даны два множества А={1,2,4,6} и B={0,3,4,6}. Найти С=B \ А. C={0,3} Операции над множествамиСимметрической разностью множеств А и В (А В или А В) называется множество, содержащее те и только те элементы, которые принадлежат одному из множеств: либо А, либо В, но не являются общими элементами. Пример. Пусть A = {1,2,3,4,5}, B = {3,4,5,6,7}. Тогда AΔB = (АВ) \ (АВ) = {1,2,3,4,5,6,7} \ {3,4,5} = {1,2,6,7}. Пример. Даны два множества: А={1,2,4,6} и B={0,3,4,6}. Найти С=А Δ B. C= ({1,2,4,6} {0,3,4,6}) \ ({1,2,4,6} {0,3,4,6}) = {0,1,2,3,4,6} \ {4,6} = {0,1,2,3} Операции над множествамиДополнением (до универсального множества) множества А ( А ) называется множество всех элементов, не принадлежащих множеству А, но принадлежащих универсальному множеству. A={x| x A и xU} Пример. Пусть A = {1,2,4,5}, U = {1,2,3,4,5,6,7}. Тогда A=U\A = {1,2,3,4,5,6,7} \ {1,2,4,5} = {3,6,7} Пример. Пусть A = {a,d,f}, U ={a,b,c,d,e,f}. Найти А. А = {a,b,c,d,e,f} \ {a,d,f} = {b,c,e} Операции над множествамиКортежем длины n (n-кой) называется упорядоченная последовательность из n элементов. Элемент, занимающий первое место, называется первой компонентой n-ки, элемент, занимающий второе место, называется второй компонентой n-ки и т.д. Обозначение: (а1, а2, … аn) или а1, а2, … аn.Кортеж длины 2 называют двойкой или парой.Прямым произведением двух множеств А и В называется множество всевозможных пар (a,b), таких, что: a А, bВ. Символическая запись:АВ = {(a,b): aА, bВ}Пример: А=а,b =1,2 х В=а,1 , а,2 , b,1, b. B х A=1,a, 1,b, 2,a, 2b. Операции над множествами
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 и N5) объединение N и K; 6) разность M и N; 7) разность M и K; 8) разность N и K; 9) дополнение K до N; Операции над множествами
Операции над множествами
(М)={, {a}, {b}, {c}, {a,b}, {a,c}, {b,c}, {a,b,c}}.(М)={,{1}, {3}, {5}, {7}, {1,3}, {1,5}, {1,7}, {3,5}, {3,7}, {5,7}, {1,3,5}, {1,3,7}, {1,5,7}, {3,5,7} {1,3,5,7} }
Домашнее задание
В={2, 4, 6}, С={1,3,7}.Найти: а) АС; б) В\(СА); в) АВ;г) (СВ)(А\В); д) (АВ)\С.Пусть U — универсальное множество; A, B,C— его подмножества. Тогда имеют место следующие тождественные равенства:ассоциативность объединения и пересечения Дистрибутивность объединения относительно пересечения Дистрибутивность пересечения относительно объединения коммутативность объединения и пересечения 1. 2. 3. Идемпотентность объединения и пересечения законы де Моргана тождества поглощения А (А В) = А А (А В) = А Свойства пустого множества. А = А А = А = Свойства универсума А U = А А U = U А = U 4. 5. 6. 7. ДоказательстваДоказательства с помощью диаграмм Эйлера-Венна А \ В В U А = -- А \ В Т.к. диаграммы Эйлера-Венна для множества А \ В и множества совпадают, то эти множества равны.
Свойства операций над множествами Докажите тождество, используя диаграммы Венна. А\(В\С) = (А\В) ∪ (А∩С).Диаграмма Венна А\(В\С) Диаграмма Венна (А\В) ∪ (А∩С) Доказать, что:Доказать, что:
A\(BC)=(A\B)\C Доказательства (аналитически)Справедливость законов алгебры множеств доказывается на основе определения равенства: Х = Y, если1) Х Y: x X x Y;2) Y Х: y Y y X.Сформулированный принцип называют интуитивным принципом объемностиДля доказательств будем использовать следующие обозначения ({ - и ; [ - или ) и соотношения : x A B x A B x A B x A B x A \ B x A \ B x A ДоказательстваИспользуя отношения принадлежности, доказать тождествоПусть X = (A B) \ C; Y = (A \ C) (B \ C). 1) Если xX x (A B) \ C или (A B) \ C = (A \ C) (B \ C). Доказательства2) Если y Y y (A \ C) (B \ C) y [(A \ C) \ (B \ C)] [(B \ C) \ (A \ C)] . ДоказательстваОтсюда или = или . Следовательно тождество верно. 1) Если1) ЕслиДоказательства Докажем закон дистрибутивности: Доказательство. и и или или Доказательства Если или или и и Так как и U Операции над множествамиТестВставьте слово или фразу
1. Вставьте слово или фразу
2. Вставьте слово или фразу
3. Вставьте слово или фразу
4. 5.Установите соответствие
5 2 3 4 1 6
6.Выбрать верное утверждение7.Выбрать верный вариант ответа: 8.Выбрать верный вариант ответа 9.Выбрать верный вариант ответа 10.Выбрать верный вариант ответа 11.Выбрать все верные утверждения: Выбрать все верные утверждения: 12. Найти элементы множества F: Выбрать верный вариант ответа: 13. 14. 15.Установите соответствиеx A B x A B x A B x A B x A \ B x A \ B x A 1 2 3 4 5 6 A B C D E F
|AB C|= 16. Выбрать верный вариант ответа:
Операции над множествамиРешение задач
А В С U
А В С U А В С U
б) аналитическиА В С U А В С U А В С U А В С U Мощность объединения двух множеств равна сумме мощностей этих множеств баз мощности их пересечения:U Мощность объединения трех множеств:U Пример. На потоке из 100 студентов 28 человек изучают английский язык, 30 человек - немецкий язык, 42 человека - французский язык. Причем 8 человек изучают два языка - английский и немецкий, 10 человек изучает английский и французский языки, 5 человек - немецкий и французский языки. 3 человека изучают все 3 языка. Сколько студентов не изучает ни один из перечисленных языков? Ф- мн-во студентов, изучающих фр. язык, Ф=42.Соответственно множества студентов, изучающих по 2 или 3 ин. языка:Решение. Обозначим Y - множество студентов, изучающих иностранные языки. X - множество студентов, не изучающих иностранный язык. Пусть – S множество студентов, S=100 (студентов). A- мн-во студентов, изучающих англ. язык, A=28; По формуле мощности объединения трех множеств Ответ: 20 студентов не изучает ни один из перечисленных языков А П С U 7 – были и за границей и в Сочи, 8 – и путешествовали по России и были в Сочи и 3 – участвовали во всех трех поездках. Сколько студентов никуда не выезжало?А П С U Ответ: 142 Ответ: 32 Домашняя работа
Подготовка к контрольной работеПодготовка к контрольной работе3. Докажите, что3. Докажите, что
6. Постройте диаграммы Эйлера-Венна для множеств а) (С\В) (А\С); в) (А\С) (ВΔС); с) (С Δ А)\(В А). Контрольная работаПродолжительность 45 минутКритерии оценки:
Удачи! |