Логика естественных рассуждений - Кулик Б.А.
ISBN 5-7940-0080-5
Скачать (прямая ссылка):
1) построение СГ-замыкания, главных идеалов и главных фильтров QC-структуры;
2) построение инвариантов QC-структуры (диаграммы Хассе и минимального определяющего множеств элементарных суждений);
3) проверка корректности и перечисление всех возможных коллизий;
4) проверка полноты, проверка корректности и перечисление всех возможных базовых элементарных гипотез;
5) проверка корректности каждой из возможных экзистенциальных гипотез;
6) проверка корректности и совместимости различных QC-структур и их композиций.
По сути, эти задачи сводятся к таким задачам на графах, как построение множества достижимых вершин из заданной вершины и транзитивного замыкания графа, которые характеризуются полиномиальной вычислительной сложностью [Кристофидес, 1976]. В то же время существуют задачи, алгоритмы которых для частных случаев могут превышать полиномиальную оценку. К ним, в частности, относится:
1) задача построения всех базовых покрытий для неполных QC-структур;
2) перечисление всех возможных экзистенциальных гипотез.
Приложение Б. Частично упорядоченные множества
119
Неполиномиальная вычислительная сложность первой задачи следует из того, что некоторые корректные базовые покрытия могут быть образованы с помощью присоединения к исходной QC-структуре двух и более различных элементарных гипотез; т. е. в данном случае имеет место перебор элементарных суждений с повторениями, что ведет в общем случае к существенному увеличению вычислительной сложности алгоритмов.
Задача перечисления всех возможных экзистенциальных гипотез сводится к перечислению всех непустых и неодноэлементных подмножеств множества всех базовых литералов.
7. Операции "умножения" и "сложения" в QC-структурах
В разделе 2 Приложения Б операции "умножения" (*) и "сложения" (+) были определены как частичные операции, точное значение которых в конкретной QC-структуре Г определяется следующими правилами:
(1) если литералы А, В сравнимы в Г и A-* В, то A* B = Au А+В = В.
Кроме того, вполне естественными правилами для этих операций в QC-структурах являются следующие:
(2) если А, В, Ce=TuC = A* В, то C-^ AuC-* В;
(3) еслиА,В,С<=ГиС = А+В,тоA^ CuB-* С.
Эти правила не определяют точных значений соответствующих операций в тех случаях, когда элементы AuB несравнимы. Однако во многих случаях точные значения их можно получить и для несравнимых пар элементов QC-структур. В частности, для многих интерпретаций эти операции являются полными операциями. Покажем это на конкретных примерах.
1) Классы Set и Num. Для конкретно заданных QC-структур из классов Set и Num это очевидно. В Set такими операциями являются обычные операции пересечения и объединения алгебры множеств. Для Num, как и для любого вполне упорядоченного множества, чтобы получить точный результат операции с любой парой элементов достаточно использовать правило (1).
2) Класс Div. Для любой пары чисел (А, В) результаты "умножения" и "сложения" определим следующим образом: А*В = С, где С — наибольший общий делитель (НОД ) для AuB,nA + B = D, где D — наименьшее общее кратное (HOK) для А и В. Нетрудно убедиться, что для данного класса правила (1), (2), (3) выполняются в любом случае.
3) Класс Dom. Если в каждой координате определен точный результат этих операций для любой пары элементов, то очевидно, что определен он и для целого вектора.
120
Приложение Б. Частично упорядоченные множества
4) Класс Fun. К этому классу относится множество всех (или какой-то выбранной совокупности) непрерывных функций на отрезке [а, ?]. Для любых двух функций УHg соблюдается f — g, если j(t) < g(t) для всех t, принадлежащих этому отрезку. Если существуют миноранта 0(г) и мажоранта 1(г) этих функций на отрезке [а, ?], то класс Fun можно рассматривать не только с точки зрения теории у-множеств, но и с точки зрения теории QC-структур. Свойства этого класса во многом совпадают со свойствами класса Dom, в котором все координаты относятся к классу Num. Если аналитически заданы графики этих функций и каждая пара функций имеет на отрезке [а, ?] конечное число точек пересечения или непрерывных областей пересечения, то можно построить для любой пары функций соответствующие графики или аналитические зависимости для их "умножений" и "сложений". Для этого требуется лишь разложить отрезок [а, ?] на конечное число отрезков, границы которых совпадают с ординатами точек пересечения или являются границами областей пересечения сравниваемых функций. Тогда в каждом таком элементарном отрезке пары областей значений функций окажутся сравнимыми. Остается только при осуществлении соответствующей операции выбрать график соответствующей функции в каждом отрезке. В формальных QC-структурах ситуация с операциями намного сложнее и теоретические предпосылки для общего случая QC-структур пока что не сформулированы достаточно четко. Поэтому здесь мы ограничимся в основном некоторыми оценками результатов операций в формальных QC-структурах.
Оказывается, что в формальных f-структурах можно получить точные результаты операций и для некоторых несравнимых пар элементов.
