Автор неизвестен - Бионика интелекта информация язык интеллект№ 3 (77) 2011научно-технический журналоснован в октябре 1967 г - страница 23

Страницы:
1  2  3  4  5  6  7  8  9  10  11  12  13  14  15  16  17  18  19  20  21  22  23  24  25  26  27  28  29  30  31  32  33  34  35  36  37  38  39  40  41  42  43  44  45  46  47  48  49  50  51  52  53  54  55  56  57  58  59  60  61  62  63  64  65  66  67  68  69  70  71  72  73  74  75  76  77 

22

xx

12

y11 = 1, (x12 © x22) v x12x22

x22)~       = 1.

Сравнивая систему (ж) с уравнением (в), ви­дим, что в результате преобразования выражений, полученных вторым методом, мы пришли в дан­ном примере к более компактному результату, чем тот, который был достигнут на базе первого метода (11 узнаваний буквы против 26). Правда, систему (ж) можно считать полным описанием заданного алфавитного оператора только при условии при­соединения к ней системы уравнений (а), а это до­бавляет еще 12 узнаваний букв. Заметим, что без предварительного перехода к описанию алфавит­ного оператора F системой уравнений было бы за­труднительно перейти от уравнения (в) к системе (ж). Таким образом, использование второго мето­да неявного представления алфавитного операто­ра в данном случае привело, в конечном счете, к отысканию более простой записи этого оператора. Практика решения одних и тех же задач обоими ме­тодами показывает, что в зависимости от характера задачи в одних случаях более предпочтительным оказывается первый метод, а в других второй. Было бы интересно на базе изучения асимптотиче­ских оценок сложности формул выяснить вопрос о

y21 =1,

(ж)

