- •31. Замыкание множества булевых функций.
- •38. Определение и свойства групп.
- •39. Группа подстановок.
- •40. Подгруппы. Пересечение подгрупп. Циклические подгруппы.
- •41.Теорема о подгруппе циклической группы.
- •42. Порядок элемента группы. Теорема о циклической подгруппе.
- •43. Разложение группы по подгруппе. Теорема Лагранжа.
- •44. Гомоморфизмы и изоморфизмы групп. Ядро гомоморфизма. Изоморфизм циклических групп.
- •45. Нормальные подгруппы. Фактор-группы.
- •46. Теорема о гомоморфизме групп.
- •47. Определение и свойства колец.
- •48. Гомоморфизмы колец.
- •49. Идеалы, классы вычетов, фактор-кольца.
- •50. Теорема о гомоморфизме колец.
- •53) Простое поле. Теорема о изоморфизме простого поля.
- •54) Основные понятия теории графов.
- •55) Маршруты в графавах.
- •56) Матрица смежности и матрица инцидентности.
- •57) Алгоритмы обхода графа в ширину и глубину.
- •58) Алгоритмы Дейкстры.
43. Разложение группы по подгруппе. Теорема Лагранжа.
Пусть H подгруппа группы G .Рассмотрим бинарное отношение
RH={(a,b)|a-1b€H}
Теорема отношение RH является отношением эквивалентности .
Доказательство: Рефлейсивность: a-1a=e€H=>(a,a) €RH
Симметричность: (a,b) €RH =>a-1 b=h€H=> b-1a=h-1€H=>(b,a) €RH
Транзитивность: (a,b) €RH,(p,c) €RH=>a-1b=h1€H, b-1c=h2€H=>
c=bh2 =>a-1c=a-1bh2=h1h2€(a,b) €RH
Определение: Левые смежные классы группы G подгруппы H есть множество
a H={ah (h€H}
Теорема: Классы эквивалентности отношения RH есть левые смежные классы G по H [a]=aH
Доказательство: b€[a]a-1b=h€Hb=ah € aH Левые смежные классы образуют разбиения группы. Аналогично определяются правые смежные классы.
Теорема Лагранжа: пусть G конечная группа порядка n, H подгруппа G порядка K, тогда n делится на K Доказательство: Все левые смежные классы содержат ровно K элементов, т.к.из равенства ah1= ah2 , h1h2 €H следует h1=h2
Пусть Р есть число различных смежных классов, тогда n=kp
44. Гомоморфизмы и изоморфизмы групп. Ядро гомоморфизма. Изоморфизм циклических групп.
Определение: Отображение f группы G на группу H называется гомоморфизмом, если для любых a,b€G f(a,b)=f(a)f(b)
Определение: взаимно однозначный гомоморфизм называется изоморфизмом
Теорема: пусть f есть гомоморфизм G на H . Тогда f(e) есть единичный элемент ВH,f(a-1)=f-1 (a)
Доказательство:
1)h=f(a) €H=>hf(e)=f(a)f(e)=f(a,e)=f(a)=h
F(e)h=f(e)f(a)=f(e,a)=f(a)=h
2)a€G=>f(a)f(a-1)=f(aa-1)=f(e) f(a-1)f(a)=f(aa-1)=f(e)=>f(a-1)=f-1(a)
Определение: ядром гомоморфизма f группы G на группу H называется множество ker f={a€G | f(a)=f(e)} Теорема: ядро f является подгруппой G
Доказательство:a,b€kerf=>f(a,b)=f(a)f(b)=f(e)f(e)=f(e)=>a,b€kerf
a€kerf =>f(a-1)=f-1(a)=f-1(e)=f(e)
Теорема: все бесконечные циклические группы изоморфны .Все конечные циклические группы данного порядка n изоморфны.
Доказательство: G={a}, H={b},f(ak)=bk
G={ ak /k=0,±1….}
H={ bk /k=0±1…..}
Теорема: если G-бесконечно циклическая группа ,то G изоморфна любой своей подруппе, т.к. любая подгруппа бесконечно циклической группы бесконечна
45. Нормальные подгруппы. Фактор-группы.
Определение: Подгруппа H группы G H≤G называется нормальной подгруппой или нормальным делителем группы G, если левостороннее разложение группы G по подгруппе H совпадает с правосторонним.
(для любого)¥а€G=>aH=Hc
aH={ah/h€H} То любая ее подгруппа называется нормальной . Элементы a,b€G называются сопряженными ,если существует (сущ)Ex€G:xa=bx или ax=bx, a=x-1bx, a=xbx-1
Две матрицы А и В называются подобными , если A=pBp-1
У подобных матриц совпадает вырожденные числа и харктерист. многочлены.
Теорема: H € G является нормальной, когда H содержит все элементы сопряженные элементам Н aH€H, b сопр.а, то b€H
aH=Haax=bx, тогда ф и b явл. Сопряженными.
Пусть H и P- 2 нормальных делителя группы G,тогда Н∩Р- нормальный делитель группы G
a€ Н∩Р=>b=x·a·x-1€ Н∩Р
Пусть H и P-два подмножества группы G
Н·Р={hp/h€H,p€P}
H-нормальная подгруппа группы G
xH, где x€G-левые смежные классы
xH·xH=(xy)HH=(xy)H
1)Aaaaa…
2)eH=H
3)(aH)-1=a-1H
Построенная т.о. группа называется фактор группой G/H
Пусть G-абелева группа ,тогда фактор группа тоже является абелевой G-циклической группой, тогда фактор группа тоже явл. циклической.
Очевидно также, что порядок факторгруппы равен натуральному числу n/m, где n — порядок группы G,а m — порядок нормальной подгруппы N. Например, факторгруппа группы симметрий квадрата по подгруппе центральных симметрий
содержит 4 элемента.
46. Теорема о гомоморфизме групп.
47. Определение и свойства колец.
48. Гомоморфизмы колец.
49. Идеалы, классы вычетов, фактор-кольца.
50. Теорема о гомоморфизме колец.