- •Дискретная математика. Теория и практика
- •Оглавление
- •Глава 1. Множества 6
- •Глава 2. Комбинаторика 24
- •Глава 3. Отношения. Отображения 34
- •Глава 4. Алгебраические структуры 55
- •Предисловие
- •Введение
- •Глава 1. Множества
- •1.1. Множества и их элементы. Способы задания множеств
- •1.2. Подмножества
- •1.3. Операции над множествами
- •1.4. Диаграммы Эйлера – Венна
- •1.5. Прямое произведение множеств
- •1.6. Метод математической индукции
- •1.7. Соответствия
- •1.8. Задачи, связанные с определением мощности конечного множества
- •Задачи и упражнения к главе 1
- •Глава 2. Комбинаторика
- •2.1. Правила суммы и произведения
- •2.2. Размещения и сочетания
- •2.3. Примеры решения задач
- •2.4. Бином Ньютона
- •2.5. Свойства биномиальных коэффициентов. Треугольник Паскаля
- •Задачи и упражнения к главе 2
- •Глава 3. Отношения. Отображения
- •3.1. Понятие отношения
- •3.2. Способы задания бинарных отношений
- •Характеристическим свойством.
- •3.3. Операции над бинарными отношениями
- •3.4. Свойства матриц бинарных отношений
- •3.5. Свойства бинарных отношений
- •3.6. Определение свойств бинарного отношения по его матрице
- •3.7. Отношение эквивалентности
- •3.8. Счетные и несчетные множества
- •3.9. Отношение порядка. Диаграммы Хассе
- •3.10. Функции
- •Задачи и упражнения к главе 3
- •Глава 4. Алгебраические структуры
- •4.1. Алгебраические операции и их свойства
- •4.2. Понятие алгебраической структуры
- •4.3. Алгебры с одной бинарной алгебраической операцией
- •4.4. Алгебры с двумя бинарными алгебраическими операциями
- •4.5. Конечные поля
- •4.6. Булевы алгебры
- •4.7. Гомоморфизмы алгебр
- •4.8. Алгебраические системы. Решетки
- •Задачи к главе 4
- •Список литературы
4.2. Понятие алгебраической структуры
Определение 4.10. Алгебраической структурой (универсальной алгеброй или просто алгеброй) называется упорядоченная пара А = < A, S >, где A – непустое множество и S – множество алгебраических операций на A.
Таким образом, алгебра представляет собой непустое множество A вместе с заданной на нем совокупностью операций S = {f1, …, fm, …}, где fi: ® A и ni – ранг операции fi. Множество A называется основным (несущим) множеством или основой (носителем) алгебры; упорядоченная последовательность рангов (n1,…, nm) называется типом алгебры; множество операций S называется сигнатурой алгебры.
Если < A, S > – алгебра, то также говорят, что множество A есть алгебра относительно операций S.
Наиболее частым является случай, когда сигнатура конечна. Если
S = {f1, …, fm}, то вместо записи А = < A, {f1, …, fm }> обычно употребляется запись А = < A, f1, …, fm >.
Замечание 4.1. Для обозначения алгебры везде, где это необходимо, используется рукописная прописная буква латинского алфавита, а для обозначения ее носителя – соответствующая печатная прописная буква.
Определение 4.11. Алгебры А = < A, f1, …, fm > и В = < В, , …, > называются однотипными, если их типы совпадают, то есть ранг операции fi совпадает с рангом соответствующей ей операции для i = 1,…, m.
Пример 4.6. 1. Пусть + и ∙ (сложение и умножение) – арифметические операции на множестве действительных чисел. Алгебра < R, +, ∙ > является алгеброй типа (2, 2).
2. Пусть P(A) – булеан непустого множества A и È, Ç, ‾ – операции пересечения, объединения и дополнения над подмножествами множества A. Алгебра < P(A), È, Ç, ‾ > является алгеброй типа (2, 2, 1).
Определение 4.12. Пусть алгебры А = < A, f1, …, fm > и
В = < В,> – однотипные алгебры. Алгебра В называется подалгеброй алгебры А , если В Í A и любая операция (i = 1, …, m) алгебры В и соответствующая ей операция fi алгебры А удовлетворяют условию:
(" b1, …, Î B) (b1, …, )=fi (b1, …, ), где ni – ранг операций и fi. (12)
Определение 4.13. Пусть А = < A, f1, …, fm > – алгебра и В Í A. Подмножество В множества A называется замкнутым в алгебре А, если В замкнуто относительно каждой операции fi (i = 1, …, m) алгебры А, то есть выполняется условие: (" b1,…,Î B) fi(b1,…,)ÎB, где ni – ранг операции fi. (13)
Если fi – нульарная операция, которая выделяет элемент a Î A, то условие (13) принимает вид a Î В.
Из определений 4.12 и 4.13 непосредственно вытекает следующая теорема.
Теорема 4.3. Пусть А = < A, f1, …, fm > – алгебра и В – непустое подмножество множества A, замкнутое в алгебре А. Тогда алгебра В = < В, f1, …, fm > является подалгеброй алгебры А.
Пример 4.7. Рассмотрим алгебру < N, +, × >, где + и × – обычные операции сложения и умножения натуральных чисел. Пусть M – множество четных чисел, то есть M = . Множество M замкнуто относительно операций сложения и умножения натуральных чисел. Действительно,
(" 2k1, 2k2 Î M) 2k1 + 2k2 = 2(k1 + k2) Î M и 2k1 × 2k2 = 2(2k1 × k2) Î M, так как множество N замкнуто относительно сложения и умножения. Следовательно, по теореме 4.3 алгебра < M, +, × > является подалгеброй алгебры < N, +, × >.