- •Федеральное государственное бюджетное образовательное учреждение высшего профессионального образования «кемеровский государственный университет»
- •Кафедра автоматизации исследований
- •И технической кибернетики
- •Дискретная математика
- •Содержание
- •Глава 1. Теория множеств. Дискретная теория вероятности......5
- •Глава 2. Теория графов.....................................................................53
- •Глава 3. Дискретные структуры: конечные автоматы, коды...76
- •Глава 4. Алгебра логических функций..........................................88
- •Глава 5. Логика высказываний и логика предикатов..............109
- •Глава 6. Схемы переключателей. Комбинационные схемы...................................................................................................123
- •Глава 1. Теория множеств. Дискретная теория вероятности
- •Множества и операции над ними
- •Упражнения
- •1.2. Векторы и прямые произведения множеств. Проекция вектора на ось
- •Упражнения
- •1.3. Комбинаторика Правило суммы
- •Правило произведения
- •Число размещений без повторений
- •Число размещений с повторениями
- •Число перестановок без повторений
- •Число сочетаний без повторений
- •Упражнения
- •1.4. Введение в дискретную теорию вероятностей
- •Свойства элементарных событий:
- •Соотношения между событиями:
- •Свойства операций над событиями:
- •Упражнения
- •1.5. Соответствия и функции
- •Взаимно однозначные соответствия и мощность множеств
- •Упражнения
- •1.6. Отношения
- •Способы задания бинарных отношений
- •Свойства бинарных отношений
- •Отношение эквивалентности
- •Отношение порядка
- •Лексико-графический порядок.
- •Упражнения
- •1.7. Операции и алгебры
- •Свойства бинарных алгебраических операций
- •1.8. Гомоморфизм и изоморфизм алгебр
- •Полугруппы, группы, решетки
- •Упражнения
- •Глава 2. Теория графов
- •2.1. Основные определения, способы задания, основные классы, изоморфизм графов
- •Способы задания графа
- •Степени вершин графа
- •Части, суграфы и подграфы
- •Операции над частями графа
- •Графы и бинарные отношения
- •Упражнения
- •Среди пар графов, изображенных на рисунке, указать пары изоморфных графов и пары неизоморфных графов. Ответ обосновать.
- •Маршруты, цепи и циклы. Расстояния, диаметры, центры. Обходы. Разделяющие множества и разрезы
- •Упражнения
- •Деревья, их свойства. Характеристические числа графов. Сети
- •Упражнения
- •Глава 3. Дискретные структуры: конечные автоматы, коды
- •3.1. Машина Тьюринга
- •Упражнения
- •Основы теории кодирования
- •Упражнения
- •Глава 4. Алгебра логических функций
- •4.1. Основные определения
- •Упражнения
- •4.2. Эквивалентные преобразования
- •Упражнения
- •4.3. Дизъюнктивные и конъюнктивные нормальные формы
- •Упражнения
- •4.4. Дизъюнктивные нормальные формы и импликанты
- •Упражнения
- •4.5. Минимизация днф. Тупикова днф
- •Упражнения
- •4.6. Алгебра Жегалкина
- •Упражнения
- •4.7. Двойственность в алгебре логики. Самодвойственные функции
- •Принцип двойственности
- •Упражнения
- •4.8. Функциональная полнота систем
- •Упражнения
- •Глава 5. Логика высказываний и логика предикатов
- •5.1. Логика высказываний
- •Алгебра логики
- •Исчисление высказываний
- •Упражнения
- •5.2. Логика предикатов
- •Упражнения
- •Глава 6. Схемы переключателей. Комбинационные схемы
- •Схемы переключателей
- •Комбинационные схемы
- •Упражнения
- •Литература
- •650043, Кемерово, ул. Красная, 6.
1.3. Комбинаторика Правило суммы
Классическая формулировка
Если элемент можно выбрать k способами, а элемент можно выбрать m способами. Тогда или можно выбрать k +m способами.
Современная формулировка (теорема о мощности объединения множеств)
Количество элементов объединения двух множеств равно сумме количества элементов в первом и во втором множестве, за вычетом количества элементов их пересечения:
.
Причем, если множества не пересекаются, то теорема приобретает вид, аналогичный классической формулировке:
.
Для трех множеств теорема имеет вид:
.
Общее правило для имеет вид::
Пример. Староста одного курса дал следующие сведения о студентах: ”На курсе учатся 45 человек, в том числе 25 юношей. 30 человек учатся на хорошо и отлично, в том числе 16 юношей. Спортом занимаются 28 человек, в том числе 18 юношей и 17 человек, учащихся на хорошо и отлично. 15 юношей учатся на хорошо и отлично и занимаются спортом.” Проверьте правильность приведенных старостой сведений.
Для проверки правильности (непротиворечивости) приведенных данных используем теорию множеств и введем следующие обозначения.
К роме того, для наглядности, изобразим полученные данные на диаграмме Венна.
Множество юношей обозначим буквой Ю, и по данным старосты количество юношей .
Множество спортсменов обозначим С и .
Множество отличников и хорошистов обозначим О и .
При этом из условия, что 30 человек учатся на отлично и хорошо, в том числе 16 юношей, имеем .
Из условия, что спортом занимаются 28 человек, в том числе 18 юношей и 17 человек, учащихся на отлично и хорошо, следует и .
Из условия, что 15 юношей учатся на отлично и хорошо и занимаются спортом, следует .
По правилу суммы, исходя из полученных от старосты данных, общее количество студентов курса, т.е. , должно быть равно
.
Однако это противоречит исходному условию, что на курсе учатся всего 45 студентов.
Таким образом, в сведениях, поданных старостой курса, содержится ошибка.
Правило произведения
Классическая формулировка
Если элемент можно выбрать k способами, а элемент можно выбрать m способами. Тогда и можно выбрать km способами.
Современная формулировка (теорема о мощности прямого произведения множеств)
Количество элементов прямого произведения двух множеств равно произведению количества элементов первого и второго множества:
.
Пример. Из 3 экземпляров учебника алгебры, 7 экземпляров учебника геометрии и 6 экземпляров учебника физики, надо выбрать комплект, содержащий все учебники по одному разу. Сколькими способами это можно сделать?
Множество А – учебники по алгебре, В – учебники по геометрии, С – по физике. Надо составить и пересчитать все тройки из множества .
Число размещений без повторений
Число размещений без повторений из n по k – это число способов, сколькими можно из n различных элементов построить векторов с k различными координатами.
Число размещений без повторений находится по формуле:
.
Пример: Сколькими способами можно построить 3-значное число с различными цифрами, не содержащее цифры 0?
Количество цифр , размерность вектора с различными координатами