Дискуссионный математический форумМатематический форум
Математический форум Math Help Planet

Обсуждение и решение задач по математике, физике, химии, экономике

Теоретический раздел
Часовой пояс: UTC + 3 часа [ Летнее время ]
MathHelpPlanet.com RSS-лента Математического форума

Часовой пояс: UTC + 3 часа [ Летнее время ]


Метод характеристических функций в теории множеств

Метод характеристических функций в теории множеств


Доказательство сложных теоретико-множественных тождеств методом двух включений часто бывает довольно громоздким, и при построении доказательства ход рассуждений не всегда очевиден. Одним из методов, не требующих "угадывания" пути доказательства, является метод характеристических функций.


Характеристическая функция \chi_A множества A\subseteq U есть функция, отображающая универсальное множество U в двухэлементное множество \{0;1\}:


\chi_A(x)= \begin{cases}1,& \text{if}\quad x\in A;\\ 0,& \text{if}\quad x\notin A.\end{cases}

Из определения характеристической функции множества A вытекает справедливость тождества


\chi_2^2(x)=\chi_A(x).
(1.10)

Выразим характеристическую функцию пересечения множеств A и B через характеристические функции \chi_A(x) и \chi_B(x) этих множеств. Из определения пересечения следует, что искомая характеристическая функция должна принимать значение 1 для тех элементов x, которые принадлежат множествам A и B одновременно, и значение 0 в противном случае. Легко видеть, что функция


\chi_{A\cap B}(x)= \chi_A(x)\cdot \chi_B(x)

удовлетворяет этому требованию.


Можно предположить, что характеристическая функция объединения множеств A и B будет равна сумме характеристических функций множеств. Однако так ее определить нельзя, поскольку для элементов x\in A\cap B такая сумма будет иметь значение 2. Введем "поправку" и в результате получим искомую формулу:


\chi_{A\cup B}(x)=\chi_A(x)+ \chi_B(x)- \chi_A(x)\cdot \chi_B(x).

Непосредственно из определения \overline{A} — дополнения множества A — следует, что


\chi_{\overline{A}}(x)= 1-\chi_A(x).

Для разности A\setminus B характеристическая функция имеет вид


\chi_{A\setminus B}(x)= \chi_A(x)- \chi_A(x)\cdot \chi_B(x),

а для симметрической разности A\,\triangle\,B -


\chi_{A\,\triangle\,B}(x)= \chi_A(x)+\chi_B(x)- 2\chi_A(x)\cdot \chi_B(x).

Отметим, что последнюю формулу можно получить, опираясь на свойство 19 и тождество (1.10), а также на характеристические функции для пересечения, объединения и разности:


\begin{aligned}\chi_{A\,\triangle\,B}(x)&= \chi_{A\cup B}(x)- \chi_{A\cup B}(x)\cdot \chi_{A\cap B}(x)=\\[2pt] &=\chi_{A}(x)+ \chi_{B}(x)- \chi_{A}(x)\cdot \chi_{B}(x)- \bigl(\chi_{A}(x)+ \chi_{B}(x)- \chi_{A}(x) \chi_{B}(x)\bigr) \chi_{A}(x) \chi_{B}(x)=\\[2pt] &= \chi_{A}(x)+ \chi_{B}(x)- \chi_{A}(x) \chi_{B}(x)- \bigl(\chi_{A}(x) \chi_{B}(x)+ \chi_{A}(x) \chi_{B}(x)- \chi_{A}(x) \chi_{B}(x)\bigr)=\\[2pt] &=\chi_{A}(x)+ \chi_{B}(x)-2\chi_{A}(x) \chi_{B}(x). \end{aligned}

С учетом равенства (1.10) полученную формулу можно записать в виде


\chi_{A\,\triangle\,B}(x) = \bigl(\chi_{B}(x)- \chi_{B}(x)\bigr)^2.

Метод характеристических функций доказательства справедливости теоретико-множественного тождества заключается в выражении характеристических функций обеих его частей через характеристические функции входящих в него множеств. Тождество верно тогда и только тогда, когда характеристические функции левой и правой частей совпадают.




