Вопросы к экзамену по дисциплине "Дискретная математика"

Вопросы к экзамену по дисциплине “Дискретная математика”

Множество. Основные операции. Способы задания множеств.
Классификация множеств. Мощность множества.
Операции над множествами и их свойства.
Понятие высказывания. Основные логические операции.
Формулы алгебры логики.
Тождественно-истинные формулы.
Булевы функции, способы задания.
Операция двоичного сложения, свойства. Многочлен Жегалкина.
Полнота множества функции. Понятие замкнутого класса функций: важнейшие замкнутые классы.
Теорема Поста.
Понятие предиката (область определения, область истинности). Операции над предикатами (обычные, логические, кванторные).
Понятие предикатной формулы, понятие свободной и связной переменной. Методика построений отрицаний предикатам, содержащие кванторные операции.
Понятие бинарного отношения (примеры). Отношения типа эквивалентности.
Понятие отображения, обратное отображение, условие обратного отображения.
Понятие подстановки, формулы количества подстановок.
Произведение подстановок, обратная подстановка, степень подстановки.
Четные и нечетные подстановки, свойства четных и нечетных постановок.
Методика решения простейших уравнений (ax=в, ха=в, а х в= с) в алгебре вычетов.
Понятие вычета по модулю N. Операции над вычетами и их свойства.
Обратимые вычеты, система обратимых вычетов по модулю N.
Основные понятия теории кодирования.
Понятия шифрования. Шифры и замены ( Цезаря и Вижинера).
Принципы метода математической индукции.
Понятие неориентированного графа. Основные определения.
Способы задания графа (матрицы смежности, инцидентности, список ребер).
Расстояние между вершинами в графе, радиус, диаметр, центр.
Эйлеровы графы. Теорема Эйлера.
Деревья и их свойства. Ориентированные деревья.
Ориентированные графы. Основные определения.
Гамильтоновы орграфы.
Бинарные деревья.
Базовые множества для автомата: выходной алфавит, входной алфавит, множества состояний.
Таблица автомата, принципы работы, диаграмма, словарная функция автомата.

Практические задания для подготовки к экзамену

по дисциплине “Дискретная математика”

1. Составьте для данного графа матрицы смежности и инцидентности, список ребер:

2. Найдите объединение, пересечение, дополнение графов G1 и G2:

G1 G2

3. Найдите центр, радиус, диаметр графа:

4. Постройте рисунок орграфа, заданного матрицей смежности:

010010001101100010100010011001011000 010010000001100100011000011001110000
5. Для заданного дерева постройте код Прюфера.

6. Даны множества: U={2;4;6;8;10}, A={4;6;8}, B={2;6}, C={4;8;10}. Найдите: A∪B, C∩B, A\B∪C.

7. Даны множества: U={1;3;5;7;9} A={1;5} B={5;7;9} C={3;9}. Найти: A∩B, A∪B, B⨂C.

8. Даны множества: А={1,2,3,4,…}, В= {2,4,6,…}. Найдите: А∩В, А∪В,АВ,ВА, А⊕В.

9. Найти σ1-1, σ1∙σ2, σ2∙σ1, если σ1=1234513542, σ2=1234532451.

10. Найти σ2-1, σ13, σ2-4 , определить четность каждой подстановки, если σ1=1234512543, σ2=1234532154.

11. Доказать методом математической индукции, что 52n-1-1 делится на 8.

12. Методом математической индукции доказать, что 82n-1+1 делится на 9.

13. Докажите утверждение методом математической индукции:

1+22+32+…=nn+1(2n+1)6

14. Доказать методом математической индукции:

1+2+22+…+2n-1=2n-1.

15. Найти частное решение уравнения: x2+2x+14≡0mod 17.

16. Найти частное решение уравнения: x2+7x+15≡0mod 3.

17. Решить систему уравнений: 18.Решить систему уравнений:

x≡2(mod 3)x≡1(mod 4)x≡3(mod 5) x≡2(mod 3)x≡3(mod 5)x≡6(mod 2)

19. Составить таблицы истинности формул:

1) x∨y↔y↓x,

2) x|y→z⊕x∧y,

3) x∨y→z⊕x.

20. Проверьте равносильность формул:

1) x→y⊕z , x→y⊕x→z; 2) x|(y→z), xy→(x|z.

21. Для функции составьте СДНФ И СКНФ, используя построение таблицы истинности и элементарные преобразования

1) fx,y,z=x→y⊕z, 2) fx,y,z=x|(y→z), 3)fx,y,z=x∧(y↔z),

4)fx,y,z=x∨y↔y↓x.

22. Для функции, заданной вектором значений, составьте СДНФ, найдите сокращенную ДНФ, МДНФ:

1)f=(00110011), 2) f=(10011001), 3) f=(10001100).

23. Проверьте полноту системы булевых функций :

1) x∨y, x↔y, 2)x↓y, x↔y, 3)x⨁y, x⋀y

24. Постройте многочлен Жегалкина для функции:

1) fx,y,z=x∨y↔y↓x, 2) fx,y,z=x∨y→y⊕x, 3) f(0,1,0)=f(1,0,0)=f(1,0,1)=0,

4) f(0,1,0)=f(1,0,0)=f(1,0,1)=1.

25. Зашифруйте шифром Цезаря с ключевым словом фразу: «Плоды науки сладкие - корни горькие».

26. Зашифруйте шифром Вижинера фразу: «Плоды науки сладкие - корни горькие».