Voprosy_Diskretnaya_matematika_2013_I

Приложение №7 к Положению об организации и проведении промежуточной

аттестации студентов. Утверждено Приказом от 05.11.2009 г. № 108

ФГОУ СПО «Уральский радиотехнический колледж им. А.С. Попова»
ОДОБРЕНЫ		УТВЕРЖДАЮ
ЦМК «ЭВМ»		Заместитель директора по учебной работе ________ Д.В. Колесников
Протокол от «____» ___ 20 ___ г. № ___
Председатель ЦМК __________ Поликарпова С.В.		«____» ___________20___ г.

Вопросы к зачету по дисциплине

«Дискретная математика»

для специальности 080802 Прикладная информатика

семестр 4

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. Плоские графы.

39. Связность графов. Компоненты связности. Мост.

40. Эйлеров граф. Критерий эйлеровости графов.

41. Взвешенный граф. Матрица весов.

42. Гамильтонов граф. Гамильтонов цикл в графе.

43. Полный граф. Свойства полного графа.

44. Операции над графами: объединение, пересечение, кольцевая сумма, дополнение.

45. Задание графа списками вершин, списками ребер.

46. Задание графа матрицей смежности.

47. Задание графа матрицей инцидентности.

48. Подграфы. Остовный и собственный подграфы.

49. Дерево. Свойства дерева.

50. Дерево с корнем. Двоичное дерево.

51. Минимальное остовное дерево. Алгоритм Прима.

52. Минимальное остовное дерево. Жадный алгоритм.

53. Кратчайший путь между вершинами. Алгоритм Дейкстры.

54. Базовые множества для автомата: входной алфавит, выходной алфавит, множество состояний.

55. Принцип работы автомата.

56. Таблица автомата.

57. Диаграмма автомата.

58. Словарная функция автомата.

59. Финальная функция автомата.

60. Правильный автомат (автомат Мура). Упрощённый вид диаграммы для правильных автоматов.

Примерные задания

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

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

3. Для функции найти СДНФ и СКНФ, минимизировать СДНФ с помощью карт Карно.

4. Для функции найти СДНФ и СКНФ, минимизировать СДНФ с помощью карт Карно.

5. Определить, истинными или ложными являются высказывания

1. ,

2. ,

3. ,

4. ,

5. ,

построенные из предикатов

P(x): x – положительное число,

Q(x,y): x > y,

R(x,y) : студент x изучает дисциплину y.

6. Q(x,y): студент x учится в колледже y. Запишите на естественном языке высказывания и определите их истинность:

1. ,

2. ,

3. ,

4. ,

5. ,

6. .

7. По каналу связи передаются 3 сообщения, каждое из которых может быть правильно принято, независимо от других. Формализуйте высказывания (запишите с помощью символики алгебры логики):

1. «все сообщения будут искажены»;

2. «будет искажено только первое сообщение»;

3. «одно сообщение будет искажено»;

4. «хотя бы одно сообщение будет искажено».

8. Участок электрической цепи состоит из четырех элементов, каждый из которых работает независимо от других. Формализуйте высказывание «Участок цепи работает безотказно».

9. Участок электрической цепи состоит из четырех элементов, каждый из которых работает независимо от других. Формализуйте высказывание «Участок цепи вышел из строя».

10. Докажите справедливость законов алгебры логики.

11. Упростить с помощью законов логики. Сделать проверку с помощью таблиц истинности.

12. Упростить с помощью законов логики. Сделать проверку с помощью таблиц истинности.

13. Упростить с помощью законов логики. Сделать проверку с помощью таблиц истинности.

14. Записать предикат с помощью математической символики:

1. Среди чисел а, b, с есть хотя бы одна пара взаимно противоположных.

2. Данные числа х, у являются координатами точки, лежащей в первой координатной четверти.

3. Шахматный конь за один ход может переместиться с одного заданного поля на другое (каждое поле задано двумя координатами — целыми числами от 1 до 8).

4. Величина d является корнем только одного из уравнений и .

15. Даны два множества A = , , , B = , , . Что представляет собой множества А\В, А  В, АВ, В\А?

16. Найдите (BÈ А)\C, AÇ (B\C), (CÇ А)È B, если , , .

17. Три множества A, В и С изображены кругами Эйлера. Запишите множество, которое соответствует закрашенной области:

a) b)

18. Изобразите множества кругами Эйлера:

1. , если , ,;

2. , если , ,;

3. , если , ,.

19. Из 105 опрошенных человек 38 любят смотреть по телевизору фильмы ужасов, 29 − мелодрамы, 65 − комедии, смотрят фильмы ужасов или мелодрамы − 56, смотрят комедии или мелодрамы − 81, смотрят фильмы ужасов или комедии − 91, не смотрят телевизор вообще 4 человека. Сколько человек смотрят только комедии?

20. На экзамене по дискретной математике из 45 человек группы первое задание выполнили 17 человек, второе – 20, третье – 20, первое и второе – 5, второе и третье – 7, первое и третье – 6, все три – 4. Сколько студентов не выполнили ни одного задания?

21. Определите свойства отношения R, если A –множество всех людей, .

22. Определите свойства отношения R, если A –множество всех людей, .

23. Пусть , , , , , , . Найдите композицию отношений и .

24. Пусть , , . Задайте отношение R перечислением пар, постройте матрицу отношения, изобразите отношение графом. Найдите , ядро отношения Ker R.

25. Пусть , , . По матрице отношения R, запишите отношение R перечислением пар, изобразите отношение графом. Определите свойства отношения.

26. Дан граф:

1. Укажите степени вершин;

2. Найдите расстояния между вершинами и ,

3. Составьте цепь и простую цепь, соединяющие и ;

4. Составьте цикл, содержащий ;

5. Определите вид данного графа (является ли граф связным, ориентированным, эйлеровым, гамильтоновым, полным, деревом);

6. Составьте для него матрицу смежности и матрицу инцидентности.

27. Составьте матрицу смежности и матрицу инцидентности для ориентированного графа:

28. Найдите минимальное остовное дерево графа с помощью алгоритма Прима (Рис 1).

29. Найдите кратчайший маршрут между вершинами А и Л с помощью алгоритма Дейкстры (Рис 1).

30. Найдите минимальное остовное дерево графа с помощью жадного алгоритма (Рис 1).

Преподаватели: Алферьева О.В.

Рис 1

5