Инструменты пользователя

Инструменты сайта


Боковая панель

Регистрация

Учебные курсы

Учебные проекты

Материалы к экзаменам

Полезная информация

Обратная связь

textbooks:prepodavatelyu:teoria_reshetok:osnovnye_klassy_reshetok

Задача 3. В каждой решетке W=(Р, ≤) для всех а, b, с ϵ Р истинны следующие соотношения: a) а V b = b V а, а ^b = b ^ а; b) (а V b)V с = а V (b V с), (а ^b) ^ с = а ^({b ^ с)*); c) если а ≤b, то а ^ b = а и b = а V b; d) а^ b ≤ а, a ≤ а V b; e) a V(а ^ b)= а, а ^(а V b)= а; f) если а ^ b = а V b, то а =b. Доказать истинность пунктов: e,f. Решение: Докажем справедливость пункта e)a V(a^b)=a; Для этого раскроем скобки: aVa ^ aV b. Так как a ^ b≤ a (из пункта d), то докажем, что a≤b: avb ≥ a ⇒ a v a ≤ b ⇒ a≤b; а из пункта с следует, что a^b=a ⇒ av(avb)=ava=a, что и т. д. А теперь докажем справедливость пункта f) если a^b = avb , то a=b; Из пункта d знаем, что a^b≤a, a≤avb; Тогда (a^b≤a)=(avb≥a)  ava≥b = a^a≤b  a≥b = a≤b а из этого вытекает то, что мн-во a включено в b, а b включено в a;  a=b , что и т. д. “В задаче 3 мы установили, что в каждой решетке W = (Р,≤) для любых а, b, с из Р выполняются усл-я: (S1) а V b = b V а; (S2) (а V b) V с = а V(b Vс); (S3) а (а^b) = а; (Р1) a ^ b = b ^ а; (Р2) (а ^ b) ^ с = а ^ (b ^ с); (РЗ) а ^ (а V b) = а” [9,c.77]. “Можно доказать и обратное: если на некотором непустом множестве Р определены две операции ^, V так, что выполняются условия (S1) — (S3) и (Р1) — (РЗ), и если ввести отношение ≤, полагая а ≤ b тогда и только тогда, когда а ^ b = а, то это отношение ≤ упо¬рядочивает множество Р и (Р, ≤) оказывается решет¬кой. Учитывая это, часто о решетке W = (Р,≤) говорят как о решетке W=(Р, V, ^). Например, в решетке W = (Р(Е), включение) операциями являются U, ∩ (объединение и пересечение), и ее записывают так же как тройку W(Е) = (Р(Е), U, ∩). Если возьмем в решетке W(E) =(Р(Е), U, ∩) три множества А, В, С, принадлежащие Р(Е), то A∩(BUC)=(A∩B)U(A∩C) и AU(B∩C) = (AUB)∩(AUC) (приведем краткое доказательство первого соотношения: элемент х принадлежит множеству A ∩| (В U С) тогда и только тогда, когда он принадлежит А и одновременно принадлежит В или С, т. е. когда он принадлежит А ∩ В или A∩C. Впоследствии мы увидим, что второе соотно¬шение является следствием первого и того факта, что W(E) является решеткой). Решетка W=(Р, V, ^) называется дистрибутивной тогда и только тогда, когда в W для любых а, b, с ϵ Р (4) а ^ (b V с) = (a ^ b) V (а ^ с) и (5) а V (b^ с) = (а V b) ^ (а V с). Согласно этому определению W(Е) = (Р(Е), U, ∩) яв¬ляется дистрибутивной решеткой.”[9,c.45] “Будем говорить, что непустое подмножество М носителя Р решетки W замкнуто относительно операций V и ^ тогда и только тогда, когда для любых т, п, при¬надлежащих М, этому подмножеству принадлежат так¬же т V п и т ^ п. Упорядоченная тройка (М, V, ^ ) в этом случае называется подрешеткой решетки (Р, V, ^) (или решетки (Р, ≤)). Множество М называется носи¬телем этой подрешетки. Поскольку для любых трех эле¬ментов а, b, с из М выполняются условия (S1) — (S3) и (PI) — (РЗ), каждая подрешетка является и решет¬кой”[9,c.47].

Теорема 3.“Если на некотором непустом множестве Р опре¬делены операции V и ^, обладающие свойствами (S1) — (S3) и (Р1) — (РЗ), и если ввести отношение≤, полагая а ≤ b тогда и только тогда, когда а = а ^ b, то это отношение ≤ упорядочивает множество Р и (Р,≤) оказывается решеткой, причем a^b = inf (а,b) и а V b = sup (а, b). Доказательство. Ввиду (S3) а = а V (а ^ а), откуда, ис¬пользуя (РЗ), получаем а ^ а = а ^ (а V (а ^ а)) = а. Таким образом, а = а ^ а, а значит, а ≤ а. т. е. отношение ≤ рефлексивно. Если а ≤ b и b ≤ с, то а = а ^ b и b=b^c. Учи¬тывая (Р2), получаем а = а^Ь = а^(b^с) = (а^b)^с = а^с. Отсюда а ≤ с, т. е. отношение ≤ оказывается транзитивным. Если а≤ b и b≤ а, то а = а ^ b и b=b^a, откуда а=а^b=b^а=b в силу (Р1). Этим доказана антисимметричность отношения ≤. Таким образом, это отношение упорядочивает множество Р. Из равенств (а^b ) ^ а = а ^ (b^ а) = а ^ (а ^ b) = (а ^ а) ^ b = а ^ b и (а^b)^ b = а^ (b ^ b) = а^b , вытекающих из (P1), (Р2) , получаем, что a ^ b ≤ a и a^b≤b, т.е. a^b оказывается нижней гранью множества {а, b}. Если х — какая-либо другая нижняя грань этого множества, то х ≤ а и х≤b, т. е. х = х ^ а и x = х^b. Отсюда х^ (а^ b) = (х ^ а) ^ b = х ^ b = х, т. е. x≤ а ^ b. Следовательно, a ^b — наибольшая нижняя грань множества {а, b}, т. е. а ^ b= inf {а, b}. Далее, из (S1) и (РЗ) вытекает а ^ (а V b) = а и b ^ (а V b) = b ^ (b V a)=b. Следовательно, a≤aVb и b≤ a Vb, т. е. a Vb оказывается верх¬ней гранью множества {а, b}. Если х - какая-либо другая верхняя грань этого множества, то а ≤ x и b≤ x, откуда а= а ^ х и b = b^x. Теперь, используя (S3) и (Р1), получаем х = х V (х ^ а) = х V (а ^ х) = х V а и х = х V (х ^ b) = х V (b ^ х) = х V b. Но тогда, учитывая (РЗ) и (S3), получаем х V х = х V (х ^ (х V х)) = х, после чего, используя (S1), (S2) и (РЗ), приходим к (а V b) ^ х = (а Vb) ^ (х V b) = (а V b) ^ 1) = (а V b) ^ ((а V b) V х) = а V b. Следовательно, а V b ≤ x. Таким образом, а V b оказывается наи¬меньшей верхней гранью множества {а, b}, т. е. а V b = sup {а, b}”[4, c.79].

1) х V а) V b) = (а V b) ^ (х V (а V b
textbooks/prepodavatelyu/teoria_reshetok/osnovnye_klassy_reshetok.txt · Последние изменения: 2014/11/27 09:04 (внешнее изменение)