Вопросы.Дискретная Математика

Вопросы к экзамену по дискретной математике ПМ (1 семестр)

1. Множества. Способы задания множеств. Включение множеств. Транзитивность включения. Парадокс Рассела.

2. Объединение, пересечение, разность, дополнение, симметрическая разность множеств. Теорема о четырёх возможностях.

3. Вектор. Декартово произведение. Декартова степень множества. Проекции. Теорема о мощности декартова произведения конечных множеств. Теорема о количестве различных двоичных наборов размерности n.

4. Инверсия и композиция графиков. Свойства операций над графиками.

5. Соответствия. Свойства соответствий. Отображения и биекции.

6. Теорема о равномощных конечных множествах. Теорема о мощности множества всех подмножеств конечного множества.

7. Теорема о счетном подмножестве бесконечного множества. Критерий бесконечности множества.

8. Теорема о счётности множества рациональных чисел. Теорема Кантора о несчётности множества точек интервала (0,1).

9. Теорема о сравнении мощностей самого множества и множества всех его подмножеств.

10. Отношения. Свойства отношений.

11. Теоремы о связи разбиения множества с отношением эквивалентности.

12. Отношение эквивалентности. Факторизация отображений.

13. Отношения порядка. Единственность наибольшего и наименьшего элементов частично упорядоченного множества.

14. Булевы функции. Фиктивные и существенные переменные. Основные булевы функции от одной и двух переменных.

15. Булевы формулы. Упрощение формул.

16. Теорема о дизъюнктивном разложении по совокупности переменных. СДНФ. ДНФ.

17. Теорема о конъюнктивном разложении по совокупности переменных. СКНФ. КНФ.

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

19. Функциональная замкнутость и полнота. Классы T₀, T₁, L, S, их замкнутость.

20. Класс М. Теорема о ДНФ без отрицаний.

21. Лемма о несамодвойственной функции. Лемма о немонотонной функции. Теорема о слабой функцио­наль­ной полноте.

22. Лемма о нелинейной функции. Теорема Поста о функциональной полноте. Следствие.

23. Минимальная ДНФ, её нахождение с помощью алгоритма полного перебора. Теорема о сокращённой ДНФ. Теорема о сложности минимальной ДНФ.

24. Теорема о минимальной ДНФ. Метод Квайна для всюду определённых функций.

25. Теорема о минимальной ДНФ. Метод Карнау для всюду определённых функций.

26. Минимизация частичных функций методом Квайна. Метод Карнау для частичных функций.

27. Метод каскадов минимизации всюду определённых функций. Частные производные. Сложность формулы, полученной методом каскадов.

28. Метод каскадов для частичных функций. Метод Карнау для частичных функций.

29. Схемы из функциональных элементов. Анализ и синтез схем.

30. Контактная схема. Анализ контактной схемы. Метод каскадов построения контактных схем.

31. Тесты. Алгоритм нахождения минимального теста.