Методические указания к лабораторным работам по курсу "Дискретная математика". Домашова Д.В - 2 стр.

МЕТОДИЧЕСКИЕ УКАЗАНИЯ к лабораторным ра-
ботам по курсу “Дискретная математика”
                      Тема 1 Алгебраические структуры
                                   1.1 Общие понятия

     Определение. Алгебраическая структура есть множество вместе с опера-
циями определенными на этом множестве: , A–носитель, S–сигнатура.
(Структура вместе с теоремами, правилами вычислений и вывода называется
также алгебраической структурой)
     Определение. Если  – алгебраическая структура и B ⊂ A, то она на-
зывается подструктурой.
     Пример. (Z, ⊕ ) – структура, (2Z,+) – подструктура.
     Определение. Пусть (A, ⊗ ), (C, ⊕ ) – алгебраические структуры. Если
существует отображение ϕ : A → C: ∀ x,y ∈ A выполняется ϕ ( x ⊗ y ) = ϕ ( x) ⊕ ϕ ( y ) , то
ϕ называется гомоморфизмом.
     Пример. (]0,+∞[,•), ( R,+) ϕ : x α ln x ⇒ ln xy = ln x + ln y , т.е. ϕ – гомоморфиз-
мом.

                             1.2 Простейшие структуры

         Определение. Полугруппой называется множество S с бинарной опера-
цией ⊗ удовлетворяющей ассоциативности: x ⊕ ( y ⊗ z ) = ( x ⊕ y ) ⊕ z ,      x, y, z ∈ S.
         Определение. Моноидом называется множество M вместе с бинарной
операцией ⊗ :
         а) ⊗ – ассоциативна;
         б) ∃ u ∈ M: u ⊗ x = x = x ⊗ u для ∀x ∈ M. U - называется единицей по отно-
шению к операции ⊗ .
         Полугруппы и моноиды имеют особое значение при обработке строк сим-
волов и теории языков.
         Пример. Пусть A={x,y,z}, где x, y, z– просто символы, A – алфавит. Оп-
ределим A ∗ как множество всех строк символов в A. Тогда x, y, z , xx, xy, xyz,.. ∈ A ∗ .
На A ∗ вводится операция конкатенации O: если α , β ⊂ A ∗ → αOβ = αβ . Длина
строки – число символов. ∧ ∈ A ∗ , ∧ = 0 , ∧ Oα = αO ∧ = α для ∀α , → для ∀ алфа-
вита A строка < A ∗ , O> является моноидом с единицей ∧ .
         Определение. Группой G называется множество с бинарной операцией
⊗:
         а) ⊗ – ассоциативна;
         б) ∃ u ∈ G (единица по отношению к ⊗ ): u ⊗ x = x = x ⊗ u для ∀x ∈ G;
         в) каждому элементу x ∈ G соответствующий элемент y ∈ G:
( x ⊗ y ) = u = y (⊗) x –y называют обратным элементом к x по отношению к ⊗ .


                                                                                          5