Печать_семинар 6 (Семинары)
Описание файла
Файл "Печать_семинар 6" внутри архива находится в следующих папках: Семинары, Семинар 6. PDF-файл из архива "Семинары", который расположен в категории "". Всё это находится в предмете "дискретная математика" из 3 семестр, которые можно найти в файловом архиве МГТУ им. Н.Э.Баумана. Не смотря на прямую связь этого архива с МГТУ им. Н.Э.Баумана, его также можно найти и в других разделах. Архив можно найти в разделе "лекции и семинары", в предмете "дискретная математика" в общих файлах.
Просмотр PDF-файла онлайн
Текст из PDF
ЭЛЕМЕНТЫ ОБЩЕЙ АЛГЕБРЫПолугруппы и группы• First • Prev • Next • Last • Go Back • Full Screen • Close • QuitПусть на множестве A определена бинарная операция, обозначаемая ∗ .Определение 6.1. Бинарная операция ∗ называется:1) ассоциативной, если для любых x , y , z(x ∗ y) ∗ z = x ∗ (y ∗ z);2) коммутативной, если для любых x , yx ∗ y = y ∗ x;3) идемпотентной, если для любого xx ∗ x = x.• First • Prev • Next • Last • Go Back • Full Screen • Close • Quitа) Теоретико-множественные операции ∪ , ∩ являются ассоциативными, так как(A ∪ B) ∪ C = A ∪ (B ∪ C);(A ∩ B) ∩ C = A ∩ (B ∩ C);коммутативными, так какA ∪ B = B ∪ A;A ∩ B = B ∩ A;и идемпотентными, так какA ∪ A = A;A ∩ A = A;б) Операция \ разности не является ассоциативной, так какA \ (B \ C) 6= (A \ B) \ C.• First • Prev • Next • Last • Go Back • Full Screen • Close • QuitЗадача 1Ассоциативна ли операция на множестве M , если:(а) M = N,x y = 2xy ;(б) M = Z,x y = x2 + y 2 ;(в) M = R,x y = sin(x) · sin(y) ;(г) M = R,xy =x−y.• First • Prev • Next • Last • Go Back • Full Screen • Close • QuitОпределение 6.2.
Элемент 0 множества A называется левым(правым) нулем относительно данной операции, если для любогоx ∈ A 0 ∗ x = 0 ( x ∗ 0 = 0 ). Нуль, который является одновременнолевым и правым, называется просто нулем.Определение 6.3. Элемент 1 множества A называется левым(правым) нейтральным элементом относительно данной операции, если для любого x ∈ A1 ∗ x = x ( x ∗ 1 = x ). Нейтральныйэлемент, который является одновременно левым и правым, называется просто нейтральным элементом. Нейтральный элемент частоназывают единицей.• First • Prev • Next • Last • Go Back • Full Screen • Close • QuitПример 1. Пустое множество ∅ является нулем относительнопересечения, так как для любого множества AA∩∅=∅и единицей относительно объединения, так какA ∪ ∅ = A.Универсальное множество U есть нуль относительно объединения таккакA ∪ U = U,и единица относительно пересечения, так какA ∩ U = A.• First • Prev • Next • Last • Go Back • Full Screen • Close • QuitОпределение 6.4.
Группоидом называется любое множество содной бинарной операцией.Группоид, операция которого ассоциативна, называется полугруппой.Пример 2.а) Множество натуральных чисел с операцией сложения будет полугруппой, поскольку (a + b) + c = a + (b + c) .б) Множество 2A всех подмножеств множества A с операциейтеоретико-множественной разности \ только группоид, но не полугруппа, поскольку операция \ не ассоциативна.• First • Prev • Next • Last • Go Back • Full Screen • Close • QuitЗадача 2.
На множестве M определена операция ◦ по правилуx ◦ y = x . Доказать, что (M, ◦ ) — полугруппа. Что можно сказать онейтральных элементах этой полугруппы?Задача 3. На множестве M 2 , где M — некоторое множество,определена операция ◦ по правилу (x, y) ◦ (z, t) = (x, t) . Являетсяли (M 2, ◦ ) полугруппой? Существует ли в ней нейтральный элемент?x yЗадача 4.
Пусть S — полугруппа матриц вида, x,y ∈ R0 0с операцией умножения. Существуют ли в этой полугруппе левый илиправый нейтральные элементы.• First • Prev • Next • Last • Go Back • Full Screen • Close • QuitОпределение 6.5. Полугруппа называется моноидом, если в нейсуществует нейтральный элемент относительно операции (единица).Пример 3. а) Алгебра (2A, ∪) является моноидом, поскольку операция∪ ассоциативна и ∅ — нейтральный элемент относительно операцииобъединения множеств.б) Множество всех бинарных отношений на множестве A с операциейкомпозиции будет моноидом, поскольку операция композиции бинарныхотношений ассоциативна ( (ρ ◦ τ ) ◦ σ = ρ ◦ (τ ◦ σ) ), а единицей служитдиагональ idA ( idA ◦ρ = ρ ◦ idA = ρ ).Задача 5.
Пусть A = {x, y, z} — множество букв, а A∗ — множество всех слов, которые можно составить из этих букв с повторениями.Конкатенацией двух слов называется слово, полученное их склеивани”ем“, например: xxy + yzxx = xxyyzxx . Пустое слово обозначаютλ.∗Показать, что (A , +) — моноид.• First • Prev • Next • Last • Go Back • Full Screen • Close • QuitОпределение 6.6.
Элемент y множества A называется левым(правым) обратным к элементу x относительно данной операции,если y ∗ x = 1 ( x ∗ y = 1 ). Элемент y , который является одновременно левым и правым обратным, называется просто обратным к xотносительно данной операции.Определение 6.7. Моноид называется группой, если в нем длякаждого элемента существует обратный.Чтобы проверить, что алгебра (A, ∗) является группой, нужно1) проверить ассоциативность операции ∗ на множестве A ;2) найти элемент множества A – единицу относительно операции ∗ ;3) убедиться, что для каждого элемента из A существует обратный.Полугруппа (в частности, группа) называется коммутативной (абелевой), если ее операция коммутативна.• First • Prev • Next • Last • Go Back • Full Screen • Close • QuitПример 4. Рассмотрим алгебру (2A, 4, ∅) .Операция симметрической разности1) ассоциативна ( (A 4 B) 4 C = A 4(B 4 C)) ;2) для любого X ⊆ A X 4 ∅ = X , т.е.
∅ — единица относительноданной операции;3) X 4 Y = ∅ тогда и только тогда, когда X = Y , т.е. каждыйэлемент X является обратным сам к себе.Следовательно, данная алгебра является группой.Поскольку операция 4 коммутативна ( A 4 B = B 4 A ), то даннаяалгебра является абелевой группой.Задача 6. Какие из указанных множеств с операциями являютсягруппами:(а) (N, + ) ;(б) (Q, + ) ;(в) (R \ {0}, · ) .• First • Prev • Next • Last • Go Back • Full Screen • Close • QuitЗадача 7. Какие из указанных множеств квадратных вещественныхматриц образуют группу:(а) множество невырожденных матриц относительно умножения?(б) множество невырожденных матриц относительно сложения?(в) множество диагональных матриц одного порядка (включая нулевую)относительно сложения?(г) множество диагональных матриц одного порядка, исключая нулевую,относительно умножения?Задача 8. Пусть M — некоторое множество.
Является ли группойалгебра(а) (2M , ∩ ) ;(б) (2M , ∪ ) ?• First • Prev • Next • Last • Go Back • Full Screen • Close • Quit1. Решение уравнений в группахТеорема 1. В любой группе G любое уравнение вида a · x = b илиx · a = b имеет единственное решение.Решение имеет вид:x = a−1 · b или x = b · a−1.• First • Prev • Next • Last • Go Back • Full Screen • Close • QuitПример 5.В группе S3 решим следующее уравнение 1 2 31 2 31 2 3◦X ◦=.3 1 22 3 13 2 1Умножим уравнение слева на−1 1 2 31 2 3=,3 1 22 3 1получим:X◦1 2 32 3 1=1 2 32 1 3.Далее, умножая полученное уравнение справа на−1 1 2 31 2 3=2 3 13 1 2окончательно получимX=1 2 31 3 2= (2 3).• First • Prev • Next • Last • Go Back • Full Screen • Close • QuitЗадача 9.
Решить уравнение в группе S4 : 1 2 3 41 2 3 4X= (1 2) ;(а)4 2 1 33 2 1 41 2 3 4.(б) (1 2)(3 4)X(1 3) =4 2 1 3Задача 10.ВыписатьтаблицуКэлидлямножестваподстановок{ε, (12)(34), (13)(24), (14)(23)} с операцией композиции подстановок.• First • Prev • Next • Last • Go Back • Full Screen • Close • Quit.