Ремонт принтеров, сканнеров, факсов и остальной офисной техники


назад Оглавление вперед




[3]

Первые четыре тождества определяют решетку. Дистрибутивная решетка с инволютивной операцией дополнения, на которой выполняются законы Де Моргана называется решеткой Де Моргана. Решетка Де Моргана с наименьшим 0 и наибольшим U элементами называется алгеброй Де Моргана.

Отношение частичного упорядочения z элементов решетки связано с решеточными операциями n и u следующим образом:

A zB тогда и только тогда, когда AnB =A, AuB=B.(1)

Отметим также следующие свойства решеток, которые будут в дальнейшем использоваться в доказательствах:

из A zB, A zC следует A zBnC, из A zC, B zC следует AuBzC.

В алгебре Де Моргана выполняется:

l0= U,lU = 0;

из A zB следует lB <z~A.(2)

Как известно, алгебра обычных множеств является булевой алгеброй, операции которой кроме перечисленных тождеств алгебры Де Моргана удовлетворяют тождествам

AnlA = 0, AuA = U.(3)

Для алгебры нечетких множеств выполняется в общем случае лишь следующее более слабое условие

(AnA)n (BuB) =AnA (условие нормальности).

Это тождество часто записывают в виде:

AnlA z BulB(условие Клини).

Нормальная алгебра Де Моргана <F;n,u,l,0,U> называется алгеброй Клини. Алгебры Де Моргана и алгебры Клини играют важную роль при изучении неклассических логик.

Элемент A алгебры Де Моргана F, удовлетворяющий условиям (3), будет называться булевым.


В алгебрах Клини выполняются следующие соотношения [83]:

(AnlA) u(BnB)c(AnB) u(lAnB)=(A uB)n(A uB)c(A uA)n(B uB), (AnlA) u(BnlB)c(AnB) u(lAnlB)=(A u~B)n(~A uB)c(A uA)n(B uB).

2. Фокальные алгебры Клини

Пусть <F;n,u,l,0,U> - алгебра Де Моргана, и Zявляется подалгеброй F по операциям n ,u, l, т.е. из A,B eZ следует AnB eZ и A uB eZ, и из AeZ следует lA eZ. Подалгебра Z будет называться интервальной подалгеброй F, если Z является интервалом Z = [C,D], где C и D - некоторые элементы из F такие, что C с D, и Z состоит из всех элементов A eF таких, что C с A

D.

Теорема 2.1. Алгебра Де Моргана F является алгеброй Клини тогда и только тогда, когда пересечение любых ее двух интервальных подалгебр не пусто, и F является булевой алгеброй тогда и только тогда, когда она содержит лишь одну непустую интервальную подалгебру (совпадающую с

F).

Для доказательства теоремы докажем ряд вспомогательных утверждений.

Лемма 2.2. Для любого элемента CeF интервал [CnlC,CulC] является интервальной подалгеброй F, и любая интервальная подалгебра Z алгебры Де Моргана F представима в виде Z = [CnlC,CulC] для некоторого Ce F.

Д о к а з а т е л ь с т в о. Пусть Z = [CnlC,CulC] для некоторого C eF. Поскольку любой интервал решетки F является ее подалгеброй по операциям n и u, достаточно показать, что Z замкнуто относительно операции дополнения l. Из AeZ следует CnlC A CulC, из (2) получаемоткуда следует CnlC lA CulC, т. е.

lAe Z.

Пусть Z = [C,D] - интервальная подалгебра F. Тогда lC,lDe Z, что дает C lD, lC D, и из (2) получим l(lD)=D с lC, что приводит к lC= D. Из CcD=lC и (1) следует C=CnlC, CulC =D и Z = [CnlC, CulC].

Лемма доказана.

Интервальная подалгебра Z = [CnlC, CulC] алгебры Де Моргана F будет обозначаться Z(C) и называться интервальной подалгеброй F, порожденной элементом Ce F, а элемент C - элементом, порождающим интервальную подалгебру Z(C). Ясно, что Z является подмножеством любой интервальной подалгебры, содержащей C.

На множестве F можно задать отношение эквивалентности « такое, что A « B, если A и B порождают одну и ту же интервальную подалгебру.


Лемма 2.3. Каждый класс эквивалентности E отношения « в алгебре Де Моргана F образует булеву алгебру с операциями п,и,~] из F.

Доказательство. Пусть E - произвольный класс эквивалентности отношения « в алгебре Де Моргана F, и A,B -произвольные элементы из E. Тогда A и B порождают одну и ту же интервальную подалгебру Z= [AnA, AuA] = [BnB, BuB], причем из A,BeZ следует, что EcfZ. Из инволютивности ] следует, что ~A,~BeE. Покажем, что AnB принадлежит E. Обозначим C = AnB. Тогда, учитывая (1) и AnA cB, BnB cA, AnA = BnB, получим: Cn]C = (AnB)n](AnB) = AnBn(AuB) = (AnBnA)u(AnBnB) = (AnA)u(BnB) = (AnA), далее имеем Cu]C =](Cn\C) =](AnA) = AuA, что дает Z= [Cn]C, Cu]C]= Z(C), откуда следует CeE и AnBeE. Аналогично показывается, что A uB eE. Таким образом, E является подалгеброй алгебры Де Моргана F. Учитывая, что для произвольного A eE элементы AnA и A uA являются соответственно наименьшим и наибольшим элементами в E, получаем, что E образует булеву алгебру.

Лемма 2.4. Для произвольных элементов A,B алгебры Де Моргана F выполняется Z(A)nZ(B) ф 0 тогда и только тогда, когда выполняется

(AnA) u(Bn]B)c (A uA)n(B uB)(4)

Д о к а з а т е л ь с т в о. Отметим, что пересечение интервальных подалгебр алгебры Де Моргана F, если оно не пусто, является интервальной подалгеброй F, так как пересечение подалгебр является подалгеброй, а пересечение интервалов является интервалом. Пусть Z(A)nZ(B) ф 0, тогда Z(A)nZ(B) = {CeF\ AnAcCcAuA и Bn]BcCc BuB} ф 0, откуда следует Z(A)nZ(B) = {CeF\ (AnA) u(Bn~B)c: Cc (Au]A)n(Bu]B)} ф 0, что приводит к (4). Обратным путем показывается, что если существуют A,BeF, для которых выполняется (4), то Z(A)nZ(B)ф

0.

Лемма 2.5. В алгебре Де Моргана условие Клини, условие (4) и условие

из Ac] A, Bc] B следует AuB c] An] B(5)

попарно эквивалентны.

Д о к а з а т е л ь с т в о. (5) => (4). Из свойств операций пи u и законов Де Моргана следует: AnAc AuA = ~\(An~A), BnBc Bu]B = что совместно с (5) приводит к (4).

(4) (условие Клини). AnAc (An~A)u(Bn~B)c: (Au~A)n(Bu~B)c:

Bu\ B.



[стр.Начало] [стр.1] [стр.2] [стр.3] [стр.4] [стр.5] [стр.6] [стр.7] [стр.8] [стр.9] [стр.10] [стр.11] [стр.12] [стр.13] [стр.14] [стр.15] [стр.16] [стр.17] [стр.18] [стр.19] [стр.20] [стр.21] [стр.22] [стр.23] [стр.24] [стр.25] [стр.26] [стр.27] [стр.28] [стр.29] [стр.30] [стр.31] [стр.32] [стр.33]