рефераты конспекты курсовые дипломные лекции шпоры

Реферат Курсовая Конспект

ЛЕКЦИИ И ДОМАШНИИ ЗАДАНИЯ ПО КУРСУ ТОКБДИСКРЕТНАЯ МАТЕМАТИКА ВВЕДЕНИЕ В ДИСКРЕТНУЮ АЛГЕБРУ

ЛЕКЦИИ И ДОМАШНИИ ЗАДАНИЯ ПО КУРСУ ТОКБДИСКРЕТНАЯ МАТЕМАТИКА ВВЕДЕНИЕ В ДИСКРЕТНУЮ АЛГЕБРУ - Домашнее Задание, раздел Домостроительство, Глава 1 Лекции И Д...

ГЛАВА 1

ЛЕКЦИИ И ДОМАШНИИ ЗАДАНИЯ ПО КУРСУ «ТОКБДИСКРЕТНАЯ МАТЕМАТИКА»

ДЛЯ СТУДЕНТОВ ДНЕВНОГО ОТДЕЛЕНИЯ СПЕЦИАЛЬНОСТИ 2202 (КИРИШКИЙ ФИЛИАЛ ГУАП)

ВВЕДЕНИЕ В ДИСКРЕТНУЮ АЛГЕБРУ

ГРУППЫ

Группа — это собирательное название некоторых алгебраиче­ских структур. Хотя существуют многие конкретные примеры интересных групп, в математике введено абстрактное понятие группы, так как легче одновременно исследовать все математические системы с общей структурой, чем исследовать каждую из них по отдельности.

Определение 1.1.1.Группой Q называется множество элемен­тов с определенной для каждой пары элементов операцией (обо­значаемой *), обладающее следующими четырьмя свойствами:

1) замкнутость: для каждой пары а и b множества эле­мент с = а*bпринадлежит множеству;

2) ассоциативность: для всех а, b и с из множества

а * (b* с) = (а*b) * с;

3) существование единицы: в множестве существует элемент е, называемый единичным элементом и такой, что

а* е = е* а = а

для любого элемента а множества;

4) существование обратных элементов: для любого а из мно­жества существует некоторый элемент b из множества, называе­мый обратным элементу а и такой, что

а* b= b а = е.

Если группа Q содержит конечное число элементов, то она называется конечной группой, а число элементов в Q называется порядком Q.

Некоторые группы обладают тем дополнительным свойством, что для любых а и bиз группы

а* b=b * а.

Это свойство называется коммутативностью. Группы, облада­ющие этим дополнительным свойством, называются коммутатив­ными или абелевыми группами. За исключением некоторого мате­риала этого параграфа, мы всегда будем иметь дело с абелевыми группами.

В случае абелевых групп групповая операция обозначается символом + и называется сложением (даже тогда, когда она не является обычным арифметическим сложением). В этом случае единичный элемент называется нулем и обозначается 0, а обрат­ный элементу а элемент записывается в виде —а, так что

а + (—а) = (—а) + а = 0.

Иногда групповая операция обозначается символом • и назы­вается умножением (даже тогда, когда она не является обычным арифметическим умножением). В этом случае единичный элемент называется единицей и обозначается 1, а обратный элементу а элемент записывается в виде а-1, так что


 

а-а-1 = а-1-а = 1.

 

 

Теорема 1.1.2.Единичный элемент в каждой группе, является единственным. Для каждого элемента группы обратный элемент также является единственным, и -1)-1 = а.

Доказательство.Предположим, что е и е' — единичные эле­менты группы; тогда е = е*е' = е'. Далее, предположим, что b и b' — элементы, обратные элементу а; тогда

