автореферат диссертации по информатике, вычислительной технике и управлению, 05.13.11, диссертация на тему:Математические методы, алгоритмы и программные системы для решения прикладных задач качественного характера при логическом представлении нечетких знаний

о

^ На правах рукописи

СО ^ еч,

Серов Владимир Васильевич

МАТЕМАТИЧЕСКИЕ МЕТОДЫ, АЛГОРИТМЫ И ПРОГРАММНЫЕ СИСТЕМЫ ДЛЯ РЕШЕНИЯ ПРИКЛАДНЫХ ЗАДАЧ КАЧЕСТВЕННОГО ХАРАКТЕРА ПРИ ЛОГИЧЕСКОМ ПРЕДСТАВЛЕНИИ НЕЧЕТКИХ

ЗНАНИИ

05. IJ.II- Математическое и программное обеспечение вычислительных машин, комплексов, систем и сетей

АВТОРЕФЕРАТ диссертации па соискание ученой степени доктора технических наук

Москва 1997

Работа выполнена в Российском заочном институте текстильной и легкой промышленности.

Официальные ошюнешы:

доктор технических паук, профессор Корпчиеп Л.11.

доктор технических наук, профессор Минаев В.А.

доктор физико-математических паук, профессор Дементьев В.А.

Ведущая организация: Институт программных систем РАН

Защита диссертации состоится декабря 1997 г. час. на заседании диссертационного Совета Д 063.93.01 Московской Государственной Академии приборостроения и информатики (107076, Москва, Стромынка, д. 20).

С диссертацией можно ознакомиться п библиотеке Московской Государственной Академии приборостроения и информатики.

Автореферат разослан "Л" ноября 1997 т.

Ученый секретарь

диссертационного Совета Д 063.93.01

к.т.п., доцент *~ , , ==•— М.В,Ульянов

Общая характеристика работы

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

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

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

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

Цель работы заключается в разработке нового научного направления в области представления знаний и методов решения задач на ЭВМ - создании теории и методов формализации нечетких знаний прикладного характера, алгоритмов и процедур решения качественных задач, разработке на данной основе программных комплексов и экспертных систем.

Для достижения поставленной цели в диссертации должны быть решены следующие задачи:

-создание теории и методов представления и формализации логических компонентов нечетких знаний, используемых в прикладных научных исследованиях, организационной, управленческой деятельности и ряде других областей применения ЭВМ;

-разработка методов, алгоритмов и процедур решения прикладных качественных задач широко распространенных классов: прогнозирования, интерпретации, идентификации и т.д. в различных проблемных областях;

-разработка программных комплексов и экспертных систем, реализующих предложенные методы представления знаний и решения качественных задач . Научная новизна работы заключается в следующем:

-решена задача математическою синтеза и анализа молекулярных структур методами дискретной математики и разработан комплекс программ МАИСС;

-решена задача идентификации структур многоатомных молекул по спекгрохимическим данным при таблично-продукционной форме представления нечетких знаний и разработана экспертная система РАСТР;

-предложена теория и методы формализации нечетких знаний прикладного характера на основе объединения возможностей логики предикатов первого порядка и теории нечетких множеств - прикладное исчисление нечетких предикатов;

-показана возможность решения качественных задач в прикладном исчислении нечетких предикатов методом доказательства теорем с оценкой истинности полученных результатов;

-проведена формализация и структурирование логических компонентов знаний прикладного характера в ряде проблемных областей;

-проведена систематизация и формальное описание широко распространенных классов прикладных качественных задач: прогнозирования, интерпретации, идентификации;

-приведены примеры формализации знаний и решения качественных задач на языке ТУРБО-ПРОЛОГ, расширенном для нечеткой логики;

-показана возможность использования нечеткой логики в естественноязыковых приложениях.

Практическое значение. Разработанная теория и методы логического представления нечетких знаний и решения -качественных задач были использованы и используются в настоящее время при создании ряда экспертных систем и программных комплексов в области прикладных научных исследований и в области автоматизации производства и управления. К их числу относятся:

-система математического синтеза и анализа молекулярных структур МАИСС. Результаты расчетов системой МАИСС точного числа изомеров различного атомного состава и их построение получены и описаны впервые;

-экспертная система распознавания структур многоатомных молекул РАСТР. Неоднократно модифицированные варианты системы РАСТР эксплуатируются почти 20 лет;

-экспериментальная экспертная система СПРИНТ. Система используется для отработки предлагаемых методов и имеет в своем составе ряд универсальных компонентов, применимых в других системах подобного рода;

-автоматизированная система оценки качества изделий легкой промышленности;

-система контроля сроков выполнения решений.

Достоверность научных положений, выводов и результатов подтверждается: -использованием для представления логических компонентов знаний и решения качественных задач формальной аксиоматико-дедуктивной системы с общепринятыми в дискретной математике синтаксическими и семантическими конструкциями;

-использованием для решения ряда качественных задач классических методов дискретной математики;

-успешным применением разработанных методов при создании экспертных и информационных систем;

-внедрением и эксплуатацией созданных экспертных и информационных систем.

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

Более чем 20- летнюю работу в рассматриваемой области автор начинал в неформальном творческом коллективе академика РАЕН, д.ф.-м.н., проф. Л.А.Грибова под его непосредственным руководством и выражает ему искреннюю признательность. Автор благодарен д.х.н., проф. М.Е.Эляшбергу за долговременное и плодотворное сотрудничество, одним из результатов которого было создание экспертных систем МАИСС и РАСТР. За многолетнее сотрудничество автор признателен В.М.Петрову. Академику МАИ, д.т.н., проф. В.З.Букрееву автор благодарен за создание творческой атмосферы на руководимой им кафедре информатики, благодаря чему и стало возможным оформить рассматриваемые работы как диссертацию.

Апробация работы. Результаты работы были доложены и обсуждены на следующих конференциях, съездах, семинарах, совещаниях:

-Третий семинар "Использование вычислительных машин в спектроскопии молекул" (Новосибирск, 1975);

-11-ый Менделеевский съезд по общей и прикладной химии (Москва, 1975); -6-ая Межотраслевая конференция молодых специалистов (Москва, ГИРЕДМЕТ, 1976);

-4-ая Всесоюзная конференция "Использование вычислительных машин в спектроскопии молекул" (Новосибирск, 1977);

-9-ая Международная конференция по применению ЭВМ в химии и. химическом образовании (Новосибирск, 1978);

-Научно-технический семинар "Системный анализ и оптимизация управления" (Москва, 1982);

-Научно-технический семияар "Системный анализ и оптимизация управления" (Москва, 1983);

-6-ая Всесоюзная конференция "Использование вычислительных машин в спектроскопии молекул и химических исследованиях". (Новосибирск, 1983);

-Межвузовский научно-технический семинар "Системный анализ, техническая и экономическая кибернетика" ( Москва, 1984);

-5-ая Всесоюзная конференция по аналитической химии органических соединений (Москва, 1984);

-Межвузовский научно-технический семинар "Системный анализ, техническая и экономическая кибернетика " (Москва, 1984);

-7-ая Всесоюзная конференция "Использование вычислительных машин в химических исследованиях и спектроскопии молекул" (Рига, 1986);

-Всесоюзная конференция "Математические методы и ЭВМ в аналитической химии" (Москва, 1986);

-The Third USSR-JAP AN symposium on computer chemistry (Novosibirsk, 1987);

-3-я Международная научно-техническая конференция "Программное обеспечение ЭВМ" (Тверь, 1990);

-Конференция "Автоматизация проектирования и производства в легкой промышленности" (Москва, РЗИГЛП, 1995);

-Межвузовская научная конференция "Современные проблемы текстильной и легкой промышленности" (Москва, РЗИТЛП, 1996);

-The Fourth International "Workshop Multiple criteria and game problems under uncertainty (Moscow, 1996).

Публикации. Основные результаты диссертации опубликованы в 49 печатных работах. В их числе: монография, 2 статьи в ДАН СССР, 6 статей в зарубежных журналах.

Структура и объем работы. Диссертационная работа состоит из введения, восьми глав, заключения, списка литературы из 116 наименований и изложена на 211 страниц машинописного текста, включая 30 рисунков и 30 таблиц.

Содержание работы

Во введении показана актуальность работы, дано общее описание проблемы, сформулированы цели исследований.

В первой главе рассмотрено состояние вопроса и задачи исследований.

В первом разделе рассмотрены общие вопросы представления знаний и методов решения задач прикладного характера с применением ЭВМ.

Второй раздел посвящен изучению и систематизации понятий нечеткости, неясности и других граней неопределенности в теории и практических применениях.

В третьем разделе рассмотрены и обобщены известные работы по формализации решения прикладных задач качественного характера.

В четвертом разделе дано краткое описание работ, проведенных автором в рассматриваемой области: постановка задач исследований и последовательность их решения.

Вторая глава посвящена решению качественной задачи математического синтеза и анализа молекулярных структур методами дискретной математики.

В первом разделе описана постановка задачи и ее практическое значение.

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

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

Описываемая в данной главе система программ математического анализа и синтеза структур МАИСС позволяет строить все структурные формулы, удовлетворяющие заданной брутто-формуле, по набору дискретных единиц структуры (ДЕС) и всесторонне анализировать их топологические особенности.

Во втором разделе приводится описание алгоритма генерации полного набора матриц смежности неизоморфных графов.

Каждую структуру можно представить в виде конечного связного мультиграфа (рисЛа). Для определенной г-й нумерации вершин графа можно построить одну матрицу смежности Вг размерности пхп, где п - число вершин (рис. 16). Каждый элемент матрицы Вг отражает отношение между вершинами графа: если вершина I соединена ребром кратности гп с вершиной ], то элемент Ц принимает значение т (т = 0,1,2,3). Значение элемента Ь|.п+1 дополнительного столбца определяет число атомов водорода для вершины с номером 1.

Каждой структуре соответствует множество {Вг} матриц смежности. Любую матрицу Вг этого множества можно получить путем перенумерации вершин графа (свойство изоморфизма). Выделим верхний треугольник Аг в симметричной матрице Вг. Матрицу Аг преобразуем в строку, как показано на рисЛв, располагая элементы последовательно слева направо и сверху вниз. Теперь матрице Аг, а значит и В„ можно поставить в соответствие число Кг, полученное описанными преобразованиями. Назовем "большей" ту матрицу Вг, которой соответствует большее число Кг.

Основная идея процесса генерации всех возможных структур состоит в следующем. Сначала строится "максимальная" для данной брутго-формулы матрица Вт. Очевидно, этой матрице соответствует максимальное число К™. Затем производится последовательное "вычитание" из Вм минимально возможных чисел (фактически арифметическое вычитание из Кт) до тех пор, пока Кт не станет равно нулю. После каждого "вычитания" матрица смежности проходит проверку на связность. Разработанный для проверки графа на связность алгоритм можно условно

назвать "стягиванием графа в точку": смежные вершины графа последовательно объединяются в одну, при этом сохраняются все ребра, за исключением ребер, соединяющих эти вершины. Если в результате такого объединения мы получим одну вершину, то граф связен, в противном случае- нет.

1

С

4/1 \ 2 5 6

С Н I с-сн2-сн3

\ // с

3 а

1 2 3 4 5 6 7

1 1 1 2 |1 1 2

2 1 2 1 2 1

3 1 2 1 1

4 2 1 1

5 1 1 2 1

6 1 3

kr=112002010100001 в

3 1

3 1

1 1 2

2 2

2 2

2 2

3 1

3 1

1 1 2

2 2

2 1 1

1 3

3 1

