Мартинюк О.М. Конспект лекцій з дисципліни Основи дискретної математики

Для студентів очної і заочної форм навчання напрямку 6.0804 і 6.0915 інституту комп’ютерних систем. — Одеса: ОНПУ, 2004. — 224 с. Конспект лекцій з дисципліни «Основи дискретної математики» містить виклад основних визначень, операцій і властивостей п’яти базових розділів дискретної математики – теорії множин і алгебраїчних систем, комбінаторики, графів, кінцевих автоматів та булєвої алгебри, що є орієнтований на прикладні задачі комп'ютерних спеціальностей. Теорія множин і алгебраїчних систем.
Основні поняття теорії множин.
Рівняння. Покриття і розбивки. Потужність.
Упорядковані множини. Графіки.
Відповідності, образи і прообрази. Відображення і діаграми.
Відношення.
Спеціальні операції над відношеннями.
Основні властивості відношень.
Спеціальні види відношень.
Замикання. Спеціальні функції. Операції.
Закони композиції.
Алгебраїчні системи.
Комбінаторіка.
Комбінаторика. Базові методи.
Комбінаторика. Додаткові методи.
Графи.
Визначення і представлення графів.
Визначення графів. Зважені графи.
Теоретико-множинні операції над графами.
Характеристики графів. Представлення у ЕОМ.
Кінцеві автомати.
Функціонування абстрактного автомата.
Синхронні та асинхронні автомати. Перетворення.
Композиції автоматів.
Мережі автоматів.
Булєва алгебра.
Булєві функції.
Завдання булєвих функцій. Приведення формул.
Булєва алгебра. Спрощення. Подвійність.
Алгебра Жегалкіна. Типи функцій. Логічні схеми.
Графічна та таблична мінімізація.
Аналітична мінімізація. Базові методи.
Аналітична мінімізація. Додаткові методи.
Матричні форми.
Алгоритм побудови максимальних інтервалів.
Мінімізація систем булєвих функцій.
Інтервальні форми і їхні перетворення.
Використання інтервальних операцій.
Булєві рівняння й нерівності.
Булєві диференціали й похідні.
Логіка предикатів.