Файл: Алферова, З. В. Математическое обеспечение экономических расчетов с использованием теории графов.pdf

Распознаватель

с логическим

условием

pAq

обозначается на

схеме просто

pq.

Определим понятие эквивалентности операторных схем Янова.

Пусть дана схема G(AU

Л„,

ри

рк). Будем

обозначать

бук­

вой Д с индексом или без

него

упорядоченный

двоичный

набор

значений переменных рх,

рк.

понятие

конфигурации,

Для операторной схемы G определим

строящейся с

помощью процесса

«блуждения»,

задаваемого по

индукции. Сама конфигурация будет получаться

в

виде двойной

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

наборов значений

логических

переменных

Pi, •••> Рк и символов операторов

А\,

Ап,

записываемых

в виде

двух строк: верхней — для

наборов

и нижней — для

операторов.

При построении

конфигурации

основываемся

на некотором

Базис

индукции. В

верхнюю строку записывается

произволь­

ный набор А, нижняя

строка пуста. Движение

по

схеме

G начи­

нается в направлении, указанном входной стрелкой.

Шаг

индукции.

Пусть происходит движение по схеме с набором

Д. Если

стрелка

приводит к распознавателю R(a),

то

вычисляется

а ( Д ) . Если а(Д) = 1, то с тем же набором движение

продолжается

по плюс-стрелке,

выходящей из распознавателя

R.

Если

а ( Д ) = 0 ,

ременных из р\,

рк, которые входят

в сдвиг р оператора Л.

Набор Д' выписывается в верхнюю

строку, конфигурации, и

движение продолжается по стрелке, выходящей из Л.

Если стрелка

приводит к конечному

оператору, то его символ

навателю

станет бесконечным.

При

обнаружении

такого

цикла

движения

искусственно прерывается и в нижнюю строку ставится

символ пустого периода

(

) .

Таким

образом, любая

конкретная

конфигурация

имеет

вид:

Верхняя последовательность

наборов

называется

допустимой

последовательностью 5 наборов для схемы G, нижняя

последова­

тельность операторов называется значением Z схемы G, определяе­

мым допустимой

последовательностью 5.

Поскольку при

построении конфигурации возможен

произвол

(в выборе Ai при

переходе от Д т

к Am+i),

очевидно,

что

правило

ставит в

соответствие каждой схеме G некоторое множество конфи­

гураций

K(G),

являющееся в общем

случае

бесконечным.

Выпишем пример конфигурации для приведенной схемы Янова.

Пусть Д = 10

(где первая переменная

р = \,

а вторая <7 = 0), тогда

пример

конфигурации имеет вид:

10

_

10

10

10

10

10

р

pq

Аг{

)

р

q

Отношение

эквивалентности

определяется

для

любой пары

операторных схем G{ и G2

с одними

и теми же логическими пере­

менными

Pi,

рк-

Схемы

Gi

и

G2

являются

эквивалентными

( G i ^ G 2 ) ,

если

K{Gi)

=K(G2),

т. е. если совпадают

их

множества

конфигураций.

Эквивалентность

схем

обладает

свойствами рефлексивности

и транзитивности.

Как указывалось,

система

правил

преобразований

оператор­

(подграф)

схемы

G, для

которой

указана

ее связь с остальными

вершинами

схемы

G. Эта

связь указывается

в виде выходов и вхо­

дов фрагмента.

Выходы

фрагмента — это

различные

стрелки,

которые

показывают,

какие

вершины

фрагмента

соединены

с остальными

вершинами

схе­

мы.

Входы

фрагмента

— это

различные стрелки, показываю­

щие, к каким вершинам фраг­

мента ведут стрелки от осталь­

ных

вершин

схемы.

Входы

фрагмента могут быть

указаны

также в виде обобщенного вхо­

да,

который

указывает,

к ка­

кой вершине может вести про­

извольная

совокупность

стре­

лок, выходящих либо от ос­

тальных

вершин

схемы,

либо

(если это не запрещается спе­

циальной

оговоркой)

от

выхо­

дов этого же фрагмента. Обоб­

щенные

выходы

указываются

Рис. 15. Пример фрагмента операторной

ж и р

н ы м

и

стрелками.

Входы

с х е м ы

метятся

римскими

цифрами,

выходы — арабскими цифрами.

Пометка двух выходных стрелок одной и той же цифрой

означа­

ет, что обе эти стрелки должны вести к одной и той же

вершине

схемы.

I

- /

О у /

ос

) ~

