Презентация семинар 6 (Семинары)
Описание файла
Файл "Презентация семинар 6" внутри архива находится в следующих папках: Семинары, Семинар 6. PDF-файл из архива "Семинары", который расположен в категории "". Всё это находится в предмете "дискретная математика" из 3 семестр, которые можно найти в файловом архиве МГТУ им. Н.Э.Баумана. Не смотря на прямую связь этого архива с МГТУ им. Н.Э.Баумана, его также можно найти и в других разделах. Архив можно найти в разделе "лекции и семинары", в предмете "дискретная математика" в общих файлах.
Просмотр PDF-файла онлайн
Текст из PDF
ЭЛЕМЕНТЫ ОБЩЕЙ АЛГЕБРЫПолугруппы и группы• First • Prev • Next • Last • Go Back • Full Screen • Close • QuitПусть на множестве A определена бинарная операция, обозначаемая ∗ .• First • Prev • Next • Last • Go Back • Full Screen • Close • QuitПусть на множестве A определена бинарная операция, обозначаемая ∗ .Определение 6.1.
Бинарная операция ∗ называется:• First • Prev • Next • Last • Go Back • Full Screen • Close • QuitПусть на множестве A определена бинарная операция, обозначаемая ∗ .Определение 6.1. Бинарная операция ∗ называется:1) ассоциативной, если для любых x , y , z(x ∗ y) ∗ z = x ∗ (y ∗ z);• 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;• 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а) Теоретико-множественные операции ∪ , ∩ являются ассоциативными, так как• First • Prev • Next • Last • Go Back • Full Screen • Close • Quitа) Теоретико-множественные операции ∪ , ∩ являются ассоциативными, так как(A ∪ B) ∪ C = A ∪ (B ∪ C);• First • Prev • Next • Last • Go Back • Full Screen • Close • Quitа) Теоретико-множественные операции ∪ , ∩ являются ассоциативными, так как(A ∪ B) ∪ C = A ∪ (B ∪ C);(A ∩ B) ∩ C = A ∩ (B ∩ C);• First • Prev • Next • Last • Go Back • Full Screen • Close • Quitа) Теоретико-множественные операции ∪ , ∩ являются ассоциативными, так как(A ∪ B) ∪ C = A ∪ (B ∪ C);(A ∩ B) ∩ C = A ∩ (B ∩ C);коммутативными, так как• 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;• 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;• 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;и идемпотентными, так как• 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;• 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;• 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 ;• First • Prev • Next • Last • Go Back • Full Screen • Close • QuitЗадача 1Ассоциативна ли операция на множестве M , если:(а) M = N,x y = 2xy ;(б) M = Z,x y = x2 + y 2 ;• 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) ;• 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 ). Нуль, который является одновременнолевым и правым, называется просто нулем.• 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∩∅=∅• First • Prev • Next • Last • Go Back • Full Screen • Close • QuitПример 1. Пустое множество ∅ является нулем относительнопересечения, так как для любого множества AA∩∅=∅и единицей относительно объединения, так какA ∪ ∅ = A.• First • Prev • Next • Last • Go Back • Full Screen • Close • QuitПример 1. Пустое множество ∅ является нулем относительнопересечения, так как для любого множества AA∩∅=∅и единицей относительно объединения, так какA ∪ ∅ = A.Универсальное множество U есть нуль относительно объединения таккакA ∪ U = U,• 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. Группоидом называется любое множество содной бинарной операцией.• First • Prev • Next • Last • Go Back • Full Screen • Close • QuitОпределение 6.4. Группоидом называется любое множество содной бинарной операцией.Группоид, операция которого ассоциативна, называется полугруппой.• First • Prev • Next • Last • Go Back • Full Screen • Close • QuitОпределение 6.4. Группоидом называется любое множество содной бинарной операцией.Группоид, операция которого ассоциативна, называется полугруппой.Пример 2.а) Множество натуральных чисел с операцией сложения будет полугруппой, поскольку (a + b) + c = a + (b + c) .• 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, ◦ ) — полугруппа.
Что можно сказать онейтральных элементах этой полугруппы?• 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, ◦ ) полугруппой? Существует ли в ней нейтральный элемент?• 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, x,y ∈ RЗадача 4. Пусть S — полугруппа матриц вида0 0с операцией умножения. Существуют ли в этой полугруппе левый илиправый нейтральные элементы.• First • Prev • Next • Last • Go Back • Full Screen • Close • QuitОпределение 6.5. Полугруппа называется моноидом, если в нейсуществует нейтральный элемент относительно операции (единица).• First • Prev • Next • Last • Go Back • Full Screen • Close • QuitОпределение 6.5.
Полугруппа называется моноидом, если в нейсуществует нейтральный элемент относительно операции (единица).Пример 3. а) Алгебра (2A, ∪) является моноидом, поскольку операция∪ ассоциативна и ∅ — нейтральный элемент относительно операцииобъединения множеств.• First • Prev • Next • Last • Go Back • Full Screen • Close • QuitОпределение 6.5. Полугруппа называется моноидом, если в нейсуществует нейтральный элемент относительно операции (единица).Пример 3.
а) Алгебра (2A, ∪) является моноидом, поскольку операция∪ ассоциативна и ∅ — нейтральный элемент относительно операцииобъединения множеств.б) Множество всех бинарных отношений на множестве A с операциейкомпозиции будет моноидом, поскольку операция композиции бинарныхотношений ассоциативна ( (ρ ◦ τ ) ◦ σ = ρ ◦ (τ ◦ σ) ), а единицей служитдиагональ idA ( idA ◦ρ = ρ ◦ idA = ρ ).• First • Prev • Next • Last • Go Back • Full Screen • Close • QuitОпределение 6.5.
Полугруппа называется моноидом, если в нейсуществует нейтральный элемент относительно операции (единица).Пример 3. а) Алгебра (2A, ∪) является моноидом, поскольку операция∪ ассоциативна и ∅ — нейтральный элемент относительно операцииобъединения множеств.б) Множество всех бинарных отношений на множестве A с операциейкомпозиции будет моноидом, поскольку операция композиции бинарныхотношений ассоциативна ( (ρ ◦ τ ) ◦ σ = ρ ◦ (τ ◦ σ) ), а единицей служитдиагональ idA ( idA ◦ρ = ρ ◦ idA = ρ ).Задача 5.