ВУЗ:
Составители:
Рубрика:
2
Программа экзамена по дискретной математике.
1. Понятие множества. Операции над множествами. Диаграм-
мы Эйлера-Венна.
2. Мощность множества. Счетные множества.
3. Прямое произведение множеств. Понятие n-местного отно-
шения.
4. Соответствия между множествами. Функции. Инъекция,
сюръекция, биекция.
5. Отношения. Бинарные отношения. Свойства отношений.
6. Отношение эквивалентности. Связь между отношением эк-
вивалентности и разбиением множества.
7. Отношения частичного и строгого порядка.
8. Булевы функции одной и двух переменных.
9. Булевы функции. Способы задания. Существенные и фик-
тивные переменные.
10. Булевы формулы. Свойства логических операций.
11. Разложение булевой функции по переменным. Алгоритмы
построения совершенной дизъюнктивной нормальной фор-
мы и совершенной конъюнктивной нормальной формы.
12. Свойства суммы по модулю 2. Алгоритм построения полино-
ма Жегалкина.
13. Замкнутые классы функций. Классы
0
T ,
1
T
, S , M, L.
14. Функционально полные системы. Теорема о функциональ-
ной полноте двух систем функций. Теорема Поста.
15. Схемы из функциональных элементов.
16. Основные задачи комбинаторики. Правило суммы. Правило
произведения.
17. Формулы числа перестановок, размещений и сочетаний без
повторений и с повторениями.
18. Формула включения и исключения. Задача о беспорядках.
19. Понятие рекуррентного соотношения. Линейные рекур-
рентные соотношения. Метод решения.
Программа экзамена по дискретной математике.
1. Понятие множества. Операции над множествами. Диаграм-
мы Эйлера-Венна.
2. Мощность множества. Счетные множества.
3. Прямое произведение множеств. Понятие n-местного отно-
шения.
4. Соответствия между множествами. Функции. Инъекция,
сюръекция, биекция.
5. Отношения. Бинарные отношения. Свойства отношений.
6. Отношение эквивалентности. Связь между отношением эк-
вивалентности и разбиением множества.
7. Отношения частичного и строгого порядка.
8. Булевы функции одной и двух переменных.
9. Булевы функции. Способы задания. Существенные и фик-
тивные переменные.
10. Булевы формулы. Свойства логических операций.
11. Разложение булевой функции по переменным. Алгоритмы
построения совершенной дизъюнктивной нормальной фор-
мы и совершенной конъюнктивной нормальной формы.
12. Свойства суммы по модулю 2. Алгоритм построения полино-
ма Жегалкина.
13. Замкнутые классы функций. Классы T0 , T1 , S , M, L.
14. Функционально полные системы. Теорема о функциональ-
ной полноте двух систем функций. Теорема Поста.
15. Схемы из функциональных элементов.
16. Основные задачи комбинаторики. Правило суммы. Правило
произведения.
17. Формулы числа перестановок, размещений и сочетаний без
повторений и с повторениями.
18. Формула включения и исключения. Задача о беспорядках.
19. Понятие рекуррентного соотношения. Линейные рекур-
рентные соотношения. Метод решения.
2
