Экзамен по дискретной математике
за 1 курс

(!) Вопросы из билетов (!)
Алгебра высказываний.
1) Понятие о высказывании.
2) Операции над высказываниями.
3) Формулы алгебры высказываний.
4) Равносильность в алгебре высказываний.
5) Булева алгебра высказываний.
6) Двойственность в алгебре высказываний.
7) Принцип двойственности и закон двойственности. (!)
8) Нормальные формы алгебры высказываний.
9) СДНФ и СКНФ. (!)
10) Основные проблемы алгебры высказываний.
11) Критерии тождественной истинности и тождественной ложности.
12) Теория релейно-контактных схем и схем из функциональных
элементов.
13) Реле и его функция проводимости.
14) Схемы и их функции проводимости.
15) Основные задачи теории РКС: задача синтеза, задача анализа и задача
упрощения.
16) Машина голосования. Одноразрядный и многоразрядный двоичный
сумматор.(!)

Алгебра предикатов.
17) Понятие о многоместном предикате.
18) Логические операции над предикатами.
19) Равносильность в алгебре предикатов.
20) Булева алгебра предикатов.
21) Операции, уменьшающие местность предиката, кванторы.
22) Основные равносильности, содержащие кванторы.(!)
23) Кванторы как обобщение логических операций.
24) Применение языка предикатов и кванторов для записи
математических утверждений.

Алгебра множеств.
25) Множества и определяющие их предикаты.
26) Универсум и пустое множество.
27) Операции над множествами и их свойства.
28) Булева алгебра множеств
29). Подмножество. Свойства подмножеств.
30) Семейства множеств и операции над семействами.

Отображения
31) Понятие об отображении.
32) Образы и прообразы и их свойства.(!)
33) Основные типы отображений.
34) Композиция отображений.
35) Ассоциативность композиции.
36) Композиция однотипных отображений. (!)
37) Обратимость и односторонняя обратимость.(!)
38) Критерии обратимости и односторонней обратимости.(!)

Отношения.
38) Декартово произведение множеств.
39) Многоместные отношения.
40) Булевы операции над отношениями.
41) Булева алгебра отношений.
41) Двуместные отношения.
42) Композиция двуместных отношений.
43) Бинарные отношения.
44) Свойства бинарных отношений: рефлексивность, симметричность,
антисимметричность, транзитивность.
45) Отношения эквивалентности. (!)
46) Классы эквивалентности и их свойства.
47) Фактор-множество.
48) Система различных представителей.
49) Отношения порядка.
50) Упорядоченные , линейно-упорядоченные и частично-упорядоченные
множества.

Комбинаторика.
51) Основной принцип комбинаторики. Число элементов во множестве.
52) Формула включения-исключения.
53) Множества YX, In YX, Bi YX, Sur YX, теоремы и леммы о количестве
элементов в них.
54) Размещения, перестановки, сочетания.
55) Свойства сочетаний.
Бином Ньютона.
Сочетания с повторениями. Задача о пирожных.

Булевы функции.
57) Множества P2, P2(n).
58) Многочлены Жегалкина и их свойства.
59) Замыкание и его свойства.

60) Замкнутость, полнота.
61) Классы Поста и их свойства. (!)
62) Леммы о функциях, не принадлежащих классам Поста.(!)
63) Теорема Поста и следствия из неё(!)
64). Предполные классы и их свойства.(!)

Теория алгоритмов.
65)Понятие об алгоритме, черты (свойства) алгоритмов.
66) Алфавит, буквы, слова.
67) Запись слова на бесконечной ленте.
68) Операции над словами.
69) Машина Тьюринга - описание и примеры.
70) Композиция машин.
71) Машины с полулентами и теоремы о них.
72) Объединение машин, разветвление машин, итерация машин. (!)
73) Универсальный алфавит и универсальная машина.
74) Тьюрингов подход к понятию "алгоритм" и другие подходы.
75) Алгоритмически разрешимые и неразрешимые проблемы. Существование
алгоритмически неразрешимых проблем.

