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

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

(1 < j < n),

лежащий в основе определения операции отрица­ния. Однако это не ведет к трудностям, поскольку в универсальной алгебре на смену законам отрицания приходит система равенств

x,' x, j vx, j v...vx, 1,j v 111 ' (23)

vxji+1,j v... vxjki,j,

легко выводимых из усеченных законов истин­ности. Здесь i пробегает значения в пределах от 1 до kj, j в пределах от 1 до n. Уравнения (23) на­зовем усеченными законами отрицания. Они дают возможность ввести операцию отрицания также и в универсальной алгебре, в которой можно без каких бы то ни было ограничений пользоваться всеми тождествами алгебры конечных предикатов, кроме законов истинности и отрицания. Все законы ложности сохраняют силу, однако в конкретной за­даче фактически используются только те, в которых фигурируют введенные в задаче переменные и по­казатели узнавания при них из областей изменения для данных переменных.

Как было уже отмечено выше, в универсаль­ной алгебре невозможно практически воспользо­ваться совершенными дизъюнктивными и конъ­юнктивными нормальными формами — важным инструментом алгебры конечных предикатов. К счастью, им на смену приходят усеченные фор­мы, к рассмотрению которых мы и приступаем. Изучение вопроса начнем с введения смешанных n-разрядных числовых кодов или кодов типа (k1, k2,..., kn). Типом кода назовем набор чисел (k1, k2,..., kn). Введем n множеств символов Rj={0, 1,..., kj-1}, (1<j<n). Символы множества Rj назовем kj-ичными цифрами j-го разряда, под этими символами пони­маем первые kj чисел натурального ряда. Число kj назовем основанием j-го разряда. При построении смешанных кодов в их j-м разряде разрешается ис­пользовать лишь цифры из множества Rj. Каждый код: a1a2...an-1an обозначает некоторое число, на­зываемое значением этого кода и вычисляемое по формуле:

a1a2...an-1an=a1k2...kn+a2k3...kn+^+an-1kn+an. (24)

В качестве примера найдем с помощью формулы (24) числовое значение смешанного кода 122 типа (2, 4, 5). Десятичная запись значения этого кода равна 122(2 4 5)=1-4-5+2-5+2=3210. Справа внизу у смешанного кода 122 указан его тип (2, 4, 5).

Для нахождения смешанного кода типа (k1, k2,... , kn) заданного числа нужно разделить это число на kn, полученную целую часть частного разделить на kn-1 и т. д., наконец, целую часть частного n-1-го деления разделить на k1. Считывая остатки этих де­лений в обратном порядке, получаем смешанный код заданного числа. В целой части частного по­сле n-го деления должен получиться 0, в против­ном случае для заданного числа код типа (k1, k2,... , kn) не существует. В качестве примера найдем кодтипа (4, 3, 5) числа, заданного десятичным кодом 38. Выполняем последовательные деления, остатки делений указываем в скобках: 38:5=7(3), 7:3=2(1), 2:4=0(2). Имеем 3810=213(4 3 5). Заметим, что число Z(k1, k2,..., kn) всех различных n-разрядных кодов типа (k1, k2,..., kn) определяется формулой:

L(kb k2,..., kn)=k1k2...kn. (25)

При использовании универсальной алгебры описание объектов той или иной конкретной зада­чи осуществляется с помощью усеченных форм, то есть таких формул алгебры конечных предикатов, в которых встречаются не все буквы и переменные универсальной алгебры, а только их часть, указан­ная в условии задачи. Предикат, заданный усечен­ной формой, можно представить в виде усеченной таблицы его значений, которая составляется толь­ко для тех переменных и их значений, которые ука­заны в условии рассматриваемой задачи. Каждая переменная Xj при этом пробегает все значения из заданной области Tj={a1j, a2jV.., akj}. Наборы зна­чений аргументов, указанные в задаче (назовем их усеченными наборами), (x1, x2,..., xn) удобно интер­претировать как n-разрядные смешанные число­вые коды типа (k1, k2,..., kn). Буквы ay, a2jV.., akj , расположенные на j-ом месте усеченного набора, интерпретируем как числа 0, 1,..., kj-1. Заметим, что одни и те же буквы, стоящие на разных местах в наборе, могут интерпретироваться как различные числа.

В усеченной таблице наборы x1, x2,... , xn будем располагать в порядке возрастания числовых зна­чений соответствующих этим наборам смешан­ных кодов. Порядок расположения кодов назовем лексикографическим. Усеченную таблицу значений иногда удобно рассматривать как полную таблицу некоторого конечного предиката, заданного на де­картовом произведении T1xT2x...xTn. Указанный предикат будем называть усеченным конечным пре­дикатом или усечением исходного предиката уни­версальной алгебры. Усеченные предикаты могут быть все пронумерованы, для чего воспользуемся способом, описанным в п. 1.1. Всего существует 2k1k2...kn различных предикатов, заданных на декар­товом произведении T1xT2x...xTn.

Универсальную алгебру, вместе с введенны­ми в ней усеченными законами истинности и от­рицания, можно рассматривать как некую разно­видность алгебры конечных предикатов. Назовем такую алгебру усеченной. Уравнения (20) играют в ней роль тождеств этой алгебры. В усеченной ал­гебре сохраняют силу все понятия и результаты, рассмотренные в [1], в том числе понятия СДНФ и СКНФ. Отличие усеченной алгебры от ранее рас­смотренной алгебры конечных предикатов состо­ит в том, что в ней каждая буквенная переменная определена на своей собственной области. В неусе­ченной же алгебре все переменные заданы на еди­ной области. СДНФ и СКНФ усеченной алгебры можно использовать в качестве заменителей недо­сягаемых СДНФ и СКНФ универсальной алгебры при рассмотрении той или иной конкретной зада­чи, приняв их в качестве усеченных СДНФ и СКНФ универсальной алгебры.

Аналогично все другие понятия и результаты усеченной алгебры конечных предикатов могут быть приняты в качестве «усеченных» понятий и результатов универсальной алгебры. Понятия и результаты усеченной алгебры могут быть полу­чены тем же путем, что и в неусеченной алгебре с той разницей, что вместо законов истинности и отрицания нужно везде применять усеченные за­коны истинности и отрицания. Универсальной ал­геброй можно пользоваться при решении многих произвольных взаимосвязанных друг с другом за­дач столь же свободно, как и конкретной алгеброй конечных предикатов, используемой для решения какой-нибудь одной задачи. Единственной платой за полученную свободу служит необходимость вве­дения в каждой конкретной задаче дополнитель­ных уравнений — усеченных законов истинности, ограничивающих области изменения всех пере­менных, фигурирующих в данной задаче.

Рассмотрим пример пользования усеченными формами. Заданы следующие усеченные законы истинности:

x1avx1b=1, x2cvx2d=1, x3avx3d=1. (a)

Требуется преобразовать к усеченной СДНФ формулу:

j=(x1avx2d)(x1avx1bx3a)v(x1avx2c)(x2dx3dvx2cx3a). (б)

Преобразование производим, руководствуясь алгоритмом преобразования к СДНФ произволь­ной формулы алгебры конечных предикатов, опи­санным в п. 3 [1]. Раскрывая скобки и производя упрощения, имеем:

Во все конъюнкции вводим недостающие пере­менные, при этом, вопреки указаниям, содержа­щимся в описании алгоритма, пользуемся не зако­нами истинности, а равенствами (а):

y=x1a(x2cvx2d)(x3avx3d)vx1ax2d(x3avx3d)vx1bx2dx3av

vx1ax2dx3dvx1ax2cx3av(x1avx1b)x2cx3a.

Раскрывая скобки и производя упрощения, по­лучаем усеченную СДНФ:

f -y ay cy Л\/-у" ay cy d\/y ay dy a,,y ay dy dx/ j     1   2   3      1   2   3      1   2   3      1   2 3

b       c       a b       d a

Важным свойством усеченной СДНФ является то, что она указывает все решения системы уравне­ний, математически описывающей объект в кон­кретной рассматриваемой задаче. В рассмотрен­ном примере СДНФ указывает множество {(a, c, a), (a, c, d), (a, d, a), (a, d, d), (d, c, a), (b, d, a)} всех решений системы, состоящей из уравнения (б) и уравнений (а).

3. Аналитическое представление алфавитных операторов в виде уравнений

Формулы универсальной алгебры удобное средство для аналитического представления конеч­ных алфавитных операторов, нашего главного ору­дия математического описания деятельности ин­теллекта. Можно предложить несколько различных методов аналитического представления конечных алфавитных операторов. Их целесообразно разде­лить на две группы: методы неявного и явного за­дания операторов. Рассмотрим два метода неявного задания алфавитных операторов и один метод явно­го задания. Метод, который мы рассмотрим первым, позволяет осуществить неявное задание алфавитного оператора одним уравнением. Пусть yly2...yq=F(xlx2... xp) произвольно выбранный конечный алфавит­ный оператор, преобразующий входные слова x^... xp длины p в выходные слова y^...yq длины q. Что­бы получить в универсальной алгебре корректное математическое описание объекта, нужно ограни­чить области изменения всех буквенных перемен­ных, относящихся к этому объекту. В данном случае объектом математического описания служит алфа-витньгй оператор F, в роли буквенных переменных выступают символы x1, x2,..., xp, y1, y2,..., yq.

Требуемые ограничения вводим с помощью усеченных законов истинности для буквенных пе­ременных входного слова:

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

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

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

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

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