Алгебра множеств (алгебра Кантора)

Алгебра Кантора: <B(I),U,I,–>. Носителем ее является булеан универсального множества I, сигнатурой – операции объединения U, пересечения I и дополнения –[9].

Для операций алгебры Кантора выполняются следующие законы:

1) коммутативности объединения и пересечения:

М_аUМ_b=М_bUМ_а, М_аIМ_b=М_bIМ_а;

2) ассоциативности объединения и пересечения:

М_аU(М_b U М_с)=(М_аUМ_b)UМ_с, М_аI(М_bIМ_с)=(М_аIМ_b)IМ_с;

3) дистрибутивности пересечения относительно объединения и объединения относительно пересечения:

М_аI(М_bUМ_с)=(М_аIМ_b)U(М_аIМ_с),

М_аU(М_bIМ_с)=(М_аUМ_b)I(М_аUМ_с),

причем последнее соотношение не имеет аналога в обычной алгебре;

4) идемпотентности объединения и пересечения:

М_аUМ_а=М_а, М_аIМ_а=М_а,

поэтому в алгебре Кантора нет ни степеней, ни коэффициентов;

5) де Моргана:

, ;

6) двойного дополнения:

.

Выполнимы также следующие действия с универсальным I и пустым Æ множествами:

7) МUÆ=М, МIÆ=Æ, МUI=I, МII=М, , .

Все эти соотношения могут быть доказаны с использованием кругов Эйлера. Видны двойственность соотношений: они справедливы как относительно объединения, так и относительно пересечения.

Рассмотрим дополнительные законы:

8) склеивания:

9) поглощения:

МU(МIА)=М;

10) Порецкого – по фамилии российского логика, математика и астронома, профессора Казанского университета Платона Сергеевича Порецкого (1846-1907 гг.):

.

Алгебра Кантора по аддитивной операции объединения и мультипликативной операции пересечения является абелевой полугруппой, так как для этих операций выполняются законы коммутативности и ассоциативности, но она не является группой, поскольку уравнения М_аUХ=М_b, М_аIХ=М_b не имеют решения, например, для случая, когда множества не пересекаются: М_аIМ_b=Æ [9]. Поэтому алгебра Кантора по двухместным операциям I и U не является кольцом. Эта алгебра принадлежит к другому классу фундаментальных алгебр – к классу решеток.

3 Задание множеств конституентами

Формула алгебры множеств, представляющая собой пересечение, в которое входят по одному разу все множества (со знаками дополнения или без дополнений) на данном универсуме, называется конституентой единицы [9]. Формула, представляющая собой объединение, в которое входят по одному разу все множества (со знаками дополнения или без дополнений) на данном универсуме, называется конституентой нуля. Каждое множество, за исключением пустого, может быть задано объединением конституент единицы. Каждое множество за исключением универсального может быть задано пересечением конституент нуля. Рассмотрим задание множества путем указания его конституент единицы. Пусть на некотором универсуме рассматриваются два взаимно пересекающихся множества: А и В.

Зададим их графически с помощью диаграмм Эйлера (рис. 9).

Рис. 9. Диаграмма Эйлера для двух взаимно пересекающихся

множеств А и В на универсуме I

Тогда каждый из четырех сегментов (четырех «кусочков») этой диаграммы может быть закодирован конституентой, содержащей символы А и В:

– сегмент 00 – не А и не В;

– сегмент 10 – А, но не В;

– сегмент 01 – не А и В;

– сегмент 11 – А и В.

В таком случае, заданное множество можно закодировать двоичным кодом в соответствии с тем, входят ли в него указанные конституенты (табл. 4):

Таблица 4

Задание множества А двоичным числом

11	10	01	00
23	22	21	20
1	1	0	0

Множество А закодировано двоичным числом 1100. Этому двоичному числу соответствует десятичное число 12.

При таком задании множеств легко выполняются операции над ними. Например, получим пересечение множества №12 и множества №5. Результатом будет множество №4. Действительно, результат пересечения – множество, в котором при его двоичном представлении, имеются единицы в разрядах, соответствующих совпадениям единиц в исходных множествах (табл. 5).

Таблица 5

Пересечение множеств №12 и №5

