- •Дискретная математика. Теория и практика
- •Оглавление
- •Глава 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
1. Является ли операция (a, b) ab - ba бинарной алгебраической операцией на множествах N, Z, Q, 2Z, 2Z + 1, R, R+, Q [ ]? Если является, то есть ли во множестве нейтральный элемент относительно нее?
2. Пусть М(2, R) = . Проверить, является ли подалгеброй алгебры <М(2,R), × > следующее множество матриц:
а) ; б) ;
в) ; г) ;
д) ; е) .
3. Определить, какими алгебраическими структурами являются следующие алгебры: < N, + >; < Q, +, × >; < R \ {0}, × >; < 3Z, + >; < Z, – >; <C, +, × >;
< N, × >; < Q \ {0}, × >; < R, +, × >; < Z, × >; < Q, + >; < C, + >.
4. Доказать, что множество степеней числа 2 с целыми показателями образует коммутативную группу относительно обычной операции умножения рациональных чисел.
5. Доказать, что множество геометрических векторов на плоскости, лежащих на одной или параллельных прямых, образует коммутативную группу относительно операции сложения.
6. Пусть L = {aх + b a, b Î R} – множество линейных функций. Доказать, что множество L является некоммутативной группой относительно операции композиции функций.
7. Доказать, что множество невырожденных квадратных матриц порядка n образует группу относительно операции умножения матриц.
8. Является ли следующая алгебра группой: а) <P({1,2}), È >; б) <P({1,2}), Ç >?
9. Доказать, что алгебра <R, >, где a b = a + b – 2, является группой.
10. Пусть Е = { , , } есть множество поворотов вокруг центра правильного треугольника, переводящих треугольник в себя, где , и – повороты на угол 0, , соответственно. На множестве Е введем операцию умножения поворотов следующим образом: поворот получается в результате последовательного выполнения поворотов и . Построить таблицу Кэли для операции умножения. Выяснить, какую алгебраическую структуру образует множество Е относительно умножения.
11. Выяснить, образует ли кольцо (относительно + и ×) множество nZ целых чисел, кратных данному натуральному числу n.
12. Доказать, что множество квадратных матриц порядка n с действительными элементами образует некоммутативное кольцо относительно операции сложения и умножения матриц.
13. Укажите, в какой из классов вычетов , ,…, попадает каждое число: 307, –38, 25, –40, –10, 13, 85, –15, 43, если: а) n = 10; б) n = 2; в) n = 5;
г) n = 7; д) n = 6.
14. Истинно ли высказывание: а) 13 Î (mod 7); б) 85 Î (mod 7)?
15. Построить таблицу Кэли кольца Z4, указать его обратимые элементы и делители нуля, то есть элементы а, удовлетворяющие условию а× b = 0, где b – некоторый ненулевой элемент.
16. Доказать, что алгебра Zn = <Zn, +, × > – коммутативное кольцо.
17. Какие из следующих множеств матриц образуют поле относительно сложения и умножения матриц:
а) ; б) ;
в) ; г) .
18. Доказать, что множество Q [ ] = {a + b a, b Î R} образует поле относительно обычных операций сложения и умножения действительных чисел. Найти в этом поле элемент, обратный к элементу 1 – 2 .
19. Выяснить, является ли отображение гомоморфизмом указанных алгебр. Если да, то какой это вид гомоморфизма.
а) f: < R, + > → < {2x│xÎR}, × >, f(x) = 2x.
б) h: < , +, × > → <{a+b │a, b Î Z}, +, × >,
h = a + b .
в) h: < , +, × > → < Z, +, × >, h = a.