Элементы теории графов.
76) Общее определение графа.
77) Изоморфизм графов.
78) Геометрические графы.
79) Теорема о правильной реализации графа в трехмерном
пространстве.(!)
80) Плоские и неплоские графы.
81) Локальные характеристики графа.
82) Теорема Эйлера о рукопожатиях.
83) Части графа.
84) Пути, цепи, контуры, циклы. Компоненты.
85) Числа связности.
86) Мосты и точки сочленения. Теорема о мостах. (!)
87) Деревья и леса. Основная теорема о деревьях. Следствия из теоремы о
деревьях.
88) Эйлеровы графы и критерий эйлеровости. Задача о соединении
городов.(!)
89) Алгоритм Краскала. (!)
90) Помеченные графы. Перечисление помеченных деревьев (теорема
Келли). (!)
91) Цикломатика графов Теорема о цикломатическом числе графа.
92) Построение базиса пространства вектор-циклов.

93) Разрезы графа.
94) Размерность и базис пространства векторов-разрезов.
95) Ортогональность разрезов и циклов.
96) Матрицы графа.
Теорема о ранге матрицы инцидентности.

ОТВЕТЫ
Алгебра высказываний.
1) Понятие о высказывании.

2) Операции над высказываниями.

3) Формулы алгебры высказываний.

4) Равносильность в алгебре высказываний.

5) Булева алгебра высказываний.

6) Двойственность в алгебре высказываний.

7) Принцип двойственности

Закон двойственности.

8) Нормальные формы алгебры высказываний.

9) СДНФ и СКНФ.

10) Основные проблемы алгебры высказываний.

11) Критерии тождественной истинности и тождественной
ложности.

12) Теория релейно-контактных схем и схем из функциональных
элементов.

13) Реле и его функция проводимости.

14) Схемы и их функции проводимости.

15) Основные задачи теории РКС : задача синтеза, задача анализа
и задача упрощения.

16) Машина голосования.

Одноразрядный и многоразрядный двоичный сумматор

Алгебра предикатов.

17) Понятие о многоместном предикате.

18) Логические операции над предикатами.

19) Равносильность в алгебре предикатов.

20) Булева алгебра предикатов.

21) Операции, уменьшающие местность предиката,

Кванторы.

22) Основные равносильности, содержащие кванторы.

23) Кванторы как обобщение логических операций.

24) Применение языка предикатов и кванторов для записи
математических утверждений.

Алгебра множеств.

25) Множества и определяющие их предикаты.

26) Универсум и пустое множество.

27) Операции над множествами и их свойства.

28) Булева алгебра множеств

29). Подмножество.

Свойства подмножеств.

30) Семейства множеств и операции над семействами.

Отображения
31) Понятие об отображении.

32) Образы и прообразы и их свойства.

33) Основные типы отображений.

34) Композиция отображений.

35) Ассоциативность композиции.

36) Композиция однотипных отображений.

й

37) Обратимость и односторонняя обратимость.

38) Критерии обратимости и односторонней обратимости.

Отношения.
38) Декартово произведение множеств.
Декартово произведение множеств - попарное объединение элементов в
пару.
Например: X = {1, 2, 3}, Y = {4, 5}.
Тогда X × Y = {(1, 4); (2, 4); (3, 4); (1, 5); (2, 5); (3, 5)}
39) Многоместные отношения.

40) Булевы операции над отношениями.

41) Булева алгебра отношений.

41) Двуместные отношения.

42) Композиция двуместных отношений.

43) Бинарные отношения.

44) Свойства бинарных отношений:

Рефлексивность

Симметричность

Антисимметричность

Транзитивность

45) Отношения эквивалентности.

46) Классы эквивалентности и их свойства.

47) Фактор-множество.

48) Система различных представителей.

49) Отношения порядка.

50) Упорядоченные , линейно-упорядоченные и частичноупорядоченные множества.

Комбинаторика.
51) Основной принцип комбинаторики. Число элементов во
множестве.

52) Формула включения-исключения.

