Понятие разбиения множества на классы с помощью одного, двух, трех свойств

Понятия множества и операций над множествами позволяют уточнить наше представление о классификации – действии распределения объектов по классам.

Классификацию мы выполняем достаточно часто. Так, натуральные числа представляем как два класса – четные и нечетные. Углы на плоскости разбиваем на три класса: прямые, острые и тупые.

Любая классификация связана с разбиением некоторого множества объектов на подмножества. При этом считают, что множество Х разбито на классы Х₁, Х₂, …, Хn,…, если:

1) подмножества Х₁, Х₂, …, Хn,… попарно не пересекаются;

2) объединение подмножеств Х₁, Х₂, …, Хn, … совпадает с множеством Х.

Если не выполнено хотя бы одно из условий, классификацию считают неправильной. Например, если из множества Х треугольников выделить подмножества равнобедренных, равносторонних и разносторонних треугольников, то разбиения мы не получим, поскольку подмножества равнобедренных и равносторонних треугольников пересекаются (все равносторонние треугольники являются равнобедренными). В данном случае не выполнено первое условие разбиения множества на классы.

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

Рассмотрим, например, множество натуральных чисел. Его элементы обладают различными свойствами. Положим,. что нас интересуют числа, обладающие свойством «быть кратным 3». Это свойство позволяет выделить из множества натуральных чисел подмножество, состоящее из чисел, кратных 3. Тогда про остальные натуральные числа можно сказать, что они не кратны 3, т.е. получаем еще одно подмножество множества натуральных чисел. Так как выделенные подмножества не пересекаются, а их объединение совпадает с множеством натуральных чисел, то имеем разбиение этого множества на два класса.

Вообще, если на множестве Х задано одно свойство, то это множество разбивается на два класса. Первый – это класс объектов, обладающий этим свойством, а второй – дополнение первого класса до множества Х. Во втором классе содержатся такие объекты множества Х, которые заданным свойством не обладают. Такую классификацию называют дихотомической .

Рассмотрим ситуацию, когда для элементов множества заданы два свойства. Например, «быть кратным 3» и «быть кратным 5». При помощи этих свойств из множества натуральных чисел можно выделить два подмножества: А – подмножество чисел, кратных 3, и В – подмножество чисел, кратных 5. Эти множества пересекаются, но ни одно из них не является подмножеством другого. Проанализируем получившийся рисунок (справа). Конечно, разбиения множества натуральных чисел на подмножества А и В не произошло. Но круг, изображающий множество N, можно рассматривать как состоящий из четырех непересекающихся областей – на рисунке они пронумерованы. Каждая область изображает некоторое подмножество множества N. Подмножество I состоит из чисел, кратных 3 и 5; подмножество II – из чисел, кратных 3 и не кратных 5; подмножество III – из чисел, кратных 5 и не кратных 3; подмножество IY – из чисел, не кратных 3 и не кратных 5. Объединение этих четырех подмножеств есть множество N.

Таким образом, выделение двух свойств привело к разбиению множества N натуральных чисел на четыре класса.

Понятие множества и операций над множествами позволяют уточнить наше представление о классификации.

Классификация - это действие распределения объектов по классам на основании сходств объектов внутри класса и их отличия от объектов других классов.

Любая классификация связана с расчленением некоторого множества объектов на подмножества. Если при этом каждый элемент данного множества попадает в одно и только одно подмножество, а объединение всех выделенных подмножеств совпадает со всем множеством, то говорят, что данное множество разбито на непересекающиеся подмножества или классы.

Считается, что множество X разбито на классы X 1 , X 2 ,..., Х n , если:

1) подмножества X 1 , Х 2 ,..., Х n попарно не пересекаются;

2) объединение подмножеств Х 1 , Х 2 , ..., Х n совпадает с множеством X.
Если не выполнено хотя бы одно из этих условий, классификацию считают

неправильной.

Так, множество X треугольников можно разбить на три класса: остроугольные, тупоугольные и прямоугольные. Выделенные подмножества попарно не пересекаются и их объединение совпадает с подмножеством X.

Однако не всякая система подмножеств данного множества представляет собой разбиение этого множества. Так, если из множества X треугольников выделить подмножества равнобедренных, равносторонних и разносторонних, то разбиения множества X на классы мы не получим, т.к. множества равнобедренных и равносторонних треугольников пересекаются.

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

