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

45 Теорема 2.14. В ограниченной дистрибутивной решетке с дополнением выполняется; 1) дополнение а'единственно; 2) дополнение иволютивно: а" = а\ 3) грани дополняют друг друга: Г = О, О' = 1; 4) выполняются законы де Моргана; (cKJbf = a'rh\ (апЬ)' = а'иЬ'. x = xnl~xr\(a<jv) = (xna)^jixny) = 0^j{xr\y) = xr\v. => ' JI = J п i = J п (а U х) = (J п а)U( j о дг) = О ( j п д:) = ><П д-. Доказательство. 1). Пусть х,у- дополнения а. Тогда; апх =0,a\jx = } аг\у =0,a\J у = 1 Из этих соотношений получим х=хпу=у, т.е. х-у, аиа'= 1 •=> а'^ а -1] 2) \=>а = {а')'-, ana' = 0=> а па =01 П г\0 = 0,0'п0 = 0)^ 1 =0', {}u0 = !,lul'^I)^0=r-^ (а r^b) Г\(а' \jb) = (а глЬ ел a)\j (а Г\Ъ глЪ) = (о пЪ)(а Г\0) = О, (ar\h)\j(a'^b') = (a\ja'^b')r\(b\ja'\jb')-(lyjb')r\(a'yjl)-ir\l = l. Следовательно, а' KJ Ъ' является дополнением для аглЬ, т.е. (аглЪ)'=а' и6'. Аналогичным образом можно доказать и второй закон де Моргана. Частичный порядок в решетке. В любой решетке можно естественным образом ввести (нестрогий) частичный порядок: а 4 Ь о аглЬ=а. Покажем, что это определение корректно, т.е. введенное отношение удовлетворяет аксиомам частичного порядка. Теорема 2.15. Пусть а ^ b ^ аглЬ-а. Тогда отношение является отношением частичного порядка. Доказательство. 1. Рефлексивность: агла=а => а ^а. 2. Антисимметричность; (а =^Ь) и (Ь ^а) => (аг\Ь=а) И (Ьпа=Ь) => => (а=аглЬ=Ъ) => (а=-Ъ). 3. Транзитивность: (а =ib) и (Ь 4с) => (апЬ-а) и {bnc=b) => => (апс=аглЬг\с) и (апЬглс=аг\Ь) => (ar\c=ar\bniC=anb) => => (аПс=аГ\Ь) => (аг\с=а) => а <с. Примеры решеток. 1. Пусть А - непустое множество, N=2*. На М введем операции объединения и пересечения множеств. Получим решетку {М; и , о). Нижней гранью будет 0, верхней гранью - М, а дополнением элемента А - элемент А . Считаем, что А если АпВ=А. Очевидно, что не