53) Множества YX, In YX, Bi YX, Sur YX, теоремы и леммы о
количестве элементов в них.

54) Размещения

Перестановки

Сочетания

55) Свойства сочетаний.

Бином Ньютона.

Сочетания с повторениями. Задача о пирожных.

Булевы функции.
57) Множества P2, P2(n).

58) Многочлены Жегалкина и их свойства.

59) Замыкание и его свойства.

60) Замкнутость, полнота.

61) Классы Поста и их свойства.

62) Леммы о функциях, не принадлежащих классам Поста.

63) Теорема Поста и следствия из неё

64). Предполные классы и их свойства.

Теория алгоритмов.

65)Понятие об алгоритме, черты (свойства) алгоритмов.

66) Алфавит, буквы, слова.

67) Запись слова на бесконечной ленте.

68) Операции над словами.
69) Машина Тьюринга - описание и примеры.

70) Композиция машин.

71) Машины с полулентами и теоремы о них.

72) Объединение машин,

Разветвление машин

Итерация машин

73) Универсальный алфавит и универсальная машина.

74) Тьюрингов подход к понятию "алгоритм" и другие подходы.

75) Алгоритмически разрешимые и неразрешимые проблемы.
Существование алгоритмически неразрешимых проблем.

Элементы теории графов.

76) Общее определение графа.

77) Изоморфизм графов.

78) Геометрические графы.

79) Теорема о правильной реализации графа в трехмерном
пространстве.

80) Плоские и неплоские графы.

81) Локальные характеристики графа.

82) Теорема Эйлера о рукопожатиях.

83) Части графа.

84) Пути

Цепи, контуры, циклы.

Компоненты.

85) Числа связности.

86) Мосты и точки сочленения. Теорема о мостах.

87) Деревья и леса.

Основная теорема о деревьях.

Следствия из теоремы о деревьях.

88) Эйлеровы графы и критерий эйлеровости. Задача о
соединении городов.

89)

89) Алгоритм Краскала.

90) Помеченные графы.

Перечисление помеченных деревьев (теорема Келли).

91) Цикломатика графов. Теорема о цикломатическом числе
графа.

92) Построение базиса пространства вектор-циклов.

93) Разрезы графа.

94) Размерность и базис пространства векторов-разрезов.

95) Ортогональность разрезов и циклов.

96) Матрицы графа.

Теорема о ранге матрицы инцидентности.

ВОПРОСЫ ИЗ БИЛЕТОВ
Теория
Объединение, разветвление машин Тьюринга. Итерация машины Тьюринга по
предикату P. (12)
2. Класс L и его свойства. Лемма о f ∉ L. (11)
3. Задача о соединении городов. Алгоритм Краскала. (9)
4. Основные равносильности, содержащие кванторы. (8)
5. Класс M и его свойства. Лемма о f ∉ M. (6)
6. Теорема Поста и следствия из неё. (6)
7. Общий и булев принцип двойственности. (6)
8. Перечисление помеченных деревьев (теорема Келли). (5)
9. Предполные классы и их свойства. Существование предполных классов. (5)
10. Мосты графа. Теорема о мостах. (4)
11. СДНФ – существование и единственность. (4)
12. Свойства образов и прообразов. (4)
13. Класс S и его свойства. Лемма о f ∉ S. (3)
14. Теоремы о композиции однотипных отображений. (3)
15. Критерий эйлеровости графа. (3)
16. Обратимость и односторонняя обратимость отображений. Критерии
односторонней обратимости и обратимости. (2)
17. Отношение эквивалентности. Теорема о классах эквивалентности. (2)
18. Одноразрядный и многоразрядный двоичные сумматоры. (2)
19. Реализация графа в R3 (2)
20. Многочлен Жегалкина, определение, теорема о единственности
1.

