- •1. Элементы теории множеств
- •1.1 Множества. Основные понятия
- •1.2. Способы задания множеств
- •1.3. Операции над множествами. Диаграммы Венна
- •1.4. Свойства операций над множествами
- •1.5. Прямое (декартово) произведение множеств
- •1.6 Разбиения и покрытия
- •1.7. Замечание о мощности некоторых множеств
- •1.8 Представление множеств в эвм
- •1.9. Отношения
- •1.9.1.Определения
- •1.9.2 Бинарные отношения
- •1.9.3. Способы задания бинарных отношений
- •1.9.4 Свойства бинарных отношений
- •1.9.5. Отношение эквивалентности
- •1.9.5. Отношение порядка
- •1.9.6.1. Минимальные и максимальные элементы множества
- •1.9.6.2. Диаграммы Хассе
- •1.9.6.3. Принцип двойственности
- •1.9.7. Представление отношений в эвм
- •1.10. Соответствия. Функции. Операции. Отображения
- •1.10.1. Соответствия и их свойства
- •1.10.2 Функции и отображения
- •1.10.3. Инъекция, сюръекция и биекция
- •1.10.4. Композиция и суперпозиция функций. Способы задания функций
- •1.10.5. Представление функций в эвм
- •1.10.6. Операции
- •1.10.6.1. Способы задания операций
- •1.11. Алгебраические структуры
- •1.11.2. Замыкание и подалгебры
- •1.11.3. Гомоморфизм и изоморфизм
- •1.11.4. Алгебры с одной бинарной операцией
- •1.11.5. Алгебры с двумя бинарными операциями
- •1.11.6.Решетки
- •1.11.7. Булевы алгебры
- •2. Элементы математической логики и булевы функции
- •2.1. Операции над высказываниями
- •2.2. Логические операции (логические связки)
- •2.3. Элементарные булевы функции
- •2.3.1. Функции алгебры логики
- •2.3.2. Равносильность функций. Существенные и несущественные переменные
- •2.3.3. Реализация функций формулами. Суперпозиция функций
- •2.3.4. Подстановки и замены
- •2.3.5. Принцип двойственности
- •2.3.6. Нормальные формы в логике высказываний
- •2.3.6.1. Разложение булевых функций по переменным. Дизъюнктивно-нормалльная форма (днф)
- •2.3.6.2. Совершенная дизъюнктивная нормальная форма
- •2.3.7. Арифметические операции в алгебре логики. Полиномы Жегалкина
- •2.3.8. Монотонные функции алгебры логики
- •2.3.9. Функционально замкнутые классы
- •2.4. Полнота системы булевых функций. Теорема
- •2.5. Элементы логике предикатов
- •2.5.1. Определение предиката
- •2.5.2. Кванторы. Формулы логики предикатов
- •2.5.3. Равносильность формул
- •2.5.4. Предикаты на конечных областях. Логика одноместных предикатов
- •2.6. Операции над предикатами и кванторами
- •2.7. Построение доказательств в логике предикатов
- •1.6.2. Разбор решений задач по логике предикатов
- •1. Элементы теории множеств 3
- •1.1 Множества. Основные понятия 3
- •2.6. Операции над предикатами и кванторами 137
- •394026 Воронеж, Московский просп., 14
1.11. Алгебраические структуры
Алгебраические методы описания моделей находят широкое применение при формализации различных предметных областей. Часто объектом изучения в математике и ее приложениях является множество вместе с определенной на нем структурой. Грубо говоря, при построении модели предметной области все начинается с введения подходящих обозначений для операций и отношений с последующим исследованием их свойств.
При этом, словом "алгебра" обозначают не только область математики, но и один из конкретных объектов, изучаемых в этой области.
Нам уже известны числовые поля, формирующие основу обычной арифметики, линейные пространства, обеспечивающие связь геометрических объектов с операциями над числами, множества с введенными на них бинарными отношениями. Все эти структуры образуют алгебраические системы с определенными в них законами.
1.11.1. Основные определения
Пусть - всюду определенная (тотальная) функция , называемая n-арной (n-местной) операцией на М.
Множество М вместе с заданными на нем операциями называется алгеброй.
Здесь , где -арность операции .
Множество М называется основным (несущим) множеством или основной (носителем). Вектор арностей называется типом алгебры, а множество операцией называется сигнатурой. Записывают так: или .
Замечание: Операции конечноместны, сигнатура конечна. Носитель М не обязательно конечен, но не пуст.
Типом алгебры называется вектор арностей операций сигнатуры.
Примеры:
1. Алгебра - поле действительных чисел. Тип – (2,2) (сигнатура включает две бинарные операции – сложение и умножение).
2. Алгебра - алгебра подмножества над множеством М . Тип . Сигнатура включает две бинарные операции и одну унарную.
3. Алгебра , где - операция дифференцирования.
Если в качестве используются отношения, то множество М вместе с заданными на нем отношениями называется моделью. Обозначается: ,
где М – несущее множество, - сигнатура модели .
Пример 1.
Моделью является множество чисел М1 с отношениями: "быть больше" (>) и "быть равным" (=), т.е. .
Пример 2.
Набор не образует алгебру, поскольку деление не является операцией на множестве Z (например, ), а элемент не принадлежит Z.
Множество М вместе с заданными на нем операциями и отношениями называется алгебраической системой или алгебраической структурой. Обозначается:
Пример3:
На множестве М заданы: одно бинарное отношение частичного порядка (обозначение ) и две бинарные операции : - так называемая решетка.
Таким образом, одним частным случаем алгебраической структуры являются алгебры (алгебраические структуры с пустым множеством отношений). Другим частным случаем алгебраических структур являются модели, то есть множества, на которых заданы только отношения.
1.11.2. Замыкание и подалгебры
Подмножество называется замкнутым относительно операции на М1, если для любых
Если Х замкнуто относительно всех , то называется подалгеброй где
.
Примеры:
1. Для алгебры все конечные подмножества, кроме , не замкнуты относительно обеих операций.
Поле рациональных чисел образует подалгебру.
2. Для алгебры . При этом для любого подмножества Х множества М образует подалгебру.
3. Для алгебры множество элементарных функцией образует подалгебру.