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

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

v v     )(xa v xff v xbf v     )(xf v xl v xf ) Л

л(x1a v xff v xff )(xa v xf v xff v x2)(xa v xff v x2).

Таблица 8

 

Конституэнта нуля

Простая имплицента

-Cj

-Cj к"

f

-Cj -Cj

Я"

-Cj

xa v v

 

*

*

 

 

xi v x2 v x2

*

 

 

 

*

xa v xf v x\

 

 

 

*

*

xC^l v x2 v x2

 

*

 

*

 

3) Применяем всюду, где возможно, операцию конъюнктивного поглощения A(AvB)=A. В результа­те выполнения этого шага алгоритма получаем со­кращенную КНФ конечного предиката. В нашем примере имеем следующую сокращенную КНФ:

f = (xa v xf v xf)(xf v x2 v xff) л л(xa v xf v xf)(x1 v xf v x2).

4) Выполняем шаги 3-9 предыдущего алгорит­ма. В нашем примере имплицентная таблица имеет вид, представленный табл. 8, по которой находим конъюнктивное ядро предиката:

{v xf v x2, xff v xa v xff} . Имеются две тупиковые КНФ:

(x0 v xA v xf) (xf v xa2 v xff)(v xff v xff) , (xl1 v xf v   ) (xff v xa v xff)(xl1 v xff v x2) ,

каждая из которых может быть принята в качестве минимальной КНФ предиката f.

Переходим к описанию алгоритма минимиза­ции формул алгебры конечных предикатов, обоб­щающего алгоритм Нельсона конъюнктивной ми­нимизации формул алгебры логики. Исходной информацией при минимизации служит произ­вольно выбранная ДНФ предиката, для которого отыскивается минимальная КНФ. Рассмотрим пример. Пусть A={a, b, c}, B={x1, х2, х3}. Предикат задан следующей ДНФ:

f xi x2 v v x2x3 .

1) Пользуясь вторым законом дистрибутив­ности, переходим к некоторой КНФ предиката f. В примере имеем:

f (xl1 v x2)(xl1 v xl)(xl1 v xff v xl) л

v xff v x3) л     v xl v x2) л

л(xl v xl v x3)(x2 v x\ v xl).

2) Применяем операцию конъюнктивного по­глощения. В результате получаем сокращенную КНФ. В нашем примере сокращенная КНФ имеет вид:

f (%l v xl)(%l v xl)(x2 v x2b v xl) .

3) Выполняем шаги 3-9 алгоритма, описанного первым в пункте г). В примере получаем следую­щую минимальную КНФ:

f (xl v xl)(x2 v    v xl) .

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

Выводы

У читателя, ознакомившегося с [1] и настоя­щей статьей, может возникнуть вопрос: почему в работе, посвященной теории интеллекта, так мно­го внимания уделяется разработке формального языка в виде алгебры конечных предикатов? Не лучше ли было бы, довольствуясь существующим математическим аппаратом, сразу же взяться за моделирование какой-нибудь сложной интеллек­туальной деятельности, например, игры в шахматы или доказательства теорем. К своему стыду, авторы когда-то именно так и поступили. Объектом мате­матического описания был выбран русский язык. В качестве формальных языков, на которых велось описание этого объекта, были испробованы язы­ки программирования [7], аппарат теории графов [8], язык теории алгоритмов [9], логические исчис­ления [10]. Много лет ушло в малоэффективных попытках, пока наконец стало ясно, что все эти средства настолько плохо приспособлены для це­лей формального описания человеческого языка, что создают труднопреодолимые препятствия при его моделировании. Поскольку естественный язык лежит в основе интеллектуальной деятельности че­ловека, то можно не сомневаться, что и моделиро­вание вышележащих слоев интеллекта будет столь же неэффективным, если ограничится существую­щими математическими средствами.

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

Человеческий язык как явление дискретное, естественно, должен описываться средствами дис­кретной математики. Между тем выбор средств указанного типа весьма ограничен. Это языки программирования для ЭВМ, логические исчис­ления, языки теории алгоритмов, аппарат теории графов. При попытке использования языков про­граммирования или языков теории алгоритмов приходится столкнуться со следующими трудно­преодолимыми препятствиями. Эти языки, как из­вестно, предназначены для описания алгоритмов [11], то есть процедур с однозначным исходом. Между тем естественный язык многозначен, что проявляется, например, в виде омографичности слов, то есть неоднозначности их смысла. Языки программирования и теории алгоритмов это та­кие языки, которые могут описывать только одно­значные функции. Естественный же язык требует формальных средств для описания многозначных функций, то есть соответствий произвольного вида, иначе говоря, — отношений.

Для описания человеческого языка лучше всего подошел бы аппарат уравнений, подобный аппа­рату, используемому в математическом анализе, отличающийся от последнего тем, что он предна­значен для формализации не непрерывных, а дис­кретных процессов. Такой язык дают логические исчисления, а именно: исчисления высказываний и исчисления предикатов. Однако, чтобы иметь возможность эффективно решать указанные урав­нения, необходимо довести интересующие нас ис­числения до уровня алгебраической системы. Сде­лано же это только в исчислении высказываний. В результате мы имеем алгебру логики и аппаратбулевых уравнений [12]. Однако аппарат булевых уравнений для формального описания естествен­ного языка наталкивается на серьезное неудоб­ство, заключающееся в том, что в алгебре логики используются лишь двоичные знаки, в то время как в естественном языке фигурируют буквенные, то есть многозначные символы.

