Данные и знания

Глава 1

Представление знаний

Данные и знания

Д. А. Поспелов

Основные определения

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

Одинаковое число разрядов в машинных словах для команд и данных по­зволяет рассматривать их в ЭВМ в качестве одинаковых информационных еди­ниц и* выполнять операции над командами, как над данными. Содержимое памяти образует информационную базу.

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

Параллельно с развитием структуры ЭВМ происходило развитие информа­ционных структур для представления данных. Появились способы описания данных в виде векторов и матриц, возникли списочные структуры, иерархиче­ские структуры. В настоящее время в языках программирования высокого уровня используются абстрактные типы данных, структура которых задается программистом. Появление баз данных (БД) знаменовало собой еще один шаг на пути организации работы с декларативной информацией. В базах данных могут одновременно храниться большие объемы информации, а специальные средства, образующие систему управления базами данных (СУБД), позволяют эффективно манипулировать с данными, при необходимости извлекать их из базы данных и записывать в нужном порядке в базу.

Таблица 1.1

По мере развития исследований в области ИС возникла концепция зна­ний, которые объединили в себе многие черты процедурной и декларативной информации.

Особенности знаний

Перечислим ряд особенностей, присущих этой форме представления ин­формации в ЭВМ.

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

Если, например, в память ЭВМ нужно было записать сведения о сотруд­никах учреждения, представленные табл. 1.1, то без внутренней интерпретации в память ЭВМ была бы занесена совокупность из четырех машинных слов, со­ответствующих строкам этой таблицы. При этом информация о том, какими группами двоичных разрядов в этих машинных словах закодированы сведения о специалистах, у системы отсутствуют. Они известны лишь программисту, ко­торый использует данные табл. 1.1 для решения возникающих у него задач. Система не в состоянии ответить на вопросы типа «Что тебе известно о Пет­рове?» или «Есть ли среди специалистов сантехник?».

^г При переходе к знаниям в память ЭВМ вводится информация о некоторой протоструктуре информационных единиц. В рассматриваемом примере она представляет собой специальное машинное слово, в котором указано, в каких разрядах хранятся сведения о фамилиях, годах рождения, специальностях и стаже. При этом должны быть заданы специальные словари, в которых пере­числены имеющиеся в памяти системы фамилии, года рождения, названия спе­циальностей и продолжительности стажа. Все эти атрибуты могут играть роль имен для тех машинных слов, которые соответствуют строкам таблицы. По ним можно осуществлять поиск нужной информации. Каждая строка таблицы бу­дет экземпляром протоструктуры. В настоящее время СУБД обеспечивают реа­лизацию внутренней интерпретируемости всех информационных единиц, храни­мых в базе данных.

2. Структурированность. Информационные единицы должны обладать гиб­
кой структурой. Для них должен выполняться «принцип матрешки»,
т. е. рекурсивная вложимость одних информационных единиц в другие. Каж­
дая информационная единица может быть включена в состав любой другой, и
из каждой информационной единицы можно выделить некоторые составляющие
ее информационные единицы. Другими словами, должна существовать возмож­
ность произвольного установления между отдельными информационными еди­
ницами отношений типа «часть — целое», «род —вид» или «элемент — класс».

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

па. Прежде всего эти связи могут характеризовать отношения между информа­ционными единицами. Семантика отношений может носить декларативный или процедурный характер. Например, две или более информационные единицы могут быть связаны отношением <Содновременно >, две информационные еди­ницы— отношением «спричина—следствием или отношением «сбыть ря­дом^. Приведенные отношения характеризуют декларативные знания. Если между двумя информационными единицами установлено отношение ^аргу­мент— функция;», то оно характеризует процедурное знание, связанное с вы­числением определенных функций. Далее будем различать отношения структу­ризации, функциональные отношения, каузальные отношения и семантические отношения. С помощью первых задаются иерархии информационных единиц, вторые несут процедурную информацию, позволяющую находить (вычислять) одни информационные единицы через другие, третьи задают причинно-следст­венные связи, четвертые соответствуют всем остальным отношениям.

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