1	1	0	0	№12
0	1	0	1	№5
0	1	0	0	№4=(№12)I(№5)

4 Основные понятия комбинаторики

Основная задача комбинаторики, как раздела дискретной математики, – пересчет и перечисление элементов в конечных множествах [24].

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

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

При этом под решением задачи оптимизации «в сильном смысле» понимается нахождение всех элементов минимизирующих (максимизирующих) целевую функцию, а под решением задачи оптимизации «в слабом смысле» – нахождение единственного произвольного элемента [24].

Рассмотрим основополагающие правила комбинаторики – правила суммы и произведения.

Пусть Х – конечное множество, состоящее из n элементов х. Тогда говорят, что элемент х из Х может быть выбран n способами и пишут |Х|=n. Эта запись совпадает с записью мощности множества Х.

Пусть Х₁,...,Х_k – попарно непересекающиеся множества, т.е. Х_iIХ_j=Æ, i¹j.

Очевидно, что в этом случае

.

Таково комбинаторное правило суммы. Для k=2 оно формулируется следующим образом. Если объект х может быть выбран n способами из множества Х, а объект y из непересекающегося с ним множества Y, – другими m способами, то выбор «х или y» может быть осуществлен n+m способами.

Правило произведения для k=2 формулируется следующим образом. Если объект х может быть выбран n способами и после каждого из таких выборов объект y в свою очередь может быть выбран m способами, то выбор упорядоченной пары – вектора (х,y) может быть осуществлен n×m способами.

Например, Х:{x₁,x₂}, Y:{y₁,y₂}.

Тогда упорядоченные пары (x,y) описываются декартовым произведением

X×Y={(x₁,y₁),(x₁,y₂),(x₂,y₁),(x₂,y₂)}.

Выбор упорядоченной последовательности из k объектов вектора (х₁,х₂,...,х_k) может быть осуществлен n₁·n₂·...·n_k способами, где n_i – число способов выбора i-го объекта х_i, i меняется от 1 до k (записывается: ).

В частности, если все n_i равны, что может быть, например, в случае, когда элементы принадлежат одному и тому же множеству, т.е. рассматривается декартово произведение Х^k, то число способов равно n^k.

Набор элементов х_i1,...,x_ik из множества Х={x₁,...,x_n} (вектор) называется выборкой (комбинацией) объема k из n элементов или, иначе, (n,k) выборкой.

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

Если порядок следования элементов не является существенным, то такая выборка называется неупорядоченной.

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

5 Размещения

Упорядоченная (n,k) выборка, в которой элементы могут повторяться, называется (n,k) размещением с повторениями.

Иными словами размещениями с повторениями из n элементов по k называют векторы длины k, составленные из n элементов множества Х.

Число размещений с повторениями из n элементов по k определяется оценкой соответствующего декартова произведения Х^k n-элементного множества, обозначается (по-видимому от английского слова Assing – назначать) и вычисляется следующим образом:

=n^k.

Таким образом, первый элемент вектора длины k выбирается n способами, второй – n способами и т.д.: n×n×...×n=n^k.

Пример. Сколькими способами можно оснастить две различные фирмы компьютерами трех типов?

Каждый способ оснащения есть выборка (3,2), вектор длины 2, составленный из 3-х элементного множества типов Т={t₁,t₂,t₃}. Поэтому число способов оснащения – число размещений с повторениями из 3 по 2:

.

Рассмотрим подробнее:

1) (t₁,t₁); 2) (t₁,t₂); 3) (t₁,t₃);

4) (t₂,t₂); 5) (t₂,t₃); 6) (t₂,t₁);

7) (t₃,t₃); 8) (t₃,t₂); 9) (t₃,t₁).

Получили различные упорядочения двухэлементных векторов из 3-х элементного множества, т.е. множество Т².

Здесь каждый вектор соответствует способу оснащения. Видно, что, например, (t₁,t₂), (t₂,t₁) считаются разными способами, так как фирмы предполагаются различными («первая – первым типом», «вторая – вторым» и т.д.). Имеются повторения: (t₁,t₁), (t₂,t₂), (t₃,t₃).

В ряде задач необходимо определить число векторов длины k из n элементов данного множества без повторения элементов.

Если элементы упорядоченной (n,k) выборки попарно различны, то они называются (n,k) размещением без повторений или просто (n,k) размещением.