Задачи
1. На почте продаются конверты 5 видов и марки 4 видов. Сколько способов
покупки 4-х конвертов и 5–ти марок? В скольких случаях в покупке все конверты
одинаковы (одного вида)?
2. На почте продаются конверты 5 видов и марки 4 видов. Сколько способов
покупки 5-ти конвертов и 3–х марок? В каком количестве случаев в покупке все
марки одинаковы?
3. На почте продаются конверты 4 видов и марки 5 видов. Сколько способов
покупки 5-ти конвертов и 4–х марок? В каком количестве случаев в покупке все
конверты одинаковы (одного вида)?
4. В магазине продаются 5 наименований хлеба и 6 видов минеральной воды.
Сколько способов покупки 4-х булок хлеба и 3-х бутылок воды? В каком
количестве случаев в покупке все четыре булки одного наименования?
5. В магазине продаются 5 наименований хлеба и 6 марок минеральной воды.
Сколько способов покупки 3-х булок хлеба и 4-х бутылок воды? В каком
количестве случаев в покупке все булки хлеба одного наименования?
6. Чему равна сумма всех чисел, полученных перестановками цифр числа 1, 2, 4,
5? Чему равна сумма тех из них, запись которых начинается с 5?

7. Чему равна сумма всех четырехразрядных чисел образованных
перестановками цифр 1,3,5,7? Чему равна сумма тех из них, запись которых
начинается с 3?
8. Чему равна сумма всех четырехразрядных чисел образованных
перестановками цифр 1,2,5,7? Чему равна сумма тех из них, запись которых
начинается с 7?
9. Сколько делителей у числа 1800, сколько из них кратны трем?
10. Сколько делителей у числа 4200? Сколько из них делится на 10?
11. Сколько делителей у числа 7200? Сколько из них кратны пяти?
12. В концертной программе шесть номеров: А, Б, В, Г, Д, Е. Сколько способов
составить программу концерта? Сколько вариантов составить её так, чтобы
номера А и Б не следовали друг за другом подряд (в любом порядке, т.е. А
перед Б и Б перед А)?
13. В концертной программе шесть номеров: А, Б, В, Г, Д, Е. Сколько способов
составить программу концерта так, чтобы номера А и Б следовали через один
номер (в любом порядке, т.е А до Б и Б до А)?
14. В концертной программе пять номеров: А, Б, В, Г, Д. Сколько способов
составить программу концерта так, чтобы номера А и Б следовали в программе
через один номер в любом порядке (т.е. и А до Б, и Б до А)?
15. Сколько способов раскладки 5 различных монет по трем различным карманам.
В каком количестве случаев хотя бы один карман пуст?цуц
16. Сколько способов раскладки пяти одинаковых монет по трем карманам? В
скольких случаях ни один из карманов не пуст?
17. Сколько способов раскладки пяти одинаковых монет по трем различным
карманам? В скольких случаях ни один из карманов не пуст?
18. |𝑃1(𝑃)∪𝑃𝑃|=?
19. |𝑃0(𝑃)∪𝑃𝑃|=?
20. |𝑃0(𝑃)∪𝑃1(𝑃)|=?
21. Сколько способов выбрать в студенческой группе из 25 человек старосту,
профорга и трех членов профбюро? В каком количестве случаев должности
старосты и профорга занимают последние два человека из алфавитного списка
группы?
22. Сколько способов раскладки 6 различных дискет по трем различным коробкам,
в каждой из которых имеется по 5 различных отсеков, вмещающих по одной
дискете? В каком количестве случаев все отсеки одной из коробок заполнены?
23. Сколько способов раскладки 7 различных дискет по трем различным коробкам,
в каждой из которых имеется по 6 различных отсеков, вмещающих по одной
дискете? В каком количестве случаев в одной из коробок заполнены все
отсеки?
24. Сколько способов рассадки 4 пассажиров в купе поезда (по 4 места на двух
диванах) так, чтобы А сидел по ходу поезда, а пассажиры Б и В друг напротив
друга?
25. Сколько способов рассадки 4 пассажиров в купе поезда (по 4 места на двух
диванах) так, чтобы А сидел по ходу поезда, а пассажиры Б и В рядом?

Теория (ответы)

1) Класс L и его свойства. Лемма о f ∉ L.