b =b*(а*b') = (b*а)*b' = b'.

Наконец, а-1а = аа-1 = 1, так что а—обратный элементу а-1. Но в силу единственности обратного элемента (а-1)-1 = а.

Имеется бесконечно много примеров групп. Многие группы содержат бесконечное число элементов. Примерами являются целые числа относительно сложения, положительные рацио­нальные числа относительно умножения 1), множество вещественно -нозначных (2 X 2)-матриц относительно сложения. Многие дру­гие группы содержат только конечное число элементов. Приме­рами являются двухэлементное множество {О, 1} относительно операции «исключительного или» (сложения по модулю 2), мно­жество {О, 1, ..., 8, 9| относительно сложения по модулю 10 и т. д. В качестве более сложного примера построим конечную ^не -абелевую группу, т. е. менее известную структуру. Одним из способов построения групп с интересной алгебраической струк­турой является исследование преобразований простых геометри­ческих фигур и алгебраическая интерпретация этих преобразо­ваний. Например, равносторонний треугольник с вершинами А, б и С (занумерованными по часовой стрелке) можно вращением или отражением относительно оси отобразить на себя точно шестью различными способами, причем каждое из этих враще­ний и отражений имеет обратное преобразование. Используя некоторые очевидные факты, можно быстро построить алгебраи­ческую группу. Обозначим эти шесть преобразований символами 1, а, Ьb, с, dа и е следующим образом:

1 = (АВС=-+АВС) (нет изменений),

,

 

а = (АВС-Ъ = (АВС с = (АВС-
ВСА) АС В)
а = (АВС-+ СВ А)

a=(ABC=С_АВ) {вращение против часовой стрелки),

 

b=(ABC=BCA) (вращение по часовой стрелке),

 

c=(ABC=ACB) (отражение относительно биссек­трисы угла' A Л)

 

 

d=(ABC=CBA) (отражение относительно биссек­трисы угла В),

 

е = (АВС=•<-> ВАС) ] '(отражение относительно биссек­трисы угла С),

*) Этот пример дает удобный повод предостеречь относительно терминологии. В случае произвольной абелевой группы групповая операция обычно называется сложением, но не обязательно является обычным сложением. В данном примере она является обычным умножением.

2 Р. Блейхут

 

где преобразование АВС=ВСА означает, что вершина А переходит в вершину В, вершина В переходит в вершину С, а вершина С переходит в вершину А. Таким образом, треугольник поворачивается на 120°. Пусть группа (G, *) определяется мно­жеством ­
G = {1, а, Ь, с, d, е}

и y*х является элементом группы, обозначающим преобразо­вание, которое получается последовательным выполнением сна­чала преобразования х, а затем преобразования у; например,

а * d = (АВС = ВС А) * (ABС=СВА) = (АВС=ВАС) = е. Поступая таким образом, можно построить таблицу для х*у:

y x 1 a b c d e
1 a b c d e
а a b 1 a e c
b b 1 a e c d
с c e a 1 b a
d d c e d 1 b
е e d c b a 1

 

Поскольку таблица построена, можно забыть о ее геометри­ческом происхождении. Таблица сама определяет группу. Под­черкнем, что это пример не абелевой группы, так как а*с = с* а. Заметим также, что каждый элемент появляется один раз в каж­дом столбце и в каждой строке. Для конечных групп это выпол­няется всегда.

Нашим последним примером группы является группа пере­становок n букв. Пусть X представляет собой множество {1, 2, ..., п}. Взаимно-однозначное отображение этого множества на самого себя называется перестановкой. Всего имеется п! таких перестановок, и можно определить группу, называемую симме­трической группой и обозначаемую через Sn, элементами которой являются перестановки на множестве X. (Сначала может не­сколько смущать то обстоятельство, что элементами группы яв­ляются операторы — операторы перестановок на множестве X. На самом деле в примере преобразований равностороннего тре­угольника речь также идет о группе перестановок.) Если взять перестановку на выбранных целых числах и переставить их еще раз, то получится другая перестановка на этих целых числах. Выберем в качестве групповой операции * такую композицию перестановок и возьмем, например, п = 4. Всего имеется 4! = 24 перестановок в группе S4. Типичный элемент группы S4 равен

a = [(1 2 3 4) = (3 1 4 2) ]

и является перестановкой, заменяющей 1 на 3, 2 на 1, 3 на 4 и 4 на 2. Другой такой перестановкой является

b = [(1 2 3 4)= (4 1 3 2)].

Тогда произведение b* а в группе S4 равно перестановке, полу­чающейся в результате применения сначала а, а затем b:

Ь*а = [(1 2 3 4)->- (2 3 4 1)],

что является элементом группы S4. С таким определением умно­жения группа перестановок 54 является не абелевой группой, содержащей 24 элемента.

Пусть G — группа, и пусть H — некоторое подмножество в G. Тогда Н называется подгруппой группы G, если оно является группой относительно ограничения операции * на H. Для того чтобы проверить, что непустое множество H является подгруп­пой группы G, необходимо только проверить, что для всех а и b из H элемент а * b принадлежит H (замкнутость) и что элемент, обратный к a из H, также принадлежит H. Остальные группо­вые свойства наследуются из группы G. Как вскоре мы увидим при рассмотрении циклических подгрупп, в случае конечных групп из свойства замкнутости автоматически вытекает даже свойство существования обратного элемента.

Например, множество всех четных чисел и множество чисел, кратных 3, являются подгруппами в множестве всех целых чисел (положительных, отрицательных и нуля) относительно опера­ции сложения.

Один из путей построения подгруппы H конечной группы G состоит в выборе произвольного элемента h группы G и формиро­вании H как множества элементов, образованных умножением h на самого себя произвольное число раз. Таким образом, строим последовательность элементов

h, h*h, h*h*h, h*h*h*h, ....

обозначая их для простоты через h, h2, h3, h4, ... . Так как G ко­нечна, то только конечное число этих элементов различно, так что с некоторого момента последовательность начнет повторяться. Первым повторяющимся элементом должен быть сам элемент h, так как если два различных элемента h1 и h! равны, то их можно умножить на элемент, обратный h, и получить, что h(i-1) и h(j-1) также равны. Далее заметим, что если h,j = h, то h(j-1) = 1, еди­ничному элементу группы. Множество H называется подгруп­пой, порожденной элементом h.. Число с элементов в H называется порядком элемента h. Множество элементов h, h2, h3, ..., hс = 1 называется циклом. Цикл является подгруппой, так как произ­ведение двух элементов такого вида снова является элементом этого вида, а элемент, обратный элементу h1, равен h(c-i) и, следо­вательно, является одним из элементов цикла. Группа, состоя­щая из всех степеней одного из ее элементов, называется цик­лической группой.

Для заданных конечной группы G и подгруппы H существует важная операция, которая устанавливает некоторые взаимо­связи между G и H и называется разложением группы G на смеж­ные классы по H. Обозначим через h1, h2, h3, ... элементы из H, причем через h1 обозначим единичный элемент. Построим таб­лицу следующим образом. Первая строка состоит из элементов подгруппы H, причем первым слева выписан единичный элемент h1 и каждый элемент из H записан в строке один и только один раз. Выберем произвольный элемент группы G, не содержащийся в первой строке. Назовем его g2 и используем в качестве первого элемента второй строки. Остальные элементы второй строки получаются умножением слева элементов подгруппы на этот пер­вый элемент. Аналогично строим третью, четвертую и пятую строки: каждый раз в качестве элемента первого столбца выби­раем не использованный на предыдущих шагах элемент группы G. Построение заканчивается тогда, когда после некоторого шага оказывается, что каждый элемент группы записан в некотором месте таблицы. Процесс обрывается в силу конечности G. В ре­зультате получается следующая таблица

 

h1=1, h2, h3, …. hn

g2 * h1 =g2 g2 * h2 g2* h3 g2 * hn

g3 * h1 =g3 g3 * h2 g3* h3 g3 * hn

. .

. .

. .

gm * h1 =gm gm * h2 gm* h3 gm * hn

 

Первый элемент слева в каждой строке называется лидером смеж­ного класса. Каждая строка таблицы называется левым смежным классом, а в случае абелевой группы — просто смежным классом. Если при построении разложения группы на смежные классы использовать правое умножение на элементы группы G вместо левого, то строки называются правыми смежными классами. В силу указанных выше правил построения разложение на смеж­ные классы всегда представляется прямоугольной таблицей, все строки которой полностью заполнены. Докажем теперь, что всегда получается таблица, в которой каждый элемент группы встречается точно один раз.

Теорема 1.1.3.В разложении группы G на смежные классы каждый элемент из G встречается один и только один раз.

Доказательство.Каждый элемент появится хотя бы один раз, так как в противном случае процесс не остановится. Докажем теперь, что каждый элемент не может появиться дважды в одной и той же строке и что один и тот же элемент не может появиться в двух разных строках.

Предположим, что два элемента одной и той же строки, gi * hk и gi * hj равны. Тогда умножение. каждого из них на gi(-1)дает равенство hk= hj . Это противоречит тому, что каждый элемент подгруппы выписан в первой строке только один раз.

Предположим, что два элемента различных строк gi*hj, и gk*h равны и что k<j.Умножение справа на hj-1приводит к равенству gi=gk*hj*hj-1 Тогда gi порождает k-й смежный класс, так как элемент hj*hj-1принадлежит k подгруппе.

Это противоречит указанному выше правилу выбора лидеров смеж­ных классов. Следствие 1.1.4.Если Н — подгруппа группы G, то число элементов в Н делит число элементов в G. Таким образом, (Порядок H)- (Число смежных классов G по H) =

= (Порядок G). П

Доказательствоследует непосредственно из прямоугольности таблицы разложения на смежные классы.

Теорема 1.1.5.Порядок конечной группы делится на порядок любого из ее элементов.

Доказательство.Группа содержит циклическую подгруппу, порожденную любым из ее элементов; таким образом, утвержде­ние теоремы вытекает из следствия 1.1.4.

 

КОЛЬЦА

Следующей необходимой нам алгебраической структурой является кольцо. Кольцо представляет собой абстрактное множество, которое является абелевой группой и наделено дополнительной структурой.

Определение 1.2.1.Кольцом R называется множество с двумя определенными на нем операциями: первая называется сложением (обозначается +), вторая называется умножением (обозначается соседним расположением), причем имеют место следующие ак­сиомы:

1) относительно сложения (+) R является абелевой групцой;