Перечисленные три особенности знаний позволяют ввести общую модель представления знаний, которую можно назвать семантической сетью, представ­ляющей собой иерархическую сеть, в вершинах которой находятся информа­ционные единицы. Эти единицы снабжены индивидуальными именами. Дуги семантической сети соответствуют различным связям между информационными единицами. При этом иерархические связи определяются отношениями струк­туризации, а неиерархические связи — отношениями иных типов [Hendrix, 1975; Schubert, 1975].

4. Семантическая метрика. На множестве информационных единиц в неко­торых случаях полезно задавать отношение, характеризующее ситуационную близость информационных единиц, т. е. силу ассоциативной связи между ин­формационными единицами. Его можно было бы назвать отношением реле­вантности для информационных единиц. Такое отношение дает возможность выделять в информационной базе некоторые типовые ситуации (например, «покупка», «регулирование движения на перекрестке»). Отношение релевантно­сти при работе с информационными единицами позволяет находить знания, близкие к уже найденным.

5. Активность. С момента появления ЭВМ и разделения используемых в ней информационных единиц на данные и команды создалась ситуация, при кото­рой данные пассивны, а команды активны. Все процессы, протекающие в ЭВМ, инициируются командами, а данные используются этими командами лишь в случае необходимости. Для ИС эта ситуация неприемлема. Как и у челове­ка, в ИС актуализации тех или иных действий способствуют знания, имеющиеся в системе. Таким образом, выполнение программ в ИС должно инициировать­ся текущим состоянием информационной базы. Появление в базе фактов или описаний событий, установление связей может стать источником активности системы.

Перечисленные пять особенностей информационных единиц определяют ту грань, за которой данные превращаются в знания, а базы данных перераста­ют в базы знаний (БЗ). Совокупность средств, обеспечивающих работу с зна­ниями, образует систему управления базой знаний (СУБЗ). В настоящее вре­мя не существует баз знаний, в которых в полной мере были бы реализованы внутренняя интерпретируемость, структуризация, связность, введена семанти­ческая мера и обеспечена активность знаний.

Модели представления данных *

В 70-х годах различали три основные модели представления данных: ре­ляционные, сетевые и иерархические. В настоящее время появилось второе по-

В написании данного раздела участвовала С. М. Ефимова.

коление таких моделей, в рамках которых происходит постепенное слияние данных и знаний [Цикритис и др., 1985], В развитых моделях представления дан­ных можно выделить два компонента: интенсиональные представления и экстен­сиональные представления. Оба компонента хранятся в базе данных. При этом в ее экстенсиональную часть входят конкретные факты, касающиеся предмет­ной области (например, строки табл. 1.1), а в интенсиональную часть — схемы связей между атрибутами (например, между именами столбцов табл. 1.1.). Таким образом, экстенсиональные представления описывают конкретные объек­ты из предметной области, конкретные события, происходящие в ней, или кон­кретные явления и процессы, а интенсиональные представления фиксируют те закономерности и связи, которым все эти конкретные объекты, события, явле­ния или процессы обязаны в данной проблемной области удовлетворять. Эк­стенсиональные представления относятся к данным. Относительно интенсио­нальных представлений единого мнения нет. Апологеты баз данных говорят в этом случае о схемах базы данных, а представители искусственного интел­лекта — о знаниях о проблемной области.

Элементами схемы базы данных являются схемы вида Q(Ai, A2,...,А„), где Q — некоторое отношение, а множество элементов, входящих в Q, — мно­жество атрибутов. В зависимости от того, какие отношения Q допускаются в схемах баз данных, возникают различные представления данных.

Введем понятие домена Di для некоторого атрибута A_L. Элементами А будем считать все конкретные факты в экстенсиональном представлении, соот­ветствующие этому атрибуту. Например, в простейшем случае табл. 1.1 доме­ны образуются из элементов столбцов таблицы, а соответствующий каждому домену атрибут показан как обозначение столбца. Домены, относящиеся к раз­личным атрибутам, могут иметь пустое пересечение, непустое пересечение или включаться друг в друга. В предельном случае домены двух различных атри­бутов могут полностью совпадать. При этом атрибуты оказываются синонима­ми. Например, если все токари на данном предприятии (и только они) имеют по трое детей, то атрибуты «Токари» и «Отцы, имеющие троих детей» в данной БД окажутся синонимичными.

