Поля и кольца.
Определение. Множество R с двумя определенными в нем алгебраическими операциями, сложением и умножением, называется кольцом, если относительно операции сложения оно является абелевой группой, а операция умножения дистрибутивна, т.е. для любых элементов a, b и с R справедливы равенства:
Если операция умножения, определенная в кольце коммутативна, то такое кольцо называется коммутативным кольцом.
Из определения следует, что любое кольцо имеет две бинарные и одну унарную (см. пункт 2) операцию, поэтому его тип - .
Определение. Полем называется коммутативное кольцо, в котором для любого ненулевого элемента a 0 и любого элемента b существует единственный элемент такой, что ax = b.
Другими словами, для любой пары элементов и уравнение имеет единственный корень. Практически это определяет в поле существование операции деления.
Пример 3.
а) Алгебра является кольцом и называется кольцом целых чисел. Она, однако, не является полем, поскольку, например, уравнение в ней неразрешимо.
б) Алгебра является полем и называется полем рациональных чисел.
Решётки.
До сих пор нами рассматривались алгебры, то есть множества, на которых заданы операции. Множества, на которых кроме операций, заданы отношения, называются алгебраическими системами. Таким образом, алгебры можно считать частным случаем алгебраических систем, у которых множество алгебраических отношений пусто. Другим частным случаем алгебраических систем являются модели – множества, на которых заданы только отношения.
Рассмотрим здесь лишь один пример алгебраической системы, который наиболее часто встречается в теоретической алгебре и её приложениях - решётки.
Определение. Решёткой называется множество , частично упорядоченное отношением нестрогого порядка , с двумя бинарными операциями и , такое что выполнены следующие условия (аксиомы решётки):
1. (идемподентность);
2. (коммутативность);
3. (ассоциативность);
4. (поглощение).
Решётка называется дистрибутивной, если выполняются два следующих условия и .
Определение. Если в решётке существует элемент 0, такой что для любого выполняется , то он называется нижней гранью (нулём) решётки.
Определение. Если в решётке существует элемент 1, такой что для любого выполняется , то он называется верхней гранью (единицей) решётки.
Определение. Решётка, имеющая верхнюю и нижнюю грани, называется ограниченной.
Теорема 6.1. Если нижняя (верхняя) грань решётки существует, то она единственная.
Определение. В ограниченной решётке элемент называется дополнением элемента , если и .
Пример 4.
а) Любое полностью упорядоченное множество, например, множество целых чисел, можно превратить в решётку, определив для любых , что и .
б) Определим на множестве натуральных чисел отношение частичного порядка следующим образом: , если является делителем . Тогда есть наименьшее общее кратное этих чисел, а их наибольший общий делитель.
Решётка, в которой пересечение и объединение существуют для любого подмножества её элементов, называется полной. Конечная решётка всегда полна.
- Конспект лекций по дисциплине “Дискретная математика”
- Санкт Петербург Содержание.
- Раздел I. Множества, функции, отношения. Лекция № 1. Множества и операции над ними.
- 1. Основные понятия теории множеств.
- 2. Операции над множествами и их свойства.
- 3. Векторы и прямые произведения.
- Лекция № 2. Соответствия и функции.
- Соответствия.
- Отображения и функции.
- Лекция № 3. Отношения и их свойства.
- Основные понятия и определения.
- Свойства отношений.
- Лекция № 4. Основные виды отношений.
- Отношения эквивалентности.
- Отношения порядка.
- Лекция № 4. Пересчёт.
- Раздел II. Введение в общую алгебру. Лекция № 6. Элементы общей алгебры.
- 1. Свойства бинарных алгебраических операций.
- 2. Алгебраические структуры.
- Гомоморфизм и изоморфизм.
- Лекция № 7. Различные виды алгебраических структур.
- Полугруппы.
- Группы.
- Поля и кольца.
- Раздел III. Введение в логику. Лекция № 8. Элементы математической логики.
- Булевы функции.
- Лекция № 9. Логические функции.
- Функции алгебры логики.
- Примеры логических функций.
- Суперпозиции и формулы.
- Лекция № 10. Булевы алгебры.
- Разложение функций по переменным. Совершенная дизъюнктивная нормальная форма.
- Булева алгебра функций.
- Эквивалентные преобразования.
- Лекция № 11. Булевы алгебры и теория множеств.
- Двойственность.
- Булева алгебра и теория множеств.
- Днф, интервалы и покрытия.
- Лекция № 12. Полнота и замкнутость.
- Функционально полные системы.
- Алгебра Жегалкина и линейные функции.
- Замкнутые классы. Монотонные функции.
- Теоремы о функциональной полноте.
- Лекция № 13. Язык логики предикатов.
- Предикаты.
- Кванторы.
- Истинные формулы и эквивалентные соотношения.
- Доказательства в логике предикатов.
- Лекция № 14. Комбинаторика.
- Правила суммы и произведения.
- Размещения.
- Перестановки.
- Сочетания. Бином Ньютона.
- Раздел IV. Теория графов. Лекция № 15. Графы: основные понятия и операции.
- Графы, их вершины, рёбра и дуги. Изображение графов.
- Матрица инцидентности и список рёбер. Матрица смежности графа.
- Идентификация графов, заданных своими представлениями.
- Лекция № 16. Маршруты, цепи и циклы.
- Основные определения.
- Связные компоненты графов.
- Расстояния. Диаметр, радиус и центр графа. Протяжённости.
- Эйлеровы графы.
- Лекция № 17. Некоторые классы графов и их частей.
- Деревья.
- Ориентированные графы.
- Графы с помеченными вершинами и рёбрами.
- Лекция № 18. Теория алгоритмов Понятие алгоритма
- 1.2.1. Основные требования к алгоритмам
- 1.2.2. Машина Тьюринга
- Универсальная машина Тьюринга
- 1.2.3. Тезис Тьюринга
- 1.3. Граф машина
- 1.3.1. Модель данных
- 1.3.2. Построение моделей алгоритмов в системе graph
- 2. Сложность алгоритмов
- 2.1.Временная и пространственная сложность алгоритма. Классы dtime и dspace
- 2.2. Классы сложности
- 2.2.1. Полиномиальность и эффективность
- 2.2.2. Алгоритмическая сводимость задач
- 3. Алгоритмы и их сложность
- 3.1. Представление абстрактных объектов (последовательностей)
- 3.1.1. Смежное представление последовательностей
- 3.1.2. Связанное представление последовательностей
- Список вопросов для подготовки к экзамену по дисциплине "дискретная математика"