3 1

1 1 2

2 2

2 2

4

кта=310001000200202 кг=310001000200201 кг=310001000200200

где Рис. 1. Синтез струкгурных формул

Известно, что каждому графу соответствует множество матриц смежности, элементы которого можно получить перенумерацией вершин. Если в скелете молекулы содержится П! дискретных единиц структуры (ДЕС) первого типа, пг-второго,... nk- k-ro типа, то число возможных перенумераций равно П|!« гь!-... .пк!. Из этого множества необходимо выделить только одну матрицу (каноническую), в качестве которой выберем максимальную из возможных матриц, соответствующих определенному графу. Тогда алгоритм проверки на каноничность заключается в анализе возможности перенумерации строк матрицы В„ которая приводит к такой матрице Вр, что КР>КГ. Если это невозможно, то полученная матрица канонична.

Возможна как строгая проверка на каноничность, так и проверка с помощью различных эвристических критериев.

В третьем разделе описан алгоритм анализа матриц смежности по их топологическим особенностям.

Рассмотрим некоторый химический граф А, отображаемый его матрицей смежности А. Требуется установить наличие или отсутствие в этом графе любых наперед заданных фрагментов (подграфов).

Пусть исходный набор, определяющий матрицу смежности А графа А, состоит из N дискретных единиц структуры и N = Е пк, где к = 1,2, .Д и Т число типов ДЕС (ТьТ2,...,Ть...,Тг), цк- число ДЕС к-го типа. Предположим, что необходимо установить наличие или отсутствие в графе А подграфа В, содержащего в вершинах Р дискретных

единиц структуры, причем Р=£рь где рк- число ДЕС типа к в подграфе В, к=1,2.....{.

Сопоставим подграфу В матрицу смежности В, которую будем называть матрицей подграфа.

На первом этапе из матрицы А формируется матрица Ц, которая включает в себя те строки и столбцы матрицы А, которые могут по набору значений элементов образовать матрицу подграфа.

Второй этап заключается в том, чтобы из матрицы О построить все возможные матрицы 1),„ обладающие тем свойством, что их размерность и количество ДЕС различных типов (обозначим их как <1к) совпадают с аналогичными характеристиками матрицы В.

Третий этап заключается в проверке Ои на связность и установлении соответствия Ии и матрицы В. Общее число перестановок строк всех формируемых матриц необходимое для того, чтобы убедиться в отсутствии подграфа В в графе А, равно М.Р, где М=ПСЛР\ Р=ПРк!, отсюда М. Р=П(С,1крк.рк!)=П4!/(с1к-рк)!=ПА(1крк. Здесь АЛрк - число размещений из с!к элементов по р^.

В четвертом разделе описан комплекс программ, реализующий описанные алгоритмы - система МАИСС.

Процесс функционирования МАИСС включает в себя: генерацию всех матриц смежности, удовлетворяющих заданному набору ДЕС и атомов водорода; эвристическую проверку матриц смежности на каноничность (неизоморфность) для исключения повторений структур; проверку матриц смежности на связность; проверку на соответствие подграфам ограничений; математически строгую проверку на каноничность.

Программы системы МАИСС разработаны на алгоритмическом языке ■ ФОРТРАН. Разумная граница размерности решаемых задач равна 8 ДЕС, так как уже при 6 ДЕС число структур может приближаться к тысяче.

Пятый раздел содержит описание примеров применения системы МАИСС.

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

функциональных групп, например С-С, ОН, (Ж и т.д. Например, анализ формулы С^НуЫО показал, что ей соответствует 762 топологических изомера. Из них около 70 % (530)- циклические, 147 содержат только одинарные связи. Наибольшее количество структур содержат в себе спиртовые группы С-ОН (248, из них 160 приходятся на стабильные изомеры), группы -Ш2 (175), С=Ы (154) и С-О-С (103). Оксимов (ОН-Х-С) оказалось всего 9, альдегидов - 30, кетонов - 6.

Большой интерес для специалистов представляют полициклические соединения необычной структуры, особенно в классе углеводородов. Например, расчеты для эмпирической формулы С6Н6 показали, что ей соответствует 217 топологических изомеров, из них 15- ациклические, 14 не содержат кратных связей. Найденные полициклическне структуры с ординарными связями изображены на рис.2.

Рис. 2. Примеры полициклических изомеров состава С6Нй

Третья глава содержит описание решения задачи идентификации структур многоатомных молекул по спектрохимическим данным при таблично-продукционной форме представления нечетких знаний.

Первый раздел содержит описание постановки задачи и ее практического значения.

Молекулярная спектроскопия изучает оптические спектры, возникаюшие при испускании или поглощении излучения молекулами. Сложность молекулярных спекторов обусловлена тем, что в процессах испускания, поглощения и рассеяния

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

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

С точки зрения представления знаний информация имеет явно выраженный логический характер в форме ЕСЛИ-»ТО, т.е. системы продукций. В то же время знания нечетки из-за сложности объекта исследований, которым является многоатомная молекула. Характеристические частоты задаются возможными интервалами числовых значений, интенсивность и полуширина полосы описываются лингвистически (слабая, сильная, очень сильная, узкая, широкая и т.д.)

Все сказанное о концепции характеристических признаков ИК- спектров справедливо для химсдвигов и мультиплегиостей в спектрах протонного магнитного резонанса (ПМР).

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

Второй раздел содержит описание экспертной системы распознавания структур многоатомных молекул РАСТР.

Обобщенная схема системы представлена на рис. 3.

Работа системы начинается с проведения формального структурно-группового анализа (СГА) в исчислении высказываний (булевой алгебре), результатом которого являются наборы фрагментов, удовлетворяющие спектру и брутго-формуле (БФ).

Блок 1 структурно-группового анализа формирует и решает логические уравнения, отражающие взаимосвязь спектра со структурой.

Составляются логические соотношения, связывающие каждый ]-ый' характеристический признак экспериментального спектра со структурными

элементами, т.е. фрагментами из таблиц спектро- структурных корреляций А,-': л, (о, -» А,^А2' У...УАЛ (1)

Исходное представление знаний, отражающее концепцию характеристических признаков, имеет форму:

л-, (А, -» со/л а>2 л...ла>ь) (2)

При этом если в форме (1) характеристические признаки представляют собой константы, то в форме (2) их значения задаются интервалами. Прямое математическое преобразование из одной формы в другую невозможно. Чтобы его осуществить, необходимо для каждого характеристического признака с^ просмотреть всю библиотеку спекгро-структурных корреляций и отобрать только те фрагменты А}, для которых все интервальные значения признаков находят подтверждение в экспериментальном спектре.

Брупо-форнула ^ ПК. - спектр

Блок СГА

Комбинаторный блок

М А И С С

Раскрытие фрагментов

V

ИК-фильгр

ЯМР - фильтр

УФ - фияьтр

МС - фильтр

ЯМР - спектр . ЫФ - спектр . МС - спектр

Варианты структурных формуя

Рис 3. Обобщенная схема системы РАСТР

Полученная таким образом система импликаций вида (1) преобразуются в дизъюнктивную нормальную форму, при этом каждый конъюнкт и представляет собой формальное отображение возможного табора фрагментов. Каждый из наборов объясняет спектральные данные с учетом атомного состава молекул. В определенном

смысле можно сказать, что на этом этапе моделируется процесс рассуждений специалиста.

Комбинаторный блок 2 позволяет провести дальнейшее понижение размерности задачи путем построения из данного набора фрагментов таких комбинаций, которые содержат несколько одинаковых фрагментов, при условии, что требования БФ выполняются.

Блок 3 производит математический синтез структурных формул всех изомеров из наборов фрагментов и атомов с учетом требований БФ и представляет собой описанную выше систему программ МАИСС.

Блок 4 раскрывает внутреннюю структуру фрагментов, входящих в состав построенных МАИСС структурных формул в виде скелетных "макроатомов".

Блоки 5-8 представляют собой систему фильтров по данным ИК, ЯМР, УФ и масс-спектроскопии. Каждому из фильтров соответствует своя библиотека типовых фрагментов (БТФ). Фрагменты из ИК и УФ БТФ сопоставляются с наборами интервалов характеристических частот или длин волн, для ЯМР-фрагментов указываются пределы изменения характеристических химических сдвигов и мультиплегности в спектрах первого порядка. МС-БТФ содержит массовые числа, характеристичные для определенных структурных фрагментов.

Алгоритмы работы блоков-фильтров сходны и основаны на математическом решении задачи топологического анализа структурных формул. При поступлении на вход фильтра структурной формулы вся библиотека рассматриваемого фильтра "просеивается" через нее. Если обнаружится, что фрагмент из библиотеки присутствует в структуре, то производится проверка наличия в соответствующем спектре всех признаков данного фрагмента. Присутствие фрагмента подтверждается, если в соответствующих спектрах (ИК, ИР, УФ, ЯМР) имеются признаки, попадающие в характеристические интервалы данного структурного элемента. В случае отсутствия в спектре хотя бы одного характеристического признака фрагмента, найденного в структурной формуле, последняя исключается из рассмотрения.

В третьем разделе описано представление и содержание знаний в системе.

В системе имеются четыре основных типа информации, связывающей фрагменты с теми или иными их свойствами.

Первый тип- это список запрещенных фрагментов. При помощи этого списка из рассмотрения исключаются структуры, содержащие фрагменты, существование которых в природе маловероятно.

Следующий тип структурной информации- библиотека фрагментов для блока структурно-группового анализа по колебательным спектрам. Она представляет собой табличную форму системы продукций с интервальным представлением нечетких значений характеристических признаков. Некоторые примеры фрагментов для СГА приведены в табл. 1. Каждому фрагменту поставлены в соответствие характеристические интервалы частот.

Таблица 1

Примеры фрагментов для анализа ИК-спектров

Изображение фрагмента Интервалы характеристических частот, см"'

-СНз 1350- 1395, 1430-1470, 2870-2990

>С(СН3)2 1430-1470, 1380-1390, 1360-1370,2860-2990

-С(СНз)з 1430-1470, 1385-1395, 1360-1370,2860-2990

сн2=сн-я, 3010-3120,1625-1650,1395-1440,990-1010,

895-935

СН^С-И.! 3220-3350, 2100-2170,600-700

2160-2280

>с=с=с< 1950-1990

-сн2-он 3200-3640, 1000-1075

>с=с=о 2130-2170

-С=М 2110-2260

>с=ы- 1500-1690

-мн2 3200-3510, 1580-1650

-N=¿=0 2240-2275

>с=с-со-с< 1600-1650, 1665-1685, 1150-1250

>с=с-сон 1600-1650, 1685-1700

Аг-СО-С< 1670-1700, 1590-1633, 1480-1520

Аг-СОН 1690-1710, 1590-1633, 1480-1520

Аг-ОН 3200-3600, 1590-1633,1480-1520

-с-ко2 1530-1570, 1340-1385

>С=С-0- 1610-1670

>С=С< 1600-2000

Третий тип структурной информации- фрагменты, применяемые для раскрытия полной атомной структуры молекул, представленных матрицами смежности, в которых в качестве ДЕС фигурируют не только атомы, но и более крупные структурные единицы.

Четвертый тип информации представляет собой библиотеки фильтров. Библиотеки содержат фрагменты в виде матриц смежности и их характеристические спектральные признаки в виде интервалов возможных значений.

В четвертом разделе приведены примеры решения задач идентификации структур молекул.

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

Таблица 2

Примеры последовательного прохождения задач в системе РАСТР

1.С4Н802