Экстенсиональное отношение — это определенным образом выделенное под­множество декартова произведения доменов, относящихся к некоторому набо­ру атрибутов. Например, содержимое табл. 1.1 есть подмножество декартова произведения доменов, соответствующих атрибутам: «Фамилия», «Год рожде-ния», «Специальность» и «Стаж». Из всех возможных кортежей, полученных в этом декартовом произведении, в таблицу отобраны лишь те, которые отра­жают реальных людей, работающих на предприятии, В схеме баз данных та­кому экстенсиональному отношению будет соответствовать интенсиональное отношение R{A\, Ац,...,А_т). Имя этого отношения совпадает с именем экстен» сионального отношения (именем той таблицы, которым оно задано, например R может выглядеть как «Список сотрудников данного предприятия»), а в каче­стве его аргументов выступают атрибуты, домены которых использовались для образования соответствующего экстенсионального отношения.

Описанная модель представления данных, т. е. табличное представление данных, протоструктура которых определяется экстенсиональными отношения­ми, а схема базы данных — интенсиональными отношениями [Codd, 1979, 1981], характерна для реляционных баз данных.

В сетевых моделях представления данных используются табличные и гра­фовые представления. Вершинам графа соответствуют информационные едини­цы, называемые записями, которые представляют собой специальным образом организованные таблицы, а дугам графа — типы отношений между записями [Мартин, 1980; Ульман, 1983; Цикритис и др., 1985]. В отличие от реляцион­ных моделей, в которых запрещается повторение одинаковых строк в множе­стве, определяющем экстенсиональное отношение, в сетевых моделях такие по­вторения допустимы. Другим отличием является явное задание отношений между записями с помощью графа, а не опосредованное, как в реляционной модели.

В иерархических моделях представления данных в отличие от реляционных и сетевых моделей схема базы данных представляет собой множество схем отношений, упорядоченных в деревообразную структуру. В отличие от сетевой модели, в которой экстенсиональные отношения могут быть определены на до­менах, элементы которых сами могут быть агрегированными записями (т. е. представлять собой целые фрагменты графа), в иерархических моделях (как и в реляционных) элементами доменов могут быть лишь простые факты [Дейт, 1980; Мартин, 1980; Ульман, 1983].

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

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

Многие авторы, например [Дейт, 1980; Дрибас, 1982; Калиниченко, 1983], определяют базы данных как совокупность ЯОД и ЯМД, что сближает их с понятиями алгебры и универсальной алгебраической системы [Мальцев, 1970]. На сегодняшний день можно считать завершенной теорию реляционных баз данных [Maier, 1983; Цаленко, 1985]. Сейчас уже ясно, что все три типа баз данных равномощны [Jacoby, 1982; Филиппов, 1983, 1985].

Второе поколение баз данных характеризуется рядом особенностей моде­лей представления данных [Цаленко, 1985; Цикритис и др., 1985]. Расширение возможностей таких моделей происходит из-за ослабления требований к виду отношений Q в экстенсиональных представлениях и к виду отношений R в интенсиональных представлениях.

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

Например, в бинарных моделях представления данных используются лишь бинарные отношения между информационными единицами. Близкой к таким моделям является модель, опирающаяся на язык синтагматических цепей, при­менявшийся в ситуационном управлении [Поспелов Д., 1981]. Наиболее из­вестной бинарной моделью является модель Сенко [Senko, 1980].

В модели U-графов [Ефимова, 1985; Ефимова и др., 1986] фиксирована топология семантической сети, используемой в схеме базы данных: отношения вида Q(Ao\ A_ir...,Am) описывают фрагменты семантической сети, называемые звездами. Тело звезды — вершина семантической сети с именем Аа. Вершины с именами А\,..., А_т связаны с вершиной А_о бинарными отношениями с неко­торыми именами Ru..., R_m. Такой способ представления информации имеет не­которые аналоги с моделью /?Х-кодов, предлагавшейся для информационно-по­исковых систем [Скороходько, 1968].

Модели представления знаний

