- •Введение
- •Дискретная математика
- •Бинарная операция ассоциативна, если тождественно выполняется: ;
- •4.Классы булевых функций :
- •X1 x2 X
- •5. Теория полноты
- •I этап :
- •3 Случай :
- •II этап :
- •1); 2); 3); 4).
- •1) ; 2); 3);
- •4) ; 5);
- •5.4. Полные системы в классах т0, т1, м, s, l.
- •5.5 Базисы в классах t0 , t1, s, m, l Все полные системы для классов t0, t1, s, m, l в утверждениях выше являются базисами для этих систем.
- •6 .Минимизация булевых функций
- •1 Этап:
- •2 Этап:
- •Достаточно ясна связь задачи нахождения тупиковых покрытий и минимизации функции покрытия.
- •7. Исчисления высказываний
- •8. Семь теорем
- •Доказательство полноты исчисления высказываний.
- •Представление графов
- •1. Задание графа с помощью матрицы смежности.
- •2. Задание графа с помощью матрицы инцидентности.
- •3. Задание графа с помощью списка смежности.
- •Связные графы
- •Алгоритмы нахождения компонент связности
- •1. Поиск в ширину
- •2. Поиск в глубину
- •Укладки графов
- •Теорема Эйлера
- •Критерий Понтрягина-Куратовского
- •Раскраски графов
- •Основные понятия комбинаторики.
- •1 1.2 Упорядоченные наборы элементов изn-данных
- •1.3 Неупорядоченные наборы элементов изданных без повторений.
- •1.4 Неупорядоченные наборы элементов изп данных с возможными повторениями.
- •2 Метод включения-исключения.
- •Упражнения.
- •3 Метод производящих функций
- •1324 0100.
- •4 Основы теории перечисления Пойа. Лемма Бернсайда.
- •Упражнения.
- •Глава. Основы схем из функциональных элементов.
- •1) Мультиплексор порядка
- •2) Дешифратор порядка .
- •3) Универсальный многополюсник.
- •Глава. Введение в теорию конечных автоматов.
- •Глава. Введение в теорию кодирования.
- •Теория кодирования.
Основные понятия комбинаторики.
Упорядоченные наборы а элементов n данных с возможными повторениями.
Пример. Упорядоченные наборы 3-х элементов множества {1,2} — это упорядоченные множества
{111} {112} {121} {122} {211} {212} {221} {222}. Упорядоченные наборы называют также словами.
Теорема. Число упорядоченных наборов с возможными повторениями а элементов из n данных есть n.
Доказательство. Пусть F есть искомое число упорядоченных наборов с повторениями элементов изn данных. Тогда разобьем все упорядоченные наборы на n групп, где в i-тую группу войдут те наборы, которые начинаются на -ый элемент. В нашем примере, где n= 2 ,= 3 группы выглядят так:
1: 111, 112, 121, 122;
2: 211, 212, 221, 222.
Тогда число наборов в каждой группе равно числу
упорядоченных наборов -1 элементов изn данных, т. е. F, а число групп есть n. Поэтому
Пример 1. Дан алфавит из n букв . Найти число различных слов длины в этом алфавите.
Решение. Нетрудно видеть, что это число равно числу упорядоченных
наборов элементов из n данных, т. е .
Пример 2. Дано множество из n элементов . Найти число различных подмножеств этого множества.
Решение. Для каждого подмножества введем характеристический вектор длины n, компонента i которого равна 1, если входит в рассматриваемое подмножество, и 0 в противном случае. Тогда характеристический вектор (слово в {0,1} длиныn) однозначно определяет подмножество множества . Поэтому число подмножеств равно .
Пример 3. Пусть дано V — множество и множество Р некоторых упорядоченных пар . Тогда (V,P) называют ориентированным графом, V — множество вершин, Р — ориентированные ребра. Ребро называютпетлей. Полным ориентированным графом с петлями на множестве V называют граф со всеми ориентированными ребрами. Тогда число ребер в полном ориентированном графе равно .
1 1.2 Упорядоченные наборы элементов изn-данных
без повторения ().
Пример. , = 2. Тогда упорядоченные наборы без повторения:
.
Теорема. Число упорядоченных наборов элементов из n данных есть
где естьпроизведение.. Обозначают это число.
Доказательство. Пусть есть искомое число упорядоченных наборовэлементов изn данных без повторения. Тогда разобьем все эти наборы на n групп, в i-тую группу войдут наборы, начинающиеся на. Тогда число элементов вi-ой группе равно числу упорядоченных наборов - ого элемента из(— 1)-ого данного, так как элементы в наборе не повторяются, т.е. числу . Поэтому
т.к.
В нашем примере группы выглядят так:
Упорядоченный набор n элементов из n данных без повторения называют перестановкой: 1,2,3. Перестановки
{123} {132} {213} {231} {312} {321} .
Число перестановок из n- элементов есть (0! считаем равным 1).
Пример 1. Пусть (V, Р) — ориентированный граф. Полным
ориентированным графом называют граф, в котором присутствуют все
ориентированные ребра, кроме петель.
Тогда ориентированные ребра такого графа есть упорядоченные
пары из множества без повторений, и их число по доказанной теореме есть
Пример 2. Имеется n мест и человек. Скольким числом способов можно рассадить этих человек наместах.
Решение. 1. . Занумеруем места числами 1,2, ... ,. Тогда каждому упорядоченному наборуэлементов изсоответствует способ посадки. Поэтому искомое число есть
.
2. Занумеруем людей 1,2,.. ,.. Тогда каждому упорядоченному выбору элементов изданных соответствует способ посадки и наоборот. Поэтому искомое число есть