PR_SEM1 (Семинары)
Описание файла
Файл "PR_SEM1" внутри архива находится в следующих папках: Семинары, Семинар 1. PDF-файл из архива "Семинары", который расположен в категории "". Всё это находится в предмете "дискретная математика" из 3 семестр, которые можно найти в файловом архиве МГТУ им. Н.Э.Баумана. Не смотря на прямую связь этого архива с МГТУ им. Н.Э.Баумана, его также можно найти и в других разделах. Архив можно найти в разделе "лекции и семинары", в предмете "дискретная математика" в общих файлах.
Просмотр PDF-файла онлайн
Текст из PDF
Семинар 1. ЭЛЕМЕНТЫТЕОРИИ МНОЖЕСТВ1.1. МножестваПонятие множества является исходным, для него нельзя дать строгого математического определения. Множество состоит из элементов.Основоположник теории множеств Георг Кантор, поясняя интуитивную идею множества, писал:Под ... множеством, я понимаю вообще все многое, которое возможно мыслить как”единое,т.е.
такую совокупность определенных элементов, которая посредством одногозакона может быть соединена в одно целое.“Принадлежность элемента x множеству A обозначается с помощью знака ∈ ( при”надлежит“): x ∈ A .Элементы формальной логикиДля сокращения записи мы будем использовать элементы формальной логики, оперирующей с высказываниями.Высказывание — это предложение, которое может быть истинно или ложно. Длязаписи высказываний используют логические символы.• Символ ∧ (конъюнкция) заменяет в речи союз и“.”• Cимвол ∨ (дизъюнкция) — союз или“.”• Cимвол ⇒ (импликация) — слова если . . . , то“.”• Cимвол ⇔ — слово равносильно“.”• Cимвол ¬ — слово не“.”Будем также пользоваться кванторами ∀ (всеобщности) и ∃ (существования).Равенство множеств.
ПодмножествоДва множества 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СЕМИНАР 1. ЭЛЕМЕНТЫ ТЕОРИИ МНОЖЕСТВ2и собственное подмножество любого непустого множества.Теоретико-множественные операцииДля любых двух множеств 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 );• 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) A ∪ B = B ∪ A2) A ∩ B = B ∩ A3) A ∪ (B ∪ C) = (A ∪ B) ∪ C4) 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 ∩ B8) A ∩ B = A ∪ B9) A ∪ ∅ = A10) A ∩ ∅ = ∅11) A ∩ U = A12) A ∪ U = U13) A ∪ A = U14) A ∩ A = ∅15) A ∪ A = A16) A ∩ A = A17) A = A18) A \ B = A ∩ B19) A 4 B = (A ∪ B) \ (A ∩ B)Метод двух включенийЛюбое высказывание о равенстве двух множеств может быть доказано так называемымметодом двух включений, основанном на определении равенства через включения:A = B ⇔ (A ⊆ B) ∧ (B ⊆ A)СЕМИНАР 1.
ЭЛЕМЕНТЫ ТЕОРИИ МНОЖЕСТВ3Если нужно доказать тождество X = Y , то достаточно из предположения x ∈ Xвывести, что x ∈ Y , и, обратно, из предположения x ∈ Y вывести x ∈ X .Докажем, например, тождество 19)A 4 B = (A ∪ B) \ (A ∩ B),используя метод двух включений.Покажем первое включение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.Оба включения имеют место, тождество доказано.Задачи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(б) M[n ∩ Mm(в)Mp , где P — множество простых чисел.p∈PСЕМИНАР 1. ЭЛЕМЕНТЫ ТЕОРИИ МНОЖЕСТВ1.3. Найти∞[n=1(а)(б)(в)(г)∞\Xn и4Xn :n=1Xn = [−1/n, 1/n] ;Xn = (−1/n, 1/n) ;Xn = [0, 1/n] ;Xn = (0, 1/n) .1.4. Найти множество точек круга, принадлежащих объединению и пересечению(а) всех треугольников, вписанных в данный круг;(б) всех правильных треугольников, вписанных в данный круг.1.5. Доказать, что пересечение произвольной системы выпуклых множеств на плоскости есть выпуклое множество.
(Множество точек на плоскости будет выпуклым, есливсе точки отрезка, соединяющего любые две точки множества, принадлежат этому множеству). Верно ли это утверждение для объединения?1.6. Метод эквивалентных преобразований доказательства теоретикомножественных тождеств заключается в применении ранее установленных тождествдля преобразования правой части исследуемого тождества к левой или наоборот.Используя тождества 1)–19), проверить, что справедливы тождества:(а) (A ∪ B) \ (A ∩ B) = (A ∩ B) ∪ (B ∩ A) ;(б) A \ B = A ∪ (A ∩ B) ;.