![]() Главная страница Случайная страница КАТЕГОРИИ: АвтомобилиАстрономияБиологияГеографияДом и садДругие языкиДругоеИнформатикаИсторияКультураЛитератураЛогикаМатематикаМедицинаМеталлургияМеханикаОбразованиеОхрана трудаПедагогикаПолитикаПравоПсихологияРелигияРиторикаСоциологияСпортСтроительствоТехнологияТуризмФизикаФилософияФинансыХимияЧерчениеЭкологияЭкономикаЭлектроника |
Примеры доказательств тождеств с множествами
Пример 1. Доказать или опровергнуть справедливость тождества (A Доказательство. Докажем, используя метод взаимного включения. Пусть (A E 1. Докажем необходимость: E
2. Докажем достаточность: F
3. Следовательно, E=F, т.е. исходное тождество справедливо. Пример 2. Доказать или опровергнуть справедливость тождества A Доказательство. Докажем методом от противного: предположим, что это выражение не равно пустому множеству. a Получаем противоречие: элемент Пример 3. Доказать, что A Доказательство. Пусть А и В – подмножества некоторого универсума U, А
Значит B’ Пример 4. Доказать (A Доказательство. Докажем, используя геометрический метод. Построим диаграммы Эйлера-Венна для множеств (A
На первой диаграмме множество (A Булеан Множество всех подмножеств множества М называется булеаном и обозначается 2М: 2М = {А| А Теорема. Для конечного множества М |2М| = 2|M| Доказательство: Индукция по |M|. База: если |M| = 0, то М= Ø и 2Ø = {Ø }. Следовательно, |2Ø | = |{Ø }| = 1 = 20=2|Ø |. Индукционный переход: пусть |М| = k. Положим M1 = {X Имеем 2M = M1UМ2 и Mi∩ М2 = Ø. По индукционному предположению |M1| = 2k-1, |M2| = 2k-1. Следовательно, |2М| = |M1| + |M2| =2k-1 + 2k-1=2 × 2k-1 =2k=2М. Пример. Пусть X = {1, 2, 3}. Тогда множество всех подмножеств X будет 2X = {0, {1}, {2}, {3}, {1, 2}, {1, 3}, {2, 3}, X}.
|