7

/

г

г

г

Р

/

2

3. Яка/омы распределения

наборов

/

// /

//

I

I

? 9

9)

Ю)

V

8)

я

pvmax№)

p

некоторыми

логическими функциями, представляющими те набо­

ры, которые

могут «проходить»

вдоль

стрелок при

построении

конфигураций схемы. Аксиома

7 носит

служебный

характер,

переносится на выходы распознавателя; при этом

те наборы из ср,

на которых а = 1 , переносятся на плюс-стрелку, а

остальные — на

минус-стрелку. Аксиома 10 утверждает, что если

на вход

опера­

тора А со сдвигом Р попадает множество наборов ср, то оно

порож­

ров из

ф только,

может

быть,

значениями

переменных,

входящих

в сдвиг

Р.

Из

аксиом

распределения

наборов

видно, что

при

пометке

стрелок

схемы

единственным

безусловным

источником

наборов

значений

логических переменных является

входная

стрелка. Ак­

сиома 9 переносит на выходные стрелки лишь

те наборы, которые

поступают на вход распознавателя. Аксиома

10 порождает

лишь

те наборы, которые могут получиться

из

наборов,

поступающих

на вход оператора, применением операции

взятия максимума

(за­

метим,

что max

(0)=0

для любого Р).

Таким

образом, если

в

ре-

р

зультате применения аксиом 7—10 на

стрелке 5,

ведущей

к

не­

которой вершине V операторной схемы, появилось множество набо­

ров ф, то это значит, что каждый из этих

наборов

мог

появиться

на стрелке 5 лишь в результате применения аксиом 7—10

к цепоч­

ке фрагментов

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

шины

V.

Поскольку операторная схема в целом является частным слу­

чаем понятия

фрагмента, рассмотренная

аксиоматика

позволяет

выводить

соотношения

равносильности

для

операторных

схем.

рефлексивным, симметричным и транзитивным.

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

Рефлексивность

следует

из правила

1 при

одинаковых а и р .

Симметричность

следует

из правила 2,

если в

качестве посылки

взять

следующие

соотношения:

F\

~ F2 >

F\ ~ F\ •

F2~F\>

F2~F3

.

откуда по правилу 2 вытекает, что F

i ~ F \ .

ляет

следующая

лемма (правило подстановки): если

Fi~F2,

то

F(Fl)~F(Fa)

•

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

Взяв в правиле 2 в качестве

посылки

f , ~ f a ,

F(Fl)~F(F1)

.

получим, что F(F2)

~ FIF^),

откуда

в

силу симметричности

выте­

кает

утверждение

леммы.

Таким образом, справедлива следующая теорема: любые две

равносильные операторные схемы Янова эквивалентны.

До сих

пор

мы

рассматривали

эквивалентность

операторных

схем

Янова

как

совпадение

множества

всех

конфигураций

этих

ности

схем Янова

[19]. Операторные схемы

Янова G\ и

G2

конеч-

k

но эквивалентны

(Gi~G2),

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

их конечных

конфигу­

раций

совпадают.

Для получения полной системы конечно

эквивалентных

преоб­

разований к полной системе эквивалентных

преобразований до­

знавания конечной

эквивалентности

операторных

схем

может

быть получен

из алгоритма

преобразования любой

операторной

схемы Янова

некоторой

его

модификацией.

§

3. 5.

ЭКВИВАЛЕНТНЫЕ

ПРЕОБРАЗОВАНИЯ

ПРОГРАММ

Система эквивалентных преобразований алгоритмов является

теоретической

основой для

разработки и совершенствования

аппа­

лениях:

а)

с

целью

экономии

памяти;

б)

с

целью

экономии

времени.