В ИС используются различные способы описания знаний. 1. Логические модели. В основе моделей такого типа лежит формальная система, задаваемая четверкой вида М—<.Т, Р, А, В>. Множество Т есть множество базовых элементов различной природы, например слов из некото­рого ограниченного словаря, деталей детского конструктора, входящих в со­став некоторого набора и т. п. Важно, что для множества Т существует не­который способ определения принадлежности или непринадлежности произ­вольного элемента к этому множеству. Процедура такой проверки может быть любой, но за конечное число шагов она должна давать положительный или отрицательный ответ на вопрос, является ли х элементом множества Т. Обо­значим эту процедуру П(Г).

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

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

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

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

2. Сетевые модели. В основе моделей этого типа лежит конструкция, на­званная ранее семантической сетью. Сетевые модели формально можно задать в виде #=</, С], С₂,..., С_п, Г>. Здесь / есть множество информационных единиц; С\, С₂,..., С_п — множество типов связей между информационными еди­ницами. Отображение Г задает между информационными единицами, входя­щими в /, связи из заданного набора типов связей.

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

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

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

(Имя фрейма:

Имя слота 1 (значение слота 1) Имя слота 2 (значение слота 2);

Имя слота К (значение слота /С)).

Значением слота может быть практически что угодно (числа или матема­тические соотношения, тексты на естественном языке или программы, правила вывода или ссылки на другие слоты данного фрейма или других фреймов). В качестве значения слота может выступать набор слотов более низкого уров­ня, что позволяет во фреймовых представлениях реализовать «принцип ма­трешки».

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

Например, структура табл. 1.1, записанная в виде протофрейма, имеет вид

(Список работников:

Фамилия (значение слота 1); Год рождения (значение слота 2); Специальность (значение слота 3); Стаж (значение слота 4)).

Если в качестве значений слотов использовать данные табл. 1.1, то получится фрейм-экземпляр

(Список работников:

Фамилия (Попов—Сидоров—Иванов—Петров); Год рождения (1965—1946—1925—1937); Специальность (Слесарь—токарь—токарь—сантехник); Стаж (5—20-30—25)).

Связи 'между фреймами задаются значениями специального слота с име­нем <Связь>. Часть специалистов по ИС считает, что нет необходимости специально выделять фреймовые модели в представлении знаний, так как в них объединены все основные особенности моделей остальных типов. В справочни­ке фреймовые модели будут рассматриваться в общем контексте с сетевыми.

1.2. Логические модели

Г. С. Плесневач

Основные определения

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

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

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

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

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

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

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

дет:Операция ->-Деталь, ст:Операция ->Станок (1)

нач:Операция -»-Время, кон:Операция -*Время (2)

тип_дет:Деталь -+-ТипДетали, тип_ст:Станок -*-ТипСтанка (3)

ток: ->-ТипСтанка, фрез -мГипСтанка (4)
14

вал шест: ->-ТипДетали, ставал: ->ТипДетали

0: -^-Время, 1: -^Время....... t: ->Время.

+:ВремяХВремя -НВремя

<;;ВремяХВремя -*-Т

фрез_торц:Операция -+-Т, ток_обр:Операция -*Т

Выражения (1) — (9), составляющие так называемую сигнатуру, имеют сле­дующий смысл:

(1) задает две функции дет (деталь) и ст (станок), которые, будучи при­
менены к объекту е сорта Операция, дают деталь дет(е) и станок ст(е), участ­
вующие в операции е;

(2) задает функции начала и конца операции е, причем нач(^) и кон(е)
есть объекты сорта Время;

(3) задает функции, значениями которых служат типы деталей и типы
станков;

(4) задает две константы: ток (токарный станок) и фрез (фрезерный ста­
нок) сорта ТипСтанка (эти константы рассматриваются как нуль-местные
функции);

(5) задает константы вал-шест (вал-шестерня) и ст_вал (ступенчатый вал)
сорта ТипДетали;

(6) задает счетное множество констант, обозначающих натуральные числа
(эти константы принадлежат сорту Время);

(7) задает двуместную функцию, аргументами которой служат объекты
сорта Время (предполагаемая интерпретация этой функции — сложение нату­
ральных чисел, измеряющих моменты времени);

(8) задает двуместный предикат на объектах сорта Время (предполагае­
мая интерпретация предиката — двуместное отношение «меньше или равно»
между натуральными числами);