Пример 1.22. Используя метод характеристических функций, выясним, справедливо ли тождество


(A\,\triangle\,B)\cap C=(A\cap C)\,\triangle\,(B\cap C)

С одной стороны,

\begin{aligned}\chi_{(A\,\triangle\,B)\cap C}(x)&= \chi_{A\,\triangle\,B}\chi_{C} (x)=\\[2pt] &= \bigl(\chi_{A}(x)+ \chi_{B}(x)- 2\chi_{A}(x) \chi_{B}(x)\bigr) \chi_{C}(x)=\\[2pt] &= \chi_{A}(x) \chi_{C}(x)+ \chi_{B}(x) \chi_{C}(x)- 2\chi_{A}(x) \chi_{B}(x) \chi_{C}(x). \end{aligned}

С другой стороны,

\begin{aligned}\chi_{(A\cap C)\,\triangle\,(B\cap C)}(x)&= \chi_{A\cap C}(x)+ \chi_{B\cap C}(x)- 2\chi_{A\cap C}(x) \chi_{B\cap C}(x)=\\[2pt] &=\chi_{A}(x) \chi_{C}(x)+ \chi_{B}(x) \chi_{C}(x)- 2\chi_{A}(x) \chi_{C}(x) \chi_{B}(x) \chi_{C}(x)=\\[2pt] &=\chi_{A}(x) \chi_{C}(x)+ \chi_{B}(x) \chi_{C}(x)- 2\chi_{A}(x) \chi_{B}(x) \chi_{C}(x). \end{aligned}

Характеристические функции левой и правой частей тождества совпадают. Следовательно, тождество верно.




Пример 1.23. Выясним, является ли тождеством следующее выражение:


A \setminus (B \setminus C)= (A \setminus B) \setminus C.

С одной стороны,

\begin{aligned}\chi_{A \setminus (B \setminus C)}(x)&= \chi_{A}(x)- \chi_{A}(x) \chi_{B \setminus C}(x)=\\[2pt] &= \chi_{A}(x)- \chi_{A}(x) \bigl(\chi_{B}(x)- \chi_{B}(x) \chi_{C}(x) \bigr)=\\[2pt] &= \chi_{A}(x)- \chi_{A}(x) \chi_{B}(x)+ \chi_{A}(x) \chi_{B}(x) \chi_{C}(x). \end{aligned}

С другой стороны,

\begin{aligned}\chi_{(A\setminus B)\setminus C}(x)&= \chi_{A\setminus B}(x)- \chi_{A \setminus B}(x) \chi_{C}(x)=\\[2pt] &=\chi_{A}(x)- \chi_{A}(x) \chi_{B}(x)-\bigl(\chi_{A}(x)- \chi_{A}(x) \chi_{B}(x)\bigr) \chi_{C}(x)=\\[2pt] &=\chi_{A}(x)- \chi_{A}(x) \chi_{B}(x)- \chi_{A}(x) \chi_{C}(x)+ \chi_{A}(x) \chi_{B}(x) \chi_{C}(x).\end{aligned}

Легко видеть, что получены разные характеристические функции. Например,при x\in A,~ x\notin B и x\in C имеем


\chi_{A \setminus (B \setminus C)}(x)=1, а \chi_{(A \setminus B)\setminus C}(x)=0.

Таким образом, доказано, что A\setminus (B\setminus C)\ne (A\setminus B)\setminus C.


Отметим, что метод характеристических функций не является универсальным. Так, его нельзя использовать при доказательстве тождеств, содержащих декартово произведение множеств, в частности, тождеств для соответствий (бинарных отношений).

Математический форум (помощь с решением задач, обсуждение вопросов по математике).
Кнопка "Поделиться"

Часовой пояс: UTC + 3 часа [ Летнее время ]


Яндекс.Метрика

Copyright © 2010-2019 MathHelpPlanet.com. All rights reserved