Учебно-методический комплекс теоретические основы компьютерной безопасности

любая вершина τ _ik несравнима с любой другой вершиной τ _im того же подмножества² –

τ _ik <> τ _im, k ≠ m;

2. 
   в {τ_i1, τ_i2,…, τ_iL} не содержится полного набора сыновей ни одной из вершин.
   

Множество всех мультирубрик на корневом дереве рубрик будем обозначать T^м (T ^м ∈ T^м).
Покажем, что между рубрикаторными идеалами и мультирубриками имеется взаимно однозначное соответствие.
Для удобства введем несколько вспомогательных определений.
Определение 2.3.18. Порожденным (частичным порядком) множеством будем считать наименьшее множество, содержащее порождающее (исходное) множество и замкнутое относительно операции взятия меньшего.
Пусть M ⊆ T_и. Через < M > обозначим рубрикаторный идеал, порожденный множеством M, т. е. пересечение всех рубрикаторых идеалов, содержащих M. Ясно, что < M > является наименьшим рубрикаторным идеалом, содержащим M.
Определение 2.3.19. Элемент τ рубрикаторного идеала I_Р будем называть максимальным, если для любого τ'∈ I_Р либо τ' ≤ τ, либо τ' и τ несравнимы.
Обозначим через A множество всех максимальных элементов из рубрикаторного идеала I_Р. Тогда по определению 4.18 очевидно, что A является порождающим множеством рубрикаторного идеала I_Р. Заметим, далее, что по определению 4.18 также очевидно, что A состоит из попарно несравнимых элементов. Подобные подмножества будем называть антицепями (в отличие от цепей, образуемых множеством попарно сравнимых элементов).
Очевидна справедливость следующего утверждения.
Лемма 2.3.5. Антицепь, образуемая множеством всех максимальных элементов некоторого рубрикаторного идеала, является мультирубрикой, порождающей соответствующий рубрикаторный идеал.
Таким образом, имеется естественное взаимно однозначное соответствие между мультирубриками и рубрикаторными идеалами. Отметим, что пустой мультирубрике соответствует пустой рубрикаторный идеал. Кроме того, каждой рубрике отвечает одноэлементная мультирубрика, ее содержащая. Для удобства в дальнейшем одноэлементную мультирубрику будем отождествлять с ее единственной рубрикой.
Покажем далее, что на множестве мультирубрик можно построить решетку, эквивалентную решетке рубрикаторных идеалов Λ_и(I_Р, ⊆, ∩,
∪_ир).
С этой целью, прежде всего, введем понятие доминирования мультирубрик.
Определение 2.3.20. Мультирубрика T ^м_i доминирует¹ над мульти-
рубрикой T ^м_j – {τ_j1, τ_j2,…, τ_jJ} ≤ {τ_i1, τ_i2,…, τ_iI} в том и только в том случае, когда для любого m=1,…,J существует k=1,…,I такое, что τ_jm ≤ τ_ik (вершина τ_jm подчинена по корневому дереву вершине τ_ik ):
∀ τjm ∈ T мj , ∃ τik ∈ T мi , τjm ≤ τik .
Легко проверить, что введенное отношение доминирования мультирубрик ≤ рефлексивно, транзитивно и антисимметрично, т. е. является отношением частичного порядка.
В частности, вернувшись еще раз к корневому дереву на рис. 4.7, можно привести следующие примеры доминирования мультирубрик:
{τ₅,τ₆} ≤ {τ₂,τ₃}, {τ₃,τ₅,τ₆} ≤ {τ₂,τ₃}, {τ₇,τ₁₁} ≤ {τ₂,τ₃}, {τ₁₃,τ₁₇} ≤ {τ₇,τ₈},
{τ₁₂,τ₁₉} ≤ {τ₇,τ₈}, {τ₉,τ₁₀,τ₁₃,τ₁₄,τ₁₆,τ₁₈} ≤ {τ₃,τ₄,τ₆}, {τ₁₁,τ₁₂,τ₁₉} ≤ {τ₃,τ₄,τ₆} и т. д.
Справедливо следующее утверждение.
Теорема 2.3.3. Частично упорядоченное относительно отношения включения ⊆ множество рубрикаторных идеалов изоморфно частично упорядоченному по отношению доминирования ≤ множеству мультирубрик иерархического классификатора. Доказательство.
Лемма 2.3.5 определяет биективность отображения I_Рi → T ^м_i. Действительно, разные рубрикаторные идеалы имеют различные наборы максимальных элементов и, следовательно, им соответствуют различные мультирубрики. В свою очередь, различные мультирубрики порождают различные рубрикаторные идеалы.
Пусть для рубрикаторных идеалов I_Рj и I_Рi выполняется I_Рj ⊆ I_Рi. Тогда очевидно для мультирубрик T ^м_j и T ^м_i выполняется условие определения 2.3.20, т. е. T ^м_j ≤ T ^м_i.
Верно и обратное. Пусть мультирубрики сравнимы и T ^м_j ≤ T ^м_i. Тогда для рубрики из набора {τ_j1, τ_j2,…, τ_jJ} найдется рубрика-доминанта в наборе {τ_i1, τ_i2,…, τ_iI}. Отсюда следует, что подмножества, порождаемые рубриками из набора {τ_j1, τ_j2,…, τ_jJ} включаются в подмножества рубрик, порождаемых соответствующими доминантами из набора {τ_i1, τ_i2,…, τ_iI}.
Следовательно, и все множество рубрик рубрикаторного идеала I_Рj входит (является подмножеством) рубрик, составляющих рубрикаторный идеал