Этого недостатка, казалось бы, можно избежать, обратившись к аппарату многозначной логики [13]. Однако при ближайшем рассмотрении обнаружива­ется, что многозначная логика развита только в сто­рону описания однозначных функций, а не отноше­ний. Учение об уравнениях в многозначной логике, насколько нам известно, совершенно не развито. Развитие же в этом направлении многозначной ло­гики принудительно приводит к алгебре конечных предикатов. Действительно, чтобы иметь возмож­ность записывать самые общие уравнения много­значной логики, в правой их части нет необходи­мости ставить произвольные формулы, достаточно писать константы. Необязательно использовать все константы, достаточно взять всего две знака: 0 и 1. Но как только мы так поступим, немедленно при­ходим к понятию конечного предиката, а следова­тельно, и к алгебре конечных предикатов.

Использование исчисления предикатов [3] для целей математического описания человеческо­го языка также наталкивается на определенную трудность: исчисление очень слабо развито при­менительно к нуждам описания конечных объек­тов. Исчисление предикатов не располагает даже средствами для формульной записи любых инди­видуальных конечных отношений. Вместе с тем, человеческий язык явление сугубо конечное и он требует для своей формализации аппарата конеч­ной математики. Пытаясь алгебраизировать конеч­ный фрагмент исчисления предикатов, мы не смо­жем прийти ни к чему иному, как только к алгебре конечных предикатов. Наконец, обратившись к аппарату теории графов [14], мы обнаружим, что, хотя он и используется для описания конечных от­ношений, однако совершенно не содержит в себе выразительных средств для записи этих отношений в виде уравнений некоторой алгебры. Если же мы захотим перевести информацию, содержащуюся в графах, на язык таблиц, то увидим, что с помощью графов выражаются именно конечные предикаты.

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

Список литературы: 1. Бондаренко, М.Ф. Об алгебре конеч­ных предикатов [Текст] / М.Ф. Бондаренко, Ю.П. Шабанов-Кушнаренко, С.Ю. Шабанов-Кушнаренко // Бионика интеллекта: науч.-техн. журнал. — 2011. — № 3. — С. 3-13. 2. Мальцев, А.И. Алгебраические системы [Текст] / А.И. Мальцев. М.: Наука, 1970. — 310 с. 3. Ершов, Ю.Л. Ма­тематическая логика / Ю.Л. Ершов, Е.А. Палютин. М.: Наука, 1979. — 372 с. 4. Глушков, В.М. Введение в киберне­тику [Текст] / В.М. Глушков. К.: Изд. АН УССР, 1964. — С. 67-75. 5. Глушков, В.М. Синтез цифровых автоматов [Текст] / В.М. Глушков. М.: Физматгиз, 1962. — 316 с. 6. Шабанов-Кушнаренко, Ю.П. Об одной математической модели морфологической классификации множества имен существительных русского языка [Текст] / Ю.П. Шабанов-Кушнаренко, Л.И. Якименко. Проблемы био­ники. 1971. — Вып. 6. — С. 104-107. 7. Шабанов-Кушнаренко, Ю.П. Математическая модель определения классов оди­наковых слов [Текст] / Ю.П. Шабанов-Кушнаренко, Л.И. Якименко // Проблемы бионики. — 1971. — Вып. 7. — С. 103-105. 8. Шабанов-Кушнаренко, Ю.П. К вопросу об авто­матическом морфологическом анализе причастий русско­го языка [Текст] / Ю.П. Шабанов-Кушнаренко, Е.А. Соло­вьева // Проблемы бионики. — 1974. — Вып. 12. — С. 46-50. 9. Осыка, А.Ф. Модель определения исходной формы числительных русского языка [Текст] / А.Ф. Осыка, Ю.П. Шабанов-Кушнаренко // Проблемы бионики. — 1976. — Вып. 16. — С. 78-84. 10. Осыка, А.Ф. К вопросу о модели­ровании грамматической обработки имен числительных [Текст] / А.Ф. Осыка. — Пробл. бионики, 1979, Вып. 22, С. 129-137. 11. Мальцев, А.И. Алгоритмы и рекурсивные функции [Текст] / А.И. Мальцев. М.: Наука, 1965. — С. 9-11. 12. Закревский, А.Д. Логические уравнения [Текст] / А.Д. Закревский. Минск: Наука и техника, 1975. — С. 92. 13. Дискретная математика и математические вопро­сы кибернетики [Текст] / Под ред. С.В. Яблонского и О.Б. Лупанова. М.: Наука, 1974. — Т. 1. — С. 35-66. 14. Белов, В.В. Теория графов [Текст] / В.В. Белов, Е.Н. Воробьев, В.Е. Шаталов. М.: Высш. школа, 1976. — 389 с.

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

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

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

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

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