Дискретная математика (Хороший учебник по дискретной математике), страница 11

(аоЬ) "= Ь 'оа г; 2. аоЬ=аос=ьЬ=с; 3. Ьоа=соа~Ь=с; 4. (а ') = а. Глава 2. Алгебраические структуры доклзлт аль от в о 1 (аоЬ)о(Ь 1аа 1)=ао(ЬоЬ 1)оа г=аоео 2, аоЬ= асс=»а 'о(аоЬ) =а 1о(асс) =» =» еоЬ= ео с=» Ь = с. 3. Ьоа = со а =» (Ьоа) оа 1 = (сои) о а 1 =» =» Ьое = сое =» Ь= с.

а 1=оса ~=е. (а 1 о а) оЬ = (а 1 о а) ос =» Ьо (а о а 1) — — со'(а о а 1) =Ф 4. (а 1) о а = а 1 о а = е. ТЕОРЕМА В группе можно однозначно решить уравнение а о х = Ь, (решение: х = а 1 о Ь). доклалтальство аох = Ь =~ а 1 о(а ох) = а 1 оЬ =» (а 1 оа) ох = а 1оЬ ~ еох — а 1оЬ =» =» х = а ' о Ь. Коммупиипиеная группа, то есть группа, в которой аеЬ=Ьоа, называется абелееой'. В абелевых группах приняты следующие обозначения: групповая операция обозначается + или й, обратный элемент к а обозначает- ся — а, единица группы обозначается О н называется нулем. Пример 2.4. Алгебры о двумя операциями В этом разделе рассматриваются алгебры с двумя бинарными операциями: св, З: М х М -+ М, которые условно называются «сложением» и «умиоженнем», соответственно.

Нильс Хенрик Абель 11802-1929) 1. (е.;+) — множество целых чисел образует абелеву группу относительно сложения. Нулем группы является число О. Обратным элементом является число с противоположным знаком: х ': = — х. 2. (че+, ) — множество положительных рациональных чисел образует абелеву группу относительно умножения. Нулем группы является число 1. Обратным элементом является обратное число: (пь/и) ': = и/гп.

3. (2м; гз) — булеан образует абелеву группу относительно симметрической разности. Нулем группы является пустое множество й1. Обратным элементом является дополнение: Х ':=М'1Х. 2.4. Алгебры о двумя операциями 2.4.1. КОЛ1еЦм Кольцо — это множество М с двумя бинарными операциями ев и Э, в котором; 1. (а евЬ) 9 с = а®(ЬЩс) сложение ассоциативно; 2.

30 Е М Уа а Е 0 = 0 щ а = а существует нуль; 3. Ча3 — аале — а=О существует обратный элемент; 4.атЬ=ЬЩа сложение коммутативно, то есть кольцо — абелева группа по сложению; 5. аЗ(ЬЗс) = (аЭЬ) Эс умножение ассоциативно, то есть кольцо — полугруппа по умножению; 6. а Э (Ь Ю с) = (а З Ь) Ю (а З с) умножение дистрибутивно (а®Ь)Эс=(аЭс)Ю(ЬЭс) слева неправа. Кольцо называется коммутативным, если 7.аЗЬ=ЬЗа умножение коммутативно.

Коммутативное кольцо называется кольцом с единицей, если 8. 31 Е М а Э 1 = 1 Э а = а существует единица; то есть кольцо с единицей — моноид по умножению. ТЕОРЕМА В кольце выполняются следующие соотношвнияг 1.0За=аЗО=О; 2. а З ( — Ь) = ( — а) З Ь = -(а З 6); 3. ( — а) Э(-Ь) = аЭЬ. Доказательство 1. 0 З а = (О Ю 0) З а = (О З а) 9 (О З а) =ь =ь — (ОЭа)9(ОЭа) = -(ОЗа)Ю((ОЭа)9(ОЭа)) = ( — (ОЗа)Ю(ОЗа))Ю(ОЗа) =ь =ь 0 = 0®(ОЗа) = ОЭа. 2.

(а З ( — Ь) ) Ю (а З Ь) = а З (-Ь ц~ Ь) = а З 0 = 0 =ь =~ а ® ( — Ь) = — (а З Ь), (а Э Ь) Щ (( — а) Э Ь) = (а Ю ( — а)) З Ь = 0 Э Ь = 0 =ь ь (-а) ЗЬ= -(аЗЬ). 3. ( — а) З ( — Ь) = — (а З ( — Ь)) = — (-(а Э Ь)) = а Э Ь. П Пример (Е; +,*) — коммутативное кольцо с единицей. Для любого натурального п (Е„; +,*) — коммутативное кольцо с единицей.

