Новиков Ф.А. Дискретная математика для программистов (860615), страница 18
Текст из файла (страница 18)
Если существует операция F х V —> V (знак этой операции опускается), такая, что для любых a,b е F и для любых х , у е У выполняютсясоотношения:1) (а + 6)х = ах + 6х,2) а(х + у) = ах + ау,3) (а • Ь)х = а(Ьх),4) 1х = х,то V называется векторным пространством над полем З7, элементы F называются скалярами, элементы V называются векторами, нейтральный элемент группы V называется нуль-вектором и обозначается 0, а пеобозначеппая операцияF х V —> V называется умножением вектора на скаляр.Примеры1. Пусть J = ( F ; + , •) — некоторое поле. Рассмотрим множество кортежей FN.Тогда У1 = (Fn\ +), гдеDef( a i , . . . , a n ) + (&i,..., bn) = (ai + 6 Ь ... , a n + bn)является абелевой группой, в которой-(ab...,an) =f(-ab...,-an)и0 = f ( 0 , .
. . , 0).92Глава 2. Алгебраические структурыПоложима(а 1 , . . . , а п ) = f (а • а ь . . . , а • а„).Тогда "Зп является векторным пространством над 7 для любого (конечного) п.В частности, Мп является векторным пространством для любого п. Векторноепространство М2 (и R 3 ) имеет естественную геометрическую интерпретацию(рис. 2.1).2. Двоичная арифметика Z2 = (£2;+2,-) является полем, а булеан ( 2 м ; д ) ссимметрической разностью является абелевой группой.
Положим IX=f X,OX = f 0 . Таким образом, булеан с симметрической разностью является векторным пространством над двоичной арифметикой.3. Пусть X = { : r i , . . . , хп} — произвольное конечное множество, а 7 = (F; +, •) —поле. Рассмотрим множество Vx всех формальных сумм видахехгде Хх е F.Положим£+£КххЕХх£Хa ^[ixX^хХ=fJ2 fix + Их)х,=J2 (а • \х)х,ХЕХхЕХгде а,\х,[1ххЕХе F.Ясно, что Vx является векторным пространством, а X является его множеством образующих или базисом (см. 2.4.3). В таком случае говорят, что Vx —это векторное пространство, «натянутое» на множество X.4.
В условиях предыдущего примера ( X = { x i , . . . , х п ) — произвольное конечноемножество, а = (F; +, •) — поле) рассмотрим множество Ф : = { / | / : X —> F}.Положим( / + flO(z) = f / ( s ) + 0(z)>(af)(x)f= а • f{x),гдегдеaeFJef,geФ,Ф.Нетрудно видеть, что Ф является векторным пространством.ТЕОРЕМА1. V x е V(Ох =0).2. Va е F (аО = 0).ДОКАЗАТЕЛЬСТВО[ 1 ] Ох = (1 - 1)х = 1х - 1х = х - х = 0.[ 2 ] аО = а(0 - 0) = аО - аО = (а - а)0 = 00 = 0.•932.4. Векторные пространства и модулиJLУ(*1+*2. г/1+1/2)(*2. 2/2)/// /(x2-xv г/2-г/i)^^,У/WX~Г\ ^ ^ /^ ^ 1_ /^J(-V2, -уг/2)Рис.
2.1. Операции над векторами в М22.4.2. Линейные комбинацииЕсли V — векторное пространство над полем 7, S — некоторое множество векторов, S с V, то конечная сумма видап^aiXi,a» G F,х* G S,i—1называется линейной комбинацией векторов из S. Пусть X = {xi,...,xfc} —конечное множество векторов. Еслик^агХг = 0У г G l . . k (ai = 0 ) ,г=1то множество X называется линейно независимым. В противном случае, то естьесли( кк\ j ai ф 0 &г=1г=1множество X называется линейно зависимым.ТЕОРЕМА\= 0)'/Линейно независимое множество векторов не содержит нуль-вектора.О Т противного.
Пусть линейно независимое множество S == { x i , x 2 , . . . ,Xfc} содержит нуль-вектор и пусть для определённости xi = 0.ДОКАЗАТЕЛЬСТВО94Глава 2. Алгебраические структурыПоложим a i : = 1, а 2 : = 0 , . . . , ак : = 0. Имеем 53 а г х г = 10 + 0х 2 + • • • + Ох/с =г= 1= 0 + 0 + . ..
+ 0 = 0, что противоречит линейной независимости S.•2.4.3. Базис и размерностьПодмножество векторов S е V, такое, что любой элемент V может быть представлен в виде линейной комбинаций элементов S, называется порождающиммножеством пространства V или множеством образующих.
Линейно независимоепорождающее множество называется базисом векторного пространства.1Пусть векторное пространство V имеет базис В = { E I , . . . , E N } .Тогда каждый элемент векторного пространства имеет единственное представление в данном базисе.ТЕОРЕМАДОКАЗАТЕЛЬСТВО11~г=1Т1=г=1пПусть х = 53t=l(«г _п0 = х - х = 53<=1«и х = 53 bТогдаг=1= > V« G 1..ГО (rtj -= 0 =>• V'/ («* =~•Коэффициенты разложения вектора в данном базисе называются его координатами.2Пусть В = { E I , . . . , Е П } — базис, а X = { X I , .
. . , Х Ш } — линейнонезависимое множество векторного пространства V. Тогда n ^ га.ТЕОРЕМАДОКАЗАТЕЛЬСТВООТпротивного. Пусть п < т и В — базис. Тогда3oi,...,Оп 6 F (xi = oiei + ... +anen).ПИмеем xi ф 0 ==> \J <цф 0. Пусть для определённости ai Ф 0. Тогдаi=lei = a,i l xi - (af 1 аа)е 3 - (af l a n ) e n .Так как В порождает V, то и {xi,©a,... ,©п} тоже порождает V. Диалогично{хьха,©з,... , е п } порождает V.
Продолжая процесс, получаем, что { x i , . . . , х п }порождает V. Следовательно,пХп+1 -пbiXi ^ ф x n + i -biXi = 0.<•1Таким образом, X — линейно зависимое множество, что противоречит условию.•952.4. Векторные пространства и модулиЕсли в векторном пространстве V множество векторов X == {xi,..., хп} — линейно независимо и векторы множества Y = {yi,..., уто} выражаются в виде линейных комбинаций векторов множества X, другими словами,СЛЕДСТВИЕУг е l..m ^Уг =aij*ij>причёмт> п,томножество Y —линейнозависимое.Рассмотрим подпространство VA векторного пространства V,порождаемое векторами множества А.
В подпространстве VA множество А — базис, а векторы множества Y — элементы. Далее от противного. Пусть множествоY линейно независимое, тогда по теореме п ^ га, что противоречит условию.•ДОКАЗАТЕЛЬСТВОТЕОРЕМА 3Если В\ и В2 — базисы векторного пространства V, то \В\| = |В2|.B I — базис и В2 — линейно независимое множество.
Следовательно, |Bi| > |В 2 |. С другой стороны, В 2 — базис, и В\ — линейно независимоемножество. Следовательно, |В 2 | ^ |Bi|. Имеем |Bi| = |В 2 |.•ДОКАЗАТЕЛЬСТВОЕсли векторное пространство V имеет базис В, то количество элементов в базисеназывается размерностью векторного пространства и обозначается dimV. Векторное пространство, имеющее конечный базис, называется конечномерным. Векторное пространство, не имеющее базиса (в смысле приведенного определения),называется бесконечномерным.Примеры1.
Одноэлементные подмножества образуют базис булеана, d i m I м = \М\.2. Кортежи вида ( 0 , . . . , 1 , 0 , . . . , 0) образуют базис пространстваdim Т1 = п.ЗАМЕЧАНИЕЕсли определить базис как максимальное линейно независимое множество (то есть множество, которое нельзя расширить, не нарушив свойства линейной независимости), топонятие базиса можно распространить и im бесконечномерные пространств!!.2.4.4. МодулиПонятие модуля во многом аналогично понятию векторного пространства, с тойлишь разницей, что векторы умножаются не на элементы из поля, а па элементыиз произвольного кольца. Пусть $ = (/?;+,#) = некоторое кольцо с операцией сложения +, операцией умножения *, нулевым элементом 0 и единичнымэлементом 1, Абелева группа М = (М;+) называется модулам над кольцомЯ если задана операция умножения на скаляр Я х М => М (здесь никак пеобозначаемая), такая что:96Глава 2. Алгебраические структуры1) (а + Ь)х = ах + 6х;2) а(х + у) = ах + ау;3) (а * 6)х = а(Ьх);4) 1х = х,где а, b е Я, а х, у £ М.
Как и в случае векторных пространств, элементы кольцаЛ называются скалярами, а элементы группы М — векторами.Примеры1. Векторное пространство V над полем J является модулем над J , так как поле,по определению, является кольцом.2. Множество векторов с целочисленными координатами в Мп является модулемнад кольцом Z.3. Любая абелева группа есть модуль над кольцом Z, если операцию умноженияна скаляр п е 1>,п > 0 определить следующим образом:Defnv=IV + V + •• •+ V .v'п раз2.5.
РешёткиРешётки иногда называют «структурами», но слово «структура» перегружено, имы не будем использовать его в этом значении. Решётки сами по себе часто встречаются в разных программистских задачах, но еще важнее то, что понятие решётки непосредственно подводит нас к понятию булевой алгебры, значение которойдля основ современной двоичной компьютерной техники трудно переоценить.2.5.1. ОпределенияРешётка — это множество М с двумя бинарными операциями П и и , такими, чтовыполнены следующие условия (аксиомы решётки):1. Идемпотентность:а Па = а, а U а =Й.2.
Коммутативность:аГ)Ь = b(la, aU b — bU а.3. Ассоциативность:(аПЬ)Пс = аП(6Пс),4. Поглощение:(а П b) U а = а,(а U Ь) U с = а U (6 U с).(а U Ь) П а = а.5. Решётка называется дистрибутивной, еслиa U (Ь П с) = (a U Ь) П (а U с), а П (b U с) = (а П b) U (а П с).972.5. Решётки2.5.2. Ограниченные решёткиЕсли в решётке 3 0 е М (Va (0 Da = 0)), то 0 называется нулем (или нижнейгранью) решётки. Если в решётке 3 1 е М (Va ( l U a = l ) ) , то 1 называетсяединицей (или верхней гранью) решётки.
Решётка с верхней и нижней граняминазывается ограниченной.ТЕОРЕМА 1ЕслиДОКАЗАТЕЛЬСТВОТЕОРЕМА 2(верхняя) грань существует, то она единственна.Пусть 0' —ещё один пуль решётки. Тогда 0' = 0П0'= 0'П0 = 0.а П b = Ъ <^=> a U b =•а.ДОКАЗАТЕЛЬСТВО[ = > ] a U 6 = a U (а П 6) = (а П Ь) U а = а.[ <*= ] а П b = (a U Ь) Г\ b = (b U а) П b = Ь.СЛЕДСТВИЕ0 U а =1Па =•а.2.5.3.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