(9) задает два одноместных предиката фрез_торц (фрезерование торцов)
и ток_обр (токарная обработка); эти предикаты представляют свойства опе­
раций; фрез_торц(е) = 1 тогда и только тогда, когда е есть операция фрезеро­
вания торцов (и аналогично для ток_обр).

В общем случае сигнатурой называется множество 2 выражений* вида f:AiXA₂X -XAn -*-В, где А_}, В — сорта, а / — функция, или предикат. Имя / есть имя предиката в 2, если В = Т, т. е. если значением / служит «истина» или «ложь» (обычно обозначаемые 1 и 0).

Сорта сигнатуры интерпретируются как множества. Сорт Т является осо­
бым в том смысле, что он всегда интерпретируется как множество истинност-
ных значений {0, 1}. Остальные сорта сигнатуры могут интерпретироваться
по-разному. Таким образом, предикат рассматривается как функция, заданная
на объектах (вообще говоря, разных сортов) и принимающая значение «истина»
или «ложь». Предикат можно рассматривать также как многоместное отноше*
ние между объектами (разных) сортов: объекты е_и е%,..., е_п находятся в от­
ношении р, что записывается как p(ei, е_2..... е_п) тогда и только тогда, когда

р(е_и е₂,...,е„)=*1. Заметим, что для двуместных предикатов часто использует­ся инфиксная запись: вместо р(е_и е₂) пишут eipe₂ (например, пишут х<# для предиката «меньше или равно»).

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

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

Зн1 — каждая деталь должна сначала пройти фрезерование торцов, а за­тем токарную обработку;

Зн2 — станки не должны все вместе простаивать ни в какой момент вре­мени до того момента, когда нее станки прекратят работу;

ЗнЗ — токарная обработка ступенчатого вала длится 7 мин, а вала-шестер­ни— 12 мин; фрезерование торцов ступенчатого вала длится 5 мин, а вала-ше­стерни — б мин;

Зн4 — на производственном участке имеется три станка: два токарных и один фрезерный;

Зн5 — всего было совершено восемь операций;

Знб — было обработано четыре детали: два ступенчатых вала и два вала-шестерни;

Зн7 — станок стЗ является фрезерным;

Зн8 — операция оперЗ совершалась над деталью дет2 на станке стЗ в те­чение интервала времени от момента 5 до момента 10.

Для того чтобы формально представить Зн1, перефразируем его следую­щим образом: для каждой детали х существуют операции у и г, такие, что конец операции у наступает не позже начала операции z, операция у есть фре­зерование торцов, операция г — токарная обработка и в обеих операциях уча­ствует одна и та же деталь х. Соответствующая формула будет такой:

еталь) (д у, г£ Операция), [(кон (у) < нач (г)) Д (дет (у) =*)) Л

(дет (г) = х) Л Фрез_торц (у) Д
ток_обр(г)] (10)

