PR_SEM2 (Семинары)
Описание файла
Файл "PR_SEM2" внутри архива находится в следующих папках: Семинары, Семинар 2. PDF-файл из архива "Семинары", который расположен в категории "". Всё это находится в предмете "дискретная математика" из 3 семестр, которые можно найти в файловом архиве МГТУ им. Н.Э.Баумана. Не смотря на прямую связь этого архива с МГТУ им. Н.Э.Баумана, его также можно найти и в других разделах. Архив можно найти в разделе "лекции и семинары", в предмете "дискретная математика" в общих файлах.
Просмотр PDF-файла онлайн
Текст из PDF
Семинар 2.2.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.Вывести формулы для вычисления характеристических функций a) A \ B ; б) A4B .Ответ.χA\B = χA − χA χB ;χA4B = χA + χB − 2χA χb .Характеристические функции множеств позволяют в некоторых случаях легко доказывать теоретико-множественные тождества.
Метод характеристических функцийдоказательства теоретико-множественного тождества заключается в вычислении характеристические функции обеих его частей. Тождество верно тогда и только тогда, когдаэти функции совпадают.Пример.Используя метод характеристических функций, выяснить, справедливо ли тождество:(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 .Характеристические функции левой и правой части тождества совпадают.
Следовательно, тоджество верно.Задача 2.Используя метод характеристических функций, выяснить, справедливы ли тождества:(a) (A ∩ B) ∪ C = (A ∪ C) ∩ (B ∩ C) ;(б) A \ (B ∪ C) = (A \ B) \ C ;1СЕМИНАР 2.2(в) (A4B)4C = A4(B4C) .Дом. задание.Используя метод характеристических функций, выяснить, справедливы ли тождества:(а) (A4B)4C = A4(B4C) .(б) (A \ B) \ C = A \ (B \ C) .(в) (A4B) \ C = A \ (B \ C) .СЕМИНАР 2.32.2. Декартово произведение множествЕсли на плоскости задана прямоугольная декартова система координат, то каждойточке плоскости можно поставить в соответствие упорядоченную пару (a, b) действительных чисел — координаты этой точки.В отличие от двухэлементного множества {a, b} , в упорядоченной паре важен порядокследования элементов и в общем случае (a, b) 6= (b, a) .Определение 2.1.
Декартово (прямое) произведение множеств A и B естьмножество всех упорядоченных пар (a, b), таких, что первый элемент пары берется измножества A, а второй — из множества B :A × B = {(a, b) | a ∈ A, b ∈ B}.Пример.Пусть A = {a, b, c} и B = {1, 2}. ТогдаA × B = {(a, 1), (a, 2),(b, 1), (b, 2),(c, 1), (c, 2)}.Задача 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).Покажем второе включение.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).СЕМИНАР 2.4Тождество доказано.Задачи2.1.
Привести пример, показывающий, что A × B 6= B × A. Проиллюстрироватьграфически, приняв в качестве множеств A, B отрезки числовой прямой.2.2. Доказать, что если (A ⊆ X) и (B ⊆ Y ) , то(A × B) ⊆ (X × Y ).Проиллюстрировать графически, приняв в качестве множеств A, B, X, Y отрезкичисловой прямой.2.3. Используя метод двух включений, доказать справедливость тождества:(A ∩ B) × (C ∩ D) = (A × C) ∩ (B × D).2.4. Показать, что(A × B) 6= A × B.Вывести требуемое тождество.
Проиллюстрировать полученное графически, приняв вкачестве множеств A и B отрезки числовой прямой.2.5. Проверить на примерах, справедливо ли тождество:(A \ B) × C = (A × C) \ (B × C).Если не удастся придумать пример, показывающий, что это не тождество, попробуйтедоказать его методом двух включений..