Научная литература
booksshare.net -> Добавить материал -> Логика -> Кулик Б.А. -> "Логика естественных рассуждений" -> 54

Логика естественных рассуждений - Кулик Б.А.

Кулик Б.А. Логика естественных рассуждений. Под редакцией Дюка В. А. — СПб.: Невский Диалект, 2001. — 128 c.
ISBN 5-7940-0080-5
Скачать (прямая ссылка): logika-estestvennih-rassujdeniy.djvu
Предыдущая << 1 .. 48 49 50 51 52 53 < 54 > 55 .. 56 >> Следующая


Формула Ф класса Крома невыполнима, если и только если в Ф существует литерал 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-структур системы можно рассматривать не как совокупность непересекающихся классов объектов, а как совокупность ориентированных связей между ними. При этом кластеризация объектов осуществляется уже на основе анализа этих" связей. В основу такой кластеризации можно положить следующие критерии: принадлежность определенным главным фильтрам или главным идеалам, глубина вложения относительно наибольших или максимальных элементов и т. д.
Предыдущая << 1 .. 48 49 50 51 52 53 < 54 > 55 .. 56 >> Следующая

Реклама

c1c0fc952cf0704ad12d6af2ad3bf47e03017fed

Есть, чем поделиться? Отправьте
материал
нам
Авторские права © 2009 BooksShare.
Все права защищены.
Rambler's Top100

c1c0fc952cf0704ad12d6af2ad3bf47e03017fed