Материал: erovenko_va_osnovy_vysshei_matematiki_dlia_filologov

Коммутативный закон показывает, что можно как угодно менять порядок множеств в указанных операциях. Действительно, множества A B

è B A состоят из элементов, принадлежащих хотя бы одному из множеств A èëè B, и не содержат никаких других элементов, а множества

A B è B A состоят из всех элементов, принадлежащих каждому из множеств A è B.

Уместно отметить, что в естественном языке синтаксис, изучающий

соотношения знаков друг с другом, связан с семантикой, изучающей отношение между знаком и смыслом, поэтому даже в некоторых простейших ситуациях перестановка слов может изменить смысл предложения, т. е. свойство «коммутативности» выполняется не всегда.

Пример. Рассмотрим комбинации «красный + желтый» и «желтый + красный» простейшей знаковой системы — светофора. Ïîêà-

жем, что эти комбинации не совпадают друг с другом.

Достаточно сравнить синтаксис указанных комбинаций с семантикой светофора. Комбинации «красный + желтый» соответствует действие «стоять + приготовиться к движению», а комбинации «желтый + красный» соответствует действие «приготовиться к остановке + остановиться».

Замечание. Операция симметрической разности коммутативна:

A B = B A,

а операция разности некоммутативна, т. е.

A \ B B \ A.

Первое утверждение следует из определения симметрической разности, а второе показано на примерах в предыдущем разделе 1.3. Кроме того, на рис. 1.17, 1.18 приведены диаграммы Эйлера – Венна для двух множеств A è B, на которых множествам A \ B è B \ A соответствует заштрихованная часть диаграмм.

2. Законы ассоциативности. Для любых трех множеств A, B и C выполняются свойства ассоциативности для операций объединения и пересечения:

A (B C) = (A B) C, A (B C) = (A B) C.

47

Ассоциативность указанных операций позволяет не фиксировать при помощи скобок порядок, в котором проводятся операции. Действительно, множества A (B C) è (A B) C состоят их всех элементов, входящих хотя бы в одно из множеств A, B è C (заштрихованная часть диаграммы на рис. 1.19) и не содержат никаких других элементов, а множества A (B C) è (A B) C состоят только из общих элементов множеств A, B è C (заштрихованная часть диаграммы на рис. 1.20).

Заметим, что по закону ассоциативности, результат не зависит от порядка действий. Но промежуточные результаты — зависят! Произведение abc можно понимать двояко: (ab)c è a(bc). Произведение abcd можно понимать 5 способами: ((ab)c)d, (a(bc)d), a((bc)d), a(b(cd)) è (ab)(cd). Произведение abcde — 14 способами. Чтобы убедиться в этом, не обязательно их все выписывать. Достаточно заметить, что есть 5 способов вида a(bcde), 2 способа вида (ab)(cde), 2 способа вида (abc)(de) и 5 способов вида (abcd)e. В математике есть специальные числа, позволяющие посчитать количество способов расстановки скобок в произведении n множителей —

ýòî числа Каталана.

Пример. В естественном языке, в некоторых ситуациях, роль скобок играют запятые. Рассмотрим хорошо известный набор слов {казнить,

нельзя, помиловать}.

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

Понятие пересечения множеств используется не только в математике. В рассказе Артура Конан Дойля «Пять апельсиновых зернышек» в сентябре 1887 года знаменитому сыщику Шерлоку Холмсу понадобилось выяснить название одного парусного судна.

Он знал об этом корабле не слишком много: в январе или феврале 1883 года оно было в Пондишери, в январе 1885 года — в Данди, а сейчас стояло в Лондонском порту. Он сравнил три множества: «множество парусни-

48

ков, бывших в указанное время в Пондишери», «множество парусников, бывших в указанное время в Данди» и «множество парусников, находившихся сейчас в Лондоне». Только одно судно входило во все три множества — корабль «Одинокая звезда».

Замечание. Операция симметрической разности ассоциативна:

A (B C) = (A B) C,

а операция разности неассоциативна, ò. å.

A \ (B \ C) (A \ B) \ C.

Ассоциативность симметрической разности не очевидна. Доказательство ассоциативности симметрической разности приведено, например, в книге польских математиков К. Куратовского и А. Мостовского «Теория

множеств».

Отметим только, что симметрическая разность трех множеств A, B è C состоит из элементов, принадлежащих или всем трем множествам A, B è C, или только одному из них (см. ниже диаграмму рис. 1.23), т. е.

A B C = (A B C) [(A \ (B C)) (B \ (C A)) (C \ (A B))].

