13. Отношения порядка. Диаграмма Хассе.

Отношение нестрогого порядка – это отношение, обладающее свойствами рефлексивности, антисимметричности и транзитивности.

Отношение строго порядка – это отношение, обладающее свойствами антирефлексивности, антисимметричности и транзитивности.

Для обоих типов отношений порядка, элементы и сравниваются по отношению порядка , если выполняется или.

Множество, на котором задано отношение порядка, называется линейно (полностью) упорядоченным, если любые два элемента множества сравнимы, а в в противном случае - частично упорядоченным.

Пример

Отношения идля чисел являются отношениями нестрого порядка, отношения < и > – отношениями строгого порядка.

Диаграмма Хассе – это графическое изображение частично или линейно упорядоченных множеств.

Диаграмма Хассе строится сле­дующим образом. Меньшие по порядку элементы располагают ниже, а большие – выше; и проводят линии, показывающие, какой из двух элементов больше, а какой меньше другого.

14. Алгебра. Тип алгебры, сигнатура. Примеры.

Сигнатура алгебры – это множество операций.

Тип алгебры – последовательность рангов операций входящих в сигнатуру.

Ранг операции – к-во операндов.

15. Замыкания и подалгебры.

Про подалгебры:

Алгебра Вета – подалгебра однотипной ей алгебры Альфа, если B – подмножество А и тождественное отображение множества В в А является мономорфизмом, то есть каждая главная операция алгебры Вета является ограничением соответствующей операции алгебры Альфа множеством В.

Про замыкания:

Замыкание в общей алгебре — минимально возможное расширение заданного множества относительно заданного набора алгебраических операций, в котором любое применение этих операций к элементам такого расширения не выходит за его пределы.

16. Свойства бинарных операций. Примеры.

Коммутативность (переместительность)

Свойство бинарной алгебраической операции при котором выполняется условие: где — некоторое рассматриваемое множество.

Примеры:

• Сумма и произведение действительных чисел

• Конъюнкция и дизъюнкция

• объединение, пересечение и симметрическая разность множеств

Ассоциативность (сочетательность)

Свойство бинарной алгебраической операции при котором выполняется условие: где — некоторое рассматриваемое множество.

Примерами ассоциативных операций являются:

• сложение действительных чисел:

• {\displaystyle (a+b)+c=a+(b+c)}умножение действительных чисел:

• {\displaystyle (a\cdot b)\cdot c=a\cdot (b\cdot c)}композиция функций

Дистрибутивность (распределительный закон ) — свойство согласованности двух бинарных операций, определённых на одном и том же множестве.

Говорят, что две бинарные операции «+» и «×» удовлетворяют свойству дистрибутивности, если для любых трёх элементов:,

дистрибутивность слева;

дистрибутивность справа.

17. Комбинаторные задачи. Модели комбинаторных задач

Комбинаторные задачи – это задачи, требующие осуществления перебора всех возможных вариантов или подсчета их числа.

18. Правила суммы и произведения. Формула включения и исключения.

Правило суммы. Пусть некоторый объект A можно выбрать n различными способами, а другой объект B можно выбрать m способами. Тогда существует  n+m способов выбрать либо объект A, либо объект B. 

Правило произведения. Пусть объект A можно выбрать n способами и после каждого такого выбора объект B можно выбрать m способами. Тогда выбор пары (A,B) можно осуществить n*m способами.

Формула включения-исключения — комбинаторная формула, выражающая мощность объединения конечных множеств через мощности всех множеств и мощности всех их возможных пересечений.

Для случая из двух множеств  формула включения-исключения имеет следующий вид:

18. Основные типы наборов комбинаторики: размещения, сочетания, перестановки.

18. Подсчет разбиений в комбинаторике.