Рассмотрим множество натуральных чисел. Его элементы обладают различными свойствами. Среди натуральных чисел есть четные, нечетные, кратные трем, кратные пяти и т.д. Предположим, что нас интересуют натуральные числа, обладающие свойством делится на три. Это свойство позволяет выделить из множества натуральных чисел подмножество чисел, кратных 3. Тогда про остальные натуральные числа можно сказать, что они не кратны 3, т.е. получаем еще одно подмножество множества натуральных чисел. Данные подмножества не пересекаются, а их объединение совпадает с множеством N натуральных чисел.

Т.о., Задание одного свойства элементов множества натуральных чисел привело к разбиению этого множества на два класса: класс чисел, кратных 3, и класс чисел кратных 3.

А каким будет разбиение множества на классы, если для его элементов указать два свойства, т.е. выделить из множества два различных подмножества?

Рассмотрим два свойства натуральных чисел: «быть кратным 3» и «быть кратным 5». При помощи этих свойств из множества натуральных чисел можно выделить два подмножества: А - подмножество чисел, кратных 3, и В -подмножество чисел, кратных 5. Эти подмножества пересекаются, но ни одно из них не является подмножеством другого.

Выделение двух свойств натуральных чисел привело к изменению множества натуральных чисел на 4 класса: класс чисел, кратных 3 и 5; класс чисел, кратных 3 и не кратных 5; класс чисел, кратных 5 и не кратных 3;.класс чисел, не кратных 3 и не кратных 5.

Не следует думать, что задание двух свойств элементов множества приводит к разбиению этого множества именно на 4 класса. Так бывает не всегда. Например, при помощи двух свойств «быть прямоугольным» и «быть тупоугольным» множество треугольников разбивается на три класса: класс прямоугольных треугольников; класс тупоугольных треугольников; класс треугольников, не являющихся ни прямоугольными, ни тупоугольными треугольниками.

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

Классификация - это действие распределения объектов по классам на основании сходств внутри класса и их отличия от других объектов. Классификация широко применяется в математике.

Например, натуральные числа делятся на четные и нечетные; углы бывают острые, тупые и прямые и т.д.

Любая классификация связана с разбиением некоторого множества объектов на подмножества.

Считают, что множество Х разбито на классы Х , Х ,…, Х , если:

1) подмножества Х , Х,…, Х попарно не пересекаются;

2) объединение этих подмножеств совпадает с множеством Х.

Если не выполнено хотя бы одно из этих условий, классификацию считают неправильной.

Например: а) Множество треугольников Х разбито на три класса: остроугольные, прямоугольные и тупоугольные. Действительно, выделенные подмножества попарно не пересекаются, а их объединение совпадает с множеством Х; b) Из множества треугольников Х выделили подмножества равнобедренных, равносторонних и разносторонних треугольников. Так как множества равнобедренных и равносторонних треугольников пересекаются, значит, не выполнено первое условие классификации, и разбиения множества Х на классы мы не получили.

Рассмотрим, например, множество натуральных чисел. Его элементы обладают различными свойствами. Нас интересуют числа со свойством «быть кратным 3 ». Это свойство позволяет выделить из множества N подмножество, состоящее из чисел, кратных 3 . Тогда про остальные натуральные числа можно сказать, что они не кратны 3 , т.е. получаем еще одно подмножество множества N . Так как выделенные подмножества не пересекаются, а их объединение совпадает с множеством N , то имеем разбиение данного множества на два класса.

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

Рассмотрим ситуацию, когда для элементов множества заданы два свойства. Например, свойства натуральных чисел: «быть кратным 3» и «быть кратным 5». При помощи этих свойств из множества N можно выделить два подмножества: А - множество чисел, кратных 3 и В - множество чисел, кратных 5. Эти множества пересекаются, но ни одно из них не является подмножеством другого (рис. 13). Разбиения на подмножества А и В в данном случае на произошло. Но круг, изображающий множество N , можно рассматривать как состоящий из четырех непересекающихся областей. Каждая область изображает некоторое подмножество множество N . Множество I состоит из чисел, кратных 3 и 5, множество I - из чисел, кратных 3 и не кратных 5, множество III - из чисел, кратных 5 и не кратных 3, множество IV - из чисел, не кратных 3 и не кратных 5. Объединение этих четырех множеств есть множество N.

Таким образом, выделение двух свойств привело к разбиению множества N натуральных чисел на четыре класса.

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

на три класса (рис. 14): I - класс чисел, кратных 6; II - класс чисел, кратных 3, но не кратных 6; III - класс чисел, не кратных 3.

