Дискретная математика (998286), страница 12
Текст из файла (страница 12)
ТЕОРЕМА Пусть В = (еь,...,е„) — базис, а Х = (хм .,х ) — лшьейно независимое множество пространства 7. Тогда и > т. поля) е1 =а ьх1 — (а ьаз)ер — (аь'а„)е„. Так как В порождает 7, то и (хт,ер,...,е„) тоже порождает 7. Аналогично [хю ха, ез,, е„) поРождает 7. ПРодолжаЯ пРоцесс, полУчаем, что (хь,..., хи) порождает 7. Следовательно, и и и х +1 ки~ Ь,хьй~/61~О~Х+1 — ~~ ЬХ =О=Ф 1=1 1=1 1=1 Х вЂ” линейно зависимое множество. П Доказательство От противного. Пусть и < пь и  — базис, Тогда 3 аь,..., а„н с' хь — - аье1 + + аие„ Имеем хь Р О =ь ~/ аь „-А О.
Пусть для определенности а1 ,-А О. Тогда (свойства 2.6. Решетки ТЕОРЕМА Пусть Вк и Вз — базисы векторного пространства Тт, тогда !Вк |.=!Вз!. Могдность любого базиса векторного пространства 7 называется размерностью векторного пространства и обозначается т11ш(7). Векторное пространство, имею- щее базис, называется конечнсмерным. Пример 1. Одноэлементные подмножества образуют базис булеана, т1пп 2м = ~М~. 2. Кортежи вида (О,..., О, 1, О,..., О) образуют базис пространства 3", т(пп У" = ж 2.6.
Решетки Решетки иногда называют «структурами», но слово «структура» перегружено, и мы не будем использовать его в этом значении. Решетки сами по себе часто встречаются в разных программистских задачах, но еще важнее то,' что понятие решетки непосредственно подводит нас к понятию булевой алгебры, катаре имеет множество приложений в программировании и вычислительной технике. 2.6.1.
Определения Ртиетха — это множество М с двумя бинарными операциями и ц такими что выполнены следующие условия (аксиомы решетки): 1. идемпотентносткс а Гт а = а, 2. коммутативностгс аГ|Ь = Ьпа 3. ассоциативность: (а п Ь) п с = а и (Ь и с), 4. поглощение: (апЬ) Оа = а, 5. Решетка называется дистрибутпиеной, если аО(ЬП с) = (аш Ь) П(асс), аша=а; а гг Ь = Ь 0 а; (а 0 Ь) 0 с = а 0 (Ь О с); (а 0Ь) Г~а = а; а й (Ь О с) = (а П Ь) О (а й с). доккзатвяьство Вт — базис, и Ва — линейно независимое множество. Следовательно, ~Вт~ > ~Вз~. С другой стороны, Вз — базис, и В, — линейно независимое множество, Следовательно, ~Вз~ > (Вт(.
Имеем ~Вт~ = Щ. П Глава 2. Алгебраические струютры 2.6.2. Ограниченные решетки Если в решетке ЭО Е М Уа 0 й а = О, то 0 называется нулем (или нижней гранью) решетки. Если в решетке 31 Е М Уа 111а = 1, то 1 называется единицей (или верхней гранью) решетки. Решетка с верхней и нижней гранями называется ограниченной.
ТЕОРЕМА Егли нижняя (верхняя) грань сущеппвует, то она единственна. ДОКАЗАтаЯЬСтво Пусть 0' — еще один нуль решетки. Тогда Ой О' 0' и 0'йО,,'= О, Следовательно 0 = 0'. ТЕОРЕМА айЬ=ЬЧ=«а0Ь=а. ДОКАЗАтвлЬство = Пусть айЬ=6, Тогда а11Ь=аГ1(айЬ) = (айЬ)Г1а =а, Пусть аГ1Ь = а. Тогда айЬ = (аиЬ) йЬ= (ЬОа) йЬ= Ь. СЛЕДСТВИЕ 0 й а = 0 Е=«0 0 а = а, 1 Г1 а = 1 Е=«1 й а = а. 2.6.3. Решетка с дополнением В ограниченной решетке элемент а' называется дополнением элемента а, если айа' = 0 и аГ1а' = 1. Если Ча Е М 3 а' Е М ай а' = 0 й аг1а' = 1, то ограниченная решетка называется решеткой с дополнением, Вообще говоря, дополнение не обязано существовать и не обязано быть единственным.
ТЕОРЕМА (о свойствах дополнения) В ограниченной дистрибутивной решетке с дополнением выполняется следующее: 1. дополнение е' единственно; 2. дополнение инволютивно: ач = а; 3. грани дополняют друг друга: 1' = О, 0' = 1; 4. выполняются законы де Моргана: (а Г1 Ь) = а' й Ь', (а й Ь)' = а' 11 Ь'. Доказательство 1. Пусть х, у — дополнения а.
Тогда а й х = О, а г1 х = 1, а й у = О, а 11 у = 1. Имеем: (х = х й 1 = х й (а Г1 у) = (х й а) О (х й у) = 0 Г1(х й у) = х й у у = уй1 = уй(аГ1х) = (уйа) 0(уйх) = ОГ1(уйх) =уйх = хйу) =«х = у. 2. (аГ1а' =1 ~ а'Ба =1, айа' = 0 =«а'йа = 0) =«а =а". 2,6. Решетки 3, (1 й 0 = О, 0' й 0 = 0) =ь 1 = 0', (1 0 О = 1,101' 1) =~.0 = 1'. 4, (ай Ь) й (а'0Ь') = (ай Ь й а') 0(айЬй Ь') = (ОйЬ) 0 (ай О) = 000 = О, (айЬ) 0(а'0Ь'.) = (а0а'0Ь') й(Ь'0а'0Ь') = (106')й(10а') =1й1 = 1, г.г 2.6.4. Частичный порядок в решетке В любой решетке можно естественным образом ввести нестрогий частичный по- рядок, а именно: а ~ Ь:=айЬ= а. ТЕОРЕМА Пусть а ч Ь: =а й б = а.
Тогда .ч является отношением частичного порядка. Доказательство 1. Рефлексивность: ай а = а =ь а -ч а. 2. Антнсимметричностьс а с Ьй Ь -~ а =ь а й Ь = а ьг 6 й а = Ь =ь а = а й Ь = = Ь й а = Ь. 3. Траизитивностьс а ч Ьйб ч с ~ айЬ= аьгбйс = Ь=ь айс = (айЬ) йс = а й (Ь й с) = а й Ь = а =ь а -г с. С) Наличие частичного порядка в решетке не случайно, это ее характеристическое свойство. Более того, обычно решетку определяют, начиная с частичного порядка, следующим образом.
Пусть М вЂ” частично упорядоченное множество с частичным порядком ~. Элемент х называется нижней границей для а и 6, если х ~ ай х .ч 6, Аналогично у называется верхней границей для а и Ь, если а ч у ьг Ь ч у. Элемент х называется нижней гранью (наибольшей нижней границей) элементов а и Ь, если х — нижняя граница элементов а и б и для любой другой нижней границы о элементов а и Ь о ч х. Обозначение: х = ш((а, Ь). Аналогично, у называется верхней гранью (наименьшей верхней границей) элементов а и б, если у — верхняя граница элементов а и Ь и для любой другой верхней границы и элементов а и Ь у -г и. Обозначение; у = впр(а, Ь).
ТЕОРЕМА Если нижняя (верхняя) грань существует, то она единственна. Доказательство х = т((а,б) йу = 1п((а,б) ~ у с хйх ~ у =ь х = у. ТЕОРЕМА Если в частично упорядоченном множестве для любых двух элементов существуют нижняя и верхняя грани, то зто множество образует решетьу относительно 1пг" и зор (то есть х й у: = 1пГ(х, и), х 0 у: = вор(х, у)). 70 Глава 2.
Алгебраические структуры ДОКАЗАТЕЛЬСТВО 1. 1иЦх, х) = х ~ х й х = х, эир(х, х) = х =Ф х О х = х; 2. 1иг(х,у) = 1иГ(у,х) =Ь хйу = уйх, вир(х,у) =эир(у,х) ~ хОу = уОх; 3. 1ит(х,1иг(у,г)) = шт"(шах,у),г) =~ хй(у йг) = (хйу) йг, вор(х, эир(у, г)) = эир(эир(х, у), г) =ь х О (у О г) = (х О у) О г; 4. зир(1п1(а, Ь), а) = а ~ (а й Ь) О а = а, 1п1(эир(а, Ь), а) = а =ь (а О Ь) й а = а.
2.6.5. Булеаы алгебры 1. аОа=а, по определению решетки; 2. аОЬ = ЬОа, по определению решетки; 3. аО(ЬОс) = (аОЬ) Ос, по определению решетки; 4. (айЬ) Оа = а, по определению решетки; 5. ОО(Ьйс) = (аОЬ) й(аОС), по свойству дистрибутивности; 6. аО1 =1, по свойству ограниченности; 7. аОО = а, по следствию из теоремы ограниченности; 8. а"=а по теореме о свойствах дополнения; 9. (ай Ь)' = а'ОЬ', по теореме о свойствах дополнения; 10. аОа' = 1, так как дополнение существует. айа= а айЬюЬйа ай(Ьйс) = (айЬ) йс (аОЬ) йа = а ай (ЬОс) = (айЬ) О(ай с) ай0=0 ай1=а (ООЬ)' = а'йЬ' айа' = 0 Пример 1.
(2м;й,О, ) — булева алгебра, 1 = ГГ, 0= а, <=с. 2. (Ег,дг,тт', ) — булева алгебра, 1 1, 0 =1, -<=,". Дистрибутивная ограниченная решетка, в которой для каждого элемента суще- ствует дополнение, называется булевой алгеброй. Свойства булевой алгебры: гд. Матра аы 3. пустьк(р):=(д ~ о н 1чйд — простоейо < р) — множествопростыхчисел,не превосходящих р, множество произведений различных чисел из к(р). Тогда (Р; Н.О.Д., Н.О.К., ДОП) — булеза алгебра, где Н.О.Д.
— наибольший общий делитель, Н.О.К. — наименьшее общее кратное, ДОП( ):=- П ~. 1 че«Ю 1;= П о, О:=1, т «и:=о делится нат. чая(р) 2.?. Матроиды Матроиды, рассматриваемые в этом разделе, вообще говоря, не являются алгебраическими структурами в том смысле, который был придан этому понятию в первом разделе данной главы. Однако, во-первых, матроиды имеют много общего с рассмотренными алгебраическими структурами (в частности, с линейно независимыми множествами в векторных пространствах) и изучаются сходными метолами, а во-вторых, они являются теоретической основой для изучения и анализа «жадных» алгоритмов; Ясное понимание природы и области применимости жадных алгоритмов совершенно необходимо всякому программисту. 2.7.1.
Определения Маиуоидом М = (Е, Я) называется конечное множество Е, ~Е~ = и и семейство его подмножеств Я с 2н, такое что выполняются следующие три аксиомы: Мг.' ИЕЯ; Мз. .АебйВСА=~ВЕЯ; Мз. А В е Е й )В) = )А) + 1 =~ Л е е В ~ А А 0 (е) е Я. Элементы множества б называются независимыми, а остальные подмножества Е (2н ~ Е) — зависимыми множествами. ЗАМЕЧАНИЕ Аксиома М, исключает из рассмотрения вырожденный случай с' = В.
Пример Семейство линейно независимых множеств векторов любого векторного пространства является матроидом. Действительно, по определению можно считать, Глава 2. Алгебраические структуры 72 что пустое множество линейно независимо. Всякое подмножество линейно. независимого множества векторов линейно независимо. Пусть А: =(а,,..., а ) и В; =(Ьы..., Ье,+г) — линейно независимые множества. Если бы все векторы из множества В выражались в виде линейной комбинации векторов из множества А, то множество В было бы линейно зависимым. Стало быть, среди векторов множества В есть по крайней мере один вектор Ь, которгяй не входит в множество А и не выражается в виде линейной комбинации векторов из множества А. Добавление вектора Ъ к множеству А образует линейно независимое множество.
ЗАМЕЧАНИЕ Само понятие матронда возникло в результате исследований линейной независимости в векторных простриютзах. 2.7.2. Максимальные независимые подмножества Пусть Х с Š— произвольное множество. Максимальным независимым подмно- жеством множества Х называется множество У, такое что У сХЙУбЕЙУЯе Е ЯсХ=~ЯсУ.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
