Метасистемный подход в управлении - часть 69

 

275 

   

Если  опустить  свойство 2, то  свойство 1 определяет  класс  ин-

вариантности  реконструктивных  гипотез,  отличающихся  друг  от  друга 
только функциями поведения их элементов. Этот класс инвариантности для 
того,  чтобы  отличать  его  от  отдельных  реконструктивных  гипотез  класса, 
будем  называть  структурой.  Напомним,  что  каждая  отдельная  ре-
конструктивная 

гипотеза 

представляет 

собой 

конкретную 

структурированную  систему.  Таким  образом,  структура - это  свойство 
структурированной  системы,  инвариантное  относительно  изменения 
функций поведения ее элементов. 

Для  данного  множества  переменных,  скажем  множества 

S

,  множество 

структур, представляющих все реконструктивные гипотезы любой обобщен-
ной системы, определенной на 

S

, состоит из семейств подмножеств 

S

, удов-

летворяющих  условиям  неизбыточности  и  покрытия.  Будем  для  удобства 
представлять все множества переменных одной мощности, скажем мощности 

n

,  общим  множеством  структур,  скажем  множеством 

G

n

,  определенным  на 

множестве 

N

n

 положительных целых чисел. Формально для любого 

N

n

∈

 

G

n 

= {

G

i

/

G

i

i

n

G

),

N

(

P

⊂

 удовлетворяет условиям неизбыточности и по-

крытия}. 

В этом формальном определении через 

G

i

 обозначены элементы 

G

n

, яв-

ляющиеся  наиболее  общими  структурами,  рассматриваемыми  при  решении 
задачи реконструкции (некие специальные типы этих структур будут введе-
ны ниже); индекс 

i

 идентифицирует структуры из 

G

n

 и обычно 

|

G

|

n

N

i

∈

.

 

Мно-

жество 

G

n

 

тривиально  интерпретируется  на  языке  любого  множества  пере-

менных 

S

, такого, что |

S

| = 

n

, заданием взаимно однозначного отображения 

переменных  из 

S

  на  целые  из 

N

n

. 

Будем  для  удобства  структуры  из  мно-

жеств 

G

n

 

называть 

G

-структурами. 

Из  некоторых  соображений  удобно  расширить  множество 

G

n 

до 

множества  G

+

n

  всех  обобщенных  реконструктивных  гипотез.  Формально 

для любого n

∈

N 

G

+

n

={G

i

|G

i

i

n

G

),

N

(

P

⊂

 

удовлетворяет условию неизбыточности

}

.  

Несмотря на то, что далее в этой главе основное внимание будет уде-

ляться множествам  

G

n

, все  результаты  относительно 

G

n 

могут быть легко 

обобщены и на множества G

+

n

. 

Если  множество 

G

n

  для  некоторого  определенного 

п 

получает  кон-

кретную интерпретацию в контексте некой обобщенной системы с поведе-
нием с 

п 

переменными, то структуры в 

G

n

 представляют  собой  однознач-

ные  представления    реконструктивных гипотез, связанных с этой обобщен-
ной системой. Это непосредственно следует из того факта, что функции по-
ведения,  соответствующие  любым  подмножествам  переменных,  определя-
ются однозначно как соответствующие проекции обобщенной функции по-
ведения. Следовательно, реконструктивные гипотезы могут изучаться в ви-
де  абстрактных  структур.  Данная  структура  из  G

n 

становится  конкретной 

реконструктивной  гипотезой,  когда  интерпретируется  в  контексте  сравни-
мой с ней определенной обобщенной системы с поведением (то есть систе-
мы с 

п 

переменными). 

 

276 

   

Основным вопросом задачи реконструкции является разработка эффек-

тивных  вычислительных  процедур,  допускающих  представление,  оценку  и 
сравнение  реконструктивных  гипотез,  представленных  всеми  структурами 
для данного множества переменных. Это очень непростая задача, посколь-
ку,  как  будет  показано  ниже  в  этом  разделе,  число  структур  растет  очень 
быстро. Для успешного решения этой задачи необходимо использовать соот-
ветствующее упорядочение и классификацию структур. 

Определим  сначала  естественное  упорядочение  структур,  называемое 

уточняющим  упорядочением. 

Пусть  даны  две  структуры 

G

i

, 

G

j

n

&

∈

 

Будем 

называть 

G

i

 уточнением G

j

 (и, соответственно, 

G

j

 укрупнением 

G

i

) тогда 

и  только  тогда,  когда  для  любого 

x

i

G

∈

 существует 

j

G

y

∈

,  такое,  что 

y

x

⊆

; пусть 

G

i 

≤ 

G

j

 означает, что 

G

i

 это уточнение 

G

j

. 

Рассмотрим две структуры 

G

i

, 

G

j

n

&

∈

, такие, что 

G

i 

≤ 

G

j

. Тогда 

