Логика естественных рассуждений - Кулик Б.А.
ISBN 5-7940-0080-5
Скачать (прямая ссылка):
Формула Ф класса Крома невыполнима, если и только если в Ф существует литерал Wu в 6?(Ф) существует цикл такой, что в нем содержится как W, так U^1W.
Поскольку задача поиска такого цикла в б(Ф) решается с помощью алгоритма полиномиальной сложности, то задача выполнимости в Ф также решается с помощью алгоритма полиномиальной сложности.
Приложение.^ Частично упорядоченные множества
123
Чтобы лучше понять сходство между QC-структурами и классом Крома, рассмотрим более подробно преобразование формулы Ф в граф С(Ф). В нем используется известное преобразование двухлитерной дизъюнкции в импликацию с помощью равенства XvY = —X=3 Y, где => — обозначение импликации. В графе С(Ф) каждая импликация представлена ориентированной дугой между соответствующими литералами. Вторая дуга в С7(Ф) для подформулы Xv У получается уже из подформулы —1X ^ Yc использованием закона контрапозиции — этот закон является теоремой исчисления высказываний. Представление одноли-терной дизъюнкции X дугой ("1X — X) в С(Ф) обусловлено тем, что соответствующая формула (—'X => X) эквивалентна X.
В исчислении высказываний имеется теорема, которая соответствует свойству транзитивности у-множеств. Поэтому цикл в (7(Ф), содержащий "Zh-1W7, означает, что выполнение правил транзитивности приводит к появлению в С(Ф) дуг (W- —1W) и (-^W- W), а это, в свою очередь, подразумевает, что следствием формулы Ф является невыполнимая конъюнкция (И7=1 -iW) & (-•U7=1 W), из чего заключаем, что сама Ф также невыполнима.
Таким образом, в QC-структурах используются те же правила вывода, что и в графе Крома. Кроме того, очевидно, что любое суждение в QC-структурах, содержащее в правой части более одного литерала, также изоморфно графу Крома, поскольку может быть разложено на элементарные суждения, содержащие в правой части один литерал.
Рассмотрим отображение ф: Г —> Ф, переводящее QC-структуру Г в формулу Ф класса Крома, такое что каждой паре литералов (X, X) в Г соответствует пара (X, —•X) литералов в Ф и отношению порядка в Г соответствует импликация в Г. Допустимые коллизии типа X —" X в Г соответствуют в Ф однолитерной дизъюнкции "1X
Из изложенного ясно, что преобразование Ф в С(Ф) полностью соответствует преобразованию Г в Г6, когда в исходную структуру добавляются все следствия, полученные только с помощью правила контрапозиции. Задача распознавания невыполнимости в Ф соответствует задаче распознавания вырожденности Г (см. определение Б.9).
Из соответствия Гс и С(Ф) следует, что многие задачи, решаемые в рамках QC-структур (распознавание коллизий, анализ неполноты, формирование множества корректных гипотез и т. д.), могут быть сформулированы на языке исчисления высказываний в формулах класса Крома, но их интерпретация в этом случае является менее объемной, чем интерпретация QC-структур, а смысл многих результатов анализа явно не совпадает. Например, коллизия парадокса в классе формул Крома означает тривиальную тавтологию —1X-X=X. Для у-множеств и QC-структур данное равенство не имеет смысла.
124_Приложение Б. Частично упорядоченН&іе'множества_
Заключение
Первым практическим приложением QC-структур стало изложенное в работах автора использование их частного случая (^-структур) для расширения аналитических возможностей полисиллогистики. Вопрос о других практических приложениях QC-структур пока что остается открытым. Здесь мы рассмотрим лишь некоторые сформулированные в общем виде возможные рекомендации.
1. Результаты и методы теории частично упорядоченных множеств используются во многих областях знаний, например в системах логического вывода, при анализе измеримых пространств, семейств аналитических функций, в приложениях нечетких множеств и т. д. Но во многих случаях ради увеличения аналитических возможностей у-множеств их сужают до решеток, что не позволяет полностью отобразить многие свойства исследуемых структур, если они по своей природе не соответствуют аксиомам решеток. В этом случае вместо решеток можно использовать QC-структуры, в которых по сравнению с обычными у-множе-ствами увеличиваются аналитические возможности не за счет редукции структурных связей, аза счет введения операций.
2. Значительная часть задач современной теории распознавания образов сводится к задачам классификации, т. е. к построению методов и алгоритмов, с помощью которых исходная выборка разделяется на некоторое число непересекающихся классов объектов. При таком отображении в разные классы нередко попадают объекты, между которыми имеются структурные связи со свойствами частичного порядка. Тем самым теряется возможность адекватного восстановления причинных связей в том случае, если исследуемые объекты принадлежат некоторой развивающейся во времени или пространстве системе. В то же время с точки зрения теории QC-структур системы можно рассматривать не как совокупность непересекающихся классов объектов, а как совокупность ориентированных связей между ними. При этом кластеризация объектов осуществляется уже на основе анализа этих" связей. В основу такой кластеризации можно положить следующие критерии: принадлежность определенным главным фильтрам или главным идеалам, глубина вложения относительно наибольших или максимальных элементов и т. д.