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

Страницы:
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 

N=b1kn-1+b2kn-2+...+bn-1k1+bnk0.

Разделим число N на k:

N=bkn-2+bkn-3 +...+bn 2k0 + bn. k   1       1 k

Целая часть частного N1 этого деления равна:

N1 =b1kn-2 +b2kn-3+^+bn_2k1 +bn-1k0.

В остатке получаем bn. Итак, в результате де­ления числа N на k в остатке получаем последний разряд k-ичного кода этого числа. Выполним вто­рое деление, разделив число N1 на k. В целой части частного получаем число

N2=b1kn-3+b2kn-4+^+bn-3k1+bn-2k0,

а в остатке bn-1, то есть предпоследний разряд k-ичного кода числа N. При третьем делении в остат­ке получаем bn-2 и т. д. При n-ном делении в остатке получаем b1, то есть первый разряд k-ичного кода, а в целой части частного — нуль.

В итоге приходим к следующему правилу пере­вода десятичного кода в k-ичн^ій. Для перевода де­сятичного кода в k-ичн^ій код следует разделить его на k, полученную целую часть частного снова раз­делить на k и т. д. Деление продолжать до тех пор, пока в целой части частного получится нуль. Счи­тывая остатки этих делений в обратном порядке, получаем k-ичный код числа. В качестве примера переведем число 169 в двоичный код. Выполняем последовательные деления заданного числа на 2, в скобках записываем остатки делений: 169:2=84 (1), 84:2=42 (0), 42:2=21 (0), 21:2=10 (1), 10:2=5 (0), 5:2=2 (1), 2:2=1 (0), 1:2=0 (1). Считывая остатки, получаем двоичный код числа: 16910=101010012.

Введем число L(n, £)всехразличных n-разрядных k-ичных кодов. Оно выражается формулой L(n, k)=kn. Для примера подсчитаем число всех трехраз­рядных восьмиричных кодов: L(3, 8)=83=512. На­боры значений аргументов (x1, x2,..., xn) n-местных k-ичных предикатов удобно интерпретировать как n-разрядные k-ичные числовые коды. При этом буквы a1, a2,..., ak алфавита А интерпретируем как k-ичные цифры соответственно 0, 1,..., k-1. В та­блице значений предиката наборы значений ар­гументов будем располагать в порядке возраста­ния представляемых ими чисел. Именно в таком порядке расположены, к примеру, двухразрядные троичные коды в табл. 1. В этом случае буквы а, м, п интерпретируем соответственно как троичные цифры 0, 1, 2. Введем число М(п, k) всех различных наборов значений аргументов n-местного k-ичного предиката. Очевидно, что M(n, k)=L(n, k)=kn. Чис­ло столбцов в таблице значений предиката, в кото­рых располагаются наборы значений аргументов, определяется величиной M(n, k). Например, чис­ло столбцов табл. 1 равно M(2, 3)=32=9. Каждому набору значений конечного предиката присвоим свой номер, в качестве которого примем число, со­ответствующее этому набору при его интерпрета­ции в виде числового кода.

Пронумеруем все k-ичные n-местные предика­ты. С этой целью будем интерпретировать последо­вательность значений предиката, расположенную в нижней строке его таблицы, как kn-разрядный двоичный код. При этом символ 0 интерпретируем как цифру нуль, а символ 1 — как цифру один. Чис­ло, соответствующее этому коду, примем в качестве номера конечного предиката. К примеру, предика­ту, представленному табл. 1, присваиваем номер 001110011, что соответствует числу 115 в десятич­ной записи. Пусть N(n, k) число всех различных n-местных k-ичных предикатов. Очевидно, оно совпадает с числом всех ^-разрядных двоичных кодов, поэтому N(n, k)=L(kn, 2)= 2(k ). В виде при­мера определим число всех различных двуместных троичных предикатов: N(2,3) = 2(3) = 29 = 512.

4. Применения конечных предикатов

Каждому конечному алфавитному оператору можно поставить в соответствие некоторый свой конечный предикат. Сделать это можно следую­щим образом. Пусть

F(x1x2-xm)=^1^2-^m

произвольно выбранный конечный алфавитный оператор, преобразующий входные слова x1x2. xm длины m в выходные слова y1y2^ym той же дли­ны, составленные из букв алфавита А. Построим

2m-местный конечный предикатf(x1, x2,..., xm, y1, y2,..., ym) над алфавитом А, руководствуясь следую­щим правилом:

f(^ x2,..., xm, yl, ^v-v ym ) =

= | 1,если F (x1 x2... xm) = У1У2... ym, (1)

l0, если F(x1 x2... xm ) * y1 y2... ym .

Запишем уравнение:

fxb x2,^, xm, y1, У2,..., ym)=1. (2)

Это уравнение связывает переменные x1, x2,., xm, y1, y2,--, ym некоторым отношением [5]. Под­ставляя в (2) буквы x1, x2,..., xm входного слова x1x2_ xm алфавитного оператора F, получим в результате решения этого уравнения буквы y1, y2,..., ym вы­ходного слова y1y2. ym. Таким образом, предикат f, построенный указанным способом, содержит в себе всю информацию об интересующем нас ал­фавитном операторе F. С его помощью можно определить выходное слово алфавитного операто­ра, представляемого этим предикатом, для любого входного слова.

Важно отметить, что точно таким же способом можно задать с помощью конечных предикатов не только всюду определенные, но также и любые ча­стичные конечные алфавитные операторы. Если для входного слова x1x2. xm алфавитный оператор F не ставит в соответствие никакого выходного слова, это значит, что уравнение (2) для заданного набора значений аргументов (x1, x2,., xm) не име­ет ни одного решения относительно набора пере­менных (y1, y2,., ym), то есть что решения этого уравнения не существует. Важно, что с помощью одного конечного предиката можно задать целое семейство конечных алфавитных операторов. Это достигается введением в предикат дополнитель­ной переменной z, значениями которой служат но­мера задаваемых алфавитных операторов. Пусть, к примеру, нам нужно представить в виде конечного предиката семейство, состоящее из трех алфавит­ных операторов:

F1(x1x2. xm)=y1y2. ym, F2(x1x2. xm)=y1y2. ym,

F3(x1x2..xm)=y1y2."ym.

Строим 2m+1-местный предикат f(x1, x2,..., xm, y1, y2,..., ym, z), полагая, что при z=1 он соответству­ет алфавитному оператору F1, при z=2 — оператору F2, при z=3 оператору F3.

С помощью конечных предикатов можно пред­ставить не только интересующие нас конечные ал­фавитные операторы с однозначными значениями, но и так называемые многозначные операторы. Многозначным конечным алфавитным оператором называется такое соответствие F, которое связы­вает каждое входное слово из Am с некоторым се­мейством входных слов из того же множества. Если входному слову x1x2. xm алфавитный оператор F ставит в соответствие несколько входных слов, зна­чит, уравнение (2) для заданного набора значений аргументов (x1, x2,..., xm) имеет несколько решений относительно набора переменных (y1, y2,..., ym).

Многозначный оператор можно рассматривать как обобщение понятия однозначного конечно­го алфавитного оператора. Однозначный конечный алфавитный оператор это такой многозначный конечный оператор, который каждому входному слову ставит в соответствие некоторое множество выходных слов, состоящее не более чем из одного слова. Если каждому входному слову ставится в со­ответствие множество, состоящее не менее чем из одного слова, то такой конечный алфавитный опе­ратор называется всюду определенным, если же не­которым из входных слов ставится в соответствие пустое множество слов, то — частичным.

Поначалу, быть может, несколько обескуражи­вает то, что конечные предикаты дают нам больше, чем мы от них ожидали. В самом деле, введя ко­нечные предикаты, мы хотели получить средство представления только для однозначных конечных алфавитных операторов, фактически же получи­ли в виде «бесплатного приложения» возможность представления и многозначных операторов. Хоро­шо это или плохо? Если бы оказалось, что много­значные алфавитные операторы бесполезны для теории интеллекта, то это, конечно, было бы пло­хо, так как в теории интеллекта появились бы не-интерпретируемые математические структуры. К счастью, однако, обнаруживается, что многознач­ные алфавитные операторы (а это покажет даль­нейшее изложение) весьма удобны для математи­ческого описания высказываний или суждений интеллекта важных объектов теории интеллекта. Однозначным же алфавитным операторам отво­дится роль средства математического описания деятельности интеллекта.

Читатель, вероятно, заметил, что при переходе от конечных алфавитных операторов к соответству­ющим им конечным предикатам мы одновременно совершили переход от переменных Xи Y, значени­ями которых были слова, к переменным x1, x2,..., xm, y1, y2,.-, ym, пробегающим буквенные значения. Переход к буквенным переменным очень важен, он дает нам в руки удобный математический язык для описания функций интеллекта. Важно понять, что буквенные переменные было бы невозможно использовать, если б мы в свое время не перешли к конечным алфавитным операторам, а продолжали базироваться на понятии алфавитного оператора, заданного на бесконечном множестве слов произ­вольной длины.

Страницы:
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 самых важных уроков библии

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

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

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

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