Лекции по дискретной математике

ЛЕКЦИИ И ДОМАШНИЕ ЗАДАНИЕ ПО КУРСУ «ДИСКРЕТНАЯ МАТЕМАТИКА» ДЛЯ СТУДЕНТОВ ЗАОЧНОГО ОТДЕЛЕНИЯ СПЕЦИАЛЬНОСТИ 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.2. Единичный элемент в каждой группе, является единственным. Для каждого элемента группы обратный элемент также является единственным, и (а^-1)^-1 = а.

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

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

Наконец, а^-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С=СВА) = (АВС=ВАС) = е. Поступая таким образом, можно построить таблицу для х*у:

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

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

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* а в группе S₄ равно перестановке, полу­чающейся в результате применения сначала а, а затем b:

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

что является элементом группы S₄. С таким определением умно­жения группа перестановок 5₄ является не абелевой группой, содержащей 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, h², h³, h⁴, ... . Так как G ко­нечна, то только конечное число этих элементов различно, так что с некоторого момента последовательность начнет повторяться. Первым повторяющимся элементом должен быть сам элемент h, так как если два различных элемента h¹ и h^! равны, то их можно умножить на элемент, обратный h, и получить, что h^(i-1) и h^(j-1) также равны. Далее заметим, что если h,^j = h, то h^(j-1) = 1, еди­ничному элементу группы. Множество H называется подгруп­пой, порожденной элементом h.. Число с элементов в H называется порядком элемента h. Множество элементов h, h², h³, ..., h^с = 1 называется циклом. Цикл является подгруппой, так как произ­ведение двух элементов такого вида снова является элементом этого вида, а элемент, обратный элементу h¹, равен h^(c-i) и, следо­вательно, является одним из элементов цикла. Группа, состоя­щая из всех степеней одного из ее элементов, называется цик­лической группой.

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

h₁=1, h₂, h₃, …. h_n

g_{2 *} h₁ =g₂ g_{2 *} h₂ g_2* h₃ g_{2 *} h_n