- •Раздел 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. Примеры синтеза автоматов
Тема 3.2. Основные принципы комбинаторики
Теорема (принцип умножения)
Пусть имеется, групп элементов, причём -я группа содержитэлементов,. Выберем из каждой группы по одному элементу. Тогда общее число способов, которыми можно произвести такой выбор, равняется
Замечание:В теореме считается, что даже если все элементы в-й группе неразличимы, выбрать один из них можноспособами.
Замечание:Результат выбора, описанного в теореме, представим в виде наборав котором– выбранный из- й группы элемент. Тогда общее число различных наборовтакже равняется.
Доказательство:
Занумеруем элементы- ой группы числами от 1 до. Элемент из первой группы можно выбратьспособами. Если мы выбрали элемент,, то выбрать элемент из второй группы мы можемспособами. Получаем, что с первым элементомвозможно составитьпар, где.
Но столько же пар можно составить и с любым другим элементом первой группы. Тогда всего пар, в которых первый элемент выбран из первой группы, а второй - из второй, существует ровно .
Иначе говоря, есть способов выбрать по одному элементу из первых двух групп. Возьмём одну такую пару. Заметим, что элемент из третьей группы можно выбратьспособами, то есть возможно составить ровнотроек, добавляя к данной парелюбой изэлементов третьей группы.
Но столько же троек можно составить и с любой другой парой . Тогда всего троек, в которых первый элемент выбран из первой группы, второй - из второй, а третий - из третьей, существует ровно.
Продолжая рассуждения, методом математической индукции заключаем справедливость утверждения теоремы.
Рассмотрим некоторые примеры применения принципа умножения.
Пример 3.3:Даны два конечных множестваис числом элементовисоответственно. Требуется определить число элементов декартова произведения этих множеств, т.е..
Решение:
Из определения декартова произведения двух множеств следует, что любой элемент множества может быть получен в результате выполнения действия из двух этапов. Первый этап – выбрать произвольный элемент множестваи поместить его на первое место в упорядоченной паре, второй этап – выбрать произвольный элемент множестваи поместить его на второе место в паре. Теперь, согласно принципу умножения, получаем.
Следствие – обобщение:Аналогично, или используя метод математической индукции, можно доказать, что если даны конечные множествасто.
В частности, если – конечное множество с, то.
Пример 3.4:Пусть дано множествои множествои пусть на множествес областью значенийзадана функция. Спрашивается: сколько всего имеется различных функций указанного вида?
Решение:Каждую функциюможно задать следующей таблицей:
… |
… | ||||
|
|
Где – это тот элемент множествакоторый поставлен в соответствие. Нижняя строка таблицыесть кортеж длины, составленный из элементов множестват.е. элемент множества. Так как число различных элементов множествасогласно формуле предыдущего примера, равно, то имеется ровноразличных функций с областью определенияи областью значений.
Теорема (принцип сложения)
Если некоторое действие №1 можно осуществить способами, а действие №2 – способами, то осуществить «либо действие №1, либо действие №2» можно способами.
Справедливость теоремы очевидна. Например, если студенту необходимо попасть в лекционный корпус, к которому можно подъехать либо на одном из трёх автобусных маршрутов, либо на одном из четырёх трамвайных, то студент обязательно окажется около корпуса, воспользовавшись одним из семи маршрутов городского транспорта.
Пример 3.5: Сколькими способами из 28 костей домино можно выбрать две кости одну за другой так, чтобы вторую можно было приложить к первой?
Решение:
Если первой костью является дубль , то вторую можно приложить к первойспособами. Если первая кость не дубль, то вторую можно приложить к первойспособами. Теперь, последовательно применяя принцип умножения и принцип сложения, для искомого числа получаем
Теорема: Если и конечные подмножества некоторого универсального множества, то
Доказательство:Применим метод полной индукции. Рассмотрим последовательно все пять различных случаев «взаимного расположения» двух множеств и .
1. ,тогда
формула даёт – т.е. верное равенство;
2. ,тогда
формула даёт – т.е. верное равенство;
3. аналогично случаю 2;
4. , тогдаи формула даёт верное равенство.
5. , тогда в силу того, что общие элементы будут посчитаны дважды .
Установим общую формулу для определения числа элементов объединения конечного числа конечных множеств.
Теорема. Если конечные подмножества универсального множества, то
или
где есть сумма чиселпо всем возможным пересечениям ровноразличных множеств из множеств.
Доказательство:
Проведём доказательство методом математической индукции. Из формулы предыдущей теоремы следует, что приведённая формула справедлива для двух множеств, т.е. для .
Пусть формула верна для всех тогда последовательно получаем
Для того чтобы отсюда получить искомую формулу, остаётся принять во внимание, что
Следовательно, согласно принципу математической индукции, формула верна для любого натурального .
Следствие. Если, то
Пример 3.6:Каждый студент в группе - либо девушка, либо блондин, либо говорит по-английски. В группе 16 девушек, из них 6 блондинок, и 4 блондинки знают английский язык. Всего в группе 11 блондинов, по-английски из них говорят 8. Всего студентов, которые могут общаться на английском языке 20, из них 12 девушек. Сколько студентов в данной группе?
Решение:
Пусть – множество девушек,– множество блондинов,– множество студентов, которые знают английский язык. Тогдаискомое число студентов в группе;
– множество блондинок;
– множество девушек, которые говорят по-английски;
– множество всех блондинов (юношей и девушек), которые знают английский язык;
– множество блондинок, которые говорят по-английски. Из данных задачи следует, что
Теперь по формуле при получаем
.
Таким образом, в группе 25 студентов.