Новиков Ф.А. Дискретная математика для программистов (860615), страница 17
Текст из файла (страница 17)
Тогда а - 1 =* ( а * Ь) = ( а - 1 * а ) * Ь = е * 6 = 6.•В любой группе выполняются следующие соотношения:1. (а * б) - 1•а"1.2. а * Ь = а * с => Ь = с.3. b * а = с * а1b — с.14. (а" )" = а.ДОКАЗАТЕЛЬСТВО[ 1 ] (а * b) * (lrl * сГ 1 ) = а * (b ** а " 1 = а * е * а""1 = а * а " 1 = е.[ 2 ] 6 = е * Ь ~ ( а ' 1 * а) к b — а~ 1 * (а * 6) = а~1 * (а * с) = (а" 1 * а ) * с = е * с — с.[ 3 ] Ь = Ь*е = 6 * ( а * о" 1 ) ~ (Ь * о) * а " 1 = (с * а) * а " 1 = с * (а * а" 1 ) = с * е — с.[ 4 ]а~1 * а = е.•В группе можно однозначно решить уравнениеа * х = b {решение: х = а - 1 * 6).ТЕОРЕМА 3ДОКАЗАТЕЛЬСТВО==i> е * ж = а-1а*х= b =Ф- а- 1* ( а * Я) = а- 1* 6(о- 1* а) * ж = а- 1* Ь = >1* 6 ==> х = а~ * Ь.•Коммутативная группа, то есть группа, в которойVa, b (a * b = b * a),называется абелевойВ абелевых группах обычно приняты следующие обозначения: групповая операция обозначается +, обратный элемент к а обозначается -а,единица группы обозначается 0 и называется нулем или нейтральным элементом.Примеры1.
(Z; +) — множество целых чисел образует абелеву группу относительно сложения. Нейтральным элементом группы является число 0. Обратным элементом_ 1 Defявляется число с противоположным знаком: х 1 = —х.2. (Q+;-) — множество положительных рациональных чисел образует абелевугруппу относительно умножения. Нейтральным элементом группы являетсячисло 1. Обратным элементом является обратное число: (га/п) - 1 =1Нильс Хеирик Абель (1802-1829).п/т.872.3. Алгебры сдвумяоперациями3.
( 2 м ; А) — булеан образует абелеву группу относительно симметрической разности. Нейтральным элементом группы является пустое множество 0 . Обрат_1пым элементом к элементу х является оп сам: хDef= х.2 . 2 . 5 . Группа п е р е с т а н о в о кВ этом подразделе рассматривается одна из важнейших групп, называемая группой перестановок, или симметрической группой.
Биективная функция / : X —• Xназывается перестановкой множества X.ЗАМЕЧАНИЕЕсли множество X конечно (|Л"| = п), то, не ограничивая общности, можно считать,что X = 1 ..71, В этом случае перестановку / : 1.лг —• 1..п удобно задавать таблицей издвух строк. В первой строке — значения аргументов, во второй — соответствующие значения функции. Такая таблица называется подстановкой. В сущности, перестановка иподстановка — синонимы.Пример/=15223 41 4Произведением перестановок fug< •1532 31 29 = 44355(обозначается f g ) называется их суперпозицияПример1fg = 52 31 44352ТЬждественная перестановка — это перестановка е, такая, что е(х) = х.Примере =1122334455Обратная перестановка — это обратная функция, которая всегда существует,поскольку перестановка является биекцией.ЗАМЕЧАНИЕТаблицу обратной подстановки можно получить, если просто поменять местами строкитаблицы исходной подстановки.Пример/ =1324324155314223145514233 41 25588Глава 2.
Алгебраические структурыТаким образом, поскольку суперпозиция функций ассоциативна, а единичный иобратный элементы существуют, множество перестановок n-элементиого множества образует группу относительно операции суперпозиции. Эта группа называется симметрической степени п и обозначается Sn.2.3. Алгебры с двумя операциямиВ этом разделе мы обращаемся к объектам, знакомым читателю со школы. Средиалгебр с двумя операциями наиболее важными являются кольца и поля, а основными примерами колец и полей являются множества целых, рациональных ивещественных чисел с операциями сложения и умножения.2.3.1. КольцаКольцо — это множество М с двумя бинарными операциями + и * (они называются сложением и умножением соответственно), в котором:1.2.3.4.(а + Ь) + С=: а + {Ь + с)30 ем (V а (а + 0 = 0 + а = а))Va (3 - а ( а + ( - а ) = 0))а + b — b +а5. а * (b * с) = (а*Ь) * с6.
a* (b + с) == (а * Ъ) + (а * с)(а + Ь) * с = (а * с) + (6 * с)сложение ассоциативно.существует нуль.существует обратный элемент.сложение коммутативно, то естькольцо — абелева группа по сложению.умножение ассоциативно, то естькольцо — полугруппа по умножению.умножение дистрибутивно относительносложения слева и справа.Кольцо называется коммутативным, если7. а*Ь = 6 * аумножение коммутативно.Кольцо называется кольцом с единицей, если8. 31 е М (а*1 = 1*а = а)существует единица, то есть кольцос единицей — моноид по умножению.ТЕОРЕМАВ кольце выполняются следующие соотношения:1. 0 * а = а * 0 = 0.2. а * (—Ь) = (—а) * Ъ = —(а * Ь).3. (—а) * (—Ь) = а*Ь.4.
(—а) = а * (—1).5. - ( а + 6) = (—а) + (—Ь).6. а ф 0( а " 1 ) - 1 = а.892.3. Алгебры с двумя операциямиДОКАЗАТЕЛЬСТВО[ 1 ] 0 * а = (0 + 0) * а = (0 * а) + (0 * а)- ( 0 * а) + (0 * а) = - ( 0 * а) + ((0 * а) ++ (0 * а)) = ( - ( 0 * а) + (0 * а)) + (0 * а)0 = 0 + (0 * а) = 0 * а.[ 2 ] (а * ( - 6 ) ) + (а * Ь) = А * ( - 6 + Ъ) = А * 0 = О,(а * Ь) + ( ( - а ) * Ь) = (а + ( - а ) ) *6 = 0*Ь = 0.[ 3 ] (-а) * (-6) = - ( а * (-6)) = - ( - ( а*Ь))=А*Ь.[ 4 ] (а * ( - 1 ) ) + а = (а * ( - 1 ) ) + (а * 1) = а * ( - 1 + 1) = а * 0 = 0.[ 5 ] (а + 6) + ( ( - а ) + ( - 6 ) ) = (а + Ь) + ((-6) + ( - а ) ) = а + (Ъ + ( - 6 ) ) + ( - а ) == а + 0 + ( - а ) = а + ( - а ) - 0.[ 6 ] а - 1 *а = 1.•Пример (Z;+,*) — коммутативное кольцо с единицей. Кроме того, V?i( ( Z n ; + , *)) — коммутативное кольцо с единицей.
В частности, машинная арифметика целых чисел (Z 2 is; +, *) — коммутативное кольцо с единицей.2.3.2. Области целостностиЕсли в кольце для некоторых ненулевых элементов х, у выполняется равенствох * у = 0, то х называется левым, а у — правым делителем нуля.ПримерВ машинной арифметике (Z2ie; +, *) имеем 256*128 = 2 8 *2 7 = 21Г) = 0.Заметим, что если в кольце нет делителей нуля, то Vz Ф 0,у Ф 0 ( х * у фО).В группе V а, 6, с ((а * Ь = а * с => b = с) & ( б * а = с * аЬ = с)), однако в произвольном кольце это не так.Пример В машинной арифметике (Z 2 is; +, *) имеем 2 8 * 2 7 = 0 и 0 * 2 7 = 0, но0 ф 2 8 = 256.ТЕОРЕМАVa ф 0,6, с ((а* 6 = a * сb = с) &(ft*a = c * a =4> b = с)) «$=•ДОКАЗАТЕЛЬСТВО[] От противного.
Пусть За; ^/ 0 (ж * у = 0). Тогда= 0 & ж * 0 = 0 = * г / = 0.[] 0 = (а*Ь) + (—(а*Ь)) = (а*Ь)+(-(а*с)) = {а*Ь) +(а*(-с))а* (b+ (—с)) = 0 &: а Ф 0 = > b + (—с) = 0b = с.== а*(Ь+(-с)),•Коммутативное кольцо с единицей, не имеющее делителей нуля, называетсяобластью целостности.Пример Целые числа (Z; +, *) являются областью целостности, а машиннаяарифметика (Z 2 is;+,*) — не является.90Глава 2. Алгебраические структуры2.3.3. ПоляПоле — это множество М с двумя бинарными операциями + и *, такими, что:1.2.3.4.5.6.7.8.(а + Ь) + с = а + (Ь + с)сложение ассоциативно.30 е М (а + 0 = 0 + а = а) существует нуль.Va (3 - а (а 4- - а = 0))существует обратный элемент по сложению.а+ b= Ь+асложение коммутативно, то есть поле — абелевагруппа по сложению.а* (Ь* с) = (а*Ь) * сумножение ассоциативно.31 е М ( a * l = l * a = a) существует единица.Va ф 0 ( З а - 1 ( а - 1 * а = 1)) существует обратный элемент по умножению.a *6 = 6*аумножение коммутативно, то есть ненулевые элементы образуют абелеву группу по умножению.9.
а * (6 + с) = (a * Ь) + (а * с)умножение дистрибутивноотносительно сложения.Таким образом, поле — это коммутативное кольцо с единицей, в котором каждыйэлемент, кроме нейтрального элемента по сложению, имеет обратный элемент поумножению.Примеры1. (IR; +, *) — поле вещественных чисел.2.
(Q; +, *) — поле рациональных чисел.Def3. Пусть Е2 = {0,1}. Определим операции +, •: Е2 х Е2 -+ Е2 следующим образом: 0 0 = 0 1 = 1 0 = 0, 1 1 = 1 (конъюнкция), 0 + 0 = 1 + 1 = 0,Def0 + 1 = 1 + 0 = 1 (сложение по модулю 2). Тогда Ъ2 = (Е2-,+,-) являетсяполем и называется двоичной арифметикой. В двоичной арифметике нуль —это 0, единица — это 1, - 1 = 1 _ 1 = 1 , а 0 - 1 — как всегда, не определён.4. Если в условиях предыдущего примера взять в качестве сложения дизъюнкцию, то есть определить операции следующим образом: 0 0 = 0 1 = 1 0 = 0,1 - 1 = 1 (конъюнкция), 0 + 0 = 0, 0 + 1 = 1 + 0 = 1 + 1 = 1 (дизъюнкция), тоструктура (Е2] V, •) не является полем, поскольку у элемента 1 нет обратногопо сложению.ТЕОРЕМА 1Поле является областью целостности: а * b =а*Ь = 0&саф0= а ~ * 0 = 0, а*Ь = 0кЬф0=>а= б - 1 * (а * 6) = б - 1 * 0 = 0.ДОКАЗАТЕЛЬСТВО10=> а =0 VЪ=0.==> 6 = 1 * 6 = ( a - 1 * а) * b = а - 1 * (а * Ь) == 1 * а = (Ь - 1 * b) * а = Ъ~1 * (Ь * а) =•912.4.
Векторные пространства и модулиТЕОРЕМА 2Если а Ф 0, то в поле единственным образом разрешимоа * х + b = 0 (решение: х = - (а~1) * 6).ДОКАЗАТЕЛЬСТВОа*х+Ь = 0 = > а*х+6+(-6)= 0 + (-6)уравнениеА * х 4- (b + ( - 6 ) )== —Ъ => а*х+О = —6 = > а*ж — —Ь = > а - 1 * ( а * х ) = а - 1 *(—6) =>• ( а - 1 * а) * х == — ( а - 1 * 6) =>• 1 * х = — ( а - 1 * Ь) ==*• х = — ( а - 1 * Ь).•2.4.
Векторные пространства и модулиПонятие векторного пространства должно быть известно читателю из курса средней школы и других математических курсов. Обычно это понятие ассоциируетсяс геометрической интерпретацией векторов в пространствах К 2 и К 3 . В этомразделе даны и другие примеры векторных пространств, которые используются в последующих главах для решения задач, весьма далеких от геометрическойинтерпретации.2.4.1. Векторное пространствоПусть 7 = (F; +, •) — поле с операцией сложения +, операцией умножения •,аддитивным нейтральным элементом (нулем) 0 и мультипликативным(единицей) 1. Пусть V = (V; +) — абелева группа с операцией + и нейтральнымэлементом 0.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