G

i

 

назы-

вается 

непосредственным уточнением G

j

 (a 

G

j

 — 

непосредственным укрупне-

нием 

G

i

 

) 

тогда  и  только  тогда,  когда  не  существует 

G

k

n

&

∈

, 

такого  что 

G

i

n

&

∈

 

и 

G

k 

≤ 

G

j

. Для заданной структуры 

G

i

∈G

n

 структурное соседство 

оп-

ределяется  как  множество  всех  непосредственных  уточнений  и  непосред-
ственных укрупнений 

G

i

 в 

&

п

.

 

Легко видеть, что отношение уточнения определяет частичное упорядо-

чение. Более того, пара ( 

&

п

 ≤ 

) определяет решетку, что подтверждают сле-

дующие факты: 1) существует универсальная верхняя граница — множество 

(N

n

}; 2) 

существует  универсальная  нижняя  граница - множество 

{{

x

}|

n

N

x

∈

}; 3) для  любой  пары 

G

i

, 

G

j

n

&

∈

  

наибольшим  общим  уточне-

нием 

является 

неизбыточный 

эквивалент 

множества 

{

j

i

G

y

,

G

x

|

y

x

∈

∈

∩

}; 4) для  любой  пары 

G

i

, 

G

j

n

&

∈

 

наименьшим  общим 

укрупнением  является  неизбыточный  эквивалент  множества 

j

i

G

G

∩

.  Будем 

называть  эти  решетки 

решетками  уточнения  G

-структур). (по  одной  для 

каждого 

N

n

∈ ). 

Отметим, что уточняющее упорядочение применимо и к 

множествам G

+

n

, что дает решетки 

(&

+

п

,≤ 

). 

Понятно,  что  решетка  уточнения  или  некая  нужная  ее  часть  может 

быть  получена  с  помощью  неоднократного  выполнения  процедуры,  порож-
дающей все непосредственные уточнения для любой структуры из решетки. 
Одна такая процедура определяется следующим образом. 

Уточняющая процедура для G-структур 

(или 

RG-процедура). 

Заданы 

G

-

структуры 

G

i

={

k

S

|

k

∈N

q

}

∈&

n

. 

Для  определения  всех  их непосредственных 

уточнений 

1)  положить 

k 

= 0; 

2)  если 

k<q, 

то 

k+1→k, 

иначе перейти на шаг 5; 

3) 

если    |

k

S| ≥ 2, то    (G

i

-{

k

S})

∪ X→R,   где   X={x|x⊂

k

S, 

|

x

|

 =|

k

S| 

- 1}; иначе перейти на шаг 2; 

4) 

R→Q, 

где Q — неизбыточный аналог 

R, 

записать Q в качестве непо-

средственного уточнения 

G

i

, 

перейти на 2; 

5)  конец. 

 

277 

   

Обратите внимание на то, что условие |

k

S| ≥ 2 из шага 3 обеспечивает 

то, что порождаемые структуры будут удовлетворять условию покрытия; 
замена этого условия на условие |

k

S| ≥ l позволяет работать с множества-

ми &

+

п

 

обобщенных реконструктивных гипотез. Шаг 4 обеспечивает выпол-

нение условия неизбыточности. Тот факт, что наименьшее возможное из-
менение делается на шаге 3, т. е. только один элемент 

G

i

 

изменяется на не-

посредственно  следующие  меньшие  элементы  (подмножества),  обспечивает 
то,  что  порождаемые  структуры  являются  непосредственными  уточнениями 

G

i

. 

Пример  Г.17.  Дано 

G

i

= {

1

S= {1, 2, 3}, 

2

S={2, 3, 4}, 

3

S={ 1 ,   4 } } .  

Сразу  видно,  что  для  всех 

2

3

≥

∈

|

S

|

N

k

k

,   и,  следовательно, 

RG

-процедуры 

применимы  к  любому  элементу.  Таким  образом,  имеются  три  непосредст-
венных уточнения 

G

i

. Множество 

1

S 

заменяется на множества {1, 2}, {1, 

3}, {2, 3}, однако  третье  множество  является  подмножеством  и  будет  ис-
ключено на шаге 4; это даст следующее непосредственное уточнение: 

{{

1, 2

}, {

1, 3

}

,

 {

2, 3, 4

}

,

 {

1, 4

}}

. 

Аналогичная замена 

2

S дает второе непосредственное уточнение: 

{{

1, 2, 3}, {2, 4}, {3, 4}, {1, 4}}. 

Наконец,  множество 

3

S  заменяется  на  множества {1} и {4}, которые 

являются избыточными и будут исключены на шаге 4; отсюда имеем третье 
непосредственное уточнение: 

{

{1, 2, 3}, {2, 3, 4}}. 

Для  сокращения  вычислительной  сложности  порождения  ре-