Число таких размещений без повторений обозначается .

Каждое (n,k) размещение без повторения является упорядоченной последовательностью длины k, элементы которой попарно различны и выбираются из множества с n элементами. Тогда первый элемент этой последовательности может быть выбран n способами, после каждого выбора первого элемента последовательности второй элемент может быть выбран n-1 способами и т.д., k-й элемент выбирается n-(k-1) способом:

=(n-1)(n-2)...[n-(k-1)].

Преобразуем эту формулу, умножая и деля ее на произведение чисел 1×2×××(n-k):

В частности, при k=0 . Очевидно, что при k>n =0.

Пример. Сколькими способами из 3-х студентов можно назначить группу на прополку клубники в составе начальника и подчиненного?

Речь идет о выборе упорядоченных двухэлементных подмножеств множества студентов, состоящего из трех элементов (K={1,2,3}), т.е. о размещениях без повторений из 3 элементов по 2, поэтому:

.

Подробнее, в виде векторов из номеров студентов, например, по журнальному списку, первая компонента которого обозначает номер студента-начальника, вторая – подчиненного:

(1,2), (1,3), (2,1), (2,3), (3,1), (3,2).

Ясно, что здесь существенен порядок следования компонент и не может быть повторений (один студент не может быть начальником и подчиненным одновременно), поэтому это множество – подмножество декартового произведения.

Пример. Сколькими способами можно провести распределение 10 механизаторов по 3 сушильным установкам? Один механизатор назначается на одну сушильную установку.

Распределение механизаторов – размещение без повторений из 10 элементов по 3, поэтому:

.

6 Перестановки

Рассмотрим различные упорядочения n элементного множества Х (вектора длины n, составленные из n элементного множества). В отличие от декартова произведения, полученные при этом векторы, отличаются лишь порядком следования элементов и называются перестановками без повторений из n элементов. Число перестановок без повторений из n элементов обозначается P_n. К перестановкам без повторений можно прийти, полагая, что осуществляется размещение без повторений из n элементов по n:

Считается, что 0!=1.

Пример. Сколько существует возможных последовательностей выполнения проверок финансовой деятельности трех подразделений?

Требуется получить число перестановок без повторений из трех элементов, т.е. Р₃=3!=6.

Получим все эти последовательности:

(1,2,3), (1,3,2), (2,3,1), (2,1,3), (3,1,2), (3,2,1).

Пример. Сколько можно составить пятизначных шифров-чисел, не кратных 5, из цифр 1,2,3,4,5 без повторений цифр?

Всего из пяти цифр можно составить Р₅=5!=120 пятизначных шифров-чисел, но они будут включать и кратные 5. Сколько будет шифров кратных 5? Из данного набора чисел кратными 5 могут быть числа, содержащие 5 в младшем разряде. Если цифру 5 записать в младшем разряде, то остальные цифры 1,2,3,4 можно распределить по разрядам Р₄=4!=24 способами. Таким образом, число пятизначных шифров из чисел 1,2,3,4,5 без повторения чисел и не кратных 5 будет 120-24=96.

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

По аналогии при наличии одинаковых компонент в некотором векторе получаем задачу оценки так называемых перестановок с повторениями данного состава [23].

Рассмотрим вначале пример: сколько различных последовательностей – кодов можно получить, переставляя цифры в числе 010, т.е. векторов длины k=3 из 2-х элементного множества В={0,1}, содержащих два нуля.

Имеется всего три разряда, которые обозначим р₁, р₂, р₃. Их можно переставить р₃=3!=6 способами. Запишем различные получаемые сочетания разрядов и соответствующие коды:

Видно, что коды повторяются тогда, когда несущественен порядок следования разрядов с одинаковой цифрой 0 (р₁,р₃). Все это соответствует тому факту, что имеется два способа (2!) перестановки этих разрядов (р₁,р₃), (р₃,р₁) без изменения кода, т.е. неповторяющихся кодов будет меньше во столько раз, сколько имеется способов перестановки повторяющихся разрядов.

Рассмотрим более сложный случай.

Сколько различных «слов», не обязательно имеющих смысл, можно получить, переставляя буквы в слове «кишмиш»?

