examDM_2014_1half

Запитання на екзамен:

Логіко-математична символіка, властивості логічних зв’язок (включаючи квантори)

Операції над множинами та їхні властивості

Сім’ї множин. Операції над ними

Декартів добуток та його властивості

Операція взяття образу множини при відповідності

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

Спеціальні види відповідностей та їх властивості

Рефлексивні відношення та їх властивості

Антирефлексивні відношення та їх властивості

Симетричні відношення та їх властивості

Антисиметричні відношення та їх властивості

Транзитивні відношення та їх властивості

Замикання відношень та їх властивості

Терміни «замикання», «замкнений» у математиці

Еквівалентності. Фактор-множина. Поняття канонічного елемента

ЧВМ. Їх різновиди. Прямий добуток порядків. Лексикографічний порядок

Найбільший/найменший, максимальний/мінімальний елементи ЧВМ. Питання їх існування та єдиності для різних видів ЧВМ

Комбінаторні правила. Комбінаторні обчислення для теоретико-множинних операцій

Комбінаторні об’єкти. Означення та правила підрахунку

Біном Ньютона та доведення тотожностей з біноміальними коефіцієнтами

Поліноміальна теорема

Числа Каталана. Метод траєкторій

Канонічні форми (ДДНФ, ДКНФ, поліном Жегалкіна) в теорії булевих функцій

Формули, функції, суперпозиції функцій

Замкнені класи булевих функцій

Екзаменаційний білет (максимум = 40 балів) складатиметься не більш ніж з 7 завдань таких типів

1. Теоретичне запитання (див. перелік вище)

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

3. Задача на доведення теоретико-множинної тотожності

4. Задача на суму з біноміальними коефіцієнтами

5), 6), 7) – задачі, аналогічні задачам з методички («Вступ до ДМ»), файлу «Задачі з комбінаторики» (№№1-126) та можливо деякі, що формулювались як теореми/твердження/вправи на лекціях.