PP_s1 (Семинары)
Описание файла
Файл "PP_s1" внутри архива находится в следующих папках: Семинары, Семинар 1. PDF-файл из архива "Семинары", который расположен в категории "". Всё это находится в предмете "дискретная математика" из 3 семестр, которые можно найти в файловом архиве МГТУ им. Н.Э.Баумана. Не смотря на прямую связь этого архива с МГТУ им. Н.Э.Баумана, его также можно найти и в других разделах. Архив можно найти в разделе "лекции и семинары", в предмете "дискретная математика" в общих файлах.
Просмотр PDF-файла онлайн
Текст из PDF
Семинар 1. ЭЛЕМЕНТЫ ТЕОРИИ МНОЖЕСТВ1.1. МножестваПонятие множества является исходным, для него нельзя датьстрогого математического определения. Множество состоит изэлементов.Основоположник теории множеств Георг Кантор, поясняя интуитивную идею множества, писал:Под ... множеством, я понимаю вообще все многое, которое воз”можно мыслить как единое, т.е. такую совокупность определенныхэлементов, которая посредством одного закона может быть соединена в одно целое.“Принадлежность элемента x множеству A обозначается с помощью знака ∈ ( принадлежит“): x ∈ A .”1СЕМИНАР 1.
ЭЛЕМЕНТЫ ТЕОРИИ МНОЖЕСТВ2Элементы формальной логикиДля сокращения записи мы будем использовать элементы формальной логики, оперирующей с высказываниями.Высказывание — это предложение, которое может быть истинноили ложно. Для записи высказываний используют логическиесимволы.• Символ ∧ (конъюнкция) заменяет в речи союз и“.”• Cимвол ∨ (дизъюнкция) — союз или“.”• Cимвол ⇒ (импликация) — слова если . . .
, то“.”• Cимвол ⇔ — слово равносильно“.”• Cимвол ¬ — слово не“.”Будем также пользоваться кванторами ∀ (всеобщности) и ∃(существования).СЕМИНАР 1. ЭЛЕМЕНТЫ ТЕОРИИ МНОЖЕСТВ3Равенство множеств. ПодмножествоДва множества A и B считаются равными, если любой элементx из множества A ( x ∈ A ) является элементом множества B( x ∈ B ) и наоборот:A = B ⇔ (∀x)(x ∈ A ⇔ x ∈ B).Говорят, что B есть подмножество множества A , если всякийэлемент B есть элемент A ( (∀x)(x ∈ B ⇒ x ∈ A) ).
Используютзапись: B ⊆ A . Символ ⊆ называют символом включения.Если B ⊆ A , но B 6= A , то пишут B ⊂ A , и B называютстрогим, или собственным подмножеством множества A , асимвол ⊂ — символом строгого включения.Пустое множество есть подмножество любого множества, т.е.(∀A)(∅ ⊆ A),и собственное подмножество любого непустого множества.СЕМИНАР 1. ЭЛЕМЕНТЫ ТЕОРИИ МНОЖЕСТВ4Теоретико-множественные операцииДля любых двух множеств A и B определены новые множества, называемые объединением, пересечением, разностьюи симметрической разностью.• A ∪ B = {x | x ∈ A ∨ x ∈ B} — объединение A и B естьмножество всех таких x , что x является элементом хотя быодного из множеств A , B ;• A ∩ B = {x | x ∈ A ∧ x ∈ B} — пересечение A и B естьмножество всех таких x , что x — одновременно элемент A иэлемент B ;• A \ B = {x | x ∈ A ∧ x ∈/ B} — разность A и B есть множествовсех таких x , что x — элемент A , но не элемент B ( x ∈/ B );СЕМИНАР 1.
ЭЛЕМЕНТЫ ТЕОРИИ МНОЖЕСТВ5• A 4 B = (A\B)∪(B \A) , а симметрическая разность A и B —множество всех таких x , что x — элемент A , но не элемент Bили x — элемент B , но не элемент A .Удобно рассматривать все множества как подмножества некоторого универсального множества U . В этом случае можно определить дополнение множества A :A = {x | x ∈/ A}.Дополнение A состоит из всех элементов универсального множестваU , которые не являются элементами множества A .Другими словами A = U \ A . В общем случае разность B \ A ,где A ⊆ B называют дополнением множества A до множества B .СЕМИНАР 1.
ЭЛЕМЕНТЫ ТЕОРИИ МНОЖЕСТВ6Свойства теоретико-множественных операцийВведенные операции над множествами, обладают следующимисвойствами.1) A ∪ B = B ∪ A3) A ∪ (B ∪ C) = (A ∪ B) ∪ C5) A ∩ (B ∪ C) = (A ∩ B) ∪ (A ∩ C)6) A ∪ (B ∩ C) = (A ∪ B) ∩ (A ∪ C)7) A ∪ B = A ∩ B9) A ∪ ∅ = A11) A ∩ U = A13) A ∪ A = U15) A ∪ A = A17) A = A19) A 4 B = (A ∪ B) \ (A ∩ B)2) A ∩ B = B ∩ A4) A ∩ (B ∩ C) = (A ∩ B) ∩ C8) A ∩ B = A ∪ B10) A ∩ ∅ = ∅12) A ∪ U = U14) A ∩ A = ∅16) A ∩ A = A18) A \ B = A ∩ BСЕМИНАР 1.
ЭЛЕМЕНТЫ ТЕОРИИ МНОЖЕСТВ7Метод двух включенийЛюбое высказывание о равенстве двух множеств может быть доказано так называемым методом двух включений, основанномна определении равенства через включения:A = B ⇔ (A ⊆ B) ∧ (B ⊆ A)Если нужно доказать тождество X = Y , то достаточно изпредположения x ∈ X вывести, что x ∈ Y , и, обратно, изпредположения x ∈ Y вывести x ∈ X .Докажем, например, тождество 19)A 4 B = (A ∪ B) \ (A ∩ B),используя метод двух включений.СЕМИНАР 1. ЭЛЕМЕНТЫ ТЕОРИИ МНОЖЕСТВПокажем первое включениеx ∈ A 4 B ⇒ x ∈ ((A \ B) ∪ (B \ A)) ⇒⇒ (x ∈ A \ B) ∨ (x ∈ B \ A) ⇒⇒ (x ∈ A ∧ x ∈/ B) ∨ (x ∈ B ∧ x ∈/ A) ⇒⇒ (x ∈ A ∪ B ∧ x ∈/ A ∩ B) ⇒⇒ x ∈ (A ∪ B) \ (A ∩ B).Первое включение установлено. Покажем второе включение.x ∈(A ∪ B) \ (A ∩ B) ⇒ (x ∈ A ∪ B) ∧ (x ∈/ A ∩ B) ⇒⇒ ((x ∈ A) ∧ (x ∈/ B)) ∨ ((x ∈ B) ∧ (x ∈/ A)) ⇒⇒ (x ∈ A \ B) ∨ (x ∈ B \ A) ⇒⇒ x ∈ (A \ B) ∪ (B \ A) ⇒⇒ x ∈ A 4 B.Оба включения имеют место, тождество доказано.8СЕМИНАР 1.
ЭЛЕМЕНТЫ ТЕОРИИ МНОЖЕСТВ9Задачи1.1. Найти A ∪ B , A ∩ B , A \ B и B \ A , сделать чертеж:(а) A = [3, 5] , B = [2, 4] ;(б) A = (3, 5) , B = (2, 4] .1.2. Пусть Mn есть множество натуральных чисел, делящихсяна натуральное число n . Найти:∞\(а)Mnn=1(б) Mn ∩ Mm[(в)Mp , где P — множество простых чисел.p∈PСЕМИНАР 1. ЭЛЕМЕНТЫ ТЕОРИИ МНОЖЕСТВ1.3.
Найти(а)(б)(в)(г)∞[n=1∞\Xn и10Xn :n=1Xn = [−1/n, 1/n] ;Xn = (−1/n, 1/n) ;Xn = [0, 1/n] ;Xn = (0, 1/n) .1.4. Найти множество точек круга, принадлежащих объединениюи пересечению(а) всех треугольников, вписанных в данный круг;(б) всех правильных треугольников, вписанных в данный круг.1.5. Доказать, что пересечение произвольной системы выпуклыхмножеств на плоскости есть выпуклое множество. (Множествоточек на плоскости будет выпуклым, если все точки отрезка,соединяющего любые две точки множества, принадлежат этомумножеству).
Верно ли это утверждение для объединения?СЕМИНАР 1. ЭЛЕМЕНТЫ ТЕОРИИ МНОЖЕСТВ111.6. Метод эквивалентных преобразований доказательства теоретико-множественных тождеств заключается в примененииранее установленных тождеств для преобразования правой части исследуемого тождества к левой или наоборот.
Используя тождества1)–19), проверить, что справедливы тождества:(а) (A ∪ B) \ (A ∩ B) = (A ∩ B) ∪ (B ∩ A) ;(б) A \ B = A ∪ (A ∩ B) ;.