Разбиение конечного множества образует любое семейство непустых и непересекающихся подмножеств его элементов, обычно называемых классами, когда каждый элемент является представителем своего класса. Каждый класс однозначно определяет состав его элементов, а порядок перечисления классов разбиений и элементов классов не имеет значения. Различными считаются разбиения, которые отличаются числом классов или составом хотя бы двух классов. Например, существует всего 5 различных разбиений трехэлементного множества {X,Y,Z} на классы. Эти разбиения перечислены ниже в таком порядке, когда число их классов не убывает:

{ {X,Y,Z} }; { {X,Y}, {Z} }; { {X,Z}, {Y} }; { {X}, {Y,Z} }; { {X}, {Y},{Z} }.

Если зафиксировать количество классов, то в общем случае число разбиений множества из n элементов на m классов при любых n ≥ m ≥ 0 оказывается соответствующим по значениям для чисел Стирлинга второго рода . Формально эти числа определяют коэффициенты разложения степени n произвольной переменной Z по убывающим m -факториалам от Z при всех целых значениях m от 0 до n :

Z n = (Z) 0 + (Z) 1 + ... + (Z) m + ... + (Z) n .

В этом разложении фигурные коэффициенты обозначают числа Стирлинга второго рода, а убывающие факториалы, перед которыми они стоят, определяют следующие произведения:

(Z) m = Z(Z−1)(Z−2) … (Z−m+1).

Учитывая выражение для убывающих факториалов, указанное разложение, например при n=3 можно записать следующим образом:

Z 3 = + Z + Z(Z - 1) + Z (Z - 1)(Z - 2).

Равенство левой и правой частей этого разложения, очевидно, будет достигнуто при следующих значениях коэффициентов, заданных соответствующими числами Стирлинга второго рода:

0 ; = 1 ; = 3 ; = 1 ;

В общем случае значения чисел Стирлинга второго рода при любых целых величинах n≥m≥0 можно записать в форме бесконечной нижнетреугольной матрицы, которая называется треугольником Стирлинга второго рода . Его начальный фрагмент, например, при 0≤n,m≤8 можно представить следующей таблицей:

Таблица 1

n										...
0	1	0	0	0	0	0	0	0	0	...
1	0	1	0	0	0	0	0	0	0	...
2	0	1	1	0	0	0	0	0	0	...
3	0	1	3	1	0	0	0	0	0	...
4	0	1	7	6	1	0	0	0	0	...
5	0	1	15	25	10	1	0	0	0	...
6	0	1	31	90	65	15	1	0	0	...
7	0	1	63	301	350	140	21	1	0	...
8	0	1	127	966	1701	1050	266	28	1	...
...	...	...	...	...	...	...	...	...	...	...

По своей структуре эта таблица похожа на треугольник Паскаля. Ее внутренние элементы определяются по следующему мнемоническому правилу. Каждое число в любой строке n>0 и столбце m>0 равно сумме числа слева над ним и непосредственно над ним, которое умножено на m . Это правило иллюстрирует следующий пример для n=3 и m=2 :

2 = 1 + 2∙1 = 3 .

В общем случае данное правило формально отражает следующее рекуррентное соотношение, которое справедливо для любых натуральных значений n≥m>0 :

Граничные условия для этого рекуррентного соотношения определяют следующие значения чисел Стирлинга второго рода при m=0 и m=n :

0 ; = 1 ; = 1.

2 = + + 2 = 0 + 1 + 2∙1 = 3 .

N(n - 1)2 и = 2 n-1 - 1 .

Следующий пример показывает, как с их помощью найти значение числа Стирлинга второго рода при n=6 и m=4 более коротким путем, чем по базовому рекуррентному соотношению:

4 = + 3 + 4= (2 4-1 - 1) + 34(4 - 1)2 + 45(5 -1)2 = 65.

Как отмечалось выше, числа Стирлинга второго рода дают мощность множества разбиений n элементов на фиксированное число классов m≤n . Общее число всех разбиений n элементов без ограничения по числу классов определяется числом Белла , значение которого равно следующей сумме чисел Стирлинга второго рода:

B n = + ... + + ... +

Принимая величину B 0 = 1 , для вычисления значений чисел Белла можно использовать также следующую рекуррентную зависимость с биномиальными коэффициентами:

B n = B 0 + B 1 + ... + B k + ... + B n

Результаты рекуррентных вычислений чисел Белла для всех значений n от 0 до 10 приведены в следующей таблице:

Таблица 2

n	0	1	2	3	4	5	6	7	8	9	10
B n	1	1	2	5	15	52	203	877	4140	21147	115975

Из таблицы значений чисел Белла следует, что мощность множества разбиений быстро растет с увеличением количества элементов. Поэтому для решения разнообразных практических задач необходимо иметь комбинаторные алгоритмы, которые обеспечивают систематический перебор разбиений конечных множеств элементов любой мощности. По ряду причин перебор разбиений целесообразно производить в порядке минимального изменения состава их классов, когда любые 2 последовательных разбиения отличаются расположением только одного элемента в их классах. Очевидно, такое изменение следует считать минимальным. Например, в следующей последовательности все 5 разбиений множества {X,Y,Z} перечислены в порядке минимального изменения, а элементы, которые при этом переходят в другой класс, выделены подчеркиванием:

{ {X,Y,Z } }; { {X,Y }, {Z} }; { {X}, {Y}, {Z } }; { {X} {Y,Z } }; { {X,Z} {Y} }.

Для генерации разбиений в порядке минимального изменения были разработаны рекурсивный и итерационный алгоритмы, которые напоминают аналогичные методы транспозиции смежных элементов для перестановок. Они ориентированы на обработку любого множества натуральных чисел от 1 до n и обеспечивают систематическое перечисление всех его разбиений в порядке минимального изменения. При этом классы разбиений обычно упорядочивают по возрастанию величин своих минимальных элементов. С учетом указанного порядка перечисления классов, последовательность разбиений, например, числового множества {1,2,3} , которую формируют алгоритмы минимального изменения, имеет следующий вид:

{ {1,2,3} }; { {1,2}, {3} }; { {1}, {2}, {3} }; { {1} {2,3} }; { {1,3} {2} }.

В рекурсивном алгоритме минимального изменения такая последовательность, в общем случае, строится по следующему рекуррентному правилу. Пусть уже получен список всех разбиений множества из (n−1) натуральных чисел от 1 до (n−1) , где классы упорядочены по возрастанию своих наименьших элементов, а любые последовательные разбиения минимально различны, в указанном выше смысле. Каждое разбиение этого списка дополняется одноэлементным классом {n} , а его классы дополняются элементом n . Причем указанные дополнения для нечетных по номеру разбиений производятся в порядке возрастания минимальных элементов классов и заканчиваются добавлением одноэлементного класса. Для четных по номеру разбиений такие же дополнения производятся в обратном порядке. В результате этой обработки получается уже список разбиений множества из n натуральных чисел, где все классы по-прежнему остаются упорядоченны по возрастанию своих наименьших элементов, а любые два соседних разбиения отличаются только расположением элемента n и, следовательно, минимально различны. Следующая диаграмма демонстрирует пример рассмотренного рекурсивного процесса, который начинается с одноэлементного множества {1} и завершается списком разбиений множества из трех чисел {1,2,3} . Для наглядности разбиения каждого уровня пронумерованы, а добавленные элементы выделены подчеркиванием, кроме того, стрелки указывают направление добавлений:

Для практической реализации рекурсивного алгоритма минимального изменения удобно задать каждое разбиение вектором наименьших элементов его классов. Тогда в общем случае любое разбиение множества последовательных натуральных чисел от 1 до n представляется вектором E(n) из n значений, где каждое значение E j обозначает наименьший элемент класса, которому принадлежит элемент j . Такое соответствие можно формально задать следующим образом:

E j = min i | E j = E i ; j = 1, ... n .

Для примера в следующей таблице перечислены все 5 последовательных разбиения множества {1,2,3} и соответствующие им векторы наименьших элементов их классов E(3) :

Таблица 3

1	2	3	4	5
{1 2 3}	{1 2} {3}	{1} {2} {3}	{1} {2 3}	{1 3} {2}
(1 1 1 2 1 3)	(1 1 1 2 3 3)	(1 1 2 2 3 3)	(1 1 2 2 2 3)	(1 1 2 2 1 3)

В соответствие с рекурсивным алгоритмом каждый вектор наименьших элементов E(n) классов разбиения множества из n элементов расширяет соответствующий вектор E(n−1) значением E n для добавленного элемента n . При этом нужно последовательно присвоить E n все различные значения из вектора E(n−1) , которые равны по величине своим индексам (j=E j) и n . Для нечетных по номеру векторов E(n−1) такое присваивание делается в порядке возрастания индексов, что соответствует увеличению значений наименьших элементов классов разбиения, и завершается присваиванием E n = n :

E n = E j | E j = j = 1, … n.