vx{x{ y{ v x{x{Уз v x12x22y30 = 1.

200

211рациональных областях применения двух этих ме­тодов. Представляет интерес и разработка других методов аналитического представления алфавит­ных операторов, в чем-то более предпочтительных в сравнении с только что описанными методами.

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

Сформулируем и докажем важное утверждение, которое назовем теоремой о явном задании конечно­го алфавитного оператора. Ограничим область из­менения буквенной переменной у значениями Ъ1, Ъ2,..., Ъ1, то есть опишем ее уравнением

уЪ vyb2 v...уЪ>

= 1.

(32)

Тогда любой однозначный, вообще говоря, частич­ный, алфавитный оператор у = G(x1, x2,..., xm, у) = 1, заданный в неявной форме уравнением

g(x1, x2,..., xm, y)=1, (33)

может быть представлен в явной форме с помощью следующей системы уравнений:

g(x1, x2,..., xm ) = У\

g(x1, X2,..., xm 2 ) = yЪ2, (34)

g(xVX2,...,xm1) = yk .

Чтобы доказать только что сформулированное утверждение, установим, что система, состоящая из уравнений (32) и (33), равносильна системе уравнений (32) и (34). Зафиксируем произволь­ным образом значения переменных x1, x2,., xm, y. Предположим, что набор (x1, x2,., xm, y) является решением системы, состоящей из уравнений (32) и (33). Отсюда следует существование такого i(1<i<l), что у=Ъ и g(x1, x2,..., xm, Ъ,)=1. В силу однозначно­сти алфавитного оператора G для любого /фі (1</<1) имеем g(x1, x2,..., xm, Ъ/)=0. Поэтому все уравнения системы (34), кроме 1-го, обращаются в тождества вида 0=0, 1-е же уравнение обращается в тождество вида 1=1. Таким образом, набор (x1, x2,..., xm, у) есть также решение системы, состоящей из урав­нений (32) и (34).

Предположим теперь, что набор (x1, x2,., xm, y) не является решением системы уравнений (32) и (33). Если уе{Ъ1, Ъ2,..., Ъ1}, то условие (32) не выпол­няется, а вместе с ним не выполняется и система условий (32) и (34). Если же у=Ъ1 (1<1<1), то не вы­полняется условие (33), поэтому g(x1, x2,..., xm, Ъ,)=0. В результате 1-е уравнение системы (34) обращает­ся в противоречие вида 0=1. Таким образом, набор (x1, x2,..., xm, у) не является также решением систе­мы уравнений (32) и (34). Следовательно, системы уравнений (32), (33) и (32), (34) равносильны друг другу. Теорема доказана. Отметим, что в случае, когда уравнением (33) задан многозначный в обла­сти значений (Ъ1, Ъ2,..., Ъ1)=1 алфавитный оператор G, системы уравнений (32), (33) и (32), (34) уже не будут равносильными друг другу. Действительно, предположим, что существуют два набора (x1, x2,..., xm, Ъ) и (x1, x2,..., xm, Ъ/), причем іф/ и 1<i, /<1, удо­влетворяющие уравнению (33). Однако ни один из этих наборов не удовлетворяет системе уравнений (34). Набор (x1, x2,..., xm, Ъ) обращает в противоре­чие вида 1=0 /-е уравнение системы (34), а набор (x1, x2,..., xm, Ъ/) i-е уравнение.

Зададим алфавитный оператор y1y2^y„=F(x1x2_ xm) системой уравнений:

f (x1 ,x2 ,---,xm,y1 ) = 1-> f2 (x1 ,x2,---,xm,y2) = 1,

fn(x1 ,x2 ,---,xm,yn) = 1.

(35)

Каждым из этих уравнений определяется зна­чение соответствующей буквы выходного слова У1У2—Уп алфавитного оператора Fдля входного сло­ва x1x2^xm. Тем самым уравнения (35) задают в не­явной форме систему алфавитных операторов:

у1 = F1(x1 x2... xm ), у1 = F2(x1 x2... xm ),

yn = Fn (x1 x2... xm X

(36)

формирующих отдельные буквы выходного слова алфавитного оператора F.

Переходя описанным выше методом к пред­ставлению в явной форме алфавитных операто­ров F1, F2, Fn, получаем в явной форме анали­тическое задание алфавитного оператора F: Здесь имеется в виду, что области изменения пере­менных yi (1<i<n) ограничены множествами букв T = {Ъд, Ъ2Ъ1Ь}, где 1i число букв в множестве Ti. Всего в системе (37) содержится 11+12+___+1n урав­нений. Система (37) допускает непосредственное вычисление букв выходного слова у^.-.у,, алфа­витного оператора F по заданным значениям букв входного слова x1x2. xm. Задание же алфавитного оператора F в виде системы (35) не дает такой воз­можности. В этом случае буквы выходного слова могут быть найдены только путем решения урав­нения.

М.Ф. Бондаренко, Ю.П. Шабанов-Кушнаренко

f\(x\ ,x2 >• f1 (xl ,x2 ,.

.,xm,b12 )

У\1'

f\(x\ ,x2 ,. f2 (xl ,x2 ,. f2 (xl ,x2 ,.

.'xm,blll ) = ..,xm,b21) = ..,xm,b22 ) =

yN

yb21

-Jh2

- y2 '

f2 (xl ,x2 ,.

"'xm'b2l2 )

b2l = y2^

 

 

fn(x\ ,x2 ' fn(x\ 'x2 ,.

Страницы:
1  2  3  4  5  6  7  8  9  10  11  12  13  14  15  16  17  18  19  20  21  22  23  24  25  26  27  28  29  30  31  32  33  34  35  36  37  38  39  40  41  42  43  44  45  46  47  48  49  50  51  52  53  54  55  56  57  58  59  60  61  62  63  64  65  66  67  68  69  70  71  72  73  74  75  76  77 


Похожие статьи

Автор неизвестен - 13 самых важных уроков библии

Автор неизвестен - Беседы на книгу бытие

Автор неизвестен - Беседы на шестоднев

Автор неизвестен - Богословие

Автор неизвестен - Божественность христа