ИК: 2960, 1450, 1365, 1290, 1250, 1120, 1075, 1045, 870 ЯМР: 3.55(1)

МС: 15, 26, 27, 28,29,30,31,41, 42, 43, 44, 45, 58, 59, 88, 89 Фрагменты не отобраны СП2 - СН2

Построено всего: 122 структуры / \

После ИК-фильтра: 14 структур О О

После ЯМР-фильтра: 1 структура \ /

После МС-фильтра: 1 структура СН2 - СН2

2. C5H,oN2

ИК: 2961, 2250, 1465, 1385, 1271, 1244, 1100, 920, 850, 765 ЯМР: 2.26(1); 2.3-2.7(1)

Наборы фрагментов: С з С-: -С з N; С з С-, -С = N

Построено всего: 140 структур После ИК-фильтра: 5 структур

(CH3)2N-CH2-CH2-CsN CH3-CH2-CH2-N-CsN

\

(CH3)2N-CH-CH3 ch3-ch2-N-ch2-ch3 СН3

\ \ CsN C~N

ch3-ch2-nch3-ch2-c=n

После Я MP-фильтра : 1 структура (CH3)2N-CHrCH2-CsN

3. C5H7N02

ИК: 2960,2273, 1750, 1450, 1370, 1335, 1270,1200, 1100, 1027, 968, 854 ЯМР: 1.25 (3), 3.55 (1), 4.25 (4)

МС: 26, 27,28,29, 30. 31, 32, 38. 39, 40, 41, 42,43, 44,45,67, 68, 69, 86 Наборы фрагментов:

-С0-0-; -С0-0-, -ОС-; -С0-0-, -C=N; -СО-О-, С=С, -CsN Построено всего: 120 структур

После ИК-фильтра: 9 структур После ЯМР-фильтра: 1 структура После МС-фильтра: 1 структура NsCH2-C0-O-CH2-CH3

4. С6Н,0О2

ИК: 3020, 2970, 1745, 1675, 14'0, 1375, 1320, 12 5, 1120,970 УФ: поглощения нет \ /

Набор фрагментов: СН s СН, -СО-ОН / \ Построено всего: 36 структур

После ИК-фильтра: 4 структуры После УФ-фильтра: 2 структуры

сн3 -о-со-снгсн=сн-"сн3. сн3-со-о-сн2-сн=сн-сн3_

структурные формулы из данного набора ДЕС. Система обладает обширными и разнообразными знаниями, тогда как людям свойственна узкая специализация.

Наиболее крупные молекулы, распознанные системой РАСТР, содержали до 20 атомов в скелете, при этом в их состав входили ароматические кольца. При решении задач большой размерности человек испытывает затруднения такого же характера, что и ЭВМ.

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

С помощью системы РАСТР было решено большое количество спектральных задач, взятых из руководств, спектральных атласов и аналитической практики. В качестве неизвестных образцов выбирались молекулы с числом скелетных атомов в среднем от 4 до 16.

Рассмотрим примеры решения задач при комплексном использовании ИК, ЯМР, УФ и масс-спектров. Табл. 2 позволяет проследить за последовательным прохождением задач в системе РАСТР. Здесь показаны характеристические признаки спектров, наборы фрагментов, отобранных по ИК- спектру и БФ, количество структурных формул, синтезированных из отобранных фрагментов и оставшихся атомов, а также число структур, прошедших через фильтры.

В четвертой главе приводится описание прикладного исчисления нечетких предикатов.

Первый раздел включает в себя постановку задачи.

В результате проведенных работ в области создания экспертных систем выявилась необходимость новой формы представления знаний, адекватно описывающей предметную область. Была разработана формальная логическая система- прикладное исчисление нечетких предикатов, объединяющая описательные возможности теории нечетких множеств с доказательными возможностями классической логики первого порядка.

Второй раздел включает в себя основные определения и свойства прикладного исчисления нечетких предикатов.

Пусть М- множество, х- элемент М, тогда нечеткое подмножество А множества М определяется как множество упорядоченных пар {(х,р./((х)},УхеМ, где р.^(х)-характеристическая функция принадлежности, принимающая свои значения во вполне упорядоченном множестве Е, которая указывает степень или уровень принадлежности элемента х подмножеству А.

Определение 1. Переменную г будем называть нечеткой, если она определена на множестве М и область ее значений составляет множество нечетких подмножеств

Определение 2. Нечетким предикатом называется функция С(г1?22,...2п), определенная на нечетких переменных гь 22,—'гъ, область значений которой составляют утверждения, истинность которых оценивается величинами из отрезка (0,1).

Для большинства практических применений можно считать, что характеристические функции р(х) кусочно- линейны и для их описания достаточно пары чисел, указывающих интервал, где ц(х)=1, и пары чисел, задающих минимальное отклонение от левой и правой границ интервала, при которых ц(х)=0. Такая форма записи позволяет описывать как обычные величины, так и нечеткие подмножества, при этом любая переменная принимает значения, описываемые списком с одним, двумя, тремя или четырьмя элементами.

Определение 3. Интерпретация формулы G исчисления нечетких предикатов включает в себя непустое множество предметной области М и указания значений констант, функциональных и предикатных символов, встречающихся в G.

Каждой константе ставится в соответствие некоторое нечеткое подмножество изМс характеристической функцией принадлежности ц(х), при этом 0<tx(x)<l.

Каждому п- местному функциональному символу ставится в соответствие отображение из М" в множество подмножеств {Mf}€M и множество их характеристических функций принадлежности {¡iF}, при этом 0< |.iFi < 1.

Каждому п- местному предикатному символу ставится в соответствие отображение М" в множество значений функции истинности {|аР}, 0< Цп<1.

Формуле G, предикатному символу Р ставится в соответствие множество внешних значений функции истинности {j^}, 0< ^¡<1.

Всякая нечеткая переменная или константа есть терм t. Выражение F(tj, t2,...t„) также терм, если tj, t2,...t„- термы. Нечеткий предикат P(t|,t2,...,tn), где tj, Ь,..ЛП,- термы, является элементарной формулой.

Определение 4. Значение функции истинности элементарной формулы равно алгебраическому произведению значений характеристических функций принадлежности термов и внешнего значения истинности нечеткого предиката.

Определение 5. Для двух формул G и F определим нечеткие логические операции следующим образом:

G л F = min (G,F) G v F = max (G,F) ^G=l-G

G -» F = -,G v F G~F = (-GvF)a(Ga-F)

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

Теорема 1. Для значений истинности ци ППФ прикладного логического исчисления справедливо 0< ди<1.

Определение 6. Две формулы G и F эквивалентны (записывается как G=F) тогда-и только тогда, когда значения истинности G и F совпадают при любой интерпретации.

Исходя из определений и свойств можно доказать свойства формул исчисления нечетких предикатов, аналогичные свойствам формул классической логики первого порядка: коммутативность, ассоциативность, идемпотентность,' дистрибутивность, теоремы де Моргана.

Эквивалентные формулы, содержащие кванторы, также сохраняют свои свойства.

Определение 7. Формула в прикладном логическом исчислении находится в предваренной нормальной форме (ПНФ) тогда и только тогда, когда она имеет вид (Х|Х|)—.(хпХп)(Р)> где Х;={У,3}, I'- формула, не содержащая кванторов, при этом (%1 Х1)...(ХпХп) называется префиксом, Р- матрицей формулы.

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

В третьем разделе рассматриваются дедуктивные вопросы прикладного исчисления нечетких предикатов.

Будем рассматривать декларативные знания как систему аксиом прикладного логического исчисления, тогда задачи представляются утверждениями (теоремами), которые необходимо доказать или опровергнуть.

Определение 8. Формула б прикладного исчисления выполнима (непротиворечива) тогда и только тогда, когда не существует интерпретации I, в которой значение исти«гости в не равно нулю.

Определение 9. Формула прикладного исчисления невыполнима (противоречива) тогда и только тогда, когда не существует интерпретации I, в которой значение истинности О не равно нулю.

Определение 10. Формула в прикладного исчисления общезначима тогда и только тогда, когда значение истинности не равно нулю при всех возможных интерпретациях.

Определение 11. Формула в есть логическое следствие формул Р|,Р2,...Р„ тогда и только тогда, когда для каждой интерпретации I, если Р]лР2...лРп имеет отличное от нуля значение истинности, то и О имеет значение истинности, отличное от нуля в I.

Задачей доказательства теорем будем считать выяснение вопроса логического следования некоторой формулы в из данного множества формул {Бь Р2, ... Р„}, т.е. выяснение общезначимости формулы (р1лР2л...лР„)->0.

Практически удобнее определять невыполнимость, а не общезначимость, поэтому будем рассматривать формулу ((р|лр1л...лр„)—>0), которая эквивалентна формуле Р1лР2л...л^Оп, невыполнимость последней и доказывают. Для установления невыполнимости необходимо доказать, что ие существует такой интерпретации, при которой одновременно истинны Р^Рь-РпрС. Процедура приведет к успеху в том случае, если О следует из р1,р,...рп, иначе она может продолжаться бесконечно.

В прикладной теории О представляет собой качественную задачу, а (Р1; Р2,...Рп) - систему логических выражений, описывающих декларативные знания, а также условия решения задачи. Дхя установления невыполнимости формулы Р|лР2л... аРпЛ-О в прикладном исчислении нечетких предикатов необходимо доказать, что не существует такой интерпретации, при которой формулы Иь Рг.-.-РпРО одновременно имеют значения истинности, отличные от нуля.

Наиболее известные из методов доказательства теорем в исчислении предикатов первого порядка базируются на принципе резолюций Робинсона. Для применения принципа логические выражения (формулы) приводятся к предваренной нормальной форме (ПНФ), то есть представляются в виде (Х1Х!)...(%„ХП)Р, где Х|е{У,Э}, а Р- формула в конъюнктивной нормальной форме (КНФ). Для преобразования используются известные тождества логики предикатов, затем скулемизацней исключаются кванторы существования 3, опускаются кванторы всеобщности V, знаки конъюнкции л заменяются на запятые, в результате мы имеем множество дизъюнктов Б.

Теорема 2. Пусть в- формула прикладного исчисления в предваренной форме, т.е. 0=(х1х1)....(хпх„)р[х1,..х„], а Р[х],..х„]- матрица формулы й, содержащая переменные хь...хп и представленная в конъюнктивной нормальной форме. Обозначим множество дизьюнкгов матрицы Р[х,,..хп] как Б. Формула О противоречива в том и только в том случае, когда Б противоречиво.

Пусть X; и 1; представляют собой множества нечетных подмножеств с функциями принадлежности (ЦиЙ)} и {ц„(Х|)}. Тогда подстановку определим как конечное множество а пар вида а = {(г1/х),{цх1(11).^,(г,)/цх1(х1)}),...(гп/хп!{цт(1п). хл (х„)}).

Множество {Са} называется унифицируемым, если существует подстановка а, при которой значения истинности каждой формулы из {Оа} отличны от нуля. Следствием такого определения является то, что ни одно из произведений щД) • йД) не должно быть равно нулю.

Если при подстановке а хотя бы одно произведение равно нулю, то определим такую подстановку ау как вырожденную.

Если произведение О<цхЛ).р,;(10<1 для всех 1|, преобразуем его к виду тах^^).^ ))(1/(тах(Цй(1ц •№&))• !АЛ)> а значение ц=тах(рхЙ).щ&)) будем называть внешним значением функции принадлежности для подстановки а.

Будем называть литерой формулу или ее отрицание, дизъюнктом- дизьюнкцию

литер.

Определим резольвенту в исчислении нечетких предикатов.

