- •Буковинський університет
- •Дискретна математика
- •Навчально-методичний посібник
- •Чернівці
- •Задачі та вправи 12
- •Задачі та вправи 28
- •Операції над множинами
- •Тема „Алгебра лінійних множин”
- •Способи задання множин
- •Порожня множина ()
- •Універсум (u)
- •Множина підмножин
- •Алгебра множин
- •Узагальнення операцій над множинами
- •Задачі до теми „Алгебра лінійних множин”
- •Тема „Відношення і функції”
- •Окремі випадки відношень
- •Властивості композицій:
- •Властивості відношень
- •Основні властивості відображень
- •Відношення еквівалентності
- •Відношення порядку
- •Відношення рівнопотужності
- •Властивості скінченних множин
- •Властивості зчисленних множин
- •Задачі до теми „Відношення і функції”
- •Тема „Булеві функції”
- •Способи задання булевих функцій
- •Булеві функції однієї змінної
- •Область визначення булевих функцій
- •Елементарні функції алгебри логіки
- •Булевий простір
- •Властивості функцій
- •Деякі операції над висловленнями
- •Формули в алгебрі логіки
- •Основні тотожності
- •Правила
- •Принцип двоїстості
- •Типи булевих функцій
- •Канонічні форми перемикальних функцій
- •Досконалі диз’юнктивні нормальні форми перемикальних функцій
- •Досконалі кон’юнктивні нормальні форми перемикальних функцій
- •Властивості досконалих форм
- •Скорочена диз’юнктивна нормальна форма перемикальних функцій
- •Утворення скороченої диз’юнктивної нормальної форми методом Квайна
- •Метод Квайна-Маккласкі
- •Утворення мінімальних кон’юктивних нормальних форм
- •Алгоритм утворення мінімальної кнф
- •Геометричне подання функцій алгебри логіки
- •Спрощення булевих функцій
- •Задачі до теми „Способи задання булевих функцій. Операція суперпозиції”
- •Задачі до теми „Істотні та фіктивні змінні”
- •Задачі до теми „Спеціальні види формул. Диз’юнктивні і кон’юнктивні нормальні форми. Поліном Жегалкіна”
- •Задачі до теми „Замкнуті класи і повнота системи булевих функцій” Важливіші замкнуті класи булевих функцій
- •Задачі до теми „Класи функцій, що зберігають константи”
- •Задачі до теми „Двоїстість і клас самодвоїстих функцій”
- •Задачі до теми „Монотонність і клас монотонних функцій”
- •Повнота систем булевих функцій
- •Тема „Рекурсивні функції”
- •Частково-рекурсивні функції
- •Тема „Скінченні автомати. Машина Тьюринга”
- •Машина Тьюринга
- •Тема „Основні поняття і властивості алгоритмів”
- •Основні вимоги до алгоритмів
- •Основні властивості алгоритму
- •Тема „Формальні системи. Алгебра висловлювань”
- •Аксіоматичний спосіб опису висловлювань
- •Властивості числення висловлювань
- •Задачі до теми „Алгебра висловлювань”
- •Тема „Логіка і числення предикатів”
- •Рівносильність формул
- •Задачі до теми „Логіка і числення предикатів”
- •Тема „Алгебри. Типи алгебр. Алгебраїчні системи”
- •Гомоморфізм та ізоморфізм алгебри
- •Типи алгебр
- •Алгебраїчні системи
- •Тема „Елементи комбінаторики”
- •Формула включень і виключень
- •Рекурентні співвідношення
- •Основні властивості кількості сполук
- •Біном Ньютона
- •Властивості розкладу бінома Ньютона і біномних коефіцієнтів
- •Поліномні твірні функції
- •Розміщення і функціональні відображення
- •Розбиття
- •Поліномна формула
- •Задачі до теми „Комбінаторика”
- •Тема „Графи”
- •Задання графа за допомогою матриці інцидентності та списку ребер
- •Задання графа за допомогою матриці суміжності
- •Локальні степені вершин графа
- •Частини графа, суграфи та підграфи
- •Операції з частинами графа
- •Маршрути, ланцюги та цикли
- •Цикломатичне число графа
- •Задачі до теми „Графи”
- •Дискретна математика
- •Література
- •Навчальне видання Пукальський Іван Дмитрович,
- •Лусте Ірина Петрівна,
Література
Бардачов Ю.М., Соколова Н.А., Ходаков В.Є. Дискретна математика. – К.: Вища шк., 2002. – 287 с.
В.І.Андрійчук, М.Я.Комарницький, Ю.Б.Іщук. Вступ до дискретної математики. – К.: Центр навчальної літератури, 2004. – 254 с.
Бортей М.С., Свердан М.Л., Якімов І.В. Дискретна математика: Методичні вказівки та завдання (для студентів математичного факультету). – Чернівці: Рута, 2000. – 94 с.
Яблонский С.В. Введение в дискретную математику. – М.: Наука, 1989. – 384 с.
Нефедов В.Н., Осипова В.А. Курс дискретной математики. – М.: Изд-во МАИ, 1992. – 264 с.
Берж К. Теория графов и ее применение. – М.: Изд-во иностр. лит, 1962.
Эйдельман С.Д. и др. Основы дискретной математики. – К.: КВИРТУ ПВО, 1978. – 128 с.
Гаврилов Г.П., Сапоженко А.А. Сборник задач по дискретной математике. – М.: Наука, 1977. – 386 с.
Ершов Ю.Л., Палютин Е.А. Математическая логика. – М.: Наука, 1987. – 336 с.
Навчальне видання Пукальський Іван Дмитрович,
кандидат фізико-математичних наук,
Лусте Ірина Петрівна,
кандидат фізико-математичних наук
Дискретна математика
Навчально-методичний посібник
Науковий редактор- В.М.Окуненко,
Комп’ютерний набір – Н.В.Романенко
Комп’ютерна верстка – Н.В.Романенко
Підписано до друку _______. Формат 6084/16.
Папір офсетний. Друк офсетний. Умов. друк. арк. ______.
Обл.-вид. арк. ____. Зам. _____. Тираж _____
Д