Логика естественных рассуждений - Кулик Б.А.
ISBN 5-7940-0080-5
Скачать (прямая ссылка):
В современной алгебре частично упорядоченные множества, как правило, рассматриваются как статичные системы, у которых изначально заданы или аналитически выявляются с помощью сравнения все возможные отношения порядка между некоторыми парами элементов. Введение операций позволяет представить частично упорядоченное множество как некоторую динамичную дедуктивную систему с универсальными правилами вывода и методами проверки совместимости и полноты. Кроме того, если рассматривать эту систему как логическую, то оказывается, что выводимые в ней несоответствия с законами булевой алгебры не являются результатом своеобразного и не всегда обоснованного произвола, а имеют строгую математическую основу и к тому же находят подтверждение на многих широко известных и часто применяемых математических объектах (числах, векторах, множествах и т. д.)
2. Операции в частично упорядоченных множествах
Традиционно частично упорядоченные множества общего вида — далее у-множества (posets) — рассматриваются как алгебраическая система без операций. Операции вводятся только для некоторых частных случаев у-множеств (в частности, для решеток и структур ). Мы здесь при введении операций будем использовать только ограниченные сверху и снизу у-множества, т. е. имеющие наибольший (1) и наименьший (0) элементы. Известно, что свойства у-множеств полностью определены свойствами бинарного отношения частичного порядка:
(1) рефлексивностью (а<а для любого а),
(2) транзитивностью (из а < Ъ и Ъ < с следует а < с) и
(3) антисимметричностью (из а < bub^a следует а = Ь), где а,Ь,с — произвольные элементы у-множества.
Широко известными частными случаями у-множеств являются вполне упорядоченные множества, а также структуры [Скорняков, 1982] (или — по другой терминологии — решетки [Биркгоф и Барти, 1976]). У-множество является вполне упорядоченным, если для любой пары (а, Ь) верно а < b либо b < а. Структуры и решетки неформально определяются как у-множества, у которых любые два элемента а и Ъ имеют точную
Приложение Б. Частично упорядоченные множества 99
нижнюю и точную верхнюю грани. Такое свойство структур и решеток позволяет определить для них две полные операции: Л (inj) и V (sup). Для вполне упорядоченных множеств, у которых сравнимы все пары элементов, естественными операциями являются min(a, b) и тах(а, Ь).
Здесь мы рассмотрим другой способ введения операций в у-множе-ства с 0 и 1 без предварительного выделения каких-либо частных случаев. Операции типа "умножение" (*) и "сложение" (+) можно ввести как частичные бинарные операции, определяемые по следующему правилу.
Если элементы а и b у-множества сравнимы и при этом a^b,moa*b = aua + b = b.B остальных случаях эти операции либо полностью не определены, либо могут быть оценены в виде одного или нескольких ограниченных с одной или с двух сторон диапазонов (например, с < а* Ь, где а, Ь, с — изначально заданные элементы у-множества).
Способы оценки возможных диапазонов для неопределенных операций мы рассмотрим ниже. Кроме того, введем для у-множеств полную унарную операцию квазидополнения со свойствами:
(i) для любого элемента/! существует или может быть построен единственный элемент А, который называется квазидополнением А;
(ii) для любого элемента А соблюдается равенство A = A; (ііі)для любых двух элементов А и В, связанных отношением А < В,
верна контрапозиция В < А.
Чтобы в у-множествах квазидополнение стало точным (т. е. без приставки "квази"), необходимо еще одно условие:
(iv) для любого элемента А из А < А следует А = 0 и А = 1.
На первый взгляд кажется, что мы от у-множеств тем самым переходим к обычной алгебре множеств (или булевой алгебре). Но это не так — далее мы увидим, что в данной системе алгебра множеств является лишь частным случаем даже в системах со свойством (iv). Кроме того, оказывается, что у-множества с квазидополнениями встречаются весьма часто. Рассмотрим некоторые примеры.
1) Множества, упорядоченные по включению (Set), для которых наименьшим элементом является пустое множество (0), а наибольшим — универсум. Если в Set использовать как квазидополнение обычное дополнение множеств, то все четыре свойства являются законами алгебры множеств. При этом допускается неполнота соответствующих систем множеств, когда операции объединения и пересечения в общем случае точно определены не для всех пар множеств системы.
2) Конечные множества положительных целых чисел, упорядоченные по делимости (Div). Здесь наименьшим элементом является
А*
100_Приложение Б, Частично упорядоченные множества
число 1. Выберем в качестве наибольшего элемента (і) в Div наименьшее общее кратное (HOK) для всех его элементов или число, кратное НОК. Тогда квазидополнение А любого элемента А можно определить как Л = І/А. При этом нетрудно доказать, что свойства (i)-(iii) сохраняются в любом ограниченном сверху и снизу у-множестве класса Div, но возможны случаи, когда нарушается свойство (iv). Примером является у-множество 5= {1, 2, 3,4,6,12} класса Div, в котором 0 = 1 и 1 = 12. Нетрудно убедиться, что в нем свойства (i)-(iii) справедливы для всех элементов, а свойство (iv) нарушается для числа 2 и его квазидополнения 6 (2 — делитель 6, но при этом 2 * 0 и 6 * 1). В то же время, если рассматривать некоторые частные случаи класса Div, например один из них, когда во всех его элементах кратность каждого простого делителя не больше единицы, то окажется, что свойство (iv) всегда выполняется.
