Труды КНЦ вып.7 (ИНФОРМАЦИОННЫЕ ТЕХНОЛОГИИ вып.2 4/2011(7))

доказано, что все структуры и операции АК имеют эквиваленты в многосортном исчислении предикатов. В результате, АК позволяет унифицировать представление различных структур знаний (предикатов, бинарных отношений, графов, семантических сетей и т.д.) и данных, например, реляционных таблиц. А также реализацию многих сложных процедур (соединение, композиция, транзитивное замыкание, квантификация и т.д.), связанных с обработкой многоместных отношений и предикатов [4-7]. 2. Возможности алгебры кортежей в логическом анализе данных и знаний В плане расширения возможностей логического анализа данных и знаний АК дает следующие преимущества: 1. В АК предложены новые методы решения таких стандартных задач логического вывода, как порождение возможных следствий из заданной системы посылок, проверка правильности следствия. Как показали исследования, применение методов алгебры кортежей к стандартным задачам логического анализа способствует ускорению процедур их решения, поскольку при выводе учитывается внутренняя структура обрабатываемых знаний, а не только выполнимость отдельных подстановок [8, 9]. 2. Свойства АК-объектов позволяют не только осуществлять логический вывод, но и решать задачи, выходящие за пределы дедукции: порождение и анализ гипотез, поиск абдуктивных заключений, которые входят в состав модифицируемых рассуждений. Отличительная особенность предлагаемых методов решения состоит в том, что они реализованы в рамках классической логики, то есть не используют неклассические логики (немонотонные логики, логики умолчаний и т.д.), в которых допускаются нарушения некоторых законов булевой алгебры и алгебры множеств [10, 11]. 3. Для организации процедур логико-семантического анализа систем посылок без привлечения неклассических логик в АК введено понятие "коллизия", c помощью которого удается устранить несоответствие между формальной логикой, где система посылок проверяется лишь на противоречивость (контрадикторность), и естественными рассуждениями, где требуется более тонкий анализ несовместности посылок (например, выявление контрарных следствий) [12-14]. 4. Алгебра кортежей позволяет распараллеливать алгоритмы логического вывода, то есть производить обработку знаний аналогично обработке табличных данных в реляционных СУБД [4, 7]. 5. В АК разработаны алгоритмы сокращения трудоемкости вычислительных процедур, направленные на снижение остроты проблемы "экспоненциальной катастрофы". Эти алгоритмы используют матричные свойства АК-объектов (монотонные и бесконфликтные блоки и т.п.), позволяющие не только эффективного распараллеливать вычисления, но и, зачастую, снизить сложность решаемых задач до полиномиальной. В АК выявлены новые структурные и статистические классы конъюнктивных нормальных форм с полиномиально распознаваемым свойством выполнимости. Доказано, что если КНФ выражена как .D-система, где содержатся только три 131