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

 Вопросы к экзамену

по дисциплине

«ОП.08 Дискретная математика»

для студентов специальности 09.02.01 Компьютерные системы и  комплексы

2 курс

Вопросы теоретической части:

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. Свойства сложения по модулю два (М2 или строгой дизъюнкции)
27. Многочлен Жегалкина, порядок его построения
28. Важнейшие замкнутые классы
29. Теорема о полноте системы логических: функций. Критерий Поста-Яблонского.
30. Метод математической индукции
31.  Понятие предиката. Область определения и область истинности предиката.
32. Операции над предикатами.
33. Формализация предложений с помощью логики предикатов
34. Кванторные операции над предикатами.
35. Понятие предикатной формулы; свободные и связанные переменные.
36. Построение отрицаний к предикатам, содержащим кванторные операции.
37. Формализация предложений с помощью логики предикатов. 
38. Понятие бинарного отношения; примеры бинарных отношений.
39. Диаграмма бинарного отношения. Рефлексивные бинарные отношения
40. Симметричные бинарные отношения. Транзитивные бинарные отношения.
41. Отношение эквивалентности; теорема о разбиении множества на классы эквивалентности.
42. Базовые множества для автомата: входной алфавит, выходной алфавит, множество состояний
43. Таблица автомата. Принцип работы автомата. Диаграмма автомата.
44.  Словарная функция автомата. Финальная функция автомата.
45. Правильный автомат (автомат Мура). Упрощённый вид диаграммы для правильных автоматов.
46. Логические конечные автоматы без памяти
47. Логические конечные автоматы с памятью

Вопросы практической части:

1        Даны отрезки А = [-4; 5], B = [2; 6], C = [5; 10]. Найдите следующее множество и изобразите его кругами Эйлера:

2        Даны отрезки А = [-7; 3], B = [1; 5], C = [4; 10]. Найдите следующие множества и изобразите их кругами Эйлера: ;

3        Даны отрезки А = [-2; 4], B = [2; 6], C = [5; 10]. Найдите следующие множества и изобразите их кругами Эйлера: ;

4        Выполните действия и определите мощность полученного множества

5        Выполните действия и определите мощность полученного множества

6        В=

7        По заданной функции постройте таблицу истинности, приведите функцию к минимальной ДНФ:
 

8        Проверьте, являются ли булевы функции F1 и F2 эквивалентными:
F1 = X → (Y ≡ Z) и F2 = (X → Y) ≡ (X → Z)

9        Проверьте, являются ли булевы функции F1 и F2 эквивалентными:
F1 = X ∙ (Y ≡ Z) и F2 = (XY) ≡ (XZ);

10    Проверьте, являются ли булевы функции F1 и F2 эквивалентными:
F1 = X → (Y Ú Z) и F2 = (X → Y) Ú (X → Z);

11    Используя законы алгебры логики доказать справедливость Закона склеивания относительно дизъюнкции и конъюнкции:    и     .

12    Доказать с помощью таблиц истинности справедливость закона де Моргана относительно операций конъюнкции и дизъюнкции.

13    Проверьте, являются ли булевы функции F₁ и F₂  эквивалентными, если  и .

14    Проверьте, являются ли булевы функции F₁ и F₂  эквивалентными, если  и .

15    Вычислите значение функции F(x₁, x₂, x₃) при заданных значениях аргументов
 x₁ = 0, x₂ = 1, x₃ = 1 и при  x₁ = 0, x₂ = 0, x₃ = 1:
F(x₁, x₂, x₃) =

16    Докажите или опровергните:

17    Построить таблицу истинности для следующей формулы: A & (B Ú Þ )

18    Построить таблицы истинности алгебраически для следующей формулы: A Ú (B Ú Þ) 

19    По заданной функции постройте таблицу истинности, приведите функцию к минимальной ДНФ:
 F(x₁,x₂,x₃) =

20    Вычислите значение функции F(x₁, x₂, x₃) при заданных значениях аргументов x₁ = 1, x₂ = 0,
x₃ = 1 и при x₁ = 1, x₂ = 0, x₃ = 1:   F(x₁,x₂,x₃) =

21    Вычислите значение функции F(x₁, x₂, x₃) при заданных значениях аргументов x₁ = 0, x₂ = 0,
x₃ = 1 и при x₁ = 0, x₂ = 1, x₃ = 1: F(x₁,x₂,x₃) =

22    Упростите функцию, приведя ее к минимальной ДНФ: F(x₁,x₂,x₃) =

23    Упростите функцию, приведя ее к минимальной ДНФ:  F(x₁,x₂,x₃) =

24    Упростите функцию, приведя ее к минимальной ДНФ:  F(x₁,x₂,x₃) =

25     Постройте логическое выражение по заданной таблице истинности, приведите его к минимальной ДНФ алгебраически:

26     Постройте логическое выражение по заданной таблице истинности, приведите его к минимальной ДНФ алгебраически:

27    Минимизируйте булеву функцию с помощью карт Карно или диаграмм Вейча:

28    Минимизируйте булеву функцию с помощью карт Карно или диаграмм Вейча:

29     Постройте совершенные ДНФ и соответствующие минимальные формы для булевых функций, заданных таблично, с помощью карт Карно. Постройте соответствующий логический элемент.

30     Постройте совершенную ДНФ по таблице истинности и преобразуйте ее в полином Жегалкина:

31     Определите по рисунку справа вид графа, степени его вершин. Имеет ли граф висячие вершины?

32     Определите по рисунку слева вид графа и постройте таблицы инцидентности и смежности