Треп о математике 2

Sergei Nickolaev написал(а) к All в Mar 23 15:08:08 по местному времени:

Привет, All!

Немного о конечных множествах.
Прежде, чем заниматься обобщением понятия количества элементов на бесконечные множества, поразбираемся с конечными. Чтобы было, что обобщать :-)

Есть весьма изящное соотношение количеств элементов в конечных множествах, в их объединии и пересечениях. Количество элементов в конечном множестве A будем обозначать |A|.
Для двух множеств: |A1 U A2| = |A1| + |A2| - |A1 П A2|
Обоснование очень простое: Если пересечение множеств непусто, то сложив количества элементов обоих множеств, мы посчитаем элементы пересечения дважды (лишнее - вычитаем).
Для трех множеств:
|A1 U A2 U A3| = |A1| + |A2| + |A3| -
|A1 П A2| - |A1 П A3| - |A2 П A3| +
|A1 П A2 П A3|
Можно обосновать похожим образом, но рассуждения несколько более сложные.
Формула обобщается на случай произвольного числа множеств: пересечения четных количеств множеств учитываются со знаком минус, нечетных - со знаком плюс.
Легко доказывается по индукции (оставляю в качестве задачки).

Есть другой способ доказательства, займемся им, потому, что он привлекает новое, очень полезное понятие: характеристическая функция подмножества.

Рассматриваем случай, когда все множества A1, ... An, входящие в выражение, являются подмножествами одного множества W, назовем его универсальным. Это не уменьшает общности, в качестве такого годится, например, объединение множеств A1,...An или любое более "широкое" множество.
Характеристическая функция подмножества Ai - это функция определенная на множестве W, принимающая значение 1 на элементах Ai и значение 0 на элементах W, которые не являются элементами Ai.
Операциям объединения и пересечения подмножеств соответствуют некоторые операции над их характеристическими функциями. Пересечению подмножеств соответствует произведение характеристических функций. С объединением не столь просто, но разобраться можно :-).
Добавим еще одну операцию - дополнение. Содержательно это те элементы, которые нужно добавить к подмножеству, чтобы получить универсальное множество W (то есть W \ Ai).
Характеристическую функцию буду записывать, указывая подмножество в квадратных скобках (принято записывать как нижний индекс, но здесь не получается).

Для пересечения A1 П A2: X[A1 П A2](u) = X[A1](u) * X[A2](u).
Для дополнения: X[W \ A1](u) = 1 - X[A1](u).

Есть замечательное утверждение (оставляется как задача):
Объединение нескольких подмножеств равно дополнению пересечений дополнений этих подмножеств.
Рассуждение на самом деле несложное, чтобы увидеть в чем дело можно взять диаграмму Венна для 3-х множеств (A1, A2, A3), нарисовать вокруг нее круг (он будет обозначать универсальное множество W). Найти на получившейся диаграмме дополнения к трем множествам A1, ... A3, увидеть их пересечение и будет понятно, почему дополнение к этому пересечению - объединение A1, ... A3.

Характеристическая функция объединения теперь получается такая:
X[A1 U A2 U ... U An](u) = 1 - (1 - X[A1](u))(1 - X[A2](u))*...(1 - X[An](u))

Если в правой части раскрыть скобки, единица сократится, останутся характеристические функции для всех Ai (с плюсом), попарные произведения функций (с минусом), произведения по 3 (с плюсом) и так далее. В точности как в формуле для количества элементов объединения. Остается сообразить, что количество элементов подмножества равно количеству 1 в значениях характеристической функции подмножества (другими словами - сумме значений характеристической функции по всем элементам универсального множества).

Кто разберется в этой технической штучке - хорошо, нет - основные идеи дальнейшего эта неудача понять не помешает. Можно помочь себе картинками. Взять W = {0,1,2,3,4,5,6}; A1={1,2,3}; A2={2,3,4}; A3={3,4,5}. Нарисовать эти точки на оси X, построить графики для характеристических функций (удобно использовать разные цвета). Скорее всего, по этой картинке идею доказательства можно понять без особых вычислений :-)

Самое важное насчет количества элементов конечных множеств: для выявления равенства количества элементов в двух множествах вовсе не обязательно пересчитывать элементы. Вместо этого можно построить взаимно-однозначное соответствие между элементами этих множеств. То есть, каждому элементу первого множества сопоставить ровно один элемент второго (каждому - свой отдельный) и наоборот. Если есть такое соответствие - число элементов в этих множествах равно. Это - основная идея для обобщения понятия числа элементов на бесконечные множества (об этом уже в другой раз). И полезная идея для решения некоторых задач :-)

Еще: количество элементов конечного множества называется также мощностью этого множества. Для общности терминологии для конечных и бесконечных множеств.

Вообще, задачи подсчета числа элементов в конечных множествах относятся к разделу математики, который называется комбинаторика. Но лезть в нее мне не хочется, там, в основном - техника. Идеи - интереснее :-)

Задачки:

1. На окружности выбраны 1000 белых точек и одна чёрная. Чего больше - треугольников с вершинами в белых точках или четырёхугольников, у которых одна вершина чёрная, а остальные три белые?

2. Докажите, что последовательностей длины n, составленных из нулей и единиц, столько же, сколько подмножеств у множества {1, 2, . . . , n}.

3. Пусть W - непустое конечное множество. Докажите, что подмножеств множества W, имеющих чётную мощность, столько же, сколько имеющих нечётную мощность.

4. Докажите, что способов расстановки скобок (указывающих порядок действий) в неассоциативном произведении из n элементов столько же, сколько способов разбить выпуклый (n + 1)-угольник на треугольники непересекающимися диагоналями. (Для произведения трёх множителей есть два варианта (ab)c и a(bc); с другой стороны, есть два способа разрезать четырёхугольник на два треугольника, проведя диагональ.
Для произведения четырёх сомножителей и для пятиугольника имеется по 5 вариантов.)

С уважением - Sergei
--- GoldED+/W32-MINGW 1.1.5-b20120519 (Kubik 3.0)