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

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

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

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

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

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

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

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

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

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

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

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

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

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

а для симметрической разности [cbm]A\,\triangle\,B[/cbm] -
[cbm]\chi_{A\,\triangle\,B}(x)= \chi_A(x)+\chi_B(x)- 2\chi_A(x)\cdot \chi_B(x).[/cbm]

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

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

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

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

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


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

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

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

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

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

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

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


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

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

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

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

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

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

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

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

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

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

Источник

Поделитесь с другими:

Если материал понравился Вам и оказался для Вас полезным, поделитесь им со своими друзьями!

Читать по теме:

Интересные статьи: