 |
Главная Случайная страница Контакты | Мы поможем в написании вашей работы! | |
Учебное пособие. Клашанов Ф. К. Дискретная математика
|
|
Москва 2011
Клашанов Ф. К. Дискретная математика. Курс лекций. Учебное пособие. М.: МГСУ, 2011. – 198 с.
В учебном пособии по дискретной математике представлены материалы в помощь бакалаврам, изучающим дискретную математику в Московском государственном строительном университете на факультете ИСТАС и обучающихся по направлению подготовки 230100 «Информатика и вычислительная техника», а профиль подготовки: Автоматизированные системы обработки информации и управления в строительстве (АСОИУ) и Системы автоматизации проектирование (САПР) в строительстве. Учебное пособие представляет собой единый методически взаимоувязанный материал, состоит из следующих взаимосвязанных разделов: элементы теории множеств; сведения из булевой алгебры; элементы комбинаторики; основы теории графов. Учебное пособие взаимосвязано с методическими пособиями по практическим и самостоятельным работам, в которых даются математические понятия приведенные в учебном пособии. Материал рассчитан на односеместровое занятие на 108 часов, куда входят аудиторные и самостоятельные занятия. В конце каждой темы приведены вопросы для самоконтроля.
Учебное пособие будет полезно при изучении курса «Дискретная математика».
СОДЕРЖАНИЕ
| Лекция 1 …………………………………………………………………………………. ВВЕДЕНИЕ ……………………………………………………………………... Цель и задачи предмета ………………………………………………………. Предмет дискретной математики ……………………………………………. Основные разделы дискретной математики ………………………………. Изоморфизм …………………………………………………………………… Контрольные вопросы ………………………………………………………………… | |
| Лекция 2 …………………………………………………………………………………. ОСНОВЫ ТЕОРИИ МНОЖЕСТВ…………………………………………………... Интуитивное понятие множества. Основные принципы …………………. Множество и элементы множества …………………………………………. Конечные и бесконечные множества ……….………………………………. Задание множества.…………………………………………………………….. Мощность множества …………………………………………………………... Подмножество, собственное подмножество ……………………………….. Кортеж …………………………………………………………………………… Символический язык содержательных теорий множеств ……………… Добавление и удаление элементов …………………………………………. Булеан и универсумом ………………………………………………………. Диаграммы Венна (Круги Эйлера) …………………………………………… Ограниченные множества. Границы множеств ……………………………. Точная верхняя (нижняя) граница ………………………………………….. Принцип двойственности ……………………………………………………… Линейные пространства ………………………………………………………... Контрольные вопросы ………………………………………………………………… | |
| Лекция 3 …………………………………………………………………………………. ОПЕРАЦИИ НАД МНОЖЕСТВАМИ……………………………………………... Симметрическая разность ……………………………………….……………. Дополнение ………………………….…………………………………………. Двуместные операции ……….…………………………………………………. Порядок выполнения операций.…………………………………………….. Теоретико-множественные тождества ……………………………………… Законы для объединения и пересечение …………………………..………. Законы для дополнений ………………………………………………………. Законы для разностей множеств …………….………………………………. Покрытие и разбиение множеств …..……………………………………… Частично упорядоченные множества …………………………………………….. Контрольные вопросы ………………………………………………………………… | |
| Лекция 4 …………………………………………………………………………………. ОТНОШЕНИЯ. ОТОБРАЖЕНИЯ. СООТВЕТСТВИЯ…………………………... Бинарные отношения …………………………………………….……………. Свойства бинарных отношений ………………………………………………. Отношение эквивалентности ……………………………………………. Отношениетолерантности.……………………………………………….. Отношения порядка ………………………………..……………………… Тернарные отношения ………………………………………………………… n- арные отношения …………………………..…………………………………. Отображения ……………………………………………………………………. Соответствие ……………………..………….…………………………………. Функция …..………………………………………………………..…………… Представление функции в терминах отношений ………………………….. Функции, функционалы, операторы ………………………………………….. Суперпозиция бинарных отношений ………………………………………. Обратная функция ………………………………………………………………. Классификация отображений ……………………………………………….. Операция ………………………………………………………………………… Частично упорядоченные множества ……………………………………….. Минимизации представления множества ………………………………….. Контрольные вопросы ………………………………………………………………… | |
| Лекция 5 …………………………………………………………………………………. ЭЛЕМЕНТЫ КОМБИНАТОРИКИ……….….……………………………………... Основные правила комбинаторики …………..………………………………. Правило произведения ……………………………………………………. Правило сумм ………………………………………………………………. Перечислительная комбинаторика ………………………………………….. Перестановки ………………………….…………………………………… Размещения ……………………………….………………………………… Размещения с повторениями …………….…………………….………. Упорядоченное размещение ……………………………………………. Сочетания ………………………….………………………………………. Сочетания с повторениями ……..………………………………………… Комбинации элементов с повторениями ……………………………… Бином Ньютона …………………………………………………………………. Разбиения. Комбинаторные числа Стирлинга и Белла …………………. Числа Стирлинга 2-го рода ……………………………………………... Метод производящий функций ………………………………………………... Контрольные вопросы ………………………………………………………………… | |
| Лекция 6 …………………………………………………………………………………. АЛГЕБРАИЧЕСКАЯ СИСТЕМА……….…………………………………………... Замыкание и подалгебры ………………………………………….……….… Морфизмы …..…………………….……………………………………………. Гомоморфизмы …………..…………………………………………………. Фундаментальные алгебры.……………….………………………………….. Алгебры с унарными операциями ……...…………………………………… Алгебры с бинарными операциями ………………………………………… Алгебры с одной бинарной операцией …………………………..…………. Полугруппа ………………………….……………………………………………. Моноид …………………………..…………….…………………………………. Группоид …..…………………………….……………………………………… Группа ……………………………………………………………………………… Абелева группа ………………………………………………………………… Алгебра с двумя операциями ……………………………………………….. Кольца ……………………….………………………………………………… Тело ……………………………………………………………………………. Поля …………………………………………………………………………… Отношения ……………………………………………………………………… Граф ……………………………………………………………………………… Матрица смежности ……………………………………………………………. Фактор-множества и фактор-алгебра …………………………………………… Целые числа по модулю m ………………………………………………………… Конгруэнции ………………………………………………………………………. Контрольные вопросы ………………………………………………………………… | |
| Лекция 7 …………………………………………………………………………………. ЭЛЕМЕНТЫ ТЕОРИИ ГРАФОВ…….……………………………………………... Определение ……………………………………….……………. ………………... Граф, вершина, ребро …………………………….………………………….……. Неориентированный граф ……….……………………………………………. Инцидентность, смешанный граф.…………………………………………….. Эквивалентный ориентированный граф ……………………………………… Обратное соответствие …………………….……………………………………… Изоморфизм графов ……………………………………..………………..………. Путь, ориентированный маршрут ………………………………………………. Смежные дуги, смежные вершины, степень вершины ………………………. Компонентная связность ………………...……………………………………… Граф со взвешенными дугами …………...……………………………………… Подграф …………...……………………………………………………………..… Контрольные вопросы ………………………………………………………………… | |
| Лекция 8 …………………………………………………………………………………. ДЕРЕВЬЯ…….…………………………………………………………………..……... Свободные деревья …………………………….……………. ………………... Ориентированные, упорядоченные и бинарные деревья …….………………….. Упорядоченные деревья ………………………………………………………. Представление деревьев в компьютере ………………………………………….. Контрольные вопросы ………………………………………………………………… | |
| Лекция 9 …………………………………………………………………………………. БУЛЕВА АЛГЕБРА...………………………………………………………………..... Основные логические функции ………………………………………………….. Булева функция ……………………………………………………….……………. Двухэлементная булева алгебра ……………………………………. ……………. Функции одной переменной y = f(x) ………………………………...................... Таблицы булевых функций ………………………………………………………. Функции двух переменных z = f(x,y) ……………………………………………… Порядок выполнения операций …………………………………………………… Эквивалентность формул …………………………………………………………. Графический способ задания булевой функции …………………………………. Фактор-алгебра алгебры формул ………………………………………………….. Контрольные вопросы ………………………………………………………………… | |
| Лекция 10 …………………………………………………………………………………. ДИЗЪЮНКТИВНЫЕ И КОНЪЮНКТИВНЫЕ НОРМАЛЬНЫЕ ФОРМЫ Определение ………………………….…………………………………………. Алгоритм приведения формулы к ДНФ ….……………………………………. Совершенные ДНФ (СДНФ) и КНФ (СКНФ) ……………………………….. Первая теорема Шеннона ……………….……………………………………… Вторая теорема Шеннона ………………………………………………………… Функциональная полнота ……………………………………………………..………. Алгоритм нахождения СДНФ ………………………………………………………. Минимизация булевых функций в классе ДНФ ….…………………………………. Метод Квайна …..……………………………………………………….. Контрольные вопросы ………………………………………………………………… | |
| Лекция 11 …………………………………………………………………………………. ПОЛНЫЕ СИСТЕМЫ БУЛЕВЫХ ФУНКЦИЙ ………………………………. Каноническое представление логических функций …………………………….. Системы булевых функций ….…………………………………………………. Теорема (о двух системах) ………..…………………………………………….. Базис Жегалкина ………………..……………………………………………… Классы булевых функций ………………………………………………………. Теорема (Пост-Яблонского) …………………………..…………………………. Теорема (Пост) ……………………………………………………………………. Алгебра Жегалкина …………………………….…………………………………. Контрольные вопросы ………………………………………………………………… | |
| Лекция 12 …………………………………………………………………………………. ЛОГИКА ВЫСКАЗЫВАНИЙ………………………………………………………. Определения ………………………….…………………………………………. Формулы логики высказываний………………………………………………. Порядок выполнения операций.…………………………………………….. Правила преобразования формул ……………………………………… Основные равносильности ……………..……………………………………… Правило перехода к булевым функциям …………………………..………. Нормальные формы формул логики высказываний ………………………. Законы логики высказываний. Тавтологии.…………………………………. Контрольные вопросы ………………………………………………………………… | |
| Лекция 13 …………………………………………………………………………………. ЛОГИКА ПРЕДИКАТОВ………………………………………………………. Определение предиката …………………………………………………………. Язык логики предикатов……….…………………………………………………. Логические операции (связки) над предикатами………………………….…….. Кванторы ………………………………………………….………………………… Квантификация многоместных высказывательных форм ……………………… Булева алгебра предикатов …………………………………..…………..………. Формулы ……………………..…………………………………………………. Алгоритм преобразования формул в нормальную форму……………………. Исчисление предикатов …..……………………………………………………… Следование и эквиваленция ……………………………………………………… Правила вывода исчисления предикатов ……………………………………….. Отрицания в исчислении предикатов ……………………………………………. Контрольные вопросы ………………………………………………………………… |
Дата публикования: 2014-11-04; Прочитано: 826 | Нарушение авторского права страницы | Мы поможем в написании вашей работы!
