Logo GenDocs.ru

Поиск по сайту:  

Загрузка...

Лекции по дискретной математике - файл 1.doc


Лекции по дискретной математике
скачать (582 kb.)

Доступные файлы (1):

1.doc582kb.21.11.2011 22:50скачать

содержание
Загрузка...

1.doc

  1   2   3   4
Реклама MarketGid:
Загрузка...
ЛЕКЦИИ И ДОМАШНИЕ ЗАДАНИЕ ПО КУРСУ «ДИСКРЕТНАЯ МАТЕМАТИКА» ДЛЯ СТУДЕНТОВ ЗАОЧНОГО ОТДЕЛЕНИЯ СПЕЦИАЛЬНОСТИ 2202
1. ВВЕДЕНИЕ В ДИСКРЕТНУЮ АЛГЕБРУ

1.1. ГРУППЫ

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

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

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

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


y

x



1 a b c d e


1


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. Типичный элемент группы 54 равен

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.2.1. Кольцом R называется множество с двумя определенными на нем операциями: первая называется сложением (обозначается +), вторая называется умножением (обозначается соседним расположением), причем имеют место следующие ак­сиомы:

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

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

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

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

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

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

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

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

(1) a0= 0a

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

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

(1). аО = а (0 + 0) = аО + аО.

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

(2). О = аО = а (b b) = аb + а (—b). Следовательно, а (-b) = - b).Вторая часть утверждения (2) доказывается аналогично.
Операция сложения в кольце имеет единичный элемент, назы­ваемый нулем. Операция умножения не обязательно имеет еди­ничный элемент, но если он есть, то является единственным. Кольцо, обладающее единственным элементом относительно умно­жения, называется кольцом с единицей. Этот единичный элемент называется единицей и обозначается символом 1. Тогда для всех а из R имеет место равенство

1а = а1= а.

Относительно операции сложения каждый элемент кольца имеет обратный. Относительно операции умножения элемент, обратный данному элементу, не обязательно существует, но в кольце с единицей обратные элементы могут существовать. Это означает, что для данного элемента а может существовать элемент b, такой, что аb = 1. Если это так, то b называется пра­вым обратным к а. Аналогично если существует элемент с, такой, что cа = 1, то с называется левым обратным к а.
Теорема 1.2.3. В кольце с единицей:

(1)- единица единственна;

(2) если элемент а имеет как правый обратный b, так и левый обратный с, то элемент а называется обратимым, причем обратный ему элемент является единственным (и обозначается через а-1);

(3) (a--1)-1 =a

Доказательство.Рассуждения аналогичны приведенным при доказательстве теоремы 1.1.2. Обратимый элемент кольца называется единицей. Множество всех единиц в кольце замкнуто относительно умножения, так как если а и bединицы, то с = ab имеет обратный элемент, равный с-1 =b-1a-1
Теорема 1.2.4.

(1) Множество единиц кольца образует группу относительно умножения в кольце

(2) Если с = аb и с единица, то а имеет правый обратный,

а b левый обратный элемент..

Доказательство. Непосредственная проверка.

Имеется много известных примеров колец, и ниже приводятся некоторые из них. Представляется поучительным проиллюстри­ровать этими примерами теоремы 1.2.3 и 1.2.4.

1. Множество всех вещественных чисел образует коммута­тивное кольцо с единицей относительно обычных сложения и ум­ножения. Каждый ненулевой элемент кольца является единицей.

2. Множество всех целых чисел (положительных, отрицатель­ных и нуля) образует коммутативное кольцо с единицей относи­тельно обычных сложения и умножения. Это кольцо принято обозначать через 2; его единицами являются только ±1.

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

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

5. Множество всех многочленов от x с вещественными коэф­фициентами образует коммутативное кольцо с единицей отно­сительно сложения и умножения многочленов. Единицей кольца является многочлен нулевой степени p (x) = 1.

1.3. ПОЛЯ


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

Определение 1.3.1. Полем, называется множество с двумя определенными на нем операциями — сложением и умножением, -причем имеют место следующие аксиомы:

1) множество образует абелевую группу по сложению;

2) поле замкнуто относительно умножения, и множество нену­левых элементов образует абелевую группу по умножению;

3) закон дистрибутивности:

(а + b) с = ас + bс для любых а, b, с из поля.

Единичный элемент относительно сложения принято обозна­чать через О/и называть нулем, аддитивный обратный элементу а элемент — через -а; единичный элемент относительно умноже­ния обозначать через 1 и называть единицей, мультипликативный обратный к элементу а элемент — через a-1. Под вычитанием (а -b) понимается а + (-b); под делением (а/b) понимается b-1а.

Широко известны следующие примеры полей:

1) R: множество вещественных чисел,

2) С: множество комплексных чисел,

3) Q: множество рациональных чисел.

Все эти поля содержат бесконечное множество элементов. Мы интересуемся полями, содержащими конечное число элемен­тов. Поле с q элементами, если оно существует, называется конеч­ным полем или полем Галуа и обозначается через GF (q).

Что представляет собой наименьшее поле? Оно обязательно содержит нулевой элемент и единичный элемент. На самом деле этого уже достаточно при следующих таблицах сложения и умно­жения:





+



0 1






0

1



0 1

1 0




















*

0 1

0

1

0 0

0 1



Это поле GF (2). Проверка показывает, что не существует другого поля с двумя элементами. Ниже конечные поля будут изучены более детально. Сейчас мы приведем два простых примера и опишем их таблицами сло­жения и умножения (вычитание и деление неявно определяются этими же таблицами).
Поле GF(3) = {0, 1, 2} с операциями

+

0 1 2




.

0 1 2

0

1

2

0 1 2

1 2 0

2 0 1




0

1

2

0 0 0

0 1 2

0 2 1

Поле GF(4)={0,1,2,3} c операциями

+

0 1 2 3




.

0 1 2 3

0

1

2

3

0 1 2 3

1 0 3 2

2 3 0 1

3 2 1 0




0

1

2

3

0 0 0 0

0 1 2 3

0 2 3 1

0 3 1 2

Отметим, что умножение в поле GF (4) не является умножением по модулю 4 и сложение не является сложением по модулю 4.

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

Прежде чем расстаться с этими примерами, заметим, что
поле ^ GF(2) содержится в GF(4), так как в поле GF(4) два эле­
мента 0 и 1 складываются и умножаются точно так же, как они
складываются и умножаются в поле GF(2). Однако GF(2) не со­
держится в GF (3).

Определение 1.3.2. Пусть F- некоторое поле. Подмножество в F называется подполем, если оно само является полем относи­тельно наследуемых из F операций сложения и умножения. В этом случае исходное поле F называется расширением поля.

Для того чтобы доказать, что подмножество конечного поля является подполем, необходимо доказать только, что оно содер­жит ненулевой элемент и что оно замкнуто относительно сложе­ния и умножения. Все остальные необходимые свойства насле­дуются из F. Обратные элементу β по сложению или умножению элементы содержатся в порожденной β циклической группе относительно операции сложения или умножения.

Поле обладает всеми свойствами кольца, а также важным Дополнительным свойством — в нем всегда возможно сокращение.

Сокращение представляет собой слабую форму деления и озна­чает, что если аb = ас, то b = с.

Теорема 1.3.3. Если в произвольном поле аb = ас и а ≠ О, то b = с.

Доказательство. Умножить на а-1.

Некоторые кольца могут также удовлетворять этому условию сокращения, но все-таки не быть полями. Простым примером служит кольцо целых чисел. В этом кольце сокращение возможно, но приведенное для теоремы 1.3.3 доказательство не проходит, так как в этом кольце не существует элемента а-1. Кольца, в ко­торых всегда возможно сокращение, имеют специальное название.

Определение 1.3.4. Коммутативное кольцо, в котором b = с, если аb = ас и элемент а отличен от нуля, называется областью целостности.
  1   2   3   4



Скачать файл (582 kb.)

Поиск по сайту:  

© gendocs.ru
При копировании укажите ссылку.
обратиться к администрации