Дискретка Коллоквиум 1 семестр

Коллоквиум по дисциплине «Дискретная математика»

1. Множества и операции над ними (объединение, пересечение, разность, дополнение, симметрическая разность).

2. Свойства операций объединения и пересечения (доказательство).

3. Операция декартово произведение множеств и ее свойства (доказательство).

4. Бинарное отношение. Свойства отношений на множестве.

5. Мощность множества. Формула включения-исключения.

6. Дерево вариантов. Правила произведения и суммы.

7. Понятие выборки. Размещения без повторений. Размещения с повторениями. Перестановки. (Вывод формул).

8. Сочетания без повторений. Сочетания с повторениями. Перестановки с повторениями. (Вывод формул).

9. Бином Ньютона и его следствия. Полиномиальная формула. Треугольник Паскаля.

10. Основные булевы функции. Свойства булевых функций.

11. Способы задания булевых функций. Число булевых функций от n переменных (доказательство).

12. Элементарная конъюнкция (дизъюнкция). Приведенная конъюнкция (дизъюнкция). Правила приведения.

13. Дизъюнктивная нормальная форма. Совершенная дизъюнктивная нормальная форма. Представление булевой функции в виде СДНФ.

Разложение булевой функции в виде ДНФ по первым k переменным.

14. Конъюнктивная нормальная форма. Совершенная конъюнктивная нормальная форма. Представление булевой функции в виде СКНФ.

Разложение булевой функции в виде КНФ по первым k переменным.

15. Полином Жегалкина. Представление булевой функции в виде полинома Жегалкина. Способы построения.

16. Существенные и фиктивные переменные. Суперпозиция функций. Замыкание системы булевых функций.

17. Полная система булевых функций. Доказательство полноты системы . Примеры других полных систем.

18. Классы Т₀, Т₁, S, M, L. Примеры функций из этих классов.

19. Замкнутость классов Т₀, Т₁, S, M, L относительно суперпозиции (доказательство).

20. Критерий Поста. Доказательство необходимости критерия Поста.

21. Лемма о несамодвойственной функции (доказательство).

22. Лемма о немонотонной функции (доказательство).

23. Лемма о нелинейной функции (доказательство).

24. Критерий Поста. Доказательство достаточности критерия Поста (без доказательств соответствующих лемм).

25. Предполный класс. Замкнутость предполного класса относительно суперпозиций (доказательство).

26. Предполнота классов Т₀, Т₁, S, M, L (доказательство).

27. Система функций полная в замкнутом классе. Примеры полных и неполных в замкнутом классе систем.

28. Базис в замкнутом классе. Примеры базисов и не базисов.

29. Зависимость функции от системы функций. Независимость любой функции базиса от оставшихся функций базиса (доказательство).

30. Оценка числа функций в базисе (доказательство).