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

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

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

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

_X²A(x) = _XA(x)    (1.10)

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

_XA∩B(x) = _XA(x)_XB(x)

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

Можно предположить, что характеристическая функция объединения множеств А и В будет равна сумме характеристических функций множеств. Однако так ее определить нельзя, поскольку для элементов х ∈ А ∩ В такая сумма будет иметь значение 2. Введем „поправку" и в результате получим искомую формулу:

_XA∪B(x) = _XA(x)+_XB(х)-_XA(x)_XB(x).

Непосредственно из определения А — дополнения множества А — следует, что

_XА(x) = 1-_XA(x).

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

_XA\B(x) = _XA(x) - _XA(x)_XB(x),

а для симметрической разности А Δ В —

_XAΔB(x) = _XA(x)+_XB(х) - 2_XA(x)_XB(x).

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

_XAΔB(x) = _{X(A∪B)\(A∩B)}(x) =

= _XA∪B(x) - _XA∪B(x)_XA∩B(x) =

= _XA(x) + _XB(x) - _XA(x)_XB(x) -

- (_XA(x) + _XB(x) - _XA(x)_XB(x))_XA(x)_XB(x) =

= _XA(x) + _XB(x) - _XA(x)_XB(x) -

- (_XA(x)_XB(x) + _XA(x)_XB(x) - _XA(x)_XB(x)) =

= _XA(x) + _XB(x) _ 2_XA(x)_XB(x).

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

_XAΔB(x) = (_XA(x) - _XB(x))².

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

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

(А Δ В) ∩ С = (А ∩ С)Δ(В ∩ С).

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

_X(AΔB)∩C(x) = XAΔBXC(x) =

= (_XA(x) + _XB(x) - 2_XA(x)_XB(x)_XC(x)) =

= _XA(x)sub>XC(x) + sub>XB(x)sub>XC(x) - 2_XA(x)_XB(x)_XC(x).

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

_{X(A∩C)Δ(B∩C)}(x) =

= _XA∩C(x) + _XB∩C(x) - 2_XA∩C(x)_XB∩C(x) =

= _XA(x)_XC(x) + _XB(x)_XC(x) - 2_XA(x)_XC(x)_XB(x)_XC(x) =

= _XA(x)_XC(x) + _XB(x)_XC(x) - 2_XA(x)_XB(x)_XC(x).

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

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

А\(В\С) = (А\В)\С.

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

_XA\(B\C)(x) = _XA(x) - _XA(x)_XB\C(x) =

= _XA(x) - _XA(x)(_XB(x) - _XB(x)_XC(x)) =

= _XA(x) - _XA(x)_XB(x) + _XA(x)_XB(x)_XC(x).

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

_X(A\B)\C(x) = _XA\B(x) - _XA\B(x)_XAC(x) =

= _XA(x) - _XA(x)_XB(x) - (_XA(x) - _XA(x)_XB(x))_XC(x) =

= _XA(x) - _XA(x)_XB(x) - _XA(x)_XC(x) + _XA(x)_XB(x)_XC(x).

Легко видеть, что получены разные характеристические функции. Например, при х ∈ А, х ∉ В и х ∈ С _XA\(B\C)(x) = 1, а _X(A\B)\C(x) = 0. Таким образом, доказано, что А \ (В \ С) ≠ (А \ В) \ С. #

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