Читать онлайн «Методические указания к лабораторным работам по курсу ''Дискретная математика''»

Министерство образования Российской Федерации ОРЕНБУРГСКИЙ ГОСУДАРСТВЕННЫЙ УНИВЕРСИТЕТ Кафедра программного обеспечения вычислительной техники и автомати- зированных систем Д. В. Домашова Н. Ф. Бахарева В. А. Стенюшкина МЕТОДИЧЕСКИЕ УКАЗАНИЯ к лабораторным работам по курсу “Дискретная математика” Оренбург 2000 4 МЕТОДИЧЕСКИЕ УКАЗАНИЯ к лабораторным ра- ботам по курсу “Дискретная математика” Тема 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  1. 3 Кольца и поля Определение. Кольцом называется множество R с двумя бинарными операциями ⊗ и ⊕ : а) ⊗ – ассоциативна; б) ⊕ – ассоциативна, коммутативна, имеет нуль, ∃ обратный элемент по сложению.