В частности, машинная арифметика целых чисел (Ею;+, е) — коммутативное кольцо с единицей. Глава 2. Алгебраические структуры Б2 2.4.2. Области целостности Пример В машинной арифметике (Еа .;+, *) имеем 256 *128 = О. В группе а сЬ = а с с =ь Ь = с, однако в произвольном кольце это не так. ТЕОРЕМА Пусть а ф О.

Тогда (а Э Ь = а Э с =ь Ь = с) ) Ь 1 е=ь ( Ф О 8с у уь О =ь * Э у Ф О). (ЬЭа ='сЭа=ь Ь= с))) ДОКАЗАТЕЛЬСТВО =ь: От противного. Пусть х®р = О. Тогда х Та О й хЭ у = 0 й х®0 = 0 =~ у = О, у ук Ойх Э у = ОйОЭ у = 0 =ь х = О. ~: 0 = (аЭЬ)9( — (а®Ь)) = (аЭЬ)9(-(аЭС)) = (а®Ь)9(аЭ(-с)) = аЭ(Ь9(-с)), а Э (Ь 9 (-с)) = 0 й а ТВ 0 =Ь Ь 9 (-с) = 0 =Ь Ь = с. О Коммутативное кольцо с единицей, не имеющее делителей нуля, называется эблостью целостности.

Пример Целые числа (Е;+, *) являются областью целостности, а машинная арифметика (Еа ', +, *) — не является. 2.4.3. Поля Уоле — это множество М с двумя бинарными операциями 9 и Э, такими что: !. (а 9 Ь) 9 с = а 9 (Ь 9 с) 2. ЭОЕМО90=09а= 3. 'т'а 3 — а а 9 — а = 0 !.а9Ь=Ь9а то есть поле — абелева 3. аЭ(ЬЭс) = (аЭЬ) ®с й В1ЕМОЭ1=1Эа= Г. 'т'а ф 0 В а ' а ' Э а = 3.аЭЬ=ЬЭа то есть поле — абелева сложение ассоциативно; а существует нуль; существует обратный элемент по сложению; сложение коммутативно, группа по сложению; умножение ассоциативно; а существует единица; 1 существует обратный элемент по умножению; умножение коммутативно, группа по умножению; Если в кольце Вх у~ 0 Ву ф 0 х Э у = О, то х называется левым, а у — правым делителем нуля.

63 65. Векторные пространства 9. аЭ(ЬЮс) =(аЭЬ) Ю(аЗС) умножение дистрибутивно относительно сложения. Пример 1. (Ж;+, ) — поле вещественных чисел. 2. (©+,.) — поле рациональных чисел. 3, Пусть Ез . =(О, 1). Определим операции ®, ' Ез х Ез -~ Ез следующим образом: 0 0=0,0 1 =0, 1 ° 0 = 0, 1 ° 1 =1, ОЮО = О, Оет1 = 1, 1тиО = 1, 1а1 = О. Тогда Ез . = (Ез, е, ) является полем и называется двоичной арифметикой. ТЕОРЕМА В лапе вьтолняютсл следующие соотношения. 1. ( — а) = а®(-1); 2. — (аетЬ) = (-а) ®( — Ь); 3. а ТЬ 0 ~ (а т) = а; 4. а®6=0 =~а = Отт'6=0. ДОКАЗАТЕЛЬСТВО 1. (аЗ( — 1)) ета = (аЗ( — 1)) Ю(аЗ1) = аЗ( — 1ПВ1) = аЭО = О. 2 (ай 6) то (( — а) Ю ( — Ь)) = (а те 6) ет (( — Ь) йв ( — а)) = а® (65п (-6)) ап ( — а) = = а йр О Ю (-а) = а 9 ( — а) = О.

3. а т За=1. 4.аЗЬ=ОйафО=« =«Ь = 1ЭЬ = (а 'Эа) ®Ь= а т Э(аЭЬ) = а ' ЗО= О а Э Ь = О й Ь пь 0 =« =«а=1Эа=(Ь т ЭЬ)®а = Ь '®(ЬЭа) =Ь т ®(аЗЬ) =Ь 'ЭО=О. (з ТЕОРЕМА Если а ть О, то в иоле единственным образам разрешимо уравнение аЗхтвЬ=О, (х=-(а т)Э6). Доказательство а З х те Ь = 0 =«а З х ап Ь тР ( — Ь) = 0 Ю (-Ь)а Э х 9 (6 йт ( — Ь)) = -Ь =« =«а Э х + 0 = — Ь =«а ® х = -Ь =«а т З (а З х) = а т Э (-Ь) =« =«(а ~За) Зх= — (а 'ЭЬ) =«1Эх= — (а ' ЭЬ) =~х= — (а 'ЗЬ). Сз 2.5.

Векторные пространства Понятие векторного пространства должно быть известно читателю из курса средней школы и других математических курсов. Обычно зто понятие ассоциируется Глава Гс Алгебраические структуры : геометрической интерпретацией векторов в пространствах Кз и Кз. В этом раз1еле даны и другие примеры векторных пространств, которые используются в юследующих главах для решения задач, весьма далеких от геометрической ин~ерпретации.

с.5.1. Определения пусть Г = (Г;+, ) — некоторое поле с операцией сложения +, операцией умно- кения, аддившеной единицей О и мультинликатиеной единицей 1. Пусть 7 = ,'У„+) — некоторая абелева группа с операцией + и единицей О. Если существу.т операция г х У -+ У (знак этой операции опуркаегся), такая что для любых И Ь Е Г и для любых х, у Е У выполняются соотнршения: Е (а+ Ь)х = ах+Ьх, 1. а(х + у) = ах + ау, 3.

(а Ь)х = а(Ьх), Е 1х=х, ю 7 называется векторным пространством над полем У, элементы г' иазываотся скалярами, элементы У называются ееюнорами, а необозначенная операция Р х У вЂ” ь У называется умножением вектора на скаляр. 1ример ~. Пусть т = (г';+, ) — некоторое поле. Рассмотрим множество кортежей г'". Тогда У" = (Р";+), где (ам...,а )+(Ьм...,6„):=(аг+Ью...,а +Ь„), является абелевой группой, если -(аг,..., а„): =(-аы..., — а„) и О: =(О,..., О).

Положим а(ам..., а„): =(а аы..., а а„). Тогда 5 является векторным пространством над г для любого (конечного) и. В частности, К" является векторным пространством для любого и. Векторное пространство Кз (и Кз) имеет естественную геометрическую интерпретацию (рис.

2.1). !. Двоичная арифметика Яз = (Ез,®, ) является полем, а булеан (2м;Ь) 'с симметрической разностью является абелевой группой. Положим 1Х:=Х, ОХ: = И. Тогда булеан с симметрической разностью является векторным пространством над двоичной арифметикой. 2.5.2. Свойства нуль-вектора '.диница группы 7 (если 7 — векторное пространство) называется нуль-еекл)ором ~ обозначается О. ЕОРЕМА УхЕУОх=О, чаЕРаО=О. 65 ?.5, Векторныв пространства ( † Рис. 2.1. Опврации над векторами в Нт ДОКАЗАТВПЬСТВО 1.

Ох = (1 — 1)х = 1х — 1х = х — х = О. 2. аО = а(0 — 0) = аΠ— аО = (а — а)0 = 00 = О. 2.5.3. Линейные комбинации Если 7 — векторное пространство над полем У, Я вЂ” некоторое множество векторов, Я С 'к', то сумма вида и а,х,, а, В Г, х; В Я 1=1 называется линейной комбинацией векторов из Я. Пусть Х = (хт,..., хь1 — конечное множество векторов. Если ь а х; = 0 =ь а1 = аз = ' ° = аь = О, к=1 то множество Х называется линейно независимым. В противном случае, то есть если 3 аы..., аь В е' ~/ а; ф 0 й ~ ~а;х; = О, к=1 а=1 то множество Х называется линейно зависимым. Глава 2. Алгебраические структуры ТЕОРЕМА Линейно независимое множество векторов не содержит нуль-вектора. ДОКАЗАТЕЛЬСТВО Пусть с = (О~ха,хь),хл .

'=О. Положим аь:1, аа. =О, и Тогда 2 аьхь = 1О+ Охз+" + Охь = О+ О+ + О = О, аь, =О. 2.5.4. Базис и размерность Подмножество векторов Я Е и, такое что любой элемент к' может быть представлен в виде линейной комбинации элементов Я, нанывается порождаьощим множеством пространства 7. Конечное линейно независимое порождающее множество называется базисом векторного пространства. Пусть векторное пространство 7 имеет базис В = (еь,..., еи). ТЕОРЕМА Каждый элемент векторного просьпранства имеет единственное представление в данном базисе. Доказательство и Пусть х = ~ аье; их= ~',беь 1=1 и и и ,'С, 'а,е; — 2 Ььеь = ~ (а; — 61)е; =ь 1=1 1=1 О =:-ь 'ььь аь = Ьр ТогдаО=х — х= Ч 11 Е 1 и аь — Ьь .