Введем ряд обозначений и опишем оператор приведения ТРВ к ТОВ - оператор бинаризации . Обозначим через множество значений (домен) условия и перенумеруем эти значения числами 1, 2,… Преобразование состоит в замене каждого многозначного условия на двоичных условий с соответствующей бинарной перекодировкой затрагиваемых элементов матрицы (где обозначает ближайшее сверху к целое число). Количество продукционных правил в ТР в ходе такого преобразования не меняется. Пусть замена многозначного условия набором двоичных условий описывается функцией : , тогда множество условий преобразованной таблицы примет вид . Компоненты и в процессе преобразования остаются неизменными (т.е. и ), а преобразование матрицы заключается в двоичном декодировании значений многозначных условий в значения соответствующих бинарных условий: . Преобразование дополнительного компонента зависит от его содержания; здесь нет смысла рассматривать все возможные ситуации. Естественно, возможно и обратное преобразование ТОВ в ТРВ с точностью до выбора группируемых вместе бинарных условий.

Проверка наиболее существенных свойств ТР (полноты, непротиворечивости, неизбыточности) может быть произведена непосредственным перебором всех возможных векторов данных. Но переборные алгоритмы оказываются применимы лишь к ТР с достаточно малым числом условий, как правило, не более 15 даже для ТОВ [Еремеев, 1987], [Еремеев, 2001]. В случае ТРВ ситуация становится еще более сложной. При прямой генерации векторов данных по ТРВ требуется анализ векторов. Если же была предварительно приведена к эквивалентной ТОВ , то потребуется перебор векторов, причём .

Таким образом, при использовании ТРВ в ИСППР РВ переборные алгоритмы практически неприменимы из-за вычислительной сложности. При проверке ТР на корректность различают полноту и непротиворечивость в синтаксическом и семантическом смысле [Еремеев, 2001]. Проверка семантических свойств ТР сложнее и связана с выделением из всего множества векторов данных (состояний) подмножества допустимых векторов .

Для проверки семантической корректности ТОВ в [Еремеев, 2001] ? предлагается алгоритм, базирующийся на проверке синтаксической корректности некоторого расширения ТОВ на основе заданного экспертом набора отношений между условиями ТОВ, т.е. на основе некоторых дополнительных знаний (метазнаний). Такой набор отношений можно рассматривать как элемент компонента в исходной таблице. Аналогично и для ТРВ с наложенными отношениями между условиями существуют два подхода к автоматической проверке семантической корректности, графически представленные на рис.1.

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

, где ;

, где , - термы;

, где , - термы;

, где и - произвольные ППФ над термами в базисе И-ИЛИ.

12

Размещено на http://www.allbest.ru/

Рис. 1. Подходы к проверке семантической корректности ТРВ

Для отношений первого и второго типов значение одного условия однозначно определяет значение другого условия. В отношениях третьего типа определенная комбинация значений условий из левой части отношения влечёт несколько альтернатив значений других условий. Четвертый тип является самым общим, он не накладывает ограничений на структуру используемых формул. Для всех приведенных типов отношений предполагается, что одно и то же условие не может входить в обе части отношения. Данный список типов отношений обладает следующими важными свойствами: он является иерархией, т.е. типы отношений вложены друг в друга в порядке нумерации; кроме того, каждый тип отношения замкнут относительно правила контрапозиции . Контрпримером к отношению между условиями вида является формула . Пусть дано множество отношений , построим множество отношений применением правила контрапозиции ко всем отношениям из . Также на основе набора построим множество , состоящее из контрпримеров ко всем отношениям из .

По ТРВ и множеству отношений построим расширенную ТРВ , руководствуясь следующими правилами:

на основании наборов и доопределим таблицу для существующих правил;

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

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

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

Утверждение. ТРВ семантически корректна тогда и только тогда, когда построенная для нее на основе логических отношений между условиями расширенная ТРВ синтаксически корректна.

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

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

2. Трансляция отношений при бинаризации таблиц решений с расширенным входом

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

1. , где и - термы;

, где , - термы;

, где и - произвольные ППФ над термами в базисе И-ИЛИ.

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

1. Отношение вида должно быть преобразовано в семейство отношений вида ;

Отношение вида должно быть преобразовано в семейство отношений вида , где ;

Отношение вида должно быть преобразовано в семейство отношений вида ;

Отношение вида должно быть преобразовано в отношение вида , где , а .

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

Существенно, что прямое отображение многозначного условия в несколько двоичных в процессе бинаризации возможно лишь в том случае, если мощность множества значений такого условия является степенью двойки (т.е.4, 8, …). В противном случае полученная ТОВ будет допускать определенное количество фиктивных состояний, не содержавшихся в исходной ТРВ, и не будет эквивалентна исходной ТРВ по описанию процесса принятия решений. Некорректной будет и проверка полученной ТОВ на полноту и/или непротиворечивость. Выходом из этой ситуации является создание при преобразовании ТРВ дополнительных ограничений над условиями создаваемой ТОВ, явным образом исключающих "запрещенные" состояния. Это позволяет получить ТОВ, эквивалентную исходной ТРВ по описанию логики принятия решения, однако дополнительное увеличение числа отношений между условиями делает процесс дальнейшей обработки такой ТОВ более трудоёмким.

Заключение