Например, вектор E(3) = (1,2,1) , который соответствует разбиению { {1,3}, {2} } , с нечетным порядковым номером 5 расширяется в следующие различные варианты вектора E(4) , образуя соответствующие им разбиения множества {1,2,3,4} :

E(3) = (1 ̲ 1 2 2 1 3) + (E4 = 1 1) −> (1 1 2 2 1 3 1 4) = E(4) ~ Ё;

E(3) = (1 1 2̲ 2 1 3) + (E4 = 2 2) −> (1 1 2 2 1 3 2 4) = E(4) ~ { {1 3} {2 4} };

E(3) = (1 1 2 2 1 3) + (E4 = 4) −> (1 1 2 2 1 3 4 4) = E(4) ~ { {1 3} {2} {4} }.

Для четных по номеру векторов E(n−1) дополнение производится аналогично, но в порядке уменьшения значений наименьших элементов классов, и начинается присваиванием E n = n :

E n = E j | E j = j = n, … 1.

Например, вектор E(3)=(1,2,2) , который соответствует разбиению { {1}, {2 3} } , с четным порядковым номером 4 расширяется в следующие различные варианты вектора E(4) , образуя соответствующие им разбиения множества {1,2,3,4} :

E(3) = (1 1 2 2 1 3) + (E4 = 1 1) −> (1 1 2 2 1 3 1 4) = E(4) ~ { {1} {2 3} {4} };

E(3) = (1 1 2̲ 2 1 3) + (E4 = 2 2) −> (1 1 2 2 1 3 2 4) = E(4) ~ { {1} {2 3 4} };

E(3) = (1̲ 1 2 2 1 3) + (E4 = 4) −> (1 1 2 2 1 3 4 4) = E(4) ~ { {1 4} {2 3} }.

Несмотря на простоту, рассмотренный рекурсивный алгоритм нельзя признать экономичным, так как приходится последовательно порождать разбиения всех множеств с мощностями от 1 до n , хотя требуется получить разбиение только множества из n элементов. В этом отношении более привлекательным представляется итерационный алгоритм минимального изменения разбиений, который реализует систематический переход элементов между классами. При этом на каждой итерации очередное разбиение образуется из предыдущего переходом одного элемента в соседний класс слева или справа, если считать, что классы упорядочены по возрастанию значений своих наименьших элементов. Такой переход может изменять состав классов при сохранении их числа и приводить к удалению или образованию одноэлементного класса. В любом случае разбиения двух соседних итераций отличаются расположением только одного элемента в своих классах и, следовательно, минимально различны. В частности, следующая последовательность переходов элементов обеспечивает перечисление разбиений множества {1,2,3} в порядке минимального изменения, а стрелки указывают направление перехода элементов между классами:

{ { 1 2 ->3} }; { { 1 ->2}, { 3 } }; { {1}, { ->2}, {3} }; { {1} { 2 <-3 } }; { {1 3} {2} }.

В общем случае для систематической организации итерационного процесса важно установить правила перехода. Они должны обеспечивать выбор направления, элемента и классов перехода на каждой итерации при генерации разбиений любого множества последовательных чисел от 1 до n. Для формального описания этих правил удобно, как и раньше, задавать каждое разбиение вектором (E 1 ,…E j, …,E n) наименьших элементов его классов, где:

E j = min i | E j = E i .

Для получения последующих разбиений на каждой итерации необходимо сначала выбрать для перехода наибольший по значению элемент m , который допустимо передвинуть вправо или влево в зависимости от установленного для него текущего направления перехода. Очевидно, переход влево любого элемента ограничен классом с наименьшим элементом 1 , который сам не может быть влево или вправо. Переход вправо любого элемента j>1 ограничен классом, где он сам является наименьшим элементом. Поэтому правило выбора наименьшего элемента m для перехода на каждой итерации можно формально записать следующим образом:

m = max j | (E ←j > 1 или E →j < j).

Для удобства практической реализации этого правила целесообразно ввести знаковую функцию d(j) кодирования направления перехода каждого элемента j . Она должна принимать значение +1 или −1 при переходе элемента j вправо или влево, соответственно. Тогда в правиле выбора переходного элемента m можно исключить альтернативную проверку направления перехода и записать его следующим образом:

Em должно быть выполнено следующее соотношение:

t < E m ≤ m.

Если для выбранного элемента m установлено направление перехода вправо, то возможны два случая. В одном случае элемент m переходит в соседний справа класс, где наименьший элемент меньше, чем m . В другом случае, когда наименьший элемент соседнего справа класса больше, чем m , или элемент m принадлежит крайнему правому классу разбиения, из m должен быть образован одноэлементный класс {m} .

