Теоретические основы защиты информации.

=> А=В.

Определение. Для А, BÎSC элемент C=AÅBÎSCназывается наименьшей верхней границей (верхней гранью), если

1) А<С, В<С;

2) A<D, B<DÞC<D

для всех DÎSC.

Элемент AÅB, вообще говоря, может не существовать. Если наименьшая верхняя граница существует, то из антисимметричности следует единственность.

Упражнение. Доказать это.

Определение. Для А, BÎC элемент E=AÄBÎSCназывается наибольшей нижней границей (нижней гранью), если

1) Е<А, Е<В;

2) D<A, D<BÞD<E.

Эта граница также может не существовать. Если она существует, то из антисимметричности следует единственность.

Упражнение. Доказать этот факт.

Определение. (SC, <) называется решеткой, если для любых А, BÎSC существует AÅBÎSC и AÄBÎSC.

Лемма. Для любого набора S={А₁,...,А_n } элементов из решетки SC существуют единственные элементы,:

ÅS=A₁Å...ÅA_n - наименьшая верхняя граница S;

ÄS=A₁Ä...ÄA_n - наибольшая нижняя граница S.

Доказательство. Докажем ассоциативность операции Å.

C₁=(A₁ÅA₂) ÅA3=A1Å(A₂ÅA₃)=C₂.

По определению C₁>A₃, C₁>A₁ÅA₂. Отсюда следует С₁>Аз, С₁>A₂, С₁>А₁. Тогда C₁>A₂ÅA₃, С₁>А₁, cледовательно, С₁>С₂. Аналогично С₂>С₁. Из антисимметричности С₁=С₂.

Отсюда следует существование и единственность ÅS. Такими же рассуждениями доказываем, что существует ÄS и она единственна. Лемма доказана.

Для всех элементов SC в конечных решетках существует верхний элемент High = ÅSC, аналогично существует нижний элемент Low = ÄSC.

Определение. Конечная линейная решетка - это линейно упорядоченное множество, можно всегда считать {0, 1 ,..., n}=SC .

Для большинства встречающихся в теории защиты информации решеток существует представление решетки в виде графа. Рассмотрим корневое дерево на вершинах из конечного множества Х={Х₁, Х₂...Х_n }с корнем в X_i. Пусть на единственном пути, соединяющем вершину X₁ с корнем, есть вершина X_j. Положим по определению, что Х_i<Х_j. Очевидно, что таким образом на дереве определен частичный порядок. Кроме того, для любой пары вершин X_i и X_j существует элемент Х_iÅХ_j, который определяется точкой слияния путей из X_i и X_j в корень. Однако такая структура не является решеткой, т.к. здесь нет нижней грани. Оказывается, что от условия единственности пути в корень можно отказаться, сохраняя при этом свойства частичного порядка и существование верхней