конструктивных  гипотез  полезно  разбить  решетки  уточнения  на  подходящие 
классы  эквивалентности  по  уровню  вычислений.  Тогда  эти  классы  эквива-
лентности  могут  быть  представлены  соответствующими  каноническими 
структурами, а уточняющие процедуры разработаны для этих канонических 
представлений  разных  уровней  вычислительной  сложности.  Чтобы  проде-
монстрировать этот подход, предположим, что описаны только два уровня вы-
числений, называемые локальным и глобальным. 

Локальный  уровень 

вычислений  представлен  уже  описанной RG-

процедурой.  Для  определения 

глобального  уровня 

вычислений  определим 

функции 

                                             

,

N

n

,

R

G

:

r

n

n

n

∈

→

 

где 

R 

- множество симметричных и рефлексивных бинарных отношений, оп-

ределенных на множестве 

N

n

 

(они также называются отношениями сравне-

ния,  отношениями  толерантности  или  неориентированными  графами  с  цик-
лами), a 

r

n

(G

i

)

 — бинарное отношение,  выполняемое  для  целых 

а 

и 

b (a, 

b

∈N

n

) 

тогда и только тогда, когда и а, и 

b 

принадлежат по крайней мере 

одному из подмножеств 

N

n

, 

входящих в 

G

i

. 

Формально 

                          

}

)

x

b

и

x

a

)(

G

x

(

|

)

b

,

a

{(

)

G

(

r

i

i

n

∈

∈

∈

∃

=

. 

 

278 

   

Будем элементы 

R

n

 называть 

графами. 

Однако мы должны помнить, что 

эти графы не ориентированы (симметричность) и содержат циклы (рефлек-
сивность). Некоторые примеры функций классов 

r

4

 и 

r

5

 

показаны на рисунке 

Г.15. При изображении этих графов опущены тривиальные циклы в узлах. 

                                   

                               

Рисунок Г.15. Примеры функции 

r

п

 

 
Понятно, что функции 

r

п

 

сюръективны, а при n ≥ 3 прообразы могут 

состоять из более чем одного элемента. Поэтому они индуцируют следующее 
отношение  эквивалентности  на  соответствующих  множествах 

G

n

 G-

структур: 

G

i

r

≡G

j

 

тогда  и  только  тогда,  когда 

G

t

, G

j

 

∈G

n

  и 

r

n

(G

i

) 

= 

r

n

(

G

j

) 

для некоторого 

N

n

∈

. Если 

G

i 

= G

j

, то мы говорим, что структуры 

G

i

  

и 

G

j

  

r

-эквивалентны. Для обозначения классов эквивалентности, индуцируемых 

r

п 

на &

п 

, 

будем использовать стандартную запись &

п

/

r

п 

.

 

Для любого 

n

N

n

∈

 множество 

R

п

 

и отношение подмножества (или, ина-

че,  операции  объединения  и  пересечения  множеств)  определяют  булеву  ре-
шетку. Очевидное взаимнооднозначное соответствие между &

п

/

r

п

 

и 

R

п

 

инду-

цирует изоморфную булеву решетку на  множестве 

G

n

/r

n

. 

Этот изоморфизм 

позволяет нам порождать классы эквивалентности на &

п

/

r

п

  

с помощью соот-

ветствующих операций на графах из 

R

п

. При этом, однако, желательно, что-

бы любой класс эквивалентности из &

п

/

r

п

 

был представлен некоей канони-

ческой структурой. С этой целью введем для любого 

N

n

∈

 следующие под-

множества &

n

: 

&

п 

,

 

в которое входят те G-структуры 

G

i

 

из множества &

п

, 

которые состоят 

из максимально сочетаемых классов, соответствующих графу 

r

n

(G

i

) 

или, но 

в  другой  терминологии,  основанных  на  кликах  этого  графа.  Подобные 
структуры  называются  также  полными  покрытиями 

r

n

(G

i

). 

Будем  обозна-

чать  структуры 

C

i

 

из 

G

n

 и называть 

С-структурами. 

Примерами С-структур 

являются структуры 

G

1

 и 

G

2

, изображенные на рисунке Г.15.  

P

n

, в которое входят те G-структуры из &

n

, элементы которых состоят из 

пар,  связанных  на  графе 

r

n

(G

i

)

  узлов  (обозначаемых  целыми  числами),  или 

являются отдельными изолированными узлами. Будем структуры из множе-
ства  &

n

  называть  Р-структурами  и  обозначать  через 

P

k

.  Примером  Р-струк-

туры является структура 

G

4

 на рисунке Г.15. 

Из  этих  определений  и  из  того  факта,  что  множество  всех  максимально 

сочетаемых  классов  для  любого  неориентированного  графа  единственно, 
следует, что любой класс эквивалентности из &

п

/

r

п

 

содержит в точности одну 

 

G

1

           G

2

           r

4

(G

1

)=r

4

(G

2

)