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

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

Поступила в редколлегию 15.06.2011

УДК 519.7

Нормальні форми формул алгебри скінченних предика­тів / М.Ф. Бондаренко, Ю.П. Шабанов-Кушнаренко, С.Ю. Шабанов-Кушнаренко // Біоніка інтелекту: наук.-техн. журнал. — 2011. — № 3 (77). — С. 14-29.

Розглянуто побудову нормальних форм формул ал­гебри скінченних предикатів, методи кон'юнктивної мінімізації. Сформульовано теорему про конюнктивний розклад предикатів.

Табл. 8. Бібліогр.: 14 найм.

UDC 519.7

PDNF in final predicates algebra / M.F. Bondarenko, S.Yu. Shabanov-Kushnarenko, Yu.P. Shabanov-Kushnaren-ko // Bionics of Intelligense: Sci. Mag. — 2011. — № 3 (77).

—P. 14-29.

The construction of the final predicates algebra formulas normalized forms and the of conjunctive minimization meth­ods is considered. The theorem about the predicates conjunc­tive decomposition is formulated.

Ref.: 14 items.

БИОНИКА ИНТЕЛЛЕКТА. 2011. 3 (77). С. 30-45

ХНУРЭ

УДК 519.7

intelligence

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

ХНУРЭ, г. Харьков, Украина

УРАВНЕНИЯ ТЕОРИИ ИНТЕЛЛЕКТА

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

АЛГЕБРА КОНЕЧНЫХ ПРЕДИКАТОВ, ПРЕДИКАТ, ИНТЕЛЛЕКТ, УРАВНЕНИЕ, УНИВЕР­САЛЬНАЯ АЛГЕБРА, АЛФАВИТНЫЙ ОПЕРАТОР

Введение

Предикаты — это основной математический инструмент теории интеллекта, они используют­ся для формального описания объектов бионики интеллекта. Алгебра предикатов это логический аппарат первой ступени, ее можно рассматривать как аналог школьной алгебры, на языке которой записываются числовые функции. Аппаратом вто­рой ступени в логике является алгебра предикат­ных операций, которую можно рассматривать как логический аналог изучаемого в вузах математиче­ского анализа. Алгебры предикатов и предикатных операций рекомендуются в качестве языка фор­мального описания для разработчиков, создающих средства искусственного интеллекта. Язык алге­бры предикатов представляет собой универсальное средство формального описания любых объектов, наблюдаемых в мире, на нем можно выразить лю­бое отношение. Язык алгебры предикатных опе­раций тоже универсален, но он используется уже в ином качестве: на нем можно выразить любые действия над отношениями. Когда возникает необ­ходимость формально описать какой-нибудь про­цесс или объект, то прибегают к услугам алгебры предикатов. Когда же требуется реально воспроиз­вести уже описанный ранее процесс или создать в натуре спроектированный объект (то есть нужно перейти от слов к делу), то используется аппарат ал­гебры предикатных операций.

Отношения выражают внутреннее строение объ­ектов, свойства объектов и связи между ними. Они представляют собой универсальное средство фор­мального представления любых объектов. За две с половиной тысячи лет существования науки ей не удалось обнаружить в мире ни одного объекта, о котором можно было бы с уверенностью сказать, что он, в принципе, не поддается формальному представлению с помощью отношений. Никакие другие известные средства формального представ­ления объектов (например, школьная алгебра и ма­тематический анализ) свойством универсальности не обладают. Естественный язык, представляющий собой универсальное средство духовного общения людей, можно рассматривать как инструмент для выражения отношений. Обращаясь с речью к дру­гим людям, мы передаем им вполне определенный смысл произносимого предложения, который есть не что иное, как некоторое отношение. Обмен мыс­лями между людьми осуществляется за счет переда­чи и приема отношений. Каждая мысль представ­ляет собой какое-то отношение. Мышление же есть процесс преобразования отношений, получения новых отношений из уже имеющихся. Информация, поступающая к нам из внешнего мира, имеет вид отношений, характеризующих структуру, свойства и связи окружающих нас предметов и процессов. Результатом действий человека во внешнем мире является приведение структуры предметов и про­цессов в соответствие тем отношениям, которые были сформированы в уме человека в результате его мыслительной деятельности.

1. Канонические уравнения

Любая интересующая нас информации о дея­тельности и суждениях интеллекта, в принципе, может быть записана в виде уравнений алгебры ко­нечных предикатов. В данной статье будут рассмо­трены способы записи таких уравнений, а также методы их аналитического решения. Для большего удобства записи уравнений алгебры конечных пре­дикатов нам понадобятся, кроме уже введенных четырех операций — дизъюнкции, конъюнкции, отрицания и импликации, еще две двуместные операции равнозначность ~ и неравнозначность ® предикатов. Эти операции формально определим следующими равенствами:

A~B AB v AB

def

A®B AB v AB

def

(1) (2)

Здесь буквами А и В обозначены произвольно выбранные формулы алгебры конечных преди­катов. Условимся в случае отсутствия в формуле скобок, регулирующих порядок выполнения опе­раций, непосредственно после выполнения опе­раций отрицания, конъюнкции, дизъюнкции им­пликации выполнять операции равнозначности и лишь затем — операции неравнозначности.

