Тема: Разбиение множества на классы. Разбиение множества на классы


Развитие представлений о числе составляет важную часть нашей истории. Оно является одним из основных математических понятий, которое позволяет выразить результаты измерения или счета. Исходным для множества математических теорий служит понятие числа. Оно применяется также в механике, физике, химии, астрономии и множестве других наук. Кроме того, в повседневной жизни мы постоянно пользуемся числами.

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

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

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

Позднее появилась идея считать десятками, а не только единицами. В 100 различных индоевропейских языках названия чисел от двух до десяти сходны, как и названия десятков. Следовательно, очень давно появилось понятие абстрактного числа, еще до того, как языки эти были разделены.

Знание математики Древнего Египта основано сегодня на двух папирусах, которые датируются приблизительно 1700 годом до н. э.

Письменность в Древнем Египте была основана на иероглифах. Пользовались египтяне непозиционной десятичной системой, в которой количеством вертикальных черт обозначались числа от 1 до 9. Индивидуальные символы вводились для степеней десяти. История развития числа в Древнем Египте продолжилась следующим образом. С возникновением папируса было введено иератическое письмо (то есть скоропись). Специальный символ использовался в нем для обозначения чисел от 1 до 9, а также кратных 10, 100 и т. д. Развитие рациональных чисел в то время происходило медленно. Они записывались, как сумма дробей с равным единице числителем.

На использовании различных букв алфавита была основана греческая система счисления. История натуральных чисел в этой стране отмечена тем, что употреблявшаяся с 6-3 веков до н. э. аттическая система для обозначения единицы применяла вертикальную черту, а 5, 10, 100 и т. д. писались с помощью начальных букв их названий на греческом языке. В ионической системе, более поздней, использовались для обозначения чисел 24 действующие буквы алфавита, а также 3 архаические. Как первые 9 чисел (от 1 до 9) обозначались кратные 1000 до 9000, однако перед буквой ставилась при этом вертикальная черта. "М" обозначались десятки тысяч (от греческого слова "мириои"). После нее следовало число, на которое следовало умножить 10000.

В Греции в 3 веке до н. э. возникла числовая система, в которой собственный знак алфавита соответствовал каждой цифре. Греки, начиная с 6 века, в качестве цифр стали использовать первые десять знаков своего алфавита. Именно в этой стране не только активно развивалась история натуральных чисел, но и зародилась математика в современном ее понимании. В других государствах того времени она применялась либо для обыденных нужд, либо для различных магических ритуалов, с помощью которых выясняли волю богов (нумерология, астрология и т. п.).

История счисления в Индии

Многообразны и широки достижения математики в Индии. Эта страна внесла большой вклад в развитие понятия о числе. Именно здесь была изобретена десятичная позиционная система, привычная нам. Индийцы предложили символы для записи 10 цифр, с некоторыми изменениями использующиеся в наши дни повсеместно. Именно в этой стране были заложены также основы десятичной арифметики.

Современные цифры произошли от индийских значков, начертание которых использовалось еще в 1 веке н. э. Изначально индийская нумерация была изысканной. Средства для записи чисел до десяти в пятидесятой степени применялись в санскрите. Сначала для цифр использовалась так называемая "сиро-финикийская" система, а с 6 века до н. э. - "брахми", с отдельными знаками для них. Эти значки, несколько видоизменившись, стали современными цифрами, называемыми сегодня арабскими.

Возникновение понятия натурального числа.

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

Дальнейшее развитие натурального числа произошло в начале семнадцатого века, когда индийские цифры стали известны на Руси. Вплоть до восемнадцатого века использовалась в России славянская нумерация. После этого она была заменена современной.


  1. Виды письменной нумерации.
Развитие счета началось в то время, когда человеку стали знакомые такие формы производства, как охота и рыболовство. Стало необходимым изготавливать орудия для овладения данными производствами. А переместившись в холодные страны, люди стали изготавливать такие предметы орудий труда, которыми легко можно было обработать прочную кожу.

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

Существовал, конечно, и словесный счет, но он стал активен только после того, как развилось сельское хозяйство.

Со временем многие народы стали придумывать наименованиям различные слова, которые и закрепились за числами. Например, если необходимо было обозначить число один, то его обозначали как «нос». «рот», «голова» (тем, что имеется у человека в одном количестве). Соответственно, за числом два закрепились слова «глаза», «руки», «ноги» и т. д.

Пальцевой счет постепенно привел к тому, что счет стал упорядочиваться, а человек, соответственно словесно упрощал числа. Допустим, выражение, которое соответствовало числу 13 – «десять пальцев на обеих ногах и три пальца на одной руке» - упрощалось в «палец на руке»; для выражения числа 26 вместо слов «десять пальцев на обеих ногах, десять пальцев на обеих руках и три пальца на ноге другого человека» говорилось иначе: «три пальца другого человека».

Первым русским памятником математического содержания до настоящего времени считается рукописное сочинение новгородского монаха Кирика, написанное им в 1136 г.

К XVI в. относится изобретение замечательного счетного прибора, получившего впоследствии название «русские счеты».

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


Лекция №7

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

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

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

Любая классификация связана с разбиением некоторого множества объектов на подмножества. При этом считают, что множество Х разбито на классы Х₁, Х₂, …, Х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 натуральных чисел на четыре класса.

Разбиение конечного множества образует любое семейство непустых и непересекающихся подмножеств его элементов, обычно называемых классами, когда каждый элемент является представителем своего класса. Каждый класс однозначно определяет состав его элементов, а порядок перечисления классов разбиений и элементов классов не имеет значения. Различными считаются разбиения, которые отличаются числом классов или составом хотя бы двух классов. Например, существует всего 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) никакие два различные подмножества не содержат общих элементов.

Графическое изображение разбиения множества изображено на рисунке 7.

Множество А разбито на пять классов А1, А2, А3, А4, А5.

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

Пример 1. Будем рассматривать множество учеников школы. Школа состоит из классов: 1, 2, 3, …, 11. Совокупность классов является разбиением, так как объединение учеников всех классов дает множество учеников школы, и никакие два класса не пересекаются: один и тот же ученик не может учиться в двух разных классах.

Отметим, что не всякая система подмножеств данного множества представляет собой разбиение этого множества.

Пример 3. Рассмотрим множество параллелограммов и выделим в нём следующие подмножества: а) прямоугольников, б) ромбов, в) параллелограммов с неравными сторонками и непрямыми углами. Будет ли это разбиением? Нет, потому что квадраты попадают в множество а) и в множество б).

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

При помощи одного свойства осуществляется разбиение множества, вообще, на 2 класса, при помощи двух свойств - на 4 класса, при помощи трех свойств - на 8 классов, при помощи свойств - на классов. В частных случаях может получиться меньше классов, так как некоторые из подмножеств оказываются пустыми.

Еще по теме §5. Разбиение множества на классы:

  1. 1. Понятие множества. Операции над множествами. Отображения. Характеристическая функция множества
  2. 9. Нигде не плотные множества. Понятие категории множеств метрического пространства. Теорема Бэра
  3. Соответствие между множеством выделенных значений и множеством акцентов
  4. 4.3.4 Контрастирование фрагментов и разбиение номера на сегменты
  5. Определение замкнутого множества. Определение компакта. Может ли множество точек на плоскости быть одновременно открытым и замкнутым?


Понравилась статья? Поделитесь с друзьями!