2) замкнутость: произведение аЬ принадлежит R для любых а и Ь из R;

3) закон, ассоциативности: '

а (Ьс) = (аЬ) с;
4) закон дистрибутивности:

а (Ь + с) = аЬ + ас, (Ь + с) а = Ьа + ca.

Сложение в кольце всегда коммутативно, а умножение не обязательно должно быть коммутативным. Коммутативное кольцо — это кольцо, в котором умножение коммутативно, т. е. аb = для всех а и Ь из R

Закон дистрибутивности в определении кольца связывает операции сложения и умножения. Этот закон имеет несколько непосредственных следствий, как, например, приведенная ниже теорема.

Теорема 1.2.2.Для произвольных элементов а и b в кольце R

(1) a0= 0a

(2) а (—Ь) = (—а) Ь = — (аЬ). . .. .

Доказательство.

Вычитая из обеих частей равенства аО, получаем 0 = аО. Вторая часть утверждения (1) доказывается аналогично, (2). О = аО = а (b — b) = аb + а (—b). Следовательно, а (-b) = - (аb).Вторая…  

Теорема 1.2.4.

(2) Если с = аb и с — единица, то а имеет правый обратный, а b — левый обратный элемент.. Доказательство.Непосредственная проверка.

ВЕКТОРНЫЕ ПРОСТРАНСТВА

