Pp_S2 (Семинары)
Описание файла
Файл "Pp_S2" внутри архива находится в следующих папках: Семинары, Семинар 2. PDF-файл из архива "Семинары", который расположен в категории "". Всё это находится в предмете "дискретная математика" из 3 семестр, которые можно найти в файловом архиве МГТУ им. Н.Э.Баумана. Не смотря на прямую связь этого архива с МГТУ им. Н.Э.Баумана, его также можно найти и в других разделах. Архив можно найти в разделе "лекции и семинары", в предмете "дискретная математика" в общих файлах.
Просмотр PDF-файла онлайн
Текст из PDF
Семинар 1.1.1. Метод характеристических функцийХарактеристическая функция χA множества A ⊆ U ,где U — универсальное множество, есть функция, отображающаяуниверсальное множество U в двухэлементное множество {0, 1} :1, если x ∈ A,χA(x) =0, если x ∈/ A.Справедливы следующие равенства:(а) χA(x)2 = χA(x) ;(б) χA∩B (x) = χA(x)χB (x) ;(в) χA∪B (x) = χA(x) + χB (x) − χA(x)χB (x) ;(г) χA(x) = 1 − χA(x) .1СЕМИНАР 1.Задача 1.Вывести формулы для вычисления характеристических функцийa) A \ B ;б) A4B .2СЕМИНАР 1.3Ответ.χA\B = χA − χAχB ;χA4B = χA + χB − 2χAχb.СЕМИНАР 1.4Характеристические функции множеств позволяют в некоторыхслучаях легко доказывать теоретико-множественные тождества.Метод характеристических функций доказательства теоретико-множественного тождества заключается в вычислении характеристические функции обеих его частей.
Тождество верно тогда и толькотогда, когда эти функции совпадают.СЕМИНАР 1.5Пример.Используя метод характеристических функций, выяснить, справедливо ли тождество: (A4B) ∩ C = (A ∩ C)4(B ∩ C) ;Решение.С одной стороныχ(A4B)∩C = χA4B χC == (χA + χB − 2χAχB ) χC == χAχC + χB χC − 2χAχB χC .С другой стороныχ(A∩C)4(B∩C) == χA∩C + χB∩C − 2χA∩C χB∩C == χAχC + χB χC − 2χAχC χB χC == χAχC + χB χC − 2χAχB χC .Характеристические функции левой и правой части тождествасовпадают. Следовательно, тоджество верно.СЕМИНАР 1.6Задача 2.Используя метод характеристических функций, выяснить, справедливы ли тождества:(a) (A ∩ B) ∪ C = (A ∪ C) ∩ (B ∩ C) ;(б) A \ (B ∪ C) = (A \ B) \ C ;(в) (A4B)4C = A4(B4C) .Дом.
задание.Используя метод характеристических функций, выяснить, справедливы ли тождества:(а) (A4B)4C = A4(B4C) .(б) (A \ B) \ C = A \ (B \ C) .(в) (A4B) \ C = A \ (B \ C) .СЕМИНАР 1.71.2. Декартово произведение множествЕсли на плоскости задана прямоугольная декартова система координат, то каждой точке плоскости можно поставить в соответствиеупорядоченную пару (a, b) действительных чисел — координаты этой точки.В отличие от двухэлементного множества {a, b} , в упорядоченнойпаре важен порядок следования элементов и в общем случае (a, b) 6=(b, a) .Определение 1.1. Декартово (прямое) произведениемножеств A и B есть множество всех упорядоченных пар (a, b),таких, что первый элемент пары берется из множества A, авторой — из множества B :A × B = {(a, b) | a ∈ A, b ∈ B}.СЕМИНАР 1.8Пример.Пусть A = {a, b, c} и B = {1, 2}. ТогдаA × B = {(a, 1), (a, 2),(b, 1), (b, 2),(c, 1), (c, 2)}.СЕМИНАР 1.9Задача 3.Методом двух включений доказать тождествоA × (B ∩ C) = (A × B) ∩ (A × C).Решение.Покажем первое включение.x =(y, z) ∈ A × (B ∩ C) ⇒⇒ (y ∈ A ∧ z ∈ B ∩ C) ⇒⇒ (y ∈ A ∧ (z ∈ B ∧ z ∈ C) ⇒⇒ (y ∈ A ∧ z ∈ B)∧∧ (y ∈ A ∧ z ∈ C) ⇒⇒ ((y, z) ∈ A × B)∧∧ ((y, z) ∈ A × C) ⇒⇒ (y, z) ∈ (A × B) ∩ (A × C).СЕМИНАР 1.10Покажем второе включение.x =(y, z) ∈ (A × B) ∩ (A × C) ⇒⇒ ((y, z) ∈ A × B)∧∧ ((y, z) ∈ A × C) ⇒⇒ (y ∈ A ∧ z ∈ B)∧∧ (y ∈ A ∧ z ∈ C) ⇒⇒ (y ∈ A ∧ (z ∈ B ∧ z ∈ C) ⇒⇒ (y ∈ A ∧ (z ∈ B ∩ C) ⇒⇒ (y, z) ∈ (A × (B ∩ C).Тождество доказано.СЕМИНАР 1.11Задачи1.1.
Привести пример, показывающий, что A × B 6= B × A.Проиллюстрировать графически, приняв в качестве множеств A,B отрезки числовой прямой.1.2. Доказать, что если (A ⊆ X) и (B ⊆ Y ) , то(A × B) ⊆ (X × Y ).Проиллюстрировать графически, приняв в качестве множеств A,B, X, Y отрезки числовой прямой.1.3. Используя метод двух включений, доказать справедливостьтождества:(A ∩ B) × (C ∩ D) = (A × C) ∩ (B × D).СЕМИНАР 1.121.4. Показать, что(A × B) 6= A × B.Вывести требуемое тождество.
Проиллюстрировать полученноеграфически, приняв в качестве множеств A и B отрезки числовойпрямой.1.5. Проверить на примерах, справедливо ли тождество:(A \ B) × C = (A × C) \ (B × C).Если не удастся придумать пример, показывающий, что это нетождество, попробуйте доказать его методом двух включений..