Главная страница Случайная страница КАТЕГОРИИ: АвтомобилиАстрономияБиологияГеографияДом и садДругие языкиДругоеИнформатикаИсторияКультураЛитератураЛогикаМатематикаМедицинаМеталлургияМеханикаОбразованиеОхрана трудаПедагогикаПолитикаПравоПсихологияРелигияРиторикаСоциологияСпортСтроительствоТехнологияТуризмФизикаФилософияФинансыХимияЧерчениеЭкологияЭкономикаЭлектроника |
Примеры доказательств тождеств с множествами
Пример 1. Доказать или опровергнуть справедливость тождества (A B) C=(A C) (B C). Доказательство. Докажем, используя метод взаимного включения. Пусть (A B) C=E, a (A C) (B C)=F. Тогда необходимо доказать или опровергнуть следующее: E F & F E. 1. Докажем необходимость: E F. a E a (A B) C a (A B)& a C (a A a B)& a C a (A C) a (B C) a (A C) (B C)⟹ a∈ F. 2. Докажем достаточность: F E a F a (A C) (B C) a (A C) a (B C) (a A & a C) (a В& a C) a (A B)& a C a (A B) C⟹ a E. 3. Следовательно, E=F, т.е. исходное тождество справедливо. Пример 2. Доказать или опровергнуть справедливость тождества A ((A B) (A B))= . Доказательство. Докажем методом от противного: предположим, что это выражение не равно пустому множеству. a A ((A B) (A B)) a A & a ((A B) (A B)) a A & (a (A B)& a (A B)) a A & (a A & a B) & (a A a B) Получаем противоречие: элемент одновременно принадлежит и не принадлежит множеству . Значит, первоначальное предположение неверно и исходное тождество справедливо, т.е. равно . Пример 3. Доказать, что A B B’ A’. Доказательство. Пусть А и В – подмножества некоторого универсума U, А B x U, x A x B x U, x A x B x U, x B’ x A’ Значит B’ A’. Пример 4. Доказать (A B) C=(A C) (B C). Доказательство. Докажем, используя геометрический метод. Построим диаграммы Эйлера-Венна для множеств (A B) C и (A C) (B C):
На первой диаграмме множество (A B) C выделено черной штриховкой, на второй множество (A C) – светлой, множество (B C) – серой, а множество (A C) (B C) является их объединением. Сравнивая эти два рисунка, можно сделать вывод, что эти множества равны, следовательно, тождество доказано. Булеан Множество всех подмножеств множества М называется булеаном и обозначается 2М: 2М = {А| А М} Теорема. Для конечного множества М |2М| = 2|M| Доказательство: Индукция по |M|. База: если |M| = 0, то М= Ø и 2Ø = {Ø }. Следовательно, |2Ø | = |{Ø }| = 1 = 20=2|Ø |. Индукционный переход: пусть M |М| < k→ |2М| = 2|M|. Рассмотрим М = {а1,..., ak}, |М| = k. Положим M1 = {X 2M |akϵ X} иМ2 = {X 2м | ak 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}.
|