Оба указанных случая учитывает следующее формальное правило, которое идентифицирует наименьший элемент t класса, куда попадет элемент m после перехода вправо:

t = min { m; E (j > m) | E j > E m }.

Очевидно, что при переходе элемента m вправо, между значениями t , m и E m должно быть выполнено следующее соотношение:

E m < t ≤ m.

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

t = min { m; E j | d(m)∙E j > d(m)∙E m }.

Независимо от способа идентификации формальный переход выбранного элемента m в класс с наименьшим элементом t обеспечивает следующее присваивание:

E m <− t .

В результате образуется очередное разбиение, которое отличается от разбиения предыдущей итерации только по составу двух классам, откуда и куда был передвинут элемент m . При этом в векторе наименьших элементов классов изменяется только значение E m . Очевидно, что такое изменение разбиения является минимальным. Аналогичные итерации нужно продолжать до получения конечного разбиения, где для перехода формально выбирается элемент m=1 , потому что все остальные элементы j>1 уже достигли своих крайних классов по установленному для них направлению перехода. Такое разбиение можно формально записать следующим образом:

d(→j)∙E j = j или d(←j)∙E j = −1 при j = 1, …, n .

Выполнение итераций рассмотренного итерационного алгоритма иллюстрируется в следующей таблице, где последовательные разбиения множества чисел {1,2,3} записаны в традиционном и векторном формате, а стрелки и знаки индексов обозначают направления перехода элементов:

Таблица 4

{ →1 →2 →3̲ }	{ →1 →2̲ } { →3 }	{ →1 →} { 2 } { →3̲ }	{ →1 } { →2 →3̲ }	{ →1 →3 } { →2 }
(1 1 1 2 1 3̲)	(1 1 1 2̱̲ 1 3)	(1 1 1 2 1 -3̲)	(1 1 1 2 1 -3̲)	(1 1 1 2 1 -3)

Понятие множества и операций над множествами позволяют уточнить наше представление о классификации.

Любая классификация связана с разбиением некоторого множества объектов на подмножества.

Определение . Множество А разбито на классы А 1 , А 2 , ..., А п , если:

1) подмножества А 1 , А 2 , ..., А п не пусты;

2) подмножества А 1 , А 2 , ..., А п попарно не пересекаются;

3) объединение подмножеств совпадает с множеством А .

Если не выполнено хотя бы одно свойство, то классификацию считают неправильной.

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

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

Пример 1 . Пусть А – множество двузначных чисел. Рассмотрим на этом множестве свойство «быть четным».

А 2

А 1

Множество А разбилось на два подмножества:

А 1 – множество четных чисел,

А 2 – множество нечетных чисел, при этом

А 1 È А 2 = А и А 1 Ç А 2 = Æ.

Т.о. задание одного свойства приводит к разбиению этого множества на 2 класса.

Пример 2. Пусть А – множество треугольников. Рассмотрим на данном множестве два свойства: «быть прямоугольным» и «быть равнобедренным». При помощи этих свойств из множества треугольников можно выделить 2 подмножества: В С – множество равнобедренных треугольников. Эти множества пересекаются, но ни одно из них не является подмножеством другого.

По рисунку видно, что получилось 4 класса:

I – В Ç С – множество равнобедренных прямоугольных треугольников;

II – В Ç – множество прямоугольных, но не равнобедренных треугольников;

III – Ç С – множество равнобедренных, но не прямоугольных треугольников;

IV – Ç – множество не равнобедренных и не прямоугольных треугольников.

Т.о. с помощью двух свойств множество разбилось на 4 класса, таких, что их пересечение пусто, а их объединение составляет множество А .

Следует отметить, что задание двух свойств приводит к разбиению множества на 4 класса не всегда.

Пример 3 . Пусть А – множество треугольников. Рассмотрим на данном множестве два свойства: «быть прямоугольным» и «быть остроугольным». При помощи этих свойств из множества треугольников можно выделить 2 подмножества: В – множество прямоугольных треугольников и С – множество остроугольных треугольников. Эти множества не пересекаются. По рисунку видно, что при помощи этих свойств множество треугольников разбивается на три класса:

I – множество прямоугольных треугольников;

II – множество остроугольных треугольников;

III – множество не прямоугольных, не остроугольных треугольников.

Контрольные вопросы

1. При каких условиях считают, что множество разбито на классы?

2. Как определить число элементов в объединении двух или трех конечных множеств?