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

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

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

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

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


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

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


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


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


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

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


[math]\chi_2^2(x)=\chi_A(x).[/math]
(1.10)

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


[math]\chi_{A\cap B}(x)= \chi_A(x)\cdot \chi_B(x)[/math]
удовлетворяет этому требованию.

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


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

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


[math]\chi_{\overline{A}}(x)= 1-\chi_A(x).[/math]

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


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

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

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

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


[math]\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}[/math]

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


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

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




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


[math](A\,\triangle\,B)\cap C=(A\cap C)\,\triangle\,(B\cap C)[/math]

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

[math]\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}[/math]

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

[math]\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}[/math]

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




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


[math]A \setminus (B \setminus C)= (A \setminus B) \setminus C.[/math]

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

[math]\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}[/math]

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

[math]\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}[/math]

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


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

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


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


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


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

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