Утверждение о неассоциативности операции разности множеств в общем случае можно проверить на конкретных примерах. На рис. 1.21 и 1.22 приведены диаграммы Эйлера – Венна для трех множеств A, B è C, на которых множествам A \ (B \ C) è (A \ B) \ C соответствуют заштрихованная часть диаграмм.

В действительности для второго множества, изображенного на рис. 1.22, справедливо равенство (A \ B) \ C = A \ (B C).

В частности, например, из ассоциативности операции симметриче- ской разности и свойства симметрической разности A A = следует, что для произвольных множеств A è B выполняется равенство:

A (A B) = B.

49

Отметим еще раз, что диаграммы Эйлера – Венна иллюстрируют, по-

могают представить и доказать, но сами ничего не доказывают. Покажем это на следующем примере. Выясним, справедливо ли равенство:

Рассмотрим несколько диаграмм Эйлера – Венна для левой и правой части этого равенства. Кроме того, отдельно рассмотрим диаграмму для случая A B C = .

На рис. 1.23 и 1.24 заштрихованная часть диаграмм соответствует ле-

вой и правой части исследуемого равенства ( ), т. е. эти две диаграммы показывают, что это равенство для указанных множеств A, B è C не выполнено. Если рассмотреть частный случай множеств A, B è C, когда, например,

на диаграмме пропадает внутренняя область, т. е. A B C = , êàê íà

рис. 1.25, то тогда рассматриваемое равенство ( ) выполнено. В общем случае справедливо следующее равенство:

(A B C) \ (A B C) = (A B C) \ [(A B) (A C) (B C)].

Мораль проста: при использовании диаграмм Эйлера – Венна необходимо следить за тем, чтобы все составляющие рассматриваемых мно-

жеств были не пусты.

Рассмотрим, как в случае пересечения конечных множеств A, B è C

посчитать число элементов множества A B C. Если просуммировать количество элементов в каждом множестве A, B è C, то согласно диаграмме Эйлера — Венна (см. рис. 1.19), некоторые подмножества при подсчете

будут учтены дважды. Если вычесть число элементов множеств A B, A C è B C, т. е. в наших обозначениях n(A B), n(A C) è n(B C), соответственно из числа элементов n(A B Ñ), то как видно из диаграммы

Эйлера – Венна (см. рис. 1.20) число элементов множества A B Ñ совсем не будет учтено. Поэтому если к указанной разности добавить

n(A B Ñ), то каждый элемент множества A B Ñ будет учтен ровно один раз. Таким образом, получаем следующую формулу:

n(A B Ñ) = n(A) + n(B) + n(Ñ) – n(A B) – n(A Ñ) – n(B Ñ) + n(A B Ñ).

50

В частности, пользуясь этой формулой, можно решить задачу о трех языках, сформулированную в конце раздела 1.1.

Начнем как всегда с обозначений. Пусть A — «множество учащихся, изучающих английский язык», B — «множество учащихся, изучающих немецкий язык», C — «множество учащихся, изучающих французский язык» и U — «множество всех учащихся лицея». Напомним, что n(U) = 100, n(A) = 50,

n(B) = 23, n(C) = 30, n(A B) = 20, n(A C) = 8, n(B C) = 10, n(A B C) = 5. По предыдущей формуле для числа элементов n(A B Ñ) имеем:

n(A B Ñ) = 50 + 23 + 30 – 20 – 8 – 10 + 5 = 70.

Напомним, что в отчете инспектора сказано, что каждый из 100 учащихся изучает хотя бы один из трех языков. Получили противоречие

100 70. Аналогичным образом посчитаем, сколько учащихся согласно отчету инспектора изучают только один немецкий язык?

n(B) – n(A B) – n(B C) + n(A B C) = 23 – 20 – 10 + 5 = –2.

Опять нелепость!

Естественный вывод. Проверка была проведена плохо или совсем не

проводилась, возможно, инспектор неудачно взял произвольные числа.

Поэтому были все основания для его увольнения, как «математиче- ски малограмотного» и профессионально непригодного специалиста.

3. Законы дистрибутивности. При чередовании операций объединения и пересечения для любых трех множеств A, B и C выполняются свойства дистрибутивности одной операции относительно другой:

A (B C) = (A B) (A C), A (B C) = (A B) (A C).

Напомним, что в числовом случае дистрибутивность умножения относительно сложения позволяет выносить общий множитель за скобку и раскрывать скобки. В случае множеств соотношений такого рода больше. На рис. 1.26 приведена диаграмма Эйлера – Венна для трех множеств A, B è C, на которой

множество A (B C) изображено заштрихованной частью соответственно на рис. 1.27 дана графическая иллюстрация для множества A (B C).

51