Пусть С) и С^ - два дизъюнкта, не имеющие общих переменных, Ь1 и 12 - две литеры с функциями истинности ри и в С| и С2. Если 1.1 и-1!^ имеют наиболее общий унификатор а , то дизъюнкт Соа = [Ци'Ни] (Ста - ^кхМСга * '^а) будем называть резольвентой С1 цСг в исчислении нечетких предикатов.

Теорема 3. Пусть даны два дизъюнкта С, и С2, не имеющие общих переменных, и их функции истинности р. 1 и Ц-2. Тогда для функции истинности (-10 резольвенты Со дизъюнктов С] и С2, полученной подстановкой а, справедливо неравенство Ц<£Ц|а' ц2а.

Пусть согласно определению резольвенты С|а = Ьа v С1^ , С2а= ^а у С'2а> Со-С'щУ С'2а, тогда ц)а= мах^а.ц1^), р2а=мах(1 - Иьсх^'га). Щ=мах([х11а,ц12а) >

мах(Ц!_а>М 'ia),MaxO - M-La-lAa)' т-к- 0<)i< 1, т.е. Ццх-Ига» 4X0 и требовалось доказать.

Теорема 4. Пусть даны два дизъюнкта Ci и С2, не имеющие общих переменных, их функции истинности |ii и р2, и существует подстановка а, такая, что С|а = LavC'ia, С2а= _lLavC2a> резольвента С0= C'kjvC^. Если хотя бы одна из функций истинности ц'|а или ц'2а>0.5, то для функции истинности Цо резольвенты Со справедливо неравенство |.Ло> Min(nia,p.2a).

Перепишем неравенство в следующем виде: max(ji' )а,ц' )a)>min (max(jiLC£, ц\а), max(l- pLa, ц'2а)). Пусть ц'щ > 0.5, и если Hlo. > p'ia, тогда шах(1- pLa, ц.'2а)<0.5, и если Hix^uVa» тогда max(p.La,(j'la) = ц'|а и неравенство также справедливо. Аналогично доказывается случай 0.5.

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

Известно, что резолюцией называется правило вывода, генерирующее резольвенты из множества дизъюнктов S. Объединение S с множеством всех резольвент, т.е. с множеством выводов, которые могут быть получены из S, обозначим D(S). Тогда D0(S)=S, Du-n(S)=D(Du(S)). Если S- произвольное конечное множество дизьюнктов, то S невыполнимо тогда и только тогда, когда DU(S) содержит для некоторого u> 0 пустой дизъюнкт. Если D„(S) содержит пустой дизъюнкт, то S невыполнимо, если Du+i(S) совпадает с D„(S), то S выполнимо. Если процедура продолжается бесконечно, то это может трактоваться как недостаток информации.

В четвертом разделе описано формальное представление и классификация прикладных задач качественного характера.

Ограничимся рассмотрением прикладных знаний, для которых существуют область посылок (причин) и область результатов (следствий). Связи между посылками и результатами могут быть логическими и структурными, конкретными и опосредованными, явными и скрытыми, объективными и субъективными, определенными и нечеткими и т.п.

Представим описанную модель следующим образом: Р => R, где Р- область посылок, R- область результатов, => - обобщенный оператор причинно- следственных связей. Разнообразие прикладных задач качественного характера очень велико. Будем считать, что задача включает в себя формулировку F и условия решения С. Очевидно, что Р, R, F и С могут содержать известные и неизвестные элементы, условно назовем их константами и переменными. В рамках предлагаемой модели возможна следующая классификация прикладных задач качественного характера:

1. Формулировка задачи включает в себя преимущественно переменные и относится к области результатов, FsR. Условия задачи включают в себя константы и относятся к области посылок, СеР. Такую задачу отнесем к классу задач

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

2. Формулировка задачи включает в себя преимущественно константы и относится к области результатов, РеК. Условия задачи включают в себя преимущественно константы и относятся к области посылок, Се Р. Такую задачу отнесем к классу задач интерпретации. В результате решения задачи устанавливаются значения переменных, содержащихся в формулировке задачи Б и, возможно, в условиях С.

В формализме исчисления нечетких предикатов обобщенный оператор причинно-следственных связей заменяется импликацией. В такой постановке задачи прогнозирования и интерпретации имеют решение, т.к. дизъюнкты из пар ~|Р и Я, ""'Р и С имеют одинаковую форму, но разные знаки, и при резольвировании будут формироваться пустые дизъюнкты.

3. Формулировка задачи включает в себя преимущественно переменные и относится к области посылок, РеР. Условия задачи включают в себя преимущественно константы и относятся к области результатов, Се 11. Такую задачу отнесем к классу задач идентификации. В результате решения задачи устанавливаются значения переменных, содержащихся в формулировке задачи Б и, возможно, в области посылок Р.

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

В науке и технике такие задачи часто относят к обратным. Для их решения необходимо преобразование описанной формы представления знаний в обратную, то есть из формы Р => Я в форму II => Р. Такое преобразование возможно не всегда, оно требует привлечения дополнительных знаний, проверки гипотез, именно здесь находится область приложения интеллекта, интуиции, здравого смысла. Такие задачи с трудом поддаются формальному решению.

В пятой главе рассмотрены вопросы формализации знаний и решения качественных задач в области молекулярной спектроскопии.

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

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

Знания и методы решения задач реализованы в виде системы программ на языке ТУРБО-ПРОЛОГ.

Рассмотрим некоторые примеры из системы предикатов для формализации спектрохимических знаний.

1|(а,Ь,х|,уь2|)- в спектре содержится полоса колебаний типа а группы Ь с частотой Х|, интенсивностью уь полушириной ъ\. Интенсивность и полуширина задаются целыми числами в интервале (0,5), значения частоты - положительными целыми числами, переменная а определена на множестве возможных типов колебаний (о3- валентные симметричные колебания, 5Р- деформационные плоскостные и т.д.).

Кг 0"|Л) - в молекуле содержится фрагмент Г| с ближайшим окружением г2.

Известные эмпирические знания в ИК-спекгроскопии упорядочены по типам структурных фрагментов и частично по типам колебаний. По своему характеру знания можно разделить на факты (выражения, содержащие константы) и закономерности (выражения, содержащие хотя бы одну переменную). В качестве единиц структурирования знаний приняты основные фрагменты, обладающие характеристическими признаками (С=С, СзС, и С=0 и т.д.). Каждый основной фрагмент описывается в целом, а затем к нему последовательно присоединяются атомы окружения, образуя фрагменты 1-ого, 2-ого, 3-его и т.д. уровней, до границы имеющихся знаний. Образующаяся иерархия знаний представляет собой граф в виде дерева. Будем называть его сетью декларативных знаний. Описание узла сети содержит в себе следующие данные: номер и структура фрагмента, список возможных типов колебаний; общие для данного фрагмента закономерности и факты; закономерости и факты для каждого типа колебаний.

В литературе знания слабо структурированы и изложены скорее хаотично, поэтому заполнение узлов сети требует участия высококвалифицированных экспертов.

В исчислении нечетких предикатов основную гипотезу, описывающую концепцию характеристических признаков в ИК-спектроскопии, можно представить как совокупность (конъюнкцию) выражений вида п,

^(а) -> л (д.^а'ьь'ьх'ьу'ьг',), (3)

1=)

где пг число областей спектра, в которых проявляются характеристические признаки фрагмента А^ ц1, - внешнее значение истинности предиката ^(а'^Ь'ь х\,у'^г',), которое представляет собой численную оценку возможности проявления характеристических признаков фрагмента A¡ в области I. Выражение (3) следует понимать следующим образом: если в структуре молекулы содержится фрагмент А„ то в каждой области I из п, областей спектра с истинностью |д\ проявляются полосы колебаний типа а'1е{о,и5,б,Зр...} структурной группы Ь1, фрагмента А| с частотой, интенсивностью и полушириной, описываемыми значениями нечетких переменных х1,, у'ь г\.

Второй раздел описывает решение качественных задач прогнозирования, интерпретации, структурно-группового анализа в исчислении нечетких предикатов.

Рассмотрим конкретный пример описания знаний и решения задач в ИК-спектроскопии. Основному фрагменту С=С соответствует нулевой уровень в иерархии знаний. Рассмотрим группу ТЯЗ СН=СН, относящуюся к первому уровню.

1. Возможные типы колебаний: валентные и(С=С), валентные о(=СН), деформационные 8(=СН), плоскостные 5р(:=СН).

2. Группа ТЯЗ-ЛЬК обычно имеет полосу валентных колебаний о(С=С) при частоте 1665-1680, интенсивность мала.

0.8 .К2(Т]18,АЬК) I, (и,С=С,(1665,1680),(1,2))

3. ТЯв имеет одну полосу и(=СН) в интервале 3000-3040.

^(П^АВД I, (о,=СН,(3000,3040))

4. ТЯБ имеет поглощение 5(=СН) в области 965-990 с интенсивностью от средней до высокой.

К2(ТК£,АЬК) -> 1,(о,=€Н,(965,990),(3,5))

5. Присоединение к ТИ8 СК, ОН, ОАЬК, С1, Вг, I на положение о(-СН) не влияет.

(Т118,С1*/ОНуОАЬКУС1\/ВМ) 1,(и,=СН,(965,990))

6. При сопряжении ТЯв с СЮ наблюдается небольшое смещение Б(=СН) в сторону больших частот.

ЯгСЛ^СЮ) -» 1,(5,=СН,(970,1000),(3,5))

7. ТИв часто дает полосу плоскостных колебаний 8Р(=СН) средней или высокой интенсивности в области 1290 -1310.

0.9.К2(ТЯ8,АиС) -> 1|(5р,=СН,(1290,1310),(3,5))

Если для формулы 0.8Л1(о,С=С,(1640,10)) осуществить подстановку значения частоты (1635,5), то значение функции истинности для частоты цх(1)»ц,(1)=0.5.( 1635,5), а формула в результате будет выглядеть следующим образом: 0.4.1,(и,С=С,(1635.5)).

Преобразуем в дизъюнкты выражения 2,3,6,7 из примера описания знаний.

1. 0.8.-'К:(ТЯ8,АЬК) У1,(и,С=С,(1665,1680),(1,2))

2. -Ч^ОгаЗДЬК) V 1,(,СН,(3000,3040))

3. -^гСП^.С^у 1,(,СН,(970,1000),(3,5))

4. 0.9.-^,^118,АЬК) V 1,(,СН,(1290,1310),(3,5))

В задачах интерпретации спектров нам известны как структура молекулы, так и её спектр, требуется установить соответствие между структурными особенностями молекулы и характеристическими признаками спектра. Добавим дизъюнкт, характеризующий условия решения задачи, в данном случае описывающий структурные особенности молекулы.

5. Я2(ТК5,АЬК)

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

6. ->1,(а,,Ь1,1670,1) [1,(а,,Ь,, 1670,1)]

7. -|1,(а2,Ь2,3030,2) [1,(а2,Ь2,3030,2)]

8.-I, (а3,Ь3,1312,4)[1з(аз,Ьз, 1312,4)]

9. ->1,(34,Ь4,970,3) [1|(а4,Ь4,970,3)]

В квадратных скобках указаны "ответные" дизъюнкты, полученные отрицанием исходного дизъюнкта. Если получается пустой дизъюнкт, то в "ответном" дизъюнкте содержатся искомые значения переменных.

Резольвируя последовательно (1),(6),(5), получаем пустой дизъюнкт, ответный дизъюнкт (10) содержит значения переменных ai,b[ и значение функции истинности

10. 0.8 .[1|(о,С=С, 1670,1)]

Резольвируя (2),(7),(5), получим

11. [1](и,=СН,3030,2)]

