18.11. Теорема

Пусть даны:

• согласованная система ВС

  SVS = <T, SH, COM, SEL, VS>

• фрейм FRAME её дерева T на выделенных вершинах

  {ndI1 .. ndIJ .. ndIK .. ndIL .. ndN1 .. ndNJ .. ndNK .. ndNL } = ND

• сопряженные с указанными

  ndI1 .. ndIJ .. ndIK .. ndIL .. ndN1 .. ndNJ .. ndNK .. ndNL

  ВС

  vsI1 .. vsIJ .. vsIK .. vsIL .. vsN1 .. vsNJ .. vsNK .. vsNL

• принадлежащие

  vsI1 .. vsIJ .. vsIK .. vsIL .. vsN1 .. vsNJ .. vsNK .. vsNL

  множества состояний

  SI1 .. SIJ .. SIK .. SIL .. SN1 .. SNJ .. SNK .. SNL

  такие, что порожденные от них множества

  S◎I1 .. S◎IJ .. S◎IK .. S◎IL .. S◎N1 .. S◎NJ .. S◎NK .. S◎NL

  из ВС vs0, сопряженной с головной вершиной nd0 фрейма, принадлежат разным каналам nd0:

  • каналу с ключом kI соответствуют множества состояний S◎I1 .. S◎IJ .. S◎IK .. S◎IL, порожденные от SI1 .. SIJ .. SIK .. SIL

    …

  • каналу с ключом kN соответствуют множества состояний .. S◎N1 .. S◎NJ .. S◎NK .. S◎NL, порожденные от .. SN1 .. SNJ .. SNK .. SNL

  а значит, сами SI1 .. SIJ .. SIK .. SIL .. SN1 .. SNJ .. SNK .. SNL находятся в отношении ЛИБО

• головная ячейка из фрейма FRAME

  c = <nd0, ndI, .. , ndN>

  такая, что:

  • вершинам ndI .. ndN подчинены листья фрейма

    ndI подчинены листья ndI1 .. ndIJ .. ndIK .. ndIL

    ..

    ndN подчинены листья ndN1 .. ndNJ .. ndNK .. ndNL

  • ndI .. ndN являются корнями фреймов, построенных на множествах вершин ND1 .. NDN, которые являются непересекающимися подмножествами множества ND:

    FRAME1 построен на множестве вершин {ndI1 .. ndIJ .. ndIK .. ndIL} = ND1 ⊂ ND

    …

    FRAMEN построен на множестве вершин {ndN1 .. ndNJ .. ndNK .. ndNL} = NDN ⊂ ND

Тогда

• в vsI множества состояний S⚪I1 .. S⚪IJ .. S⚪IK .. S⚪IL, порожденные от множеств состояний SI1 .. SIJ .. SIK .. SIL также не пересекаются, принадлежа разным каналам ndI (неважно, ЛИБО- или И-типа)
…
• в vsN множества состояний S⚪N1 .. S⚪NJ .. S⚪NK .. S⚪NL, порожденные от множеств состояний SN1 .. SNJ .. SNK .. SNL также не пересекаются, принадлежа разным каналам ndN (неважно, ЛИБО- или И-типа)

Доказательство

от противного очевидно – если бы хоть два любых таких множества пересекались , то пересекались бы и порожденные от них множества из ВС vs0.

Следовательно, на ячейке c можно построить в зависимости от типа узла nd0 ЛИБО- или И-ЛИБО-ячейку

c⋓ = <nd0, ndI, .. , ndN, {s01⚪}, .. , {s0N⚪}, {s1⚪}, .. , {sN⚪}, k1, .. , kN>

c⋓ = <nd0, ndI, .. , ndN, S◎I1 ⋃..⋃ S◎IL .. S◎N1 ⋃..⋃ S◎NL, S⚪I1 ⋃..⋃ S⚪IL .. S⚪N1 ⋃..⋃ S⚪NL, k1, .. , kN>

█

Назад Вперёд