Презентация семинар 2 (Семинары)
Описание файла
Файл "Презентация семинар 2" внутри архива находится в следующих папках: Семинары, Семинар 2. PDF-файл из архива "Семинары", который расположен в категории "". Всё это находится в предмете "дискретная математика" из 3 семестр, которые можно найти в файловом архиве МГТУ им. Н.Э.Баумана. Не смотря на прямую связь этого архива с МГТУ им. Н.Э.Баумана, его также можно найти и в других разделах. Архив можно найти в разделе "лекции и семинары", в предмете "дискретная математика" в общих файлах.
Просмотр PDF-файла онлайн
Текст из PDF
ЭЛЕМЕНТЫ ТЕОРИИМНОЖЕСТВ• First • Prev • Next • Last • Go Back • Full Screen • Close • QuitЭЛЕМЕНТЫ ТЕОРИИМНОЖЕСТВ1. Метод характеристических функций• First • Prev • Next • Last • Go Back • Full Screen • Close • QuitХарактеристическая функция χA множества A ⊆ U , гдеU — универсальное множество, есть функция, отображающая универсальное множество U в двухэлементное множество {0, 1} :1, если x ∈ A,χA(x) =0, если x ∈/ A.• First • Prev • Next • Last • Go Back • Full Screen • Close • QuitХарактеристическая функция χA множества A ⊆ U , гдеU — универсальное множество, есть функция, отображающая универсальное множество U в двухэлементное множество {0, 1} :1, если x ∈ A,χA(x) =0, если x ∈/ A.Справедливы следующие равенства:• First • Prev • Next • Last • Go Back • Full Screen • Close • QuitХарактеристическая функция χA множества A ⊆ U , гдеU — универсальное множество, есть функция, отображающая универсальное множество U в двухэлементное множество {0, 1} :1, если x ∈ A,χA(x) =0, если x ∈/ A.Справедливы следующие равенства:2(а) χA(x) = χA(x) ;• First • Prev • Next • Last • Go Back • Full Screen • Close • QuitХарактеристическая функция χA множества A ⊆ U , гдеU — универсальное множество, есть функция, отображающая универсальное множество U в двухэлементное множество {0, 1} :1, если x ∈ A,χA(x) =0, если x ∈/ A.Справедливы следующие равенства:2(а) χA(x) = χA(x) ;(б) χA∩B (x) = χA(x)χB (x) ;• First • Prev • Next • Last • Go Back • Full Screen • Close • QuitХарактеристическая функция χA множества A ⊆ U , гдеU — универсальное множество, есть функция, отображающая универсальное множество U в двухэлементное множество {0, 1} :1, если x ∈ A,χA(x) =0, если x ∈/ A.Справедливы следующие равенства:2(а) χA(x) = χA(x) ;(б) χA∩B (x) = χA(x)χB (x) ;(в) χA∪B (x) = χA(x) + χB (x) − χA(x)χB (x) ;• First • Prev • Next • Last • Go Back • Full Screen • Close • QuitХарактеристическая функция χA множества A ⊆ U , гдеU — универсальное множество, есть функция, отображающая универсальное множество U в двухэлементное множество {0, 1} :1, если x ∈ A,χA(x) =0, если x ∈/ A.Справедливы следующие равенства:2(а) χA(x) = χ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) .• First • Prev • Next • Last • Go Back • Full Screen • Close • QuitЗадача 1.Вывести формулы для вычисления характеристических функцийa) A \ B .• First • Prev • Next • Last • Go Back • Full Screen • Close • QuitЗадача 1.Вывести формулы для вычисления характеристических функцийa) A \ B .Ответ.χA\B = χA − χAχB .• First • Prev • Next • Last • Go Back • Full Screen • Close • QuitЗадача 1.Вывести формулы для вычисления характеристических функцийa) A \ B .Ответ.χA\B = χA − χAχB .б) A4B .• First • Prev • Next • Last • Go Back • Full Screen • Close • QuitЗадача 1.Вывести формулы для вычисления характеристических функцийa) A \ B .Ответ.χA\B = χA − χAχB .б) A4B .Ответ.χA4B = χA + χB − 2χAχb.• First • Prev • Next • Last • Go Back • Full Screen • Close • QuitЗадача 1.Вывести формулы для вычисления характеристических функцийa) A \ B .Ответ.χA\B = χA − χAχB .б) A4B .Ответ.χA4B = χA + χB − 2χAχb.Характеристические функции множеств позволяют в некоторых случаях легко доказывать теоретико-множественные тождества.
Методхарактеристических функций доказательства теоретико-множественного тождества заключается в вычислении характеристические функцииобеих его частей. Тождество верно тогда и только тогда, когда этифункции совпадают.• First • Prev • Next • Last • Go Back • Full Screen • Close • QuitПример.• First • Prev • Next • Last • Go Back • Full Screen • Close • QuitПример.Используя метод характеристических функций, выяснить, справедливоли тождество: (A4B) ∩ C = (A ∩ C)4(B ∩ C) ;• First • Prev • Next • Last • Go Back • Full Screen • Close • QuitПример.Используя метод характеристических функций, выяснить, справедливоли тождество: (A4B) ∩ C = (A ∩ C)4(B ∩ C) ;Решение.• First • Prev • Next • Last • Go Back • Full Screen • Close • QuitПример.Используя метод характеристических функций, выяснить, справедливоли тождество: (A4B) ∩ C = (A ∩ C)4(B ∩ C) ;Решение.С одной стороныχ(A4B)∩C = χA4B χC =• First • Prev • Next • Last • Go Back • Full Screen • Close • QuitПример.Используя метод характеристических функций, выяснить, справедливоли тождество: (A4B) ∩ C = (A ∩ C)4(B ∩ C) ;Решение.С одной стороныχ(A4B)∩C = χA4B χC == (χA + χB − 2χAχB ) χC =• First • Prev • Next • Last • Go Back • Full Screen • Close • QuitПример.Используя метод характеристических функций, выяснить, справедливоли тождество: (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 .• First • Prev • Next • Last • Go Back • Full Screen • Close • QuitПример.Используя метод характеристических функций, выяснить, справедливоли тождество: (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 .С другой стороны• First • Prev • Next • Last • Go Back • Full Screen • Close • QuitПример.Используя метод характеристических функций, выяснить, справедливоли тождество: (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) =• First • Prev • Next • Last • Go Back • Full Screen • Close • QuitПример.Используя метод характеристических функций, выяснить, справедливоли тождество: (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 =• First • Prev • Next • Last • Go Back • Full Screen • Close • QuitПример.Используя метод характеристических функций, выяснить, справедливоли тождество: (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 =• First • Prev • Next • Last • Go Back • Full Screen • Close • QuitПример.Используя метод характеристических функций, выяснить, справедливоли тождество: (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 .• First • Prev • Next • Last • Go Back • Full Screen • Close • QuitПример.Используя метод характеристических функций, выяснить, справедливоли тождество: (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 .Характеристические функции левой и правой части совпадают.
Следовательно, тоджество верно.• First • Prev • Next • Last • Go Back • Full Screen • Close • QuitЗадача 2.• First • Prev • Next • Last • Go Back • Full Screen • Close • QuitЗадача 2.Используя метод характеристических функций, выяснить, справедливыли тождества:• First • Prev • Next • Last • Go Back • Full Screen • Close • QuitЗадача 2.Используя метод характеристических функций, выяснить, справедливыли тождества:(a) (A ∩ B) ∪ C = (A ∪ C) ∩ (B ∩ C) ;• First • Prev • Next • Last • Go Back • Full Screen • Close • QuitЗадача 2.Используя метод характеристических функций, выяснить, справедливыли тождества:(a) (A ∩ B) ∪ C = (A ∪ C) ∩ (B ∩ C) ;С одной стороныχ(A∩B)∪C = χA∩B + χC − χA∩B χC =• First • Prev • Next • Last • Go Back • Full Screen • Close • QuitЗадача 2.Используя метод характеристических функций, выяснить, справедливыли тождества:(a) (A ∩ B) ∪ C = (A ∪ C) ∩ (B ∩ C) ;С одной стороныχ(A∩B)∪C = χA∩B + χC − χA∩B χC == χA χB + χС − χA χB χС .• First • Prev • Next • Last • Go Back • Full Screen • Close • QuitЗадача 2.Используя метод характеристических функций, выяснить, справедливыли тождества:(a) (A ∩ B) ∪ C = (A ∪ C) ∩ (B ∩ C) ;С одной стороныχ(A∩B)∪C = χA∩B + χC − χA∩B χC == χA χB + χС − χA χB χС .С другой стороныχ(A∪B)∩(B∩C) = χA∪C χB∩C =• First • Prev • Next • Last • Go Back • Full Screen • Close • QuitЗадача 2.Используя метод характеристических функций, выяснить, справедливыли тождества:(a) (A ∩ B) ∪ C = (A ∪ C) ∩ (B ∩ C) ;С одной стороныχ(A∩B)∪C = χA∩B + χC − χA∩B χC == χA χB + χС − χA χB χС .С другой стороныχ(A∪B)∩(B∩C) = χA∪C χB∩C == (χA + χC − χAχС ) χB χС =• First • Prev • Next • Last • Go Back • Full Screen • Close • QuitЗадача 2.Используя метод характеристических функций, выяснить, справедливыли тождества:(a) (A ∩ B) ∪ C = (A ∪ C) ∩ (B ∩ C) ;С одной стороныχ(A∩B)∪C = χA∩B + χC − χA∩B χC == χA χB + χС − χA χB χС .С другой стороныχ(A∪B)∩(B∩C) = χA∪C χB∩C == (χA + χC − χAχС ) χB χС == χA χB χC + χB χС − χA χB χСТождество не справедливо, поскольку выражения не совпадают.
Например, при χС = 1 и χB = 0 получаются различные значения: слева 1, асправа — 0.• First • Prev • Next • Last • Go Back • Full Screen • Close • Quit(б) (A4B)4C = A4(B4C) .С одной стороныχ(A4B)4C =• First • Prev • Next • Last • Go Back • Full Screen • Close • Quit(б) (A4B)4C = A4(B4C) .С одной стороныχ(A4B)4C = χA4B + χC − 2χA4B χC =• First • Prev • Next • Last • Go Back • Full Screen • Close • Quit(б) (A4B)4C = A4(B4C) .С одной стороныχ(A4B)4C = χA4B + χC − 2χA4B χC == (χA + χB − 2χAχB ) + χС − 2 (χA + χB − 2χAχB ) χС =• First • Prev • Next • Last • Go Back • Full Screen • Close • Quit(б) (A4B)4C = A4(B4C) .С одной стороныχ(A4B)4C = χA4B + χC − 2χA4B χC == (χA + χB − 2χAχB ) + χС − 2 (χA + χB − 2χAχB ) χС == χA + χB − 2χAχB + χС − 2χAχС − 2χB χС + 4χAχB χС =• First • Prev • Next • Last • Go Back • Full Screen • Close • Quit(б) (A4B)4C = A4(B4C) .С одной стороныχ(A4B)4C = χA4B + χC − 2χA4B χC == (χA + χB − 2χAχB ) + χС − 2 (χA + χB − 2χAχB ) χС == χA + χB − 2χAχB + χС − 2χAχС − 2χB χС + 4χAχB χС == χA + χB + χС − 2χAχB − 2χAχС − 2χB χС + 4χAχB χС .• First • Prev • Next • Last • Go Back • Full Screen • Close • Quit(б) (A4B)4C = A4(B4C) .С одной стороныχ(A4B)4C = χA4B + χC − 2χA4B χC == (χA + χB − 2χAχB ) + χС − 2 (χA + χB − 2χAχB ) χС == χA + χB − 2χAχB + χС − 2χAχС − 2χB χС + 4χAχB χС == χA + χB + χС − 2χAχB − 2χAχС − 2χB χС + 4χAχB χС .С другой стороныχA4(B4C) = χA + χB4C − 2χAχB4C =• First • Prev • Next • Last • Go Back • Full Screen • Close • Quit(б) (A4B)4C = A4(B4C) .С одной стороныχ(A4B)4C = χA4B + χC − 2χA4B χC == (χA + χB − 2χAχB ) + χС − 2 (χA + χB − 2χAχB ) χС == χA + χB − 2χAχB + χС − 2χAχС − 2χB χС + 4χAχB χС == χA + χB + χС − 2χAχB − 2χAχС − 2χB χС + 4χAχB χС .С другой стороныχA4(B4C) = χA + χB4C − 2χAχB4C == χA + χB + χС − 2χB χC − 2χA (χB + χC − 2χB χC ) =• First • Prev • Next • Last • Go Back • Full Screen • Close • Quit(б) (A4B)4C = A4(B4C) .С одной стороныχ(A4B)4C = χA4B + χC − 2χA4B χC == (χA + χB − 2χAχB ) + χС − 2 (χA + χB − 2χAχB ) χС == χA + χB − 2χAχB + χС − 2χAχС − 2χB χС + 4χAχB χС == χA + χB + χС − 2χAχB − 2χAχС − 2χB χС + 4χAχB χС .С другой стороныχA4(B4C) = χA + χB4C − 2χAχB4C == χA + χB + χС − 2χB χC − 2χA (χB + χC − 2χB χC ) == χA + χB + χС − 2χAχB − 2χAχС − 2χB χС + 4χAχB χС .• First • Prev • Next • Last • Go Back • Full Screen • Close • Quit(б) (A4B)4C = A4(B4C) .С одной стороныχ(A4B)4C = χA4B + χC − 2χA4B χC == (χA + χB − 2χAχB ) + χС − 2 (χA + χB − 2χAχB ) χС == χA + χB − 2χAχB + χС − 2χAχС − 2χB χС + 4χAχB χС == χA + χB + χС − 2χAχB − 2χAχС − 2χB χС + 4χAχB χС .С другой стороныχA4(B4C) = χA + χB4C − 2χAχB4C == χA + χB + χС − 2χB χC − 2χA (χB + χC − 2χB χC ) == χA + χB + χС − 2χAχB − 2χAχС − 2χB χС + 4χAχB χС .Выражения совпадают, тождество доказано.• First • Prev • Next • Last • Go Back • Full Screen • Close • QuitДом.
задание.Используя метод характеристических функций, выяснить, справедливыли тождества:(а) A \ (B ∪ C) = (A \ B) \ C .(б) (A \ B) \ C = A \ (B \ C) .(в) (A4B) \ C = A \ (B \ C) .• First • Prev • Next • Last • Go Back • Full Screen • Close • Quit2. Декартово произведение множествЕсли на плоскости задана прямоугольная декартова система координат,то каждой точке плоскости можно поставить в соответствие упорядоченную пару (a, b) действительных чисел — координаты этой точки.• First • Prev • Next • Last • Go Back • Full Screen • Close • Quit2.