В (10) использованы следующие формальные обозначения: (у) —квантор общности (_вдля всех х из А*); (дх^Л) —квантор су­ществования („существует х из А'у, /\—коньюнщия („аи Р"). Вместо блока кванторов (yXjG А) (ух₂^А)... (ух_р^А) сокращенно можно писать (\x_t, х_а,..., XpEzA); аналогично для блока кванторов д.

Перефразируем знание Зн2: существует момент времени х, такой, что: а) существует операция у, заканчивающаяся в момент х, б) каждая операция г заканчивается не позже момента х, в) не существует момента и, такого, что и<х, и какова бы ни была операция v, интервал ее исполнения не содержит и (т. е. неверно, что нач(£>Хы и и^кон(о)). Соответствующая формула

(3*е Время). (ЗУ GE Операция) (кон(#)=х) Д

(уг €~ Операция) (кон (г)<х) Д 1 (3«Е Время). (и<х)Д

(yv €? Операция) ~1 [(нач (с)<
и)М(«< кон (и)) (11)

(Здесь точка выполняет роль скобок, отделяя соответствующую подформулу, стоящую в ряду слева от точки.)

В (11) использован символ ~|> обозначающий логическое отрицание (~|а читается: «не верно, что а»).

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

(V*£ Операция). [ток_обр (х) Д (тип„_дет (дет (х)) = ст_вал) ->

(нач (х) +7 = кон (х))1 Д

[ток_обр (х) Д (тип_дет (дет (х)) =■ вал-шест) -» (нач (х) + 12 = кон (х))1Д

[фрез_торц (х) Д (тип_дет (дет (х)) — ст_вал) -♦ (нач(х) + 5 = кон(х))] Д

[фрез_торц (х) V (тип_дет (дет (х)) = вал-шест) ->

(нач (а)+6 = кон (х))] (12)

Для того чтобы формально представить знание Зн4, введем три констан­ты ст1, ст2 и стЗ сорта Станок. Получим

(VX6 Станок). [(х= ст1)\/(* = ст-2) V(* = стЗ)1Д (тцп_ст (ст1) = ток) V

(тип_ст (ст2) == ток) Д(тип_ст (стЗ) = фрез) (13)

В (12) и (13) появились два новых логических символа — V и ->-, назы­ваемых дизъюнкция и импликация (aVP читается: «а или |3»; а-^Р читается: «если а, то р»).

Знание Знб формализуется аналогично, если ввести константы, обозначаю­щие операции:

(ух €= Операция). (х = опер!) V (^х — опер2) \J (х= оперЗ) V
(х = опер4) V (х = опер5) \/ (х = оперб) V
(v = опер7)\/(х= опер8) (14)

Знание Знб представляется формулой

(V*^Деталь) \(х = дет1) \/(х = дет2) V (х =- детЗ) V(* = Дет4)] Д

(тип_дет (дет1) = ст_вал) Д (тип_дет (дет2) = ст_вал) Д (тип_дет (детЗ) = вал-шест)Д(тип_дет (дет4) = вал-шест) (15)

Знание Зн7 передается формулой
(тип_ст(стЗ) =фрез) (16)

Наконец, знание Зк8 передается формулой
(дет(оперЗ)=дет2)Л(ст(оперЗ)=стЗ)Л<нач(оперЗ)=5)Л (17)

Рассмотрим общий случай, когда задана произвольная сигнатура 2. Через °&i обозначим множество всех формул языка многосортного исчисления пре­дикатов (первого порядка), построенных на основе сигнатуры 2. Произволь­ная формула ££ составляется из атомарных формул (атомов) с использо­ванием логических связок ~~|, Д, V. -*■ и кванторов по следующим правилам:

П1. Каждый атом есть формула. Всякая входящая в атом переменная яв­ляется свободной в этом атоме.

П2. Если а и Р — уже построенные формулы, то выражения ~| а, (рДР), (aVP). (а-»-Р) —также формулы. Всякая переменная, входящая свободно (связанно) в а или Р, входит свободно и в новые формулы.

ПЗ. Если a — уже построенная формула, в которую свободно входит переменная х, значения которой принадлежат к сорту А, то выражения (у*^е еЛ)а и (дхеЛ)а также являются формулами. Переменная х считается свя­занной в новых формулах.

Атомы SS^X составляются из термов, предикатных символов и символа равенст­ва по следующим правилам:

П4. Если сигнатура 2 содержит выражение р: А1ХА2Х. — У\А_п~+Т н Ti, т₂,..., т_п — термы сортов А\, Аг,...,А_п соответственно, то p(ti, T2,.... т_п) — атом;

П5. Если т и а — термы одинакового сорта, то выражение т=о* есть атом.

Термы составляются по следующим правилам:

Пб. Переменная, принимающая значения из сорта А, есть терм сорта А.

П7. Если сигнатура 2 содержит выражение /: А\Х^2 Х- ХА_п-+В, причем ВфТ, и Т], Тг,...,т„ — уже построенные термы сортов A_t, А?,..., А_п соответст­венно, то выражение /(ti, Tj,.... т_п) есть терм сорта В.

Рассмотренный пример механообработки иллюстрирует общую ситуацию построения логической модели с использо^*игагяэы*сэ многосортного исчис­ления предикатов. Разработчик на ochqjs# тгредв&рительногс анализа предмет­ной области дает имена для констант,' ерртов, функций и предикатов. Имена эти выбирают так, чтобы их мнемоники ^оответстврвала наэвалиям неформаль-

Ь ^К::'ч^:;л'-^: ■'-■•■;.; ^: "■ 17

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

Другие связи между понятиями предметной области представляются фор­мулами из 2. Пусть Я обозначает множество формул, -построенных для пред­метной области. Эти формулы должны быть истинны в той формальной струк­туре, которая представляет предметную область (если это представление ей адекватно). Структура, интерпретирующая заданную сигнатуру 2, строится следующим образом. Указывается непустое множество U, называемое универсу­мам. Для каждого имени сорта А из сигнатуры 2 указывается некоторое под­множество универсума, которое также обозначается A (A^U). Для каждого выражения /: А1ХА2Х ••• ХА_п-+В из сигнатуры указывается функция, отобра­жающая множество Л|ХЛгХ-ХЛп в множество В; эта функция также обо­значается /.

Для примера формализации фрагмента предметной области «механообра­ботка» структура может быть построена следующим образом:

£/={дет^, ctj, onepj\j^N, /^1}U{tok, фрез, ст-вал, вал-шест}иЛГ (где N=

=0, 1,2,...);

Деталь =i дет 1, дет2, детЗ, дет4}; Станок = {ст1, ст2, стЗ};

Операция = {onepl, опер2....... опер8};

ТипСтанка = {ток, фрез); ТипДетали={ст_вал, вал-шест}; Время=jV

Функции дет, ст, нач, кон, тип_дет, тил_ст, фрез-торц и ток_обр указаны
в табл. 1.2—1.4. Предикат < имеет смысл отношения «меньше или равно» на
множестве./V натуральных чисел; функция -|---------- смысл операции сложения на­
туральных чисел. В указанной структуре истинны все формулы (10)—(17).
Как говорят в математической логике, структура эта является моделью мно­
жества формул Я={(10), (11),..., (17)}. Но здесь термин «модель» означает
не то, что в словосочетании «логическая модель».

Таблица 1.2

Таблица 1.3

Пусть 2—произвольная сигнатура и М — интерпретирующая ее структура. Каждая замкнутая формула а. £Е S6 (т. е. формула, не включающая свобод­ные переменные) в структуре М истинна или ложна. Если а истинна в М, то пишут М \—а. Формальное определение истинности или ложности замкнутой формулы а в структуре М выполняется по индуктивным правилам П8 и П9. Для применимости этих правил нужно расширить исходную сигнатуру 2, при­соединив к ней выражения а: ~*-А для каждого элемента а сорта А и каж­дого сорта А из 2. Другими словами, расширенная сигнатура 2' включает все литеральные константы, обозначающие элементы тех множеств, которые ин­терпретируют в М сорта. Благодаря такому расширению множество всех фор­мул SS ' оказывается замкнутым относительно подстановок любых литераль­ных констант вместо свободных переменных.

Базу индуктивных правил П8 и П9 составляют константные (т. е. не со­держащие переменных) атомарные формулы. Истинность или ложность каж­дого такого атома устанавливается в М непосредственно.

П8. Для любых замкнутых формул а, р€Е<2?; М |=~] а тогда и только тогда, когда не имеет места М \==а-, М |=(«А Р) тогда и только тогда, когда М |= а и М |= р; М | — (а V р) тогда и только тогда, когда М |= а или М |=Р; М j=(a -+ Р) тогда и только тогда, когда не имеет места М \ = а или имеет место

П9. Для любой формулы а£2^Е', содержащей одну свободную переменную х, т. е. a = o[jc], полагаем

•М \~ (ЗЯ^Л) ^{a Т0Г}Да и только тогда, когда М | = afa], для хотя бы одной константы а сорта А из 2'.

Структура М, интерпретирующая сигнатуру 2, называется модельной структурой для заданной совокупности замкнутых формул Sc^¹, если все

формулы из Q истинны в М, т. е. М\—а для всех aeQ.

Обращаясь к примеру сигнатуры 2 = {(1), <(2),..., (9)}, которая была по­
строена для фрагмента предметной области «механообработка», видим, что
указанная для этой сигнатуры структура является модельной структурой для
совокупности формул Q = {(10), (11).......... (17)}.

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

Поиск по сайту: