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

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

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


Из теоремы Б. 1 і следует, что в случае, когда A-* В является корректной гипотезой в Е, то в альтернативных к ней гипотезах невозможна коллизия цикла. Тем самым сужается поиск возможных опровержений предположения. Еще одно ограничение поиска формулируется в виде следующего утверждения.

Іеорема Б. 12. Если в корректной Е-структуре E соблюдаются два равенства Av П /т;((В)А) = M1 и (Af Л InV(B*) = M2, то M1OM2 = 0. Доказательство. Предположим, что в E существует базовый литерал W, такой что ІУє M) П Mi- Из теоремы 4 следует, что Inv((B)A) = Bv и Inv(Bu) = (?)v. В силу условий теоремы получается, что литерал Wb Ew предшествует одновременно литералам В тлЪ. Из соотношений W-* В и W-* В следует коллизия парадокса W-* W, что противоречит предположению о корректности /{-структуры Ё. Конец доказательства.

Из теорем Б. 11 и Б. 12 следует, что, независимо от корректности гипотез типа А -* Bjt /{-структурах, коллизию парадокса в предполагаемых гипотезах А —- В и А ~* В инициируют разные литералы.

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

Приложение.^ Мастично упорядоченные множества

117

некоторые из которых вложены друг в друга. С этой точки зрения целесообразно в теорию QC-структур ввести еще одно понятие — базовое покрытие.

Определение Б. 11. Базовым покрытием системы, заданной QC-структурой Г, называется инвариант Qi корректной QC-структуры, в которой множество базовых литералов совпадает с множеством базовых литералов Г и при этом ГСТ = П,-СТ.

Любое базовое покрытие QC-структуры Г образуется из нее путем присоединения к ней некоторой совокупности элементарных базовых гипотез, поскольку само является корректной QC-структурой. Справедливость соотношения ТСТ s QjCT для QC-структуры Г и ее базового покрытия Qi не означает, что для диаграмм Хассе этих же структур выполняется T11 S Qi4. Например, в примере Б.5 диаграмма Хассе исходной f-структуры (см. рис. Б.З) не является вложенной в диаграммы Хассе некоторых ее базовых покрытий (см. рис. Б.4 и Б.6). Понятно, что множеством {Qj} базовых покрытий полной ^-структуры является только эта структура. При моделировании с помощью QC-структур содержательных рассуждений множество базовых покрытий можно использовать для формирования индуктивных умозаключений.

Рассмотрим еще один класс суждений, которые мы назовем экзистенциальными суждениями. В отличие от базовых суждений в них левая часть содержит новый литерал, но при этом в правой части суждения содержится более одного литерала. Название обусловлено тем, что они являются обобщением частных суждений силлогистики, а в алгебре множеств экзистенциальное суждение W-* (X, Y1Z)1 где W- новый литерал, соответствует выражениюXn F п ... n Z ^ 0. Экзистенциальные суждения также можно использовать в качестве гипотез, при этом присутствие в правой части двух и более базовых литералов не всегда гарантирует, что гипотеза такого рода окажется корректной. Пример такой неудачи — суждение W~* (X, Z) для исходной f-структуры из примера Б.5. Присоединение этого предложения к данной f-структуре ведет к появлению коллизии парадокса W —* W. Для экзистенциальных суждений в формальных f-структурах можно легко доказать следующий критерий корректности.

Теорема Б. 13. Пусть W-* (S) — экзистенциальное суждение, где S — некоторое множество базовых литералов корректной формальной E-структуры Е. Тогда W —* (S) является корректной гипотезой в E и во всех ее базовых покрытиях, если в E существует хотя бы один главный фильтр ?л, такой что S Є Iа.

118

Приложение Б. Частично упорядоченные множества

Доказательство. Положим 0 и W-* L. Для любого подмножества S множества LA литералов соблюдается L —> (S). Из W^L следует W -* (S). Корректность гипотезы W — (S) справедлива также во всех базовых покрытиях Е, поскольку объем главных фильтров в них не сокращается по сравнению с главными фильтрами Е. Конец доказательства.

6. Оценка вычислительной сложности алгоритмов

Оценим вычислительную сложность алгоритмов решений приведенных выше задач анализа QC-структур. Пусть п — число литералов QC-структуры или нескольких объединяемых для решения определенных задач QC-структур, и 0(f(n)) означает функцию, порядок которой не более чем f(n). Из сказанного ясно, что число допустимых парных связей между литералами в QC-структурах не превышает числа ориентированных дуг обычного графа (т. е. не мультиграфа), содержащего п вершин. Поэтому число элементарных суждений в них не превышает числа, оценкой которого является 0(п2). С учетом этого вычислительной сложностью 0(п2) характеризуются алгоритмы, в которых результат получается в худшем случае с помощью перебора без повторений имеющихся в QC-структуре элементарных суждений. К таким алгоритмам, в частности, относятся следующие рассмотренные ранее алгоритмы:
Предыдущая << 1 .. 45 46 47 48 49 50 < 51 > 52 53 54 55 .. 56 >> Следующая

Реклама

c1c0fc952cf0704ad12d6af2ad3bf47e03017fed

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

c1c0fc952cf0704ad12d6af2ad3bf47e03017fed