Резольвируя (4),(8),(5), получим

12.0.54 .[1,(5Р ,=СН,1312,4)]

Значение функции истинности 0.54 получается как результат умножения внешнего значения 0.9 на значение 0.6, полученное в результате подстановки (1312,5/1310,5).

Резольвирование (3),(9),(5) возможно лишь в результате вырожденной подстановки, т.к. С=0 не относится к классу ALK. Вырожденная подстановка приводит к непредсказуемому изменению значений функции истинности, определить которое можно лишь привлекая дополнительные знания, описываемые как закономерности.

13. M„4.[Ii(S,=CH,970,3)]

Таким образом, ответные дизъюнкты (10-13) устанавливают соответствие между характеристическими признаками спектра (частота, интенсивность), типами колебаний и структурными группами, и дают оценку истинности этого соответствия.

Задача прогнозирования спектра состоит в том, чтобы по известным особенностям строения молекулы высказать предположения об особенностях ее ИК-спекгра, и решается во многом анатогично задаче интерпретации.

Рассмотрим далее задачу идентификации. На первом этапе решается задача структурно-группового анализа (СГА).

Для решения задачи СГА и установления структур молекул по их спектрам используется следующее следствие гипотезы (3): если в ИК-спектре имеется множество полос с частотами Xj, интенсивностью^ и полуширинами z, (j=l,k), то для множества фрагментов А; справедливы выражения:

к ш

а Ii(aj,bj,xj,yj,zj) v (]Л. njt) .R2(A,) (4 )

j-l ¡4

Значение p.J, характеризует степень соответствия j-ой полосы спектра и области t фрагмента А;. В выражения (4) включены только те фрагменты, которые имеют отношение к рассматриваемому спектру. При решении задачи СГА необходимо вводить в рассмотрение только те фрагменты, возможность присутствия которых в исследуемой молекуле подтверждается наличием в спектре всех характеристических признаков с учетом значения истинностей. Формально это утверждение описывается выражением:

nj

A ц', ^(а'.МЛУ.Д) R.2(Aji) ( 5 )

t-l

Преобразуем выражения, представленные в форме (3), в форму (5), а затем с помощью эквивалентных преобразований в множество дизъюнктов (6). К знаниям в форме (6) необходимо добавить дизъюнкты, описывающие спектр.

Первый этап решения задачи структурно-группового анализа состоит в выявлении подмножества фрагментов {AJj}, характеристические признаки которых проявились в спектре. К множеству дизъюнктов, описывающих знания в форме (6), добавим дизъюнкт, представляющий собой формулировку задачи: ""^(А). Для опровержения дизъюнкта "^(А) необходимо резольвировать дизъюнкты, описывающие знания, спектр и утверждение "^(А).

Таким образом, в результате первого этапа решения задачи СТА устанавливается, какие фрагменты можно связать с экспериментальным спектром, определяются оценки значения истинности наличия каждого фрагмента из {Ai} в молекуле, т.е. формируется множество {AJj}. Кроме того, делается частичная интерпретация групп, ответственных за появление той или иной частоты и типы колебания этих групп.

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

Для формального решения задачи установления структуры многоатомных молекул необходимо произвести генерирование вожможных вариантов структурных формул из набора фрагментов, установленных в результате СГА, и оставшихся от брутто-формулы атомов. Каждый из полученных вариантов структурной формулы необходимо проверить на соответствие экспериментальному спектру и формализованным знаниям. В исчислении нечетких предикатов эту задачу можно сформулировать следующим образом: для каждого фрагмента As; из множества {А|}, входящего в состав проверяемой структурной формулы S, доказать невыполнимость формулы ""R^A*). Если хотя бы для одного из фрагментов множества {Aj} этого сделать не удается, то структурная формула S исключается из рассмотрения. Значение функции истинности, полученное в результате доказательства, служит для ранжирования вариантов ответов. Для доказательства используется та же форма представлений знаний (4), что и для решения задачи СГА на первом этапе, при этом

ответные дизъюнкты содержат для каждого фрагмента As, сведения о группах, ответственных за появление той или иной частоты, и типах колебаний этих групп, т.е. производится интерпретация спектра.

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

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

Ключевым элементом в управлении деятельностью предприятия является принятие решения о возможности выполнении очередного производственного или коммерческого заказа и определение сроков его исполнения.

В системе предикатов, описывающих деятельность предприятия, могут присутствовать следующие:

ПРОДУКЦИЯ ( шифр, количество );

ТОВАРЫ (шифр, количество);

СЫРЬЕ ( шифр, количество );

СНАБЖЕНИЕ ( шифр, поставщик, количество );

ТРАНСПОРТ ( вид, шифр, количество );

ОПЛАТА (заказчик, вид, сумма, время ).

Здесь количество является нечеткой функцией от времени и в некоторых случаях от шифра.

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

А( СЫРЬЕ ( шифр„ количество,(tp)) —>

! puj ЛРОДУКЩЩишс^, количествоy(tp))

Здесь индекс i описывает перечень используемого сырья и материалов, необходимых для производства продукции вида j, {j}- ассортимент производимой продукции.

Выражения, описывающие производственные возможности, следует понимать таким образом: если имеется необходимое количество,(tp) сырья и материалов всех видов i, то за время t с истинностью puj может быть произведено количествоs (t) продукции вида]. Здесь характеризует степень надежности оборудования, энерго-и теплоснабжения и тому подобные факторы.

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

V( |дцг. СНАБЖЕНИЕ ( шифрк, поставщик „количествоt(tk))) ' Л( Цис> ТРАНСПОРТ ( вид, шифрь количество¿(t*))) -» с СЫРЬЕ ( шифрк, количество*(tk));

V( циг. СНАБЖЕНИЕ (шифрк, поставгцик„количество¿(t^))) 1 л( цис. ТРАНСПОРТ (вид, шифрь количество^))) -> с ТОВАРЫ ( шифрь количество^))