Лемма о нелинейной функции

2) Класс S и его свойства. Лемма о f ∉ S.

Лемма о несамодвойственной функции

3) Класс M и его свойства. Лемма о f ∉ M.
Бинарное отношение ⩽(чисто для понимания)

Класс M и его свойства

Лемма о немонотонной функции

ц

4) Теорема Поста и следствия из неё.
Используемые определения и теоремы (замыкание) (просто для понимания)

Леммы P0, P1

Теорема Поста

Следствия

5) Предполные классы и их свойства. Существование предполных
классов.

6) Основные равносильности, содержащие кванторы.

7) Общий и булев принцип двойственности.
Определение

Общий принцип двойственности

8) СДНФ – существование и единственность.

Существование СДНФ

Единственность СДНФ

9) Свойства образов и прообразов.

Свойства

10) Теоремы о композиции однотипных отображений.

(определения для понимания - необязательно писать в ответе)

11) Обратимость и односторонняя обратимость отображений.

Критерии односторонней обратимости и обратимости.
Критерий обратимости слева

Критерий обратимости справа

Критерий обратимости

12) Отношение эквивалентности.

Теорема о классах эквивалентности.

13) Одноразрядный и многоразрядный двоичные сумматоры.

14) Объединение:

Разветвление машин Тьюринга.

Итерация машины Тьюринга по предикату P.

15) Мосты графа. Теорема о мостах.

16) Критерий эйлеровости графа.

17) Перечисление помеченных деревьев (теорема Келли).

На всякий случай:

18) Задача о соединении городов.

Алгоритм Краскала.

Commented [1]: Не приводит к образованию
простых циклов, если не напишешь -5 баллов))

- это правильная цепочка
неравенств

19) Реализация графа в R3

20) Многочлен Жегалкина, определение, теорема о
единственности

Практическая часть
1) На почте продаются конверты 5 видов и марки 4 видов.
Сколько способов покупки 4-х конвертов и 5–ти марок? В скольких
случаях в покупке все конверты одинаковы (одного вида)?

7) Чему равна сумма всех четырехразрядных чисел образованных
перестановками цифр 1,3,5,7? Чему равна сумма тех из них,
запись которых начинается с 3?

4) В магазине продаются 5 наименований хлеба и 6 видов
минеральной воды. Сколько способов покупки 4-х булок хлеба и 3-х
бутылок воды? В каком количестве случаев в покупке все четыре
булки одного наименования?

10) Сколько делителей у числа 4200? Сколько из них делится на 10

Ответ: 1) 48, 2) 24

11) Сколько делителей у числа 7200? Сколько из них кратны
пяти?

Ответ: 1) 54, 2) 36

13) В концертной программе шесть номеров: А, Б, В, Г, Д, Е.
Сколько способов составить программу концерта так, чтобы
номера А и Б следовали через один номер (в любом порядке, т.е А
до Б и Б до А)?

Ответ: 192

15) Сколько способов раскладки 5 различных монет по трем
различным карманам. В каком количестве случаев хотя бы один
карман пуст?

Ответ: 1) 3^5, 2) 3*2^5

16) Сколько способов раскладки пяти одинаковых монет по трем
карманам? В скольких случаях ни один из карманов не пуст?

18) |𝑃1(𝑃)∪ 𝑃𝑃|=?

20) |𝑃0(𝑃)∪ 𝑃1(𝑃)|=?

21) Сколько способов выбрать в студенческой группе из 25
человек старосту, профорга и трех членов профбюро? В каком
количестве случаев должности старосты и профорга занимают
последние два человека из алфавитного списка группы?

\\

23) Сколько способов раскладки 7 различных дискет по трем
различным коробкам, в каждой из которых имеется по 6
различных отсеков, вмещающих по одной дискете? В каком
количестве случаев в одной из коробок заполнены все отсеки?

25) Сколько способов рассадки 4 пассажиров в купе поезда (по 4
места на двух диванах) так, чтобы А сидел по ходу поезда, а
пассажиры Б и В рядом?