Дисципліна: Дискретна математика

Кількість годин (кредитів ЄКТС): 90 (3)

Мета навчальної дисципліни: забезпечити теоретичну підготовку для розробки систем зі складною структурою.

Результати навчання за навчальною дисципліною:

знати:

- основні поняття дискретної математики;

- теоретичні методи аналізу і синтезу дискретних об’єктів, що застосовуються при проектуванні сучасних засобів обчислюваної техніки;

- набути практичні навички щодо їх використання.

Зміст дисципліни (тематика):

Елементи теорії множин

Поняття множини, підмножина, порожня множина, універсальна множина, способи завдання множин, операції над множинами, діаграми Ейлера-Венна, тотожності алгебри множин, способи доказів тотожностей, рівняння алгебри множин, булеан, покриття і розбиття множин, потужність множин, теорема Кантора про існування незліченної множини, розмиті множини.

Елементи теорії відношень

Декартовий добуток множин, поняття відношення, види відношень, композиція відношень, бінарне відношення, властивості бінарних відносин, матриця бінарного відношення, відношення еквівалентності, класи еквівалентності, фактор множина, відношення порядку, функціональне відношення, теорема тотальної бієкції.

Елементи алгебраїчних систем

Поняття алгебраїчної системи, алгебраїчні системи з однією бінарною операцією: півгрупа, моноїд, група, морфізми алгебраїчних систем, алгебри з двома бінарними операціями: кільце, поле, гратка, булева алгебра.

Елементи комбінаторики

Комбінаторні конфігурації, біном Ньютона, розбивка множин, числа Стирлінга, поліноміальна формула, метод включень виключень, рекуррентні співвідношення, рішення лінійних рекуррентних співвідношень, твірні функції, операції над твірними фукціями.

Елементи алгебри логіки

Булеві функції, булеві функції двох змінних, основні тотожності алгебри логіки, ДНФ і КНФ, ДДНФ і ДКНФ, скорочена ДНФ і КНФ, тупикова і мінімальна ДНФ і КНФ, поняття суперпозиції, принцип подвійності булевих функцій, поліном Жегалкина, класи Поста, теорема Поста про функціональну повноту.

Елементи математичної логіки

Формальна теорія, поняття логічного виведення, числення висловлень, аксіоми, правило виведення, теорема дедукції, методи доказу у численних висловлень: конструктивний, аксіоматичний, метод резолюцій, логіка предикатів, квантор загальності, квантор існування, поняття формули, інтерпретація, основні тотожності логіки предикатів, сколемовська нормальна форма, аксіоми і правила виведення, метод резолюцій.

Мови, граматики та автомати

Мови, формальні породжуючі граматики, типи граматик, дерева виводу, форми Бекуса-Науера, скінчені автомати з виходом, скінчені автомати без виходу.

Види робіт: лекційні заняття, практичні заняття, модульні контрольні роботи, самостійна робота студентів.