Материал: Алгебра_кортежей

Шаг 6. Относительно универсума [{a, b, c} {a, b, c, d} {a, d}]

Шаг 7. У D-системы R2 третий атрибут бесконфликтный, поэтому в соответствии с теоремой 3.5. достаточно проверить непустоту D-системы

D-система непуста и, следовательно, C R не выполняется.

Пусть D-система R задана в универсуме {0, 1}n, где n – число атрибутов или переменных в соответствующей формуле исчисления высказываний. В такой модели алгоритм проверки включения C-кортежа в C-систему имеет некоторые особенности по сравнению с общим алгоритмом. Пусть заданы в универсуме {0, 1}n C-кортеж C и C-система R.

Алгоритм 3.2 (проверка включения C-кортежа в C-систему в универсуме {0, 1}n):

1)проверить, существует ли в R такой C-кортеж Ci, для которого C Ci. Если существует, то выход с ответом "да";

2)вычислить R0 = C R;

3)если R0 = , то выход с ответом "нет";

4)если R0 содержит один C-кортеж, то выход с ответом "нет";

5)в C-системе R0 выделить проекцию R0 , соответствующую фиктивным

атрибутам C-кортежа C;

6) проверить непустоту полученной D-системы R0 . Если D-система пуста, то ответ "да", в противном случае – "нет".

Рассмотрим пример. Здесь для экономии места компоненты {0} и {1} записываются в АК-объектах как 0 и 1 соответственно. Пусть заданы

C = [0 1 0] и

115

Шаг 1. Условие не выполнено.

0 1 1 0

Шаг 2. R0 = 0 0 1 1 0 .

0 1 1 0

Шаги 3 и 4. Условия не выполнены.

Обоснование корректности алгоритма. Шаги 1, 2 и 3 очевидны. Шаг 4: если условие не выполнено на шаге 1, то для C-системы R0, содержащей единственный C-кортеж, возможен только один вариант: R0 C, в силу чего неверно C R0. Шаги 5 и 6: после шага 2 во всех атрибутах R0, совпадающих с нефиктивными атрибутами C, компоненты равны соответствующим компонентам C. В оставшихся атрибутах, чтобы выполнялось C R0, должен

содержаться частный универсум. Следовательно, R0 пусто.

Стоит отметить, что в случае, когда C – элементарный кортеж или может быть разложен на небольшое число элементарных кортежей (т.е. число фиктивных атрибутов сравнительно невелико), то для проверки включения достаточно ограничиться шагом 1 алгоритмов 3.1 и 3.2.

На основе этих алгоритмов легко построить алгоритм проверки включения одной C-системы в другую (проверяется включение каждого C-кортежа первой C-системы во вторую).

3.4. Алгоритм решения задачи "Выполнимость КНФ"

Важность задачи "Выполнимость КНФ" в системах искусственного интеллекта обусловлена следующими причинами.

Во-первых, это основная NP-полная задача в теории сложности вычислений, поскольку доказано, что любая задача класса NP при

116

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

Во-вторых, на основе теоремы 1.6 как для исчисления высказываний, так и для исчисления предикатов был сформулирован принцип резолюции, который широко применяется в машинных реализациях систем искусственного интеллекта. Согласно этому принципу формула F1 ... Fn G преобразуется в КНФ, и логический вывод сводится к решению задачи выполнимости КНФ.

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

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

Предлагается использовать следующий метод. На первом этапе с помощью соотношений, изложенных в подразделе 3.2, выявляется существование монотонных (при их наличии задача решается за полиномиальное время) или бесконфликтных (что позволяет уменьшить размерность D-системы) блоков. Когда эти способы исчерпаны, можно выполнить задачу преобразования D-системы в C-систему, но изменить порядок выполнения операций. Обычно вначале все D-кортежи исходной D-системы преобразуются в ортогональные C-системы, после чего последовательно находится пересечение этих C-систем. Для решения задачи выполнимости вместо поиска пересечения промежуточных C-систем в целом можно искать последовательное пересечение C-кортежей из разных C-систем до тех пор, пока не придем к последней C-системе или не прервем операцию после получения пустого C-кортежа. В последнем случае выбирается другая последовательность операций, и так до тех пор, пока не

117

доказан положительный результат или не перебраны все возможные сочетания пересечений C-кортежей, чтобы убедиться в пустоте исходной D-системы. Такой метод значительно сокращает трудоемкость алгоритма решения задачи, особенно когда осуществляется ортогонализация и используются определенные критерии, позволяющие за счет изменения порядка выполнения операций получать большое количество отрицательных результатов (пустых C-кортежей) на первых этапах вычислений [Кулик, 1993].

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

Алгоритм 3.3. (проверка выполнимости D-системы):

Пусть R – D-система, в которой отсутствуют монотонные и бесконфликтные блоки и содержится множество D-кортежей {D1, D2, ..., Dm}. Очевидно, что R = D1 D2 ... Dm.

1. Выберем какой-либо D-кортеж (например, D1) и выполним следующее преобразование:

D1 D2 ... Dm = D1 D2 ... Dm = D1 \ (D2 ... Dm ).

Подвыражение R1 = D2 ... Dm есть C-система, равная дополнению D-системы D2 ... Dm.

2. Выбранный D-кортеж D1 преобразуем по теореме 3.1 в ортогональную C-систему R0. Тогда исходную D-систему можно записать в виде R0 \ R1.

3. Для проверки выполнимости R достаточно проверить включение R0 R1. При положительном ответе R = , а при отрицательном – R .

Предположим, что на шаге 3 проверка включения некоторого C-кортежа Ci из R0 в C-систему R1 производится по алгоритму 3.1 (или 3.2) из подраздела 3.3. Если при этом достигнут последний шаг, то необходимо проверить выполнимость промежуточной D-системы Rk, имеющей меньшую размерность, чем исходная D-система R. Для проверки можно снова применить алгоритм 3.3, используя показанное выше преобразование Rk = Rk0 \ Rk1.

Ясно, что при совестном применении алгоритмов 3.3 и 3.1 (или 3.2) осуществляется обход дерева решения. Процедура завершается, если

118