Свойства введенных операций аналогичны свойствам одноименных операций, рассматривае­мых в алгебре логики. Все они могут быть выведе­ны из только что принятых определений. Перечис­лим наиболее важные тождества алгебры конечных предикатов, в которых фигурируют знаки ~, ®, а именно рефлексивность равнозначности:

A~A—1; (3)

антирефлексивность неравнозначности: A—0;

(4)

коммутативность равнозначности и неравнознач­ности:

A~B—B~A; (5)

A®B—B®A; (6)

ассоциативность равнозначности и неравнознач­ности:

(A~B)~C—A~(B~C); (7) (A®B)®C—A®(B®C); (8) дистрибутивность неравнозначности:

{A®B)C—AC®BC; (9) транзитивность равнозначности:

(A~B)(B~C)^(A~C)— 1; (10) свойства логических констант:

A~0— A;

A~1 —A; A®0—A;

A®1—A.

(11)

(12)

(13) (14)

Уравнение вида

fi(xi, x,..., x„)=1, (15)

где f произвольно выбранный фиксированный конечный предикат, назовем каноническим уравне­нием алгебры конечных предикатов для предиката f. К каноническому виду может быть приведено любое уравнение алгебры конечных предикатов. Действительно, уравнение

f1(X1, X2,..., X„)=/2(X1, X2,..., X„), (16)

где f1, f2 произвольно выбранные фиксированные конечные предикаты, является наиболее общим видом уравнения алгебры конечных предикатов, однако оно может быть записано в виде равносиль­ного ему канонического уравнения:

f1(x1

., )~/2(*1, *2,.", Х„)=1.

Система канонических уравнений

f2 (x1, xn) = 1,

(17)

(18)

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

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

(19)

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

Любое каноническое уравнение может быть интерпретировано как некоторое высказывание. В самом деле, уравнение x"=1 равносильно вы­сказыванию «x="»: если х"=1, то х=а; если x=", то x"=1. Точно так же, уравнения AvB=1, AB=1, A=1, A3B=1, A~B=1, A®B=1 соответственно равносиль­ных высказываниям «А или также В», «A и B», «лож­но, что A», «если А, то В», «А равносильно В», «или А, или В». На том же основании можно утверждать, что любое сложное высказывание, у которого в качестве простых высказываний фигурируют ка­нонические уравнения, может быть представлено в виде некоторого канонического уравнения. Для перехода от такого высказывания к каноническо­му уравнению нужно в высказывании логические связки «или также», «и», «ложно, что», «если — то», «равносильно», «или — или» заменить соответ­ственно символами v, л, , z>, ~, ® и приравнять по­лученную формулу к единице.

Как решить каноническое уравнение f(x1, x2,..., xn)=1 алгебры конечных предикатов? Решить уравнение — это значит отыскать множество всех наборов значений переменных (x1, x2,... , xn), удо­влетворяющих этому уравнению, то есть обра­щающих его левую часть в 1. Мы уже располагаем универсальным, хотя, быть может, громоздким и не всегда удобным, методом решения канониче­ского уравнения. В качестве такого метода может быть использован алгоритм приведения любой формулы алгебры конечных предикатов к СДНФ, описанньгй в п. 3 [1]. Пусть задано уравнение (15) и требуется его решить. Представляя предикат f в виде СДНФ, имеем:

f(xx, x2,..., xn)= v

12

f("1, "2     "n )=1

fm (x1, x2,..., xn ) = 1.

Каждой конституэнте  единицы   x"1 x22...x"nn СДНФ предикатаfсоответствует решение (ст1, "2,..., "n) уравнения (15). Вместе взятые, эти решения об­разуют систему всех решений уравнения (15).

Рассмотрим пример решения уравнения вида (15) при А={а, b}, В={x1, x2, x3}. Предикат f задан формулой:

f(x1, ^ x3)

(x]avx2b)(x1avx1bx3a)v(x]avx2a)(x2bx3bvx2ax3a).

a       a       a a       a       b a       b a

a       b       b b       a       a b       b b

VA^ А^  VA^ А^   VA^ Л3 .

По СДНФ предиката f находим систему Г всех решений уравнения f(x1, x2, x3)=1:

7={(a, a, a), (a, a, b), (a, b, a), (a, b, b), (b, a, a), (b, b, b)}.

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

(s<n) ДНФ предиката соответствует некоторое под­множество системы всех решений уравнения (15), составленное из всевозможных наборов значений переменных (x1, x2,..., xn), у которых на i1, i2,..., is местах стоят соответственно буквы "1i,"i2,...,"is . Объединение всех таких подмножеств дает систему всех решений уравнения (15).

Рассмотрим пример представления системы всех решений уравнения алгебры конечных пре­дикатов при А={а, b, с} и В=^ь x2, x3}с помощью минимальной ДНФ. Предикат fзадан формулой f(x1, x2, x3)—(x1avx2e)(x2avx2bvx3a).

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

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

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

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

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