Здесь шесть букв слова можно переставить друг с другом р₆=6!=720 способами, но в данном слове буквы «и» и «ш» повторяются дважды и при их перестановке слова могут повторяться. Сколько же существует вариантов перестановок этих букв без изменения слова? Первый вариант – исходный, второй – поменять местами буквы «и», третий – поменять местами буквы «ш», четвертый – поменять местами как буквы «и», так и буквы «ш». Всего четыре варианта. С учетом того, что эти четыре варианта участвуют в порождении 720 способов, получим 720/4=180 различных «слов». Можно показать, что число раз, во сколько уменьшается количество слов по сравнению с числом перестановок без повторений, представляет собой произведение факториалов количества повторяющихся букв.

Таким образом, если из n элементов множества Х={x₁,x₂,...,x_n} составлен вектор V длины k, причем каждому i-му компоненту можно поставить в соответствие число k_i, указывающее его число повторений в V, то задан вектор S=(k₁,k₂,...,k_n), который называется составом данного вектора.

Так, для Х={0,1,2,3} и V=(010223), состав: S=(2,1,2,1).

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

Общая формула числа перестановок с повторениями данного состава имеет вид

Р(k₁,k₂,...,k_n)= .

Пример. Сколько различных кодовых последовательностей можно получить перестановками кода 102202030?

Такому вектору, составленному из элементов множеств {0,1,2,3} соответствует вектор состава (1,4,3,1), поэтому число различных кодовых комбинаций определяется как число перестановок с повторениями этого состава

Р(1,4,3,1)= .

7 Сочетания

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

В результате получают так называемые сочетания без повторения.

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

Число сочетаний без повторений из n элементов по k, обозначаемое как определяется, исходя из числа размещений без повторений с учетом того, что различных неупорядоченных векторов (подмножеств исходного множества) будет меньше в число раз, соответствующее числу перестановок без повторений из k элементов:

.

Пример. Определить число двухэлементных подмножеств множества, состоящего из трех элементов. Перечисляем все двухэлементные подмножества множества Х={х₁,х₂,х₃}:

{х₁,х₂},{х₁,х₃},{х₂,х₃}.

Здесь мы имеем дело с сочетаниями из 3-х по 2:

.

Это величина в 2! раза меньше, чем число размещений из , поскольку компоненты двухэлементных векторов можно переставить Р₂=2! способами.

Пример. Сколькими способами можно выбрать 3 различных комбайна из 5 имеющихся?

Число размещений из 5 по 3 без повторений: =5×4×3=60.

Один и тот же набор комбайнов можно получить различными способами, например, векторы (а,b,с) и (b,а,с) дают один и тот же набор. Поскольку три элемента можно переставить Р₃=3!=6 способами, то число способов выбора различных 3 комбайнов равно

.

В ряде комбинаторных задач требуется подсчитывать число различных составов векторов длины k из n элементного множества. Такие векторы-составы называются сочетаниями с повторениями из n элементов по k.

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

Получаем сочетания с повторениями из 2 элементов по 3:

(m₁,m₁,m₁),(m₁,m₂,m₂),(m₁,m₁,m₂),(m₂,m₂,m₂),

где m означает тип комплекса.

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

Определение числа сочетаний с повторениями можно произвести следующим образом [24].

Каждому сочетанию с повторениями из 2 по 3 ставится в однозначное соответствие вектор длины n+k-1=2+3-1=4, состоящий из 3 нулей и n-1=1 единицы:

Количество комплексов 1-го типа	Разделитель	Количество комплексов 2-го типа	Состав вектора бригады
000	1		(m1,m1,m1)
0	1	00	(m1,m2,m2)
00	1	0	(m1,m1,m2)
	1	000	(m2,m2,m2)

В таком случае число сочетаний с повторениями, которое обозначается , равно числу перестановок с повторениями данного состава (вектор имеет одну единицу и три нуля), т.е. Р(3,1)= =4.

В общем случае, это выражение имеет вид

,

что соответствует выражению

.

Например, требуется составить подразделения из 6 рабочих 4 специальностей и определить количество способов формирования таких подразделений.

Получаем сочетания с повторениями из 4-х элементов по 6:

.

8

Бином Ньютона. Треугольник Паскаля.