Здесь индекс г описывает возможных поставщиков с оценками их надежности IV, индекс с характеризует транспортные возможности и их оценку (д„,, индекс к -перечень сырья, материалов или товаров вида к.

Рассматриваемые выражения следует понимать таким образом: если имеется потребность в сырье, материалах или товарах вида к, то при наличии необходимого транспорта требуемое количество к(Х^) с истинностью тт(риг, цис) может быть получено на склад от одного из поставщиков г за время

Сведения о запасах на складе формализуются следующим образом: лПРОДУКЦШКгигл^р,, количество^)) ! Л( СЫРЬЕ ( шифр,, количество,{ у)

' лТОВАРЫ ( шифр/,, количество к

Каждый заказ может быть описан выражениями: л ( ПРОДУКЦИЯ (шифр,, количество! (У)) л (ТОВАРЫ(шифрк,

I к

количество*(1:г))) л НЕОПЛАТА (заказчик, вид, сумма, У Формально заказ представляет собой качественную задачу, т.е. теорему, оплата и транспорт характеризуют условия ее решения, сведения о производственных возможностях, снабжении и складских запасах- знания (аксиомы). Для решения задачи необходимо доказать невыполнимость отрицания логического выражения, описывающего заказ.

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

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

Во втором разделе дано описание решения задач оценочного характера. Описана разработаная с участием автора автоматизированная система экспертных оценок изделий легкой и текстильной промышленности, включающая в себя подсистемы "Художественно-технический совет " (ХТС) и "Выставки".

Учет и анализ мнения специалистов и населения о качестве изделий производится на основе результатов рассмотрения изделий на художественно-технических советах, демонстрациях моделей, а также сведений, полученных на постоянно действующих тематических выставках.

При оценке качества продукции используются две группы показателей: объективные технические, предусмотренные стандартами; органолептические, определяемые экспертами.

Органолептическим методом определяется внешний вид изделий (художественно-колористическое оформление, отделка, конструкция, фасон-модель и т.д.). Согласно отраслевым методическим указаниям оценки качества продукции, оценка показателей, определяемых органолептическим методом, производится по 40-балльной системе. Общее количество баллов Вт„ представляет собой сумму отдельных показателей Ь„ состав и максимальные величины которых определены для различных видов т и групп п изделий. Так, для хлопчатобумажных тканей и штучных видов изделий ¡=1,2,3, при этом Ьг показатель художественно-колористического оформления, Ъ2- СТруКТрЫ, £>з - ЗаКЛЮЧИТбЛЬНОИ ОТДеЛКН, Т.е. Втл = ЕБИЬ,^. С точки зрения прикладной теории исчисления нечетких предикатов степень принадлежности изделия к той или иной категории качества будем оценивать характеристической функцией Ц1=В|/Вт„ тах, а вложенные показатели- функциями ^ =ЬД^ „ш, /Ьц тах,

^цк "Ь^/Ь^к тах • Относительная оценка каждого показателя производится по совокупности относительных оценок вложенных показателей, что соответствует их конъюнкции. Тогда значения характеристических функций ц|=ш1п{р]}, рг=тт{ру}, Иц=тт{щ,к}, т.е. оценка качества изделия определяется минимальным из множества относительных значений показателей. Фактически это означает, что качество изделия нельзя оценить выше, чем качество его наихудшего параметра.

Далее описана система контроля сроков выполнения решений на примере деятельностьи НИС вуза по формированию и выполнению плана НИР. Рассмотрена система предикатов ЗАМЕЧАНИЕ^,(1г), ВЫГОВОРИСЬ-), ОТСТРАНЕНИЕ^,с!о)), где йг, с!у, ¿о- нечеткие переменные, описывающие возможные даты утверждения и сдачи тем, которые, при сопоставлении их с реальными, могут привести к вынесению соответствующих взысканий.

В третьем разделе описано применение прикладного исчисления нечетких предикатов для разработки естественноязыкового интерфейса.

Любой практически пригодный интерфейс, воспринимающий естественный язык, должен обладать способностью обрабатывать неграмматичные выражения.

Пусть © - словарь предметной области, Ч" - множество лексем (в том числе и содержащих орфографические ошибки) входного высказывания. Задачу лексико-морфологического анализа определим как задачу идентификации элементов путем сравнения двух множеств V и © с нечетким условием типа "при идентификации лексем входного высказывания Ч' выбрать из словаря в качестве эталонных образцов такие элементы ©, которые обладали бы максимальным сходством с лексемами Ч'".

Результат лексико-морфологического анализа представляет собой множество, каждый элемент которого характеризуется набором < ср, Е, M, Q >, где <р - лексема входного высказывания 4*; H={4i} (i=l,...,n) - образцы, подобранные из словаря 0; M={Hi}(i=l,...,n) - степень сходства, с которой каждый элемент S соответствует о; f2={cot}(i=l,...,n) - морфологическая информация, соответствующая Н.

Если входное высказывание представить в виде нечеткого множества 4,=рА/<р1+...+|дп/ф„, то используя свойство лексем "быть цепочкой символов" и принцип левостороннего центрирования можно определить наиболее вероятные элементы H для каждой лексемы и степень сходства входного высказывания M=min{ (Xj. 1. Целью синтаксического анализа является построение структуры входного высказывания, отображающей синтаксические связи между лексемами этого высказывания. В рамках предлагаемого формализма подобные структуры представляют собой вариативные деревья синтаксического подчинения, каждое из которых является нечетким графом, описывающим потенциально возможный вариант разбора входного высказывания.

Описанный подход проиллюстрирован примером из предметной области "молекулярная спектроскопия".

В седьмой главе рассмотрены системные вопросы прикладной теории решения задач качественного характера на ЭВМ.

В первом разделе описаны основные понятия и модели, используемые в процессе решения качественных задач.

Решение задач рассматривается как процесс взаимодействия специалиста и ЭВМ. При этом специалист решает задачи на осознанном (рефлексном) уровне, т.е. представляет собой рефлексную решающую систему (РРС). ЭВМ решает задачи на формальном уровне, т.е. представляет собой формачьную решающую систему (ФРС).

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

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

Опишем систему S как множество совместно рассматриваемых предметов, свойств, операций, отношений, т.е. S={{A},{H},{D},{R.}}. Предметную область определим как тройку К=(К„,К2,К(). Знания для каждого из трех рассмотренных уровней определим как четверку K=({Ai},{Hi},{Pj),{R,}), где {А5},{Н)},{Р;),{R,}-множества предметов, свойств, процедур, отношений.

Прикладную качественную задачу определим как тройку T=(K'n,P,Kcrcs), где Кт и Kres - исходное и результирующее состояние предметной области; р-

активизированное подмножество знаний, включающее в себя элементы множеств {А(},{Н|},{Р|},{Я;}, значения которых в исходном состоянии неизвестны, а в результатирующим определены, а также все элементы рассмотренных множеств, необходимых для решения задачи.

Двойку Тг=(Кги,рас1) назовем результатом решения, двойку Т1=(К"1,Эас') -постановкой (формулировкой) задачи. Процесс решения задачи - это изменение исходного состояния предметной области в результирующее, т.е. К"1 в Кг".

Во втором разделе описаны вопросы общения решающих систем.

В качестве средств общения предлагается рассмотреть язык общения формальной решающей системы (ЯОФ) и ограниченное подмножество профессионального языка специалиста, т.е. язык общения рефлексный (ЯОР). Выделим в языках общения следующие типы предложений: повествовательные (информативы), вопросительные, повелительные (императивы). Дополним прикладное исчисление нечетких предикатов операторами ! и ?. Оператор ? определяет, какой из объектов ЯОФ находится под вопросом, оператор ! определяет, какие действия и с какими объектами необходимо выполнить. Результатом выполнения оператора ? является ответ, оператора ! - отчет.

Далее рассмотрено формальное представление возможных видов прямых и косвенных вопросов, императивов нахождения, а также правильных ответов и отчетов.

Для описания процесса решения задач введен новый тип предикатов-предикаты цели 0(РьР2,...,Рт,...,Рп), определенные на множестве правильно построенных формул {Рт} языка общения формальной системы, область значений которого составляют утверждения "цель поставлена" (0), "цель достигнута" (1), "достигнуты подцели" (число из интервала 0,1). Если Ь- множество переменных и констант, встречающихся в {Рт}, тогда императивом цели назовем выражение Ю^... П(Ь|)). Рассмотрены основные императивы формальной решающей системы на примере прикладных знаний ИК- спектроскопии.

В третьем разделе рассматриваются цели решающих систем.

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

В восьмой главе рассмотрены вопросы программной реализации методов решения качественных задач.

В первом разделе приведены примеры программ на ТУРБО-ПРОЛОГе, расширенном для нечеткой логики, в частности, программы решения задачи структурно-группового анализа в исчислении нечетких предикатов. Тексты описания знаний приведены ранее в главе 5.

Во втором разделе приведен пример машинной распечатки решения задачи структурно-группового анализа в нечеткой логике, включающий в себя этапы построения нечетких импликаций, интерпретации характеристических признаков,

преобразования системы импликаций в конъгокгквную нормальную форму, оценки истинности получаемых результатов.

Основные выводы и результаты

1.Предложена теория и методы формализации нечетких знаний прикладного характера на основе объединения возможностей логики предикатов первого порядка я теории нечетких множеств - прикладное исчисление нечетких предикатов.

2.Показана возможность решения качественных задач в прикладном исчислении нечетких предикатов методом доказательства теорем с оценкой истинности полученных результатов.

3.Проведена формализация и структурирование логических компонентов знаний прикладного характера в ряде проблемных областей.

4.Проведена систематизация и формальное описание широко распространенных классов прикладных качественных задач: прогнозирования, интерпретации, идентификации.

5.Приведены примеры знаний решения качественных задач в описанном формализме на языке ТУРБО-ПРОЛОГ.

6.Показана возможность использования нечеткой логики в естественноязыковых приложениях.

7.Методами дискретной математики решены качественные задачи построения полного набора структурных изомеров многоатомных молекул и идентификации структурных формул по спектрохимическим данным.

8.Разработанная теория и методы логического представления нечетких знаний и решения качественных задач были использованы и используются в настоящее время при создании ряда экспертных систем и систем обработки данных в области прикладных научных исследований и в области автоматизации производства и управления:

-система математического синтеза и анализа молекулярных структур МАИСС;

-экспертная система распознавания структур многоатомных молекул РАСТР;

- экспериментальная экспертная система СПРИНТ;

-система управления производственной и коммерческой деятельностью малого предприятия;

-автоматизированная система оценки качества изделий легкой промышленности;

-система контроля сроков выполнения решений.

Основные результаты диссертации опубликованы в следующих работах:

1. Серов В.В., Эляшберг М.Е., Грибов Л.А. Система математического "синтеза" и анализа всех структурных формул органических соединений, соответствующих заданной брутто-формуле. Доклады АН СССР. т. 224, №1, М., 1975. Зс. (в соавторстве, авторские 2с.).

2. Серов В.В., Эляшберг М.Е., Грибов Л.А. Система математического "синтеза" и анализа молекулярных структур и ее применение в химии. 11-ый Менделеевский съезд по общей и прикладной химии. Физическая химия. Химическая физика и катализ. Электрохимия. М.: Наука, 1975.7с.(в соавторстве, авторские 4с.).

3. Эляшберг М.Е., Серов В.В. Грибов J1.A. Применение ЭВМ для построения структурных формул по данным молекулярного спектрального анализа. Тезисы докладов. Третий семинар "Использование вычислительных машин в спектроскопии молекул". Новосибирск, 1975.2с. (в соавторстве, авторская 1с.).

4. Serov V.V., Elyashberg М.Е., Gribov L.A. Mathematical synthesis and analysis of molecular structures. Jornal of Molecular Structure, 31, Amsterdam, 1976. pp. 381-397. (в соавторстве, авторские Юс.).

5. Серов В.В., Эляшберг М.Е. Математический "синтез" и анализ молекулярных структур с применением ЭВМ и его использование. Тезисы докладов 6-ой Межотраслевой конф. молодых специалистов. М.: ГИРЕДМЕТ,1976.2с.(в соавторстве, авторские 1.5с.).

6. Серов В.В., Эляшберг М.Е., Грибов Л.А. Комплекс алгоритмов и программ математического "синтеза" и анализа структурных формул химических соединений. Депонент ВИНИТИ №1464-76. М.,1976. 76с. (в соавторстве, авторские 60с.).

7. Серов В.В., Эляшберг М.Е., Грибов Л.А. Алгоритм и программа проверки наличия или отсутствия заданных фрагментов в струиурных формулах химических соединений, представляемых графами. Журнал структурной химии. Т. 17, К» 6, Новосибирск, 1976.6с. ( в соавторстве, авторские 5с.).

8. Серов В.В., Эляшберг М.Е., Грибов Л.А. Математический "синтез" всех топологических изомеров бензола. Известия ТСХА. Вып. 1, М., 1977,2с.(в соавторстве, авторские 1с.).

9. Туренко Ф.П., Эляшберг М.Е., Серов В.В. Выборка методом аддитивных функций изомерных структур из множества синтезированных химических графов. Тезисы докладов. 4-ая Всесоюзная конференция "Использование вычислительных машин в спектроскопии молекул". Новосибирск, 1977. 2с. ( в соавторстве, авторские 0.5с.).

10. Серов В.В., Эляшберг М.Е. Система программ математического "синтеза" и анализа структурных формул всех изомеров, отвечающих заданной брутто-формуле. Сб. аннотаций программ для молекулярной спектроскопии. Новосибирск, 1977. 1с. (в соавторстве, авторские 0.5с.).

И. Эляшберг М.Е., Серов В.В., Грибов Л.А. Распознавание химических соединений по их молекулярным спектрам с применением программы построения структурных формул из атомов и фрагментов. Журн. прикладной спектроскопии. Т.26, Вьга. 2, Минск, 1977. 7с. ( в соавторстве, авторские Зс.).

12. Серов В.В., Грибов Л.А., Эляшберг М.Е. Алгоритм и программа идентификации многоатомных молекул по оптическим спектрам. Доклады АН СССР. Т. 232, № 3, М.,1977. 4с. ( в соавторстве, авторские Зс.).

13. Gribov L.A., Elyashberg M.E., Serov V.V. Computer system for structure recognition of polyatomic molecules by I.R., N.M.R., U.V. and M.S. methods. Anaiytica Chimica Acta, 95, Amsterdam, 1977, pp. 75-96. ( в соавторстве, авторские Юс.).

14. Серов В.В., Эляшберг М.Е., Грибов Л.А. Система распознавания структуры сложных молекул по характеристическим признакам в ИК-, КР-, ЯМР-, УФ- и масс-спектрах. Тезисы докладов. 4-ая Всесоюзная конф. "Использование вычислительных машин в спектроскопии молекул". Новосибирск, 1977. 2с. (в соавторстве, авторская 1с.).

15. Эляшберг М.Е., Серов В.В., Грибов JI.A. Анализ результатов эксплуатации системы РАСТР. Тезисы докладов. 4-ая Всесоюзная конф. "Использование вычислительных машин в спектроскопии молекул". Новосибирск, 1977. 2с. (в соавторстве, авторская 1с.).

16. Серов В.В., Эляшберг М.Е., Грибов Л.А. Структурная интерпретация молекулярных спектров. Системный подход. Сб. Теоретическая спектроскопия. М., .1977. 5с. (в соавторстве, авторские Зс.).

17. Серов В.В., Эляшберг М.Е., Грибов Л.А. Система программ автоматического распознавания структуры многоатомных молекул по колебательным спектрам. Сб. аннотаций программ для молекулярной спектроскопии. Новосибирск, 1977.2с. (в соавторстве, авторская 1с.).

18. Грибов Л.А., Эляшберг М.Е., Серов В.В. и др. Спектры и ЭВМ-инструменты определения пространственных структур молекул. Тезисы докладов 9-ой Межд. конф. по применению ЭВМ в химии и химическом образовании. Новосибирск, 1978. 2с. ( в соавторстве, авторские 0.5с).

19. Серов В.В., Грибов Л.А., Эляшберг М.Е. Система программ идентификации химических соединений по молекулярным спектрам. Депонент ВИНИТИ №2912-78. М., 1978. 125с.( в соавторстве, авторские 105с.).

20. Gribov L.A., Elyashberg М.Е., Serov V.V. On the solution of one classical problem in vibrational spectroscopy. Journal of Molecular Structure, 50, 371-387, Amsterdam, 1978.(всоавторстве, авторские25c.).

21. Эляшберг M.E., Грибов Л.А., Серов В.В. Молекулярный спектральный анализ и ЭВМ. М.: Наука, 19550, 301с. ( в соавторстве, авторские 150с.).

22. Букреев В.З., Серов В.В., Завилевич М.Л. Комплекс программ подсистемы "Выставки" автоматизированной системы экспертных опенок. Тезисы докладов. Научно-технический семинар "Системный анализ и оптимизация управления". М., 1982. 0.5с. ( в соавторстве, авторские 0.25с.).

23. Букреев В.З., Жуковский В.И., Серов В.В. и др. Вопросы совершенствования. методов оценки уровня качества образцов изделий на художественно-технических советах МИНЛЕГПРОМа. Тезисы докладов. Научно-технич. семинар "Системный анализ и оптимизация управления". М., 1983. 0.5с. ( в соавторстве, авторские 0.25с.).

24. Серов В.В., Грибов Л.А. Общесистемные вопросы использования прикладных программ по молекулярной спектроскопии. Тезисы докладов. 6-ая Всесоюзная конф. "Использование вычислительных машин в спектроскопии молекул и химических исследованиях". Новосибирск, 1983. 2с.(в соавторстве, авторская 1с.).

25. Серов В.В., Грибов Л.А., Эляшберг М.Е. Прикладное логическое исчисление для решения качественных исследовательских задач по молекулярной спектроскопии. Тезисы докладов. 6-ая Всесоюзная конф. "Использование вычислительных машин в спектроскопии молекул и химических исследованиях". Новосибирск, 1983. 2с. ( в соавторстве, авторская 1с.).

26. Серов В.В., Эляшберг М.Е, Формализация решения качественных спектроскопических задач. Тезисы докладов 5-ой Всесоюзной конференции по аналитической химии органических соединений. М.,1984. 2с. (в соавторстве, авторская 1с.).

27. Серов В.В. Решение качественых задач методом доказательства теорем в прикладном логическом исчислении. Тезисы докладов. Межвузовский научно-технич. семинар "Системный анализ, техническая и экономическая кибернетика". М., 1984. 1с.

28. Серов В.В., Орлов А.Г. Программное обеспечение подсистемы "Художественно-технический совет" автоматизированной системы экспертных оценок. Тезисы докладов. Межвузовский научно-технический семинар "Системный анализ, техническая и экономическая кибернетика". М., 1984. 1с. (в соавторстве, авторские 0.5с.).

29. Букреев В.З., Орлов А.Г., Серов В.В. Подсистема "Художественно-технический совет" автоматизированной системы экспертных оценок. Жури. Текстильная промышленность, №9, М., 1984.2с. ( в соавторстве, авторская 1с.).

30. Serov V.V., Gribov L.A., Elyashberg М.Е. Elements of the applied theory of solving gualitative problems of molecylar spectroscopy. Journal of Molecular Structure 129, Amsterdam, 1985. pp. 183-214. ( в соавторстве, авторские 20c.).

31. Серов B.B., Эляшберг М.Е., Петров В.М. Разработка системы искусственного интеллекта для молекулярной спектроскопии РАСТР-4. Тезисы докладов. 7-ая Всесоюзная конф. "Использование вычислительных машин в химических исследованиях и спектроскопии молекул". Рига, 1986. 1с. (в соавторстве, авторские 0.5с.).

32. Серов В.В., Эляшберг М.Е. Формализация решения качественных задач молекулярной спектроскопии. Журн. структурной химии. Т.27, №2, Новосибирск, 1986.7с. ( в соавторстве, авторские 5с.).

33. Эляшберг М.Е., Серов В.В. Теоретические вопросы построения системы искусственного интеллекта для молекулярной спектроскопии. Тезисы докладов. 7-ая Всесоюзная конф. "Использование вычислительных машин. в химических исследованиях и спектроскопии молекул". Рига, 1986. 2с. (в соавторстве, авторская 1с.).

34. Серов В.В., Эляшберг М.Е. Основные концепции построения системы искусственного интеллекта для молекулярной спектроскопии. Тезисы докладов. 7-ая Всесоюзная конф. "Использование вычислительных машин в химических исследованиях и спектроскопии молекул". Рига, 1986. 2с. (в соавторстве, авторская 1с.).

35. Эляшбсрг М П., Серов П.П., Никитин Г.Н. Система распознавания структуры молекул PACT Р-3. Тезисы докладов. 7-ая Всесоюзная конф. "Использование вычислительных машин в химических исследованиях и спектроскопии молекул". Рига, 1986.1с. (в соавторстве, авторские 0.5с.).

36. ')ляшберг М.П., Серов II П., Петров ИМ., Никитин Г.Н. Система искусственною интеллекта для молекулярной спектроскопии. Тешсы докладов. Всесоюзная конф. "Магматические метлы и ЭВМ в аналитической химии". М, 1986. 2с. ( в соан юрстве, авторские О 5с ).

37.1>укрс-ев 1) 3 , Самородов И.О., Серов И П. и лр. Автоматизированная система iKcncpiiH-ix опенок для оиенки качсс iua промышленной проду кипи и изучения шнрсбшельскою спроса. Сб. научных трудов "Сонсршснаионанне opiaiiiniinini и анюмашишия н юрювле юрода". III10 АСУ "Москва", М , 1986. 11с. {в соавторам, аигорекпе Зс )

38. Серо» ПИ. Исчисление нечакпх предикатов и сю использование для разработ! 'Зксисршых систем Тении до кладок. Межиуюнскин сб. научных 1рудов "('наемный анализ, техническая и жономичсская кибернетика". М., 1987. 2с.

39. riyasliherg М П., Scrov V.V., (iribov L.A. Artificial intelligence syslems for molecular spectral aifiifjsis". Vatonta, VolJ4, No.l, Great Britain, 19Я6. pp. 21-30. ( a coauiopciae, авторские 4c.).

40. Scrov V.V., ("lyashberg M.E., Gribov L.A. System-related matters in the theory of solving qualitative problems. Journal of Molecular Structure, 178, Amsterdam, 1988. pp. 1-21. ( u соавюреше. авюрские 17c.).

41. Петров П.М., Серов 1)1). Представление знаний в экспертной системе, базирующейся па обьектно-орнентиронаниом метоле и исчислении нечетких преликаюа Тешем докладов. За» Меж д. иаучно-тсхнич. конф. 'Программное обеспечение ')ПМ'\ Тверь, 1990. Зс. ( в соавторстве, авторские 1.5с.).

42. Петров II М., Серов В.П. Взаимодействие с экспертной системой на естественном языке. Межвузовский сб. научных трудов "СистемныЛ анализ, информантка и выч техника". М: I'll 1 ТЛИ, 1992. 2с. ( в соавторстве, авторская 1с.).

43. Негров ИМ , Серой !) П. Итерированная модель предметов области ъ системе, основанной на знаниях. Межвузовский сб. научных трудов "Системный липши. ниформапнаиня и прикладные задачи.1' М.: Р'Л 1ПП1. 1994. 5с. ( в соавторстве, аиюрскне 2с.).

44. Ilcipon ИМ.. Серов II В. Модель полимания связного на уровне абзаца научно-техническою текси. Матер, конф. "Автоматизация проектнрованпя и произволе 1иа в ле|коЙ промышленности.'" М.: 1'ЗНГЛП, 1995. 4с. ( в соашорстве, аиюрскне 1.5с.).

45. Петров И М . Серов II11. Me голы н формалшиИ аппарат, обеспечивающие annum нечрамматнчних выражений ограниченного естественноюязыка Матер, конф. "Анюмаппанпя проектирования и производства в легкой промышленности." М.: РЗИТЛО. 1995. 4с. ( » солшораве, авторские 1.5с.).

46. Сером В И. Основные понятия прикладного исчисления нечетких нреднкаюв для формалншини знаний и решения задач качестненкою характера. 1езнсы доклалоп. Межвузовская научная кон<|>. "Современные проблемы текстильной нлегкой промышлеииосгн''. М.: 1'ЗИТЛП. 1996. 1с.

47. Scrov V.V. Elements of the oppliend theory of solving qualitative problems. Multiple criteria ami game problems under imcertainti. The Fourth International Workshop. Moscow. 1996. 1c.

48. Серов II.H. Элементы прикладной теории исчисления нечетких предикатов и ее применение для представления знаний и решения качественных задач. Сб. научных трудов "СистемныП анализ, информатика н оптимизация* Международной академии информаитини. М., 1997. с. 138*155.

49. Серов П.П. Применение прикладной теории исчисления нечетких предикатов для формализации знанпП и принятия решений в управлении производством и коммерческой деятельностью малою предприятия. Сб. научных трудов "Системный анализ, информатика и оптимизация" Международной академии информати шиш. М, 1997. с. 156* 174.

Подписано в печать 20.10.97. Заказ ЬОЪ. Тираж ЮОэкэ. Объем 2,0 п.л. РосЭИТЛП.

Ь \i с>5

Ъь tC-* h

%

/А,

РОССИЙСКИЙ ЗАОЧНЫЙ ИНСТИТУТ ТЕКСТИЛЬНОЙ И ЛЕГКОЙ

ПРОМЫШЛЕННОСТИ

На правах рукописи

СЕРОВ Владимир Васильевич

МАТЕМАТИЧЕСКИЕ МЕТОДЫ, АЛГОРИТМЫ И ПРОГРАММНЫЕ СИСТЕМЫ ДЛЯ РЕШЕНИЯ ПРИКЛАДНЫХ ЗАДАЧ КАЧЕСТВЕННОГО ХАРАКТЕРА ПРИ ЛОГИЧЕСКОМ ПРЕДСТАВЛЕНИИ НЕЧЕТКИХ ЗНАНИЙ

05. 13.11 - Математическое и программное обеспечение вычислительных машин, комплексов, систем и сетей

Диссертация на соискание ученой степени доктора технических наук

Москва 1997

СОДЕРЖАНИЕ

ВВЕДЕНИЕ 4

1. СОСТОЯНИЕ ВОПРОСА И ЗАДАЧИ ИССЛЕДОВАНИЙ 8

1.1. Общая характеристика вопроса представления знаний и методов решения качественных задач прикладного характера

с применением ЭВМ 8

1.2. Вопросы нечеткости, неясности и других граней неопределенности в теории и практических применениях 10

1.3. Математические методы и системы для решения прикладных

задач качественного характера 15

1.4. Описание постановки задач исследований

и последовательности их решения 21

1.5. Выводы 23

2. РЕШЕНИЕ ЗАДАЧИ МАТЕМАТИЧЕСКОГО СИНТЕЗА И АНАЛИЗА МОЛЕКУЛЯРНЫХ СТРУКТУР МЕТОДАМИ ДИСКРЕТНОЙ МАТЕМАТИКИ 25

2.1. Постановка задачи и ее практическое значение 25

2.2. Алгоритм генерации полного набора матриц смежности неизоморфных графов 27

2.3. Алгоритм анализа матриц смежности по их топологическим особенностям 31

2.4. Система математического синтеза и анализа молекулярных структур МАИСС 37

2.5. Примеры применения системы МАИСС 39

2.6. Выводы 45

3. РЕШЕНИЕ ЗАДАЧИ ИДЕНТИФИКАЦИИ СТРУКТУР МНОГОАТОМНЫХ МОЛЕКУЛ ПО СПЕКТРОХИМИЧЕСКИМ ДАННЫМ ПРИ ТАБЛИЧНО - ПРОДУКЦИОННОЙ ФОРМЕ ПРЕДСТАВЛЕНИЯ НЕЧЕТКИХ ЗНАНИЙ 46

3.1. Постановка задачи и ее практическое значение 46

3.2. Система распознавания структур многоатомных молекул РАСТР 48

3.3. Представление знаний в системе РАСТР 52

3.4. Примеры решения задач идентификации структур молекул 58

3.5. Выводы 64

4. ПРИКЛАДНОЕ ИСЧИСЛЕНИЕ НЕЧЕТКИХ ПРЕДИКАТОВ 65

4.1. Постановка задачи 65

4.2. Основные определения и свойства 67

4.3. Дедуктивные вопросы прикладного исчисления нечетких предикатов 73

4.4. Формальное представление и классификация прикладных

задач качественного характера 79

4.5. Выводы 81

5. ФОРМАЛИЗАЦИЯ ЗНАНИЙ И РЕШЕНИЕ КАЧЕСТВЕННЫХ ЗАДАЧ В ОБЛАСТИ МОЛЕКУЛЯРНОЙ СПЕКТРОСКОПИИ 82

5.1. Формализация знаний 82

5.2. Решение качественных задач прогнозирования,

интерпретации, структурно-группового анализа 97

5.3. Выводы 107

6. ПРИМЕНЕНИЕ ИСЧИСЛЕНИЯ НЕЧЕТКИХ ПРЕДИКАТОВ ДЛЯ ФОРМАЛИЗАЦИИ ЗНАНИЙ И РЕШЕНИЯ ЗАДАЧ КАЧЕСТВЕННОГО ХАРАКТЕРА В РАЗЛИЧНЫХ ПРЕДМЕТНЫХ ОБЛАСТЯХ 108

6.1. Управление производственной и коммерческой

деятельностью предприятия 108

6.2. Задачи оценочного характера 125

6.2.1. Оценка качества изделий народного потребления 125

6.2.2. Контроль сроков выполнения решений 129

6.3. Разработка естественноязыкового интерфейса 131

6.4. Выводы 138

7. СИСТЕМНЫЕ ВОПРОСЫ ПРИКЛАДНОЙ ТЕОРИИ РЕШЕНИЯ ЗАДАЧ КАЧЕСТВЕННОГО ХАРАКТЕРА 140

7.1. Основные понятия и модели, используемые в процессе

решения качественных задач 140

7.2. Вопросы общения решающих систем 144

7.3. Цели решающих систем 149

7.4. Выводы 153

8. ВОПРОСЫ ПРОГРАММНОЙ РЕАЛИЗАЦИИ МЕТОДОВ РЕШЕНИЯ КАЧЕСТВЕННЫХ ЗАДАЧ В ИСЧИСЛЕНИИ НЕЧЕТКИХ ПРЕДИКАТОВ 154

8.1. Примеры программ на ТУРБО-ПРОЛОГе, расширенном для 154 нечеткой логики

8.2. Пример решения задачи структурно-группового

анализа в нечеткой логике 178

8.3. Выводы 198 ОСНОВНЫЕ ВЫВОДЫ И РЕЗУЛЬТАТЫ 199 СПИСОК ЛИТЕРАТУРЫ 201

ВВЕДЕНИЕ

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

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

В научных исследованиях компьютеры традиционно используются для моделирования, решения систем уравнений, оптимизации и т.д. в качестве вычислительного устройства, преобразующего некоторые наборы исходных данных в выходные результаты в виде массивов чисел, таблиц, графиков в соответствии с используемыми теориями и методами. Однако существует и другая сторона научных исследований, связанная с необходимостью быстрого и эффективного решения практических прикладных задач. Решение таких задач, как правило, не связано с привлечением глубоко проработанных теоретических знаний, а производится на основе эмпирических данных, известных особенностях, закономерностях и т.п. Эти знания представляют собой некоторый "поверхностный" слой, необходимый и достаточный для решения практически важных задач. Такие знания обычно объемны, слабо систематизированы, источником их является научная литература, собственный опыт специалиста, для них характерны некоторая неопределенность, нечеткость как в содержании, так и в методах применения. В то' же время прикладные задачи в основном носят массовый характер, их постоянно решают многие специалисты с разным опытом и уровнем квалификации. Важность формализации подобных знаний и разработки необходимых решающих процедур с оценкой истинности получаемых результатов не вызывает сомнения.

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

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

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

Цель работы заключается в разработке нового научного направления в области представления знаний и методов решения задач - теории и методов формализации логических компонентов нечетких знаний и процедур решения прикладных задач качественного характера.

Для достижения поставленной цели в диссертации должны быть решены следующие задачи.

1. Разработана теория и методы представления и формализации логических компонентов нечетких знаний, используемых в прикладных научных исследованиях, организационной, управленческой деятельности и ряде других областей применения ЭВМ.

2. Разработаны методы, алгоритмы и процедуры решения прикладных качественных задач широко распространенных классов: прогнозирования, интерпретации, идентификации и т.д.

3. Создан пользовательский интерфейс на основе преимуществ предложенных методов формализации нечетких знаний и решения качественных задач.

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

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

собой конструкцию, синтаксическая правильность которой гарантирует семантическую правильность.

Научная новизна диссертации заключается в следующем: -решена задача математического синтеза и анализа молекулярных структур методами дискретной математики и разработан комплекс программ МАИСС;

-решена задача идентификации структур многоатомных молекул по спектрохимическим данным при таблично-продукционной форме представления нечетких знаний и разработана экспертная система РАСТР;

-предложена теория и методы формализации нечетких знаний прикладного характера на основе объединения возможностей логики предикатов первого порядка и теории нечетких множеств - прикладное исчисление нечетких предикатов;

-показана возможность решения качественных задач в прикладном исчислении нечетких предикатов методом доказательства теорем с оценкой истинности полученных результатов;

-проведена формализация и структурирование логических компонентов знаний прикладного характера в ряде проблемных областей;

-проведена систематизация и формальное описание широко распространенных классов прикладных качественных задач: прогнозирования, интерпретации, идентификации;

-приведены примеры формализации знаний и решения качественных задач на языке ТУРБО-ПРОЛОГ, расширенном для нечеткой логики;

-показана возможность использования нечеткой логики в естественноязыковых приложениях.

Достоверность научных положений, выводов и результатов подтверждается:

-использованием для представления логических компонентов нечетких знаний и решения качественных задач формальной аксиоматико-дедуктивной системы с общепринятыми в математике синтаксическими и семантическими конструкциями;

-использованием для решения ряда качественных задач классических методов дискретной математики;

-успешным применением разработанных методов при создании экспертных и информационных систем;

-внедрением и эксплуатацией созданных экспертных и информационных систем.

Более чем 2 0-летнюю работу в рассматриваемой области автор начинал в неформальном творческом коллективе академика РАЕН, д.ф.-м.н., проф.

Л.А.Грибова под его непосредственным руководством и выражает ему искреннюю признательность. Автор благодарен д.х.н., проф. М.Е.Эляшбергу за долговременное и плодотворное сотрудничество, одним из результатов которого было создание экспертных систем МАИСС и РАСТР. За многолетнее сотрудничество автор признателен В.М.Петрову, особо отмечая его вклад в решение проблем естественноязыкового интерфейса. Академику МАИ, д.т.н., проф. В.З.Букрееву автор благодарен за создание творческой атмосферы на руководимой им кафедре информатики, благодаря чему и стало возможным оформить рассматриваемые работы как диссертацию.

Автор глубоко признателен за внимание к работе, обсуждение полученных результатов, ценные замечания по существу и полезные указания по оформлению работы профессорско-преподавательскому составу и сотрудникам Московской Государственной Академии приборостроения и информатики, Московского Государственного инженерно-физического института, кафедры информатики РосЗИТЛП, Института геохимии и аналитической химии РАН, ВЦ СО РАН, Новосибирского института органической химии СО РАН, кафедры физики ТСХА, п/я А1147, ВНИИ органического синтеза, НИИ спецтехники МВД, НИИ материаловедения, где докладывались отдельные результаты и работа в целом.

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

1.СОСТОЯНИЕ ВОПРОСА И ЗАДАЧИ ИССЛЕДОВАНИЙ

1.1. Общая характеристика вопроса представления знаний и методов решения задач прикладного характера с применением ЭВМ.

Существует мнение, что наступающий век - век искусственного интеллекта и экспертных систем [1]. Для представления знаний и решения задач с использованием систем такого рода потребуются новые теории, методы, алгоритмы.

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

Знания, которыми мы пользуемся повседневно, представлены содержательно, они несовершенны, неточны, противоречивы и т.д., в них присутствуют неформализуемые понятия, например такие, как здравый смысл.

Знания могут быть структурированы с той или иной точки зрения. Прежде всего можно выделить специальные знания, которые относительно упорядочены и доведены до определенной логической системы. В настоящее время основное внимание уделяется знаниям именно этого уровня. Такие знания принято называть микрознаниями [2]. С другой стороны, существуют макрознания, которые являются синтезом эмпирических знаний и микрознаний, в них достаточно много противоречий и нелогичности.

Макрознания трудно формально представить, описать, использовать. Тем не менее человек обычно свободно управляется с макрознаниями. Мысли человека с точки зрения логики имеют качественный характер, они нечетки. Их можно назвать макромыслями. Когда человек пытается найти решение сложной задачи, его макромысли интуитивно разбиваются на существенные и малозначащие, последние отбрасываются, а рассматриваются только первые. Кроме того, макромысли необходимы при обработке большого объема микроинформации. Однако отделить существенную и отбросить малозначащую информацию трудно, все может измениться в зависимости от поведения и цели человека, т.е. именно цели определяют образ макромыслей [2].

Идея человеко-машинных и экспертных систем состоит в том, чтобы поручить компьютеру анализ, упорядочение знаний, хранение в памяти, поиск и другую формализуемую и логическую работу, а генерацию идей, синтез, творчество и другую "правостороннюю" работу полностью доверить человеку.

Исследования в области искусственного интеллекта привели в 70-е годы к идее инженерии знаний а затем и к созданию экспертных систем. Первыми экспертными системами, успешно примененными на практике, были специализированные системы. К ним можно отнести систему DENDRAL [3] (Фейгенбаум, Ледерберг) для установления структур молекул по их масс-спектрам, систему медицинской диагностики MYCIN [4] (Шотлифф). Одновременно была разработана система РАСТР для распознавания структур многоатомных молекул по ИК, ЯМР и некоторым другим спектрам [5,6] (Эляшберг, Серов, Грибов). Относительная успешность практического применения таких экспертных систем привела к резкому росту числа их разработок во всех областях применения ЭВМ.

В специализированных экспертных системах основное внимание уделялось форме представления и конкретному содержанию знаний предметной области. Одновременно и в основном с исследовательскими целями разрабатывались системы общего назначения с акцентом на процедуры поиска решений, которые получили название решателей задач. Это общий решатель задач GPS [7], созданный Ньюэллом, Шоу и Саймоном, вопросно-ответные дедуктивные системы QA3, QA4 [8] Грина, планирующая система STRIPS [9] (Файкс, Нильсон), система программирования ПРИЗ [10] (Тыугу), семиотический решатель СФИНКС [11] (Ефимов) и т.д.

Некоторые из упомянутых систем прекратили свое существование, другие, такие как DENDRAL и РАСТР, развиваются до настоящего времени. В процессе их разработки и совершенствования были выдвинуты и опробованы многие идеи и концепции представления знаний и методов решения задач.

Основой для представления знаний очень часто является система продукций на основе правила ЕСЛИ -> ТО (посылка —> следствие, явление -> реакция). Задачи решаются методом автоматического доказательства теорем с использованием принципа резолюций Робинсона [12] или обратного метода С.Ю.Маслова [13].

Широкое распространение получила фреймовая модель М. Минского [14], в которой под фреймом понимается структура данных для представления некоторого концептуального объекта. Информация, относящаяся к фрейму, содержится в его слотах, все фреймы взаимосвязаны

и образуют единую систему, включающую в себя декларативные и процедурные знания. На базе этой концепции созданы языки представления знаний Р11Ь, КЛЬ, БМв, КШИЕ и другие.

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