9.22. Теорема

Пусть даны две ВС VS1 и VS2 с деревьями сборки T1 и T2.

Если эти VS1 и VS2 имеют произведение VS с ключами k1, … , kM

VS = (VS1 × VS2)k1, … ,kM

то и её состояния связаны между собой отношением ЛИБО, то есть для него существует некоторое дерево сборки T0.

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

• состояния одного такого канала являются между собой ЛИБО-связанными согласно лемме 8.8, то есть, для S1j и S2j существуют некие деревья сборки T1j и T2j.
• существует произведение sj = s1j × s2j между любыми двумя состояниями s1j ∈ S1j и s2j ∈ S2j

Для произвольного ключа kj и соответствующих ему каналов S1j и S2j определим дерево сборки Tj следующим образом: к каждому листу одного из этих деревьев подсоединим в качестве поддерева другое.

В этом случае такое композитное дерево сборки определяет множество ЛИБО-связанных состояний, каждое из которых является произведением некоторого состояния s1j ∈ S1j и некоторого s2j ∈ S2j, причем каждая такая пара состояний участвует в таком произведении sj = s1j × s2j для каждого kj (j = 1..M), а сами s1j и s2j имеют kj в качестве своей проекции по определению произведения.

А теперь объединим в одно искомое дерево T0 все указанные Tj дугами, размеченными ключами kj.

Такое дерево сборки не изменяет состояния, образованные в каждом из Tj, поскольку, как только что было указано, kj является проекцией каждого sj ∈ Sj в Tj. █

Назад Вперёд