Понятие комплекта. Основные определения и характеристики комплектов. Способы записи комплектов.

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

Если в теории множеств основным понятием явл. отношение включения, то в теории комплектов это ф-ция числа экземпляров: #(x, B).

Членство. Элемент х явл. членом комплекта В, если #(x, B) > 0. Обозначается x Î B. Если же #(x, B) = 0, то x Ï В.

Мощность. Мощность есть общее число экземпляров элементов в комплекте: .

Включение и равенство. Комплект А есть подкомплект комплекта В (обозн. А Í В), если #(x, А) £ #(x, B) для всех х. Два комплекта равны, если #(x, А) = #(x, B) для всех х. Комплект А строго включён в комплект В, если А Í В и А ¹ В. Ахтунг!!! Из строго включения отнюдь не следует, что #(x, А) < #(x, B), хотя |A| < |B|.

Способы записи комплектов:

1. В = { a, a, a, a, b, b, b, c }.

2. В = { n_B(x) · x: x Î S, n_B(x) Î Z⁺ }

3. B = { x^Bx: x Î S, B_x = n_B(x) Î Z⁺ }

S – это домен, т.е. конечный алфавит символов: множество, над которым задаётся комплект.

Пространство комплектов. Определим область S как множество элементов, из которых составляются комплекты (домен). Пространство комплектов Sⁿ есть множество всех таких комплектов, что их элементы принадлежат S, и ни один элемент не входит в комплект более n раз.

Множество S^¥ есть множество всех комплектов над доменом S без каких-л. ограничений на число экземпляров элемента в комплекте.

Характеристическая ф-ция комплекта.

Из приведённого ниже следует, что комплект может и не включать все символы домена:

"S "B_i Î Sⁿ "x Î B_i [ 0 £ #(x, B) £ n ].

Основные характеристики комплектов, не описанные ранее:

/В/ = dim B = – размерность комплекта.

supp B = { x: x Î S & #(x, B) > 0 } – опроное множество комплекта.

htg B = max( #(x_i, B) ) – высота комплекта.

x* Î B: #(x*, B) = htg B – пиковое значение комплекта.
9. Алгебра над комплектами. Одноместные, двуместные, многоместные операции. Носители результатов выполнения операций. Свойства операций.

//Обозначение для краткости: #_A <=> #(x, A)

1. A È B = { #_{A È B} · x: #_{A È B} = Max(#_A, #_B) }

2. A Ç B = { #_{A Ç B} · x: #_{A Ç B} = Min(#_A, #_B) }

3. A + B = { #_{A + B} · x: #_{A + B} = #_A + #_B }

4. Разность: A – B = { #_{A – B} · x: #_{A – B} = Max(#_A – #_B, 0) } =
= { #_{A – B} · x: #_{A – B} = #_A – #_{A Ç B} }

5. Симметрическая разность: A D B = { #_{A D B} · x: #_{A D B} = |#_A – #_B| }

#_{A D B} = Max(#_A, #_B) – Min(#_A, #_B). Д-во: по определению модуля.

6. Арифм. произведение: AB = { #_AB · x: #_AB = #_A * #_B }

7. Репродукция: kA = { #_kA · x: #_kA = k * #_A & k Î Z⁺ }

8. Прямое произведение: A x B = { #_{A x B} (<x_i x_j>) · (<x_ix_j>): #_{A x B}(<x_i x_j>) = #_A(x_i) * #_B(x_j),
где x_i Î A; x_j Î B }

По кол-ву операндов операции делятся на:

1. унарные (репродукция)

supp(kA) = supp(A)

2. бинарные (–, D)

supp(A – B) Ê supp(A) \ supp(B)

supp(A D B) Ê supp(A) \ supp(B)

3. многоместные (Ç, È, +, х, *)

supp(A Ç B) = supp(A) Ç supp(B)

supp(A È B) = supp(A) È supp(B)

supp(AB) = supp(A) Ç supp(B)

supp(A x B) = supp(A) x supp(B)