- •Раздел 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. Примеры синтеза автоматов
Тема 2.2. Подмножество, понятие универсального множества
Определение:Множествоявляетсяподмножеством, если любой элемент множествапринадлежит множеству. Это ещё называетсянестрогим включением.
Некоторые свойства подмножества:
– рефлективность;
– транзитивность;
т.е. пустое множество является подмножеством любого множества.
Пример 2.6:пусть – множество студентов некоторой группы, – множество отличников этой же группы. т.к. группа может состоять только из отличников.
Когда хотят подчеркнуть, что в множестве есть обязательно элементы, отличные от элементов множества , то пишут . Это называетсястрогим включением.
Пример 2.7:пусть – множество всех студентов университета, – множество студентов физико-технического института. т.к. в множестве всех студентов университета, обязательно есть элементы не принадлежащие .
Определение:Универсальное множество– это такое множество, которое строго включает в себя любое из рассматриваемых множеств, т.е..
Универсальное множество обычно обозначается .
Универсальное множество может выбираться самостоятельно, в зависимости от рассматриваемых множеств, и решаемых задач.
Пример 2.8: рассматривая множество студентов отдельной группы, в качестве универсального множества можно взять и множество студентов университета, и множество всех людей земли, и множество всех живых существ земли.
Рассматривая множество целых положительных чисел, в качестве универсального множества можно взять и множество целых чисел, и множество действительных чисел, и множество комплексных чисел.
Более подробно о свойствах универсального множества мы поговорим, обсуждая операции над множествами. Скажем только, что если роль нуля в алгебре множеств играет пустое множество. То универсальное множество, играет роль единицы в алгебре множеств.
Семейство всех подмножеств множества называется булеаном множестваи обозначается.
Пример 2.9:
Тема 2.3. Операции над множествами
Теперь определим операции над множествами.
Определение: Пересечениеммножествиназывается множество, состоящее из всех тех, и только тех элементов, которые принадлежат и множествуи множеству.
Пример 2.10:
ипересечением
Определение: Множества называютсянепересекающимися, если не имеют общих элементов, т.е. их пересечение равно пустому множеству.
Пример 2.11:непересекающимися множествами являются множества отличников группы и неуспевающих.
Данную операцию можно распространить и на большее чем два число множеств. В этом случае это будет множество элементов, принадлежащих одновременно всем множествам.
Свойства пересечения:
– коммутативности;
– ассоциативности;
– идемподентности;
;
;
;
, тогда и только тогда, когда.
Определение: Объединениемдвух множеств называется множество, состоящее из всех и только тех элементов, которые принадлежат хотя бы одному из множеств или .
Пример 2.12:
и объединением .
Данную операцию можно распространить и на большее чем два число множеств. В этом случае это будет множество элементов, принадлежащих хотя бы одному из этих множеств.
Свойства объединения:
– коммутативности;
– ассоциативности;
– идемподентности;
– принцип расширения;
Если , то;
;
.
Из свойств операций пересечения и объединения видно, что пустое множество аналогично нулю в алгебре чисел.
Теорема:1) ,
2) .
Доказательство:
1) , следовательно или , в этом случае или и , в обоих случаях по принципу расширения и , тогда .
Таким образом доказано, что .
Аналогично доказывается включение . Из этих двух включений и следует доказываемое равенство (дистрибутивность объединения множеств относительно пересечения слева).
Второе утверждение теоремы (дистрибутивность пересечения относительно объединения) доказывается аналогично.
Определение: Разностьюмножеств и называется множество, состоящее из всех тех и только тех элементов, которые принадлежат и не принадлежат .
Пример 2.13:
разность
Свойства разности множеств:
;
;
Если , то;
.
Теорема:
1. ;
2. ;
3. – дистрибутивность разности множеств относительно объединения справа;
4. – дистрибутивность разности множеств относительно пересечения справа.
Дополнением множества называется разностьи.
Свойства дополнения:
;
;
;
;
.
Определение: Симметричной разностьюмножеств и называется множество, состоящее их всех тех и только тех элементов, которые принадлежат и не принадлежати элементов, которые принадлежат и не принадлежат .
Пример 2.14: симметричная разность
Свойства симметричной разности:
;
;
;
;
;
если, тои.