Для произвольного поля можно дать абстрактное определение векторных пространств. Определение 1.4.1.Пусть F — некоторое поле. Назовем эле­менты из F скалярами.… 1) V является абелевой группой относительно векторного сложения;

W u =(с1 w1 + … + сп wп) u = с1 w1 u+ … + сп wп u.

Если u ортогонален к каждому wi, то он ортогонален к каждому w из W.

 

Если размерность подпространства W в векторном пространстве n-последовательностей равна k, то размерность ортогонального дополнения W- равна n–k. Этот факт часто используется в дальнейшем и поэтому будет доказан в виде теоремы 1.5.9.Мы сошлемся на этот факт при доказательстве следующего результата.

 

Теорема 1.4.10.Пусть W - подпространство в пространстве n-последовательностей, и пусть Wего ортогональное дополнение. Tогда W представляет собой ортогональное дополнение подпространства W.

Доказательство.Пусть размерность W равна k. Тогда, согласно теореме 1.5.9, размерность W- равна n-k, а размерность ортогонального дополнения пространства W равна k. Но каждый вектор из W ортогонален к W. Следовательно, W содержится в ортогональном дополнении к W и имеет ту же самую размерность, так что эти подпространства совпадают.

 

ЛИНЕЙНАЯ АЛГЕБРА

Широко используемые разделы прикладной математики — линейная алгебра, в частности теория матриц, — обычно изучаются только для поля вещественных… Определение 1.5.1. (п X т)-матрицей А над кольцом R называется прямоугольная…  

. . . . . .

an1 an2 . . . anm

 

 

 

 
 
 

В большинстве приложений кольцо R в действительности является полем, и мы ограничимся этим случаем. Как правило, мы будем рассматривать матрицы над конечным полем GF (q).

