Дискретная математика

44 => lt>x=d' ob=>x=a'''b. § 10. Решетки Решетки иногда называют структурами. В решетках, как и в кольцах, имеются две операции, которые можно обозначать через + и х, но так как одним из важнейших примеров решеток являются множества всех подмножеств с операциями объединения и пересечения, то для операций в решетках применяют обозначения и ип . Решетка ~ это множество М с двумя бинарными операциями и ио , такими, что для Va, b, сеМ выполнены следующие условия (аксиомы решетки): 1) идемпотентность: аиа=а, агла=а; 2) коммутативность: 0 ^ 6 =6иа, anb=bna; 3) ассоциативность: Cau6juc=au(bucj (аглЬ) Пс=аГ\(Ьпс); 4) поглощение: (апЬ)^иа=а, (аиЬ)г\а=а; 5) решетка называется дистрибутивной, если; ar\(b^c)=(anb)<j(anc), ayj(bnc)=(ayjb)r\(a^c). Ограниченные решетки. Если в решетке ЗОеМ, что для Va: 0па=0, то о называется нулем или нижней гранью решетки. Если в решетке 3 1 еМ, что для Va: то 1 называется единицей или верхней фанью решетки. Решетка с верхней и нижней гранями называется ограниченной. Теорема 2.12, Если нижняя (верхняя) грань существует, то она единственна. Доказательство. Пусть О и О* - нули решетки. Тогда On и 0 * n 0=0. Следовательно, 0=0*. Аналогично для 1. Теорема 2.13. аГ\Ь=Ь <=>aKjb=a. Доказательство. Пусть anb=b. Тогда avjb=au(anb) = =(a^a)r\(a<ob)'=ar\(ayjb)=a. (<=): Пусть aub=a. Тогда: а('лЬ=(а^Ь)г лЬ=Ь. Следствие 2.1. 0na=a' »0ua=o, \yja=\<=>\r\a~a. Решетка с дополнением. В ограниченной решетке элемент а' называется дополнением элемента а, если ana' =0 иoua ' =1.