- •Раздел 1. Алгебраические структуры Тема 1.1. Бинарные операции и их свойства
- •Тема 1.2. Алгебраические структуры
- •Тема 1.3. Основные свойства групп
- •Тема 1.4. Поля и кольца
- •Раздел 2. Алгебра множеств Тема 2.1. Основные определения теории множеств
- •Тема 2.2. Подмножество, понятие универсального множества
- •Тема 2.3. Операции над множествами
- •Раздел 3. Основные теоремы комбинаторики
- •Тема 3.1. Метод математической индукции
- •Тема 3.2. Основные принципы комбинаторики
- •Раздел 4. Комбинаторные объекты Тема 4.1. Сочетания
- •Тема 4.2. Размещения и перестановки
- •Раздел 5. Полиномиальные тождества Тема 5.1. Бином Ньютона
- •Тема 5.2. Понятие о методе рекуррентных соотношений
- •Тема 5.3. Метод производящих функций
- •Тема 5.4. Метод траекторий
- •Тема 5.5. Примеры комбинаторных задач
- •Раздел 6. Соответствие, отношение, отображение Тема 6.1. Понятие кортежа. Декартово произведение множеств
- •Тема 6.2. Определения и свойства
- •Тема 6.3. Типы отношений
- •Пересечение и объединение отношений
- •Композиция отображений и отношений
- •Тема 6.5. Решётки
- •Тема 6.4. Верхняя и нижняя границы множества.
- •Раздел 7. Операции булевой алгебры Тема 7.1.Понятие высказывания, простые и составные высказывания
- •Тема 7.2.Операции на множестве высказываний
- •Отрицание
- •Конъюнкция
- •Дизъюнкция
- •«Исключающее или»
- •Импликация
- •Эквивалентность
- •Штрих Шеффера
- •Раздел 8. Законы и тождества Булевой алгебры Тема 8.1.Формулы Булевой алгебры
- •Тема 8.2.Законы и тождества Булевой алгебры
- •Тема 8.3.Составление формулы по заданной таблице истинности
- •Тема 8.4. Двойственность
- •Тема 8.5.Булева алгебра и теория множеств
- •Тема 8.6.Днф, интервалы и покрытия
- •Раздел 9. Функциональная полнота. Алгебра Жегалкина
- •Тема 9.1.Функционально полные системы
- •Тема 9.2.Алгебра Жегалкина и линейные функции
- •Тема 9.3.Замкнутые классы. Монотонные функции
- •Тема 9.4.Теоремы о функциональной полноте
- •Раздел 10. Хорновские формулы
- •Тема 10.1.Задача получения продукции
- •Тема 10.2.Решение задачи о продукции
- •Алгоритм замыкание(X,f)
- •Алгоритм ПрямаяВолна(X,y,f)
- •Алгоритм БыстроеЗамыкание(X,f)
- •Раздел 11. Теория релейно-контактных схем Тема 11.1.Основные понятия
- •Тема 11.2.Основные задачи теории релейно-контактных схем
- •Тема 11.3.Построение машины голосования
- •Тема 11.4.Двоичный сумматор
- •Тема 11.5.Методы упрощения логических выражений. Методы решения логических задач
- •Раздел 12. Логика предикатов Тема 12.1.Определение предиката
- •Тема 12.2.Логические операции над предикатами
- •Тема 12.3.Кванторы
- •Тема 12.4. Истинные формулы и эквивалентные соотношения
- •Тема 12.5.Доказательства в логике предикатов
- •Раздел 13. Теория графов
- •Тема 13.1.Основные определения теории графов
- •Тема 13.2. Способы задания графов
- •Тема 13.3. Отношения порядка и эквивалентности на графе
- •Тема 13.4. Числовые характеристики графа
- •Тема 13.5.Изоморфизм графов
- •Раздел 14. Проблемы достижимости на графах Тема 14.1.Граф достижимости
- •Тема 14.2.Взаимная достижимость, компоненты сильной связности и базы графа
- •Раздел 15. Некоторые классы графов Тема 15.1.Деревья
- •Тема 15.2. Обход графа
- •Тема 15.3. Расстояния. Диаметр, радиус и центр графа. Протяжённости.
- •Раздел 16. Машина Тьюринга
- •Тема 16.1. Формальное описание машины Тьюринга
- •Тема 16.2. Примеры построения машины Тьюринга
- •Тема 16.3. Свойства машины Тьюринга как алгоритма
- •Раздел 17. Машина Поста
- •Тема 17.1. Теоретическая часть. Состав машины Поста
- •Тема 17.2. Применимость программ. Определение результата выполнения программ
- •Раздел 18. Основные понятия теории автоматов Тема 18.1. Общие подходы к описанию устройств, предназначенных для обработки дискретной информации
- •Тема 18.2. Способы задания конечного автомата
- •Тема 18.3. Эквивалентные автоматы
- •Тема 18.4. Автоматы Мура и Мили
- •Тема 18.5. Примеры синтеза автоматов
Тема 1.2. Алгебраические структуры
Алгебраические структуры обычно состоят из одного или нескольких множеств объектов и одной или нескольких операций, заданных на этих множествах, позволяя комбинировать элементы этих множеств тем или иным способом. Для конкретных алгебраических структур многие их свойства могут быть предсказаны на основании свойств используемых операций, т.е. мы можем разбивать алгебраические структуры на семейства, члены которых могут иметь много общего, и отнесение какой-либо алгебраической структуры к некоторому классу позволяет делать выводы относительно характерных свойств, присущих членам этого семейства. Будем считать, что – бинарная операция, заданная на непустом множестве.
Определение:Пусть дано некоторое множество, на котором задана совокупность операций. Структура виданазываетсяалгеброй; множествоназываетсянесущим множеством, совокупность операций–сигнатурой, вектор «» операцийназываетсятипом.
Определение:Множествоназываютзамкнутымотносительнооперациина множестве, если значения функциина аргументахпринадлежат(то есть). Если множествозамкнуто относительно всех операций, то структураназываетсяподалгебройалгебры.
Пример 1.12:
а) Алгебра называется полем действительных чисел (определение понятия поля будет дано ниже). Её тип –. Это означает, что сигнатура данной алгебры содержит две бинарные операции. Здесь все конечные подмножества (кроме множества) не замкнуты относительно обеих операций и, следовательно, не могут образовывать подалгебры. Но алгебра вида– поле действительных чисел – образует подалгебру.
б) Пусть задано множество . Множество всех его подмножеств – булеан, обозначается какили. Алгебраназывается булевой алгеброй множеств над множеством. Её тип:. Для любогобудет являться подалгеброй.
в) Множество одноместных функций на(то есть функцийвместе с унарной операцией дифференцирования является алгеброй. Множество элементарных функций замкнуто относительно этой операции (поскольку производная любой элементарной функции есть также элементарная функция), поэтому образует подалгебру данной алгебры.
Определение:Замыканиеммножестваотносительно сигнатуры(обозначается) называется множество всех элементов, которые можно получить из элементов этого множества, применяя операции из сигнатуры(включая сами элементы).
Например, в алгебре целых чисел замыканием числа 2 является множество чётных чисел.
Теорема:Непустое пересечение подалгебр образует подалгебру.
Определение:Структура, называетсяполугруппой, если операцияассоциативна на.
Определение: Структураназываетсяабелевой полугруппой, если операциякоммутативна и ассоциативна на.
Пример 1.13:Структуры,,– являются абелевыми полугруппами.
Пример 1.14:Возьмём непустое множество символов, и назовём его алфавитом. На заданном алфавите определим слово, как конечную, упорядоченную последовательность символов данного алфавита. Рассмотрим множество возможных последовательностей – слов алфавитаи введём на этом множестве операцию конкатенации следующим образом: если, то конкатенацией, будем называть строку, полученную путём приписывания словак концу слова.
Для любого заданного алфавита операция конкатенации является ассоциативной операцией. Следовательно, по определению структура является полугруппой, однако не является абелевой полугруппой, в силу некоммутативности операции конкатенации.
Упражнение:Пустьопределим операцию на этом множестве с помощью таблицы Кейли:
Покажите, что структура является полугруппой, но не является абелевой полугруппой.
Определение:Моноидомназывается полугруппа, имеющая элемент идентичности.
Определение: Абелевым моноидомназывается абелева полугруппа, имеющая элемент идентичности.
Пример 1.15:Структура– абелев моноид с элементом идентичности 1. Структуране является моноидом, т.к. в этой структуре нет элемента идентичности.
Структуры ,– являются абелевыми моноидами с элементами идентичности 0 и 1 соответственно.
В примере 1.14 мы ввели операцию конкатенации на множестве слов некоторого алфавита. Если множество возможных слов пополнить пустой строкой , тои следовательно структураявляется моноидом.
Определение:Группойназывается моноид, у которого каждый элемент имеет обратный.
Определение:Абелевой группойназывается абелев моноид, у которого каждый элемент имеет обратный.
Пример 1.16:Структура– является абелевой группой с элементом идентичности 0 и обратным элементомдля.
Структура – является абелевой группой с элементом идентичности 1 и обратным элементомдля.
Пример 1.17:Введём на множествебинарную операциютак, что. Будет ли структурагруппой?
Проверим сначала операцию на ассоциативность:
Следовательно, введённая операция ассоциативна – и данная структура является полугруппой.
Проверим, имеет ли данная система элемент идентичности
т.к. элемент он является элементом идентичности, и рассматриваемая структура является моноидом. Удостоверимся в наличии обратного элемента.
следовательно существует обратный элемент. По определению структураявляется группой.
Задание:покажите, что структураявляется абелевой группой.