Множество элементов аii, для которых номер строки совпа­дает с номером столбца, называется главной диагональю. Если n равно т, то матрица называется квадратной матрицей, (п X n)-матрица, все элементы главной диагонали которой равны единичному элементу поля, а остальные элементы равны нулевому элементу поля, называется единичной (п X п)-матрицей.

Единичная матрица обозначается через I. Примерами единичных матриц являются

 

 

1 0 0

1 0 и 0 1 0

1 0 0 0 1

 

 

Две ( п Х m ) матрицы А и В над полем GF (q ) можно складывать по правилу

 

A + B = C, где cij = aij + bij

(lХ п) матрицу А и ( п Х m ) матрицу В над полем GF (q ) можно умножать получив ( l X m ) матрицу С, по правилу

п

А В =С, где сij = ∑( аik bkj)

k=1

Как легко проверить, множество квадратных (nX п)-матриц образует кольцо относительно так определенных умножения и сложения матриц. Это кольцо не коммутативно, но обладает единицей, а именно единичной (п X п)-матрицей. Матрицу можно разбить на блоки по правилу

 

A11 |A12

A = ---- |------

A21 | A22

где А11А12, А21 и А22— меньшие матрицы, размеры которых очевидным образом дополняют друг друга до размеров матрицы А. А именно сумма числа строк матрицы А11(или А12) и числа строк матрицы А21 (или А22) равна числу строк матрицы А; аналогичное утверждение выполняется для столбцов. Матрицы можно перемножить поблочно, а именно если С = АВ, то при условии корректного выбора размеров блоков (корректного в том смысле, что все произведения и суммы матриц определены)

 

А11В1112В21 | А11В12 + А12В22

С = ---------------------|----------------------

А21В1122В21 | А21В12 + А22В22

 

Такое разложение можно получить как простое следствие аксиом ассоциативности и дистрибутивности основного поля-

Транспонированной к (n X m )-матрице Аназывается X n )-матрица Ат, такая, что aтij = аji. Таким образом, строками матрицы Ат служат столбцы матрицы А, а столбцами матрицы Ат служат строки матрицы А. Обратной к квадратной матрице А называется квадратная матрица А-1 (если она существует), такая что А-1А= АА-1 = I. Как можно сразу проверить, множество всех обратимых (n X n)-матриц образует группу относительно операции умножения. Следовательно, если матрица имеет обрат­ную, то обратная матрица единственна, так как в силу теоремы 1.1.2 это свойство выполняется в каждой группе. Матрица, имеющая обратную, называется невырожденной; в противном случае она называется вырожденной. Если С = АВ, то при условии, что АиВ обратимы, С-1 = В-1А-1, так как -1A-1) С= I = С (В-1A-1). Впоследствии мы увидим, что если у А или у В нет обратной матрицы, то и уС нет обратной матрицы.

Определение 1.5.2. Пусть задано поле F. Определитель квадратной (n xX n)-матрицы А для каждого п является функцией на множестве всех (n xX n)-матриц над F со значениями в поле F, обозначается через det(А) и задается формулой

detсЫ(А) = ξi1,i2,i3,…,in α1 i1 α2 i2 α3 i3 … αn inЕ&!.:. <-„й1а2,-2 • • • ащп,,

где /i1, i2, … in х, {'а, ..., 1„ — перестановка на множестве целых чисел {1, 2, ..., п}, ξi1,i2,i3,…,in |,- ... 1п равно ±1 в зависимости от четности или нечет­ности перестановки, а суммирование ведется по всем переста­новкам.

Нечетная перестановка определяется как произведение нечет­ного числа транспозиций (транспозицией называется переста­новка двух членов). Четная перестановка определяется как пере­становка, которая не может быть получена нечетным числом транс­позиций.

Один из способов сделать это определение наглядным состоит в рассмотрении множеств всех матриц, которые можно получить из матрицы А перестановкой строк. Для каждой из таких матриц возьмем произведение всех членов, лежащих на главной диаго­нали (если перестановка была нечетной, то изменим знак произ­ведения), и сложим все полученные таким образом произведения. Конечно, вычислять таким образом определитель не следует, но это дает хороший способ установления свойств определи­телей.

В приведенной ниже теореме перечислены свойства функции (det1е1 (А), вытекающие непосредственно из ее определения.

Теорема 12.56.3.

2П) Определитель матрицы равен определителю транспони­рованной матрицы.   3(ш) Если две строки матрицы поменять местами, то ее опре­делитель изменит знак..

G= .

.

gk ,

где строками являются базисные векторы. Ранг этой матрицы равен k, и размерность пространства столбцов матрицы G равна k. Вектор v принадлежит W, если

G vT = 0,

так как в этом случае он ортогонален к каждому базисному век­тору. Пусть ( h1, h2, … hr) —базис подпространства W. Пополним этот базис до базиса всего пространства {h1, h2, … hr,.f1, f2, …, Fn-r.). Теперь вектор vиз пространства столбцов матрицы G запишется в виде v = GbТ, где вектор b представляет собой некоторую линейную комбинацию базисных векторов. Следовательно, каждый вектор в пространстве столбцов матрицы Gдолжен записываться в виде линейной комбинации векторов

{GhT1, GhT2, … GhTr,.GfT1, GfT2, …, GfTn-r }.

Покажем теперь, что векторы ( GfT1, GfT2, …, GfTn-r ) образуют базис пространств столбцов матрицы G. Так как GhTi = 0, то это множество порождает пространство столбцов матрицы G. Далее, эти векторы линейно независимы, так как если

ά1 GfT1 +ά2GfT2 +,…,+άn-r GfTn-r= 0,то

G (ά1 fT1 +ά2fT2 +,…,+άn-r fTn-r)= 0,

и поэтому ά1 +ά2+,…,+άn-r =0, поскольку единственной линейной комбинацией векторов {GfT1, GfT2, …, GfTn-r }, принадлежащей нулевому пространству матрицы G, является нулевой вектор 0.Следовательно, {GfT1, GfT2, …, GfTn-r} образуют базис пространства столбцов матрицы G. Таким образом, n – r = k , что и доказывает теорему.


 

·

 

 

 


 

 

АРИФМЕТИКА ПОЛЕЙ ГАЛУА

В настоящей главе мы возвращаемся к начатому в гл.1опи­санию структуры полей Галуа. Там мы ввели определение поля, но не указали процедур построения полей Галуа, а именно их таблиц сложения и умножения. Мы будем изучать поля Галуа с помощью двух построений, одно из которых основывается на кольце целых чисел, а другое—на кольцах много членов, и докажем, что таким образом можно построить все поля Галуа.

 

КОЛЬЦО ЦЕЛЫХ ЧИСЕЛ

Множество всех целых чисел (положительных, отрицательных и нуля) образуют кольцо относительно обычных операций сложе­ния и умножения. Это кольцо… Говорят, что целое число s делится на целое число r или что r делит s (или что… Положительное целое число р > 1, которое делится только на ±р или ±1, называется простым. Положительное целое…

Теорема 2.1.2.

2 . Rd(a*b)=Rd{ Rd (a) *Rd (b) } Доказательствопредоставляется читателю в качестве упраж­нения.  

КОНЕЧНЫЕ ПОЛЯ, ОСНОВАННЫЕ НА КОЛЬЦЕ ЦЕЛЫХ ЧИСЕЛ

Определение 2.2.1.Пусть q — положительное целое число. Кольцом отношений, именуемым также кольцом целых чисел по модулю q и обозначаемым через Z… Элементы, обозначенные через 0, 1, … ,q-1, принадлежат как Z, так и Z/(q).… Теорема 2.2.2.Кольцо отношений Z (q) является кольцом.

КИТАЙСКИЕ ТЕОРЕМЫ ОБ ОСТАТКАХ

Теорема .2.23.14. Для заданного множества из k целых положи­тельных попарно взаимно простых чисел m1, m2, ..., mк и множе­ства неотрицательных целых… ci = с (mod тi;), i=1,2, ,k ,   имеет

КОЛЬЦА МНОГОЧЛЕНОВ

f(x)= fn-1 xn-1+fn-2 xn-2 +…+f1 x1 +f0 , где символ x; называется неопределенной переменной, коэффициенты fn-1, . ..,… Степенью ненулевого многочлена f (х) называется индекс старшего коэффициента fn-1; степень многочлена / f(х)…

Теорема 2.3.4.

, (2 ) Rd(х)[a(х)b(x)]= Rd(х)[ Rd(х)[a(х)] Rd(х)[b(х)].] Доказательствосводится к упражнению: использовать алгоритм деления для…  

КИТАЙСКИЕ ТЕОРЕМЫ ОБ ОСТАТКАХ

с1 (х) = с (х) (mod mi(x) i = 1, ..., k, имеет не более одного решения с (х}, удовлетворяющего условию k dtg c(x<∑deg mi (x.).

I=1

Следовательно, с(х) — с*(х) = О, и доказательство закончено.

 

Так же как и в кольце целых чисел, в кольце многочленов над произвольным полем выполняется равенство

НОД [r (х) , s(х)] = а (х) r(х) + b(х) s (х)

для некоторых а(х) и b(х). Для заданного множества попарно взаимно простых т{ (х) положим М (х) = Пki=1 mi (х) и Мi(х)=М(х)/т1(х) и допустим, что Ni (х) и пi (х) удовлетворяют ра­венствам Ni(х) Мi (х)+ пi(х) тi(х) = I; согласно следствию 2.3.7, такие многочлены N{(х) и пг (х) всегда существуют

 

 

Теорема 2.3..9. Пусть М(х) = ∏ki=1 mi(x) - произведение попарно взаимно простых многочленов, и пусть Мi (х) = М (х)/тi (х)

и Ni(х) удовлетворяют равенствам Ni(х) Мi (х)+ пi(х) тi(х) = I. Тогда единственным решением системы сравнений ,

сi(х) = с (х) (mod mi(x)), i = 1, ..., k, является

k

с(х)=∑i=1 сi(х} Ni(х) Мi (х) (mod М (х)).

Доказательство. Так как мы уже знаем, что рассматриваемая система сравнений имеет не более одного решения, то нам надо только доказать, что выписанное выше с(х) действительно является решением. Но

с (х) = сг (х) N i (х) Мi (х) (mod mi(x)),
ибо тi (х) делит Мr (х), если r ≠ i. Наконец, так как

Ni(х) Мi (х)+ пi(х) тi(х) = I,

то Ni(х) Мi(х) = 1 (mod mi(x)) и с(х) = сi (х) (mod mi(x)), что и завершает доказательство.

 

КОНЕЧНЫЕ ПОЛЯ, ОСНОВАННЫЕ НА КОЛЬЦАХ МНОГОЧЛЕНОВ

Определение 2.4.1.Для произвольного приведенного многочлена р (х) ненулевой степени над полем F кольцом многочленов по модулю р (х) называется…   Произвольный элемент r(х) кольца F[х] можно отобразить в элемент кольца РF[х]/(р (х)) с помощью соответствия r(х) —RР…

Степень Простые многочлены

3 x3 +x +1 4 x4 +x +1 5 x5 +x2 +1

ПРИМИТИВНЫЕ ЭЛЕМЕНТЫ

Определение 24.5.1.Примитивным элементом поля GF(q) называется такой элемент α, что все элементы поля, за исключением нуля, могут быть…    

СТРУКТУРА КОНЕЧНОГО ПОЛЯ

Теперь изменим точку зрения на противоположную. Вместо того чтобы строить поле, предположим, что нам дано конечное поле, и докажем, что независимо… В процессе работы над материалом данного параграфа мы углубим наше понимание… Определение 2.6.1. Число элементов наименьшего подполя поля GF(q) называется характеристикой поля GF(q).

– Конец работы –

Используемые теги: Лекции, домашнии, задания, курсу, токбдискретная, математика, Введение, дискретную, алгебру0.127

Если Вам нужно дополнительный материал на эту тему, или Вы не нашли то, что искали, рекомендуем воспользоваться поиском по нашей базе работ: ЛЕКЦИИ И ДОМАШНИИ ЗАДАНИЯ ПО КУРСУ ТОКБДИСКРЕТНАЯ МАТЕМАТИКА ВВЕДЕНИЕ В ДИСКРЕТНУЮ АЛГЕБРУ

Что будем делать с полученным материалом:

Если этот материал оказался полезным для Вас, Вы можете сохранить его на свою страничку в социальных сетях:

Еще рефераты, курсовые, дипломные работы на эту тему:

Курс русской истории Лекции I—XXXII КУРС РУССКОЙ ИСТОРИИ Лекции I—XXXII ЛЕКЦИЯ I Научная задача изучения местной истории
Все книги автора... Эта же книга в других форматах... Приятного чтения...

Курс русской истории Лекции I—XXXII Курс русской истории – 1 КУРС РУССКОЙ ИСТОРИИ Лекции I—XXXII Василий Осипович Ключевский
Курс русской истории Лекции I XXXII... Курс русской истории...

Домашние задания по алгебре. 1 курс 1 семестр Домашнее задание №1 1. Даны две матрицы A и B. Найти: а AB; б BA; в 3АВ-2А
Домашнее задание... Даны две матрицы A и B Найти а AB б BA в АВ А... A B Даны две матрицы A и B Найти а AB б В...

Учебная программа курса. 4. Лекция 1. История психологии как наука. 5. Лекция 2. Античная философия и психология. 6. Лекция 3. Развитие психологии в Средневековый период. 19. Лекция 16. Тревога и защита
Введение... Учебная программа курса... Рабочая программа курса Лекция История психологии как наука...

Лекции 1.ОСНОВНЫЕ ПОНЯТИЯ И КАТЕГОРИЯ ИНФОРМАТИКИ. 2 ЛЕКЦИИ 2. МАТЕМАТИЧЕСКИЕ ОСНОВЫ ИНФОРМАТИКИ. СИСТЕМЫ СЧИСЛЕНИЯ. 12 ЛЕКЦИЯ 3. АППАРАТНОЕ ОБЕСПЕЧЕНИЕ ЭВМ. 20 ЛЕКЦИЯ 4. ПРОГРАММНОЕ ОБЕСПЕЧЕНИЕ КОМПЬЮТЕРОВ.. 49 Широко распространён также англоязычный вар
gl ОГЛАВЛЕНИЕ... Лекции ОСНОВНЫЕ ПОНЯТИЯ И КАТЕГОРИЯ ИНФОРМАТИКИ... ЛЕКЦИИ МАТЕМАТИЧЕСКИЕ ОСНОВЫ ИНФОРМАТИКИ СИСТЕМЫ СЧИСЛЕНИЯ...

Краткий курс механики в качестве программы и методических указаний по изучению курса Физика Краткий курс механики: Программа и методические указания по изучению курса Физика / С
Федеральное агентство железнодорожного транспорта... Омский государственный университет путей сообщения...

ЛЕКЦИЯ–ВВЕДЕНИЕ Тема лекции: Введение в дисциплину Безопасность жизнедеятельности . Взаимодействие человека и окружающей среды
Тема лекции Введение в дисциплину Безопасность жизнедеятельности... Цель лекции изучить источники возникновения развитие науки Безопасность жизнедеятельности е исторические основы...

ЛЕКЦИЯ № 1. Факторы выживания в природной среде ЛЕКЦИЯ № 2. Обеспечение водой ЛЕКЦИЯ № 3. Обеспечение питанием ЛЕКЦИИ по ОБЖ
КЛАСС Содержание Стр I четверть ЛЕКЦИЯ Факторы выживания в природной среде ЛЕКЦИЯ... ЛЕКЦИЯ Факторы выживания в природной... ЛЕКЦИЯ Обеспечение питанием...

Лекция первая. ИСТОРИЯ СОЦИОЛОГИИ КАК ОБЛАСТЬ ЗНАНИЯ Лекция вторая. ИЗ КАКИХ ИДЕЙ РОДИЛАСЬ СОЦИОЛОГИЯ: ИНТЕЛЛЕКТУАЛЬНЫЕ ИСТОКИ НОВОЙ НАУКИ Лекция третья. СОЦИОЛОГИЯ ОГЮСТА КОНТА ЛЕКЦИИ
Оглавление... ОТ АВТОРА... Лекция первая ИСТОРИЯ СОЦИОЛОГИИ КАК ОБЛАСТЬ ЗНАНИЯ Лекция вторая ИЗ КАКИХ ИДЕЙ РОДИЛАСЬ СОЦИОЛОГИЯ ИНТЕЛЛЕКТУАЛЬНЫЕ ИСТОКИ НОВОЙ НАУКИ...

Лекция 1: Введение в курс Экономика организаций предприятий КРАТКИЙ КУРС ЛЕКЦИЙ
Лекция Введение в курс Экономика организаций предприятий Объект предмет структура... Лекция Предприятие и предпринимательство в рыночной... Основные понятия о предприятии Организационно правовые и организационно экономические формы...

0.07
Хотите получать на электронную почту самые свежие новости?
Education Insider Sample
Подпишитесь на Нашу рассылку
Наша политика приватности обеспечивает 100% безопасность и анонимность Ваших E-Mail
Реклама
Соответствующий теме материал
  • Похожее
  • По категориям
  • По работам