Дискретная математика, 1 курс ИС
Осенний семестр
Типовой расчет №1
Домашняя работа на несколько недель. В нем задания на темы: множества, бинарные отношения и булева алгебра.
В файлике находим себя, выполняем 5 заданий и сдаём преподавателю практики в уговоренный с ним день. Типовики можно исправлять после того как преподаватель укажет вам на ошибки.
Типовой расчет №2
Следующая большая домашняя работа. Темы: булевы функции и функциональная полнота.
План курса (каждая лекция может занимать 1-2 пары)
- Лекция 1. Вводные понятия теории множеств
- Множества и их элементы. Способы задания множеств. Подмножества. Операции над множествами. Законы де Моргана.Законы поглощения и склеивания. Диаграммы Эйлера-Венна. Декартово произведение множеств.
- Лекция 2. Бинарные отношения
- Понятие бинарного отношения. Способы задания отношений. Композиция отношений. Свойства бинарных отношений.Отношения эквивалентности. Отношения строгого\нестрогого порядка. Упорядоченные множества. Отношения соответствия. Функциональные отношения.
- Лекция 3. Математическая логика
- Высказывание. Булева алгебра. Аксиомы булевой алгебры. Свойства дизъюнкции и конъюнкции. Теоремы поглощения, склеивания, де Моргана. Теорема единственности дополнения.
- Лекция 4. Булевы функции
- Понятие булевой функции. Способы задания булевой функции. ДНФ. КНФ. Теорема о разложении ДНФ и КНФ. Макстерм. СКНФ. Минтерм. СДНФ. Единственность представления в СДНФ. Построение СДНФ и СКНФ по таблице истинности. Нахождение СКНФ через СДНФ. Минимизация булевых функций. Карты Крано\Вейча. Минимальные, сокращенные и тупиковые формы ДНФ. Перевод из КНФ в ДНФ и наоборот. Методы построения сокращенных форм.
- Лекция 5. Функциональная полнота
- Унарные и бинарные булевы функции. Суперпозиции. Полные системы функций. Полином Жегалкина. Единственность представления полиномом. Построение методом треугольника и Паскаля. Про классы эквивалентности. Теорема Поста с доказательством.
Источники