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


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


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

1) Е<А, Е<В;

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

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

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

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

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

ÅS=A1Å...ÅAn - наименьшая верхняя граница S;

ÄS=A1Ä...ÄAn - наибольшая нижняя граница S.

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

C1=(A1ÅA2) ÅA3=A1Å(A2ÅA3)=C2.

По определению C1>A3, C1>A1ÅA2. Отсюда следует С1>Аз, С1>A2, С1>А1. Тогда C1>A2ÅA3, С1>А1, cледовательно, С1>С2. Аналогично С2>С1. Из антисимметричности С1=С2.

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

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

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

Для большинства встречающихся в теории защиты информации решеток существует представление решетки в виде графа. Рассмотрим корневое дерево на вершинах из конечного множества Х={Х1, Х2...Хn }с корнем в Xi. Пусть на единственном пути, соединяющем вершину X1 с корнем, есть вершина Xj. Положим по определению, что Хi<Хj. Очевидно, что таким образом на дереве определен частичный порядок. Кроме того, для любой пары вершин Xi и Xj существует элемент ХiÅХj, который определяется точкой слияния путей из Xi и Xj в корень. Однако такая структура не является решеткой, т.к. здесь нет нижней грани. Оказывается, что от условия единственности пути в корень можно отказаться, сохраняя при этом свойства частичного порядка и существование верхней грани.


Начало  Назад  Вперед



Книжный магазин