тестовые задания к дифференцированному зачету по Дискретной математике 09.02.07
тест

09.02.07 «Информационные системы и программирование)»

Тест к дифференцированному зачету по ЕН.02 «Дискретная математика»

______________________________________________________

ФИО студента

_____________________________________________________

Группа

1. Выберите верный, на Ваш взгляд, ответ и обведите кружком его номер.

Объединение множеств А и В

2. Выберите верный, на Ваш взгляд, ответ и обведите кружком его номер.

Разность множеств В и А

3. Выберите верный, на Ваш взгляд, ответ и обведите кружком его номер.

Правило суммы (ввести ответ без скобки)

4. Выберите верный, на Ваш взгляд, ответ и обведите кружком его номер.

Мощность конечного множества А обозначается:

1) { A }

2) ∣ A ∣

3) 2A

4) [A]

5. Выберите верный, на Ваш взгляд, ответ и обведите кружком его номер.

К видам множеств не относятся

1. Конечные
2. Бесконечные
3. Ограниченные
4. Счетные

6. Выберите верный, на Ваш взгляд, ответ и обведите кружком его номер.

Соответствие, при котором каждому элементу множества А соответствует единственный элемент множества В, а каждому элементу множества В соответствует не более одного прообраза из А (отображение «в») называется

1. Сюръекция
2. Инъекция
3. Биекция
4. Эквиваленция
5. Обратным отображением

7. Выберите верный, на Ваш взгляд, ответ и обведите кружком его номер.

Какие из соотношений справедливы:

8. Выберите верный, на Ваш взгляд, ответ и обведите кружком его номер.

Отображение называется однозначным, если каждому аргументу поставлено в соответствие:

1. не менее одного образа
2. не более одного образа
3. менее одного образа
4. более одного образа.

9. Из предлагаемого перечня вариантов ответа обведите кружком номера ответов, совокупность которых составляет наиболее полный ответ.

Для операции включения справедливы свойства:

10. Из предлагаемого перечня вариантов ответа обведите кружком номера ответов, совокупность которых составляет наиболее полный ответ.

Отношение a||b на множестве R обладает свойствами

1. Рефлексивность
2. Симметричность
3. Асимметричность
4. Транзитивность
5. Антитранзитивность
6. Связность

11. Укажите номер столбца, содержащего таблицу истинности операции Штрих Шеффера

12. Выберите верный, на Ваш взгляд, ответ и обведите кружком его номер.

Высказыванием не является

1) 2*2=4

2) 2< 3

3) Город стоит на берегу реки

4) Река Волга в 2014 году н.э. впадает в Каспийское море

13. Выберите верный, на Ваш взгляд, ответ и обведите кружком его номер.

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

1) тавтология

2) высказывание

3) предикат

4) повествование

14. Поставить в соответствие

1)                a)

2)                 b)

3)          c)

15. Из предлагаемого перечня вариантов ответа обведите кружком номера ответов, совокупность которых составляет наиболее полный ответ.

Двойственными друг другу называются символы

1) отрицания

2) конъюнкции

3) дизъюнкции

4) импликации

5) эквиваленции

Ответ: 2, 3.

16. Решите задачу. Упростить выражение:

17. Выберите верный, на Ваш взгляд, ответ и обведите кружком его номер.

Функцией алгебры логики от n переменных х1, х2, . . . .хn называется любая функция

1) f: R→{0,1}

2) f : {0,1}→{0,1}

3) f : {0,1}n→{0,1}

1) f: {0,1}→R

18. Выберите верный, на Ваш взгляд, ответ и обведите кружком его номер.

Если формула является конъюнкцией (быть может одночленной) переменных и отрицаний переменных, она называется

1) элементарной конъюнкцией

2) простой конъюнкцией

3) простейшей конъюнкцией

4) упрощенной конъюнкцией

19. Выберите верный, на Ваш взгляд, ответ и обведите кружком его номер.

Если ДНФ булевой функции содержит наименьшее число элементарных конъюнкций по сравнению с другими ДНФ этой же функции она называется

1) кратчайшей ДНФ

2) минимальной ДНФ

3) сокращенной ДНФ

4) наименьшей ДНФ

20. Выберите верный, на Ваш взгляд, ответ и обведите кружком его номер.

 Число переменных в элементарной конъюнкции называется

1) длиной

2) рангом

3) константой

4) формулой

21. Выберите верный, на Ваш взгляд, ответ и обведите кружком его номер.

Выбор из всех тупиковых форм, формы с наименьшим числом вхождений переменных дает

1. сокращенную ДНФ
2. тупиковую ДНФ
3. минимальную ДНФ
4. кратчайшую ДНФ

22. Из предлагаемого перечня вариантов ответа обведите кружком правильные на ваш взгляд номера ответов.

Правильные элементарные конъюнкции

23. Из предлагаемого перечня вариантов ответа обведите кружком правильные на ваш взгляд номера ответов. Представление функции однозначно в виде

1) ДНФ

2) КНФ

3) СДНФ

4) СКНФ

5) сокращенной ДНФ

6) тупиковой ДНФ

24. Из предлагаемого перечня вариантов ответа обведите кружком правильные на ваш взгляд номера ответов.

Совершенной конъюнктивной нормальной формой (СКНФ) относительно переменных х1, х2, . . . .хn называется

1) ДНФ в которой нет одинаковых ЭК

2) КНФ в которой нет одинаковых ЭД

3) все ЭК правильны относительно переменных х1, х2, . . . . хn

4) все ЭК  полны относительно переменных х1, х2, . . . . хn

5) все ЭД правильны относительно переменных х1, х2, . . . . хn

6) все ЭД  полны относительно переменных х1, х2, . . . . хn

25. Выберите верный, на Ваш взгляд, ответ и обведите кружком его номер.

СKНФ данной функции:

26. Из предлагаемого перечня вариантов ответа обведите кружком правильные на ваш взгляд номера ответов

Произвести склеивание и выбрать справедливые соотношения

1) (0010)&(0110)→(0_10)

2)(_000)&(_001)→(_00_)

3)(0010)&(0110)→(0010)

4)(0010)&(0110)→(00_0)

5)(1111)&(0000)→(0000)

27. Выберите верный, на Ваш взгляд, ответ и обведите кружком его номер. Многочлен, являющийся суммой константы и различных правильных элементарных конъюнкций, в которых все переменные входят в первой степени называется

1. правильной элементарной конъюнкцией
2. правильной элементарной дизъюнкцией
3. полиномом Жегалкина
4. формулой Жегалкина

28. Выберите верный, на Ваш взгляд, ответ и обведите кружком его номер. Совершенной полиноминальной нормальной формой называется

1. представление функции алгебры логики в виде ДНФ,КНФ
2. представление функции алгебры логики в виде СДНФ,СКНФ
3. представление функции алгебры логики в виде полинома Жегалкина
4. представление функции алгебры логики в виде сокращенной ДНФ, КНФ

29. Выберите верный, на Ваш взгляд, ответ и обведите кружком его номер.

Функции вида

называются

1) сохраняющими 0

2) сохраняющими 1

3) самодвойственными

4) линейными

5) монотонными

30. Выберите верный, на Ваш взгляд, ответ и обведите кружком его номер.

Если f(0,0,…,0)=0 функции называются

1) сохраняющими 0

2) сохраняющими 1

3) самодвойственными

4) линейными

5) монотонными

31. Выберите верный, на Ваш взгляд, ответ и обведите кружком его номер.

Если

функции называются

1) сохраняющими 0

2) сохраняющими 1

3) самодвойственными

4) линейными

5) монотонными

32. Выберите верный, на Ваш взгляд, ответ и обведите кружком его номер. Если из условия

функции называются

1) сохраняющими 0

2) сохраняющими 1

3) самодвойственными

4) линейными

5) монотонными

33. Выберите верный, на Ваш взгляд, ответ и обведите кружком его номер. Всякая совокупность Т функций алгебры логики, замкнутая относительно суперпозиции (суперпозиция функции из Т снова принадлежит Т), называется

1) функционально замкнутым объединением

2) обобщенным классом

3) функционально свободным  классом

4) функционально замкнутым  классом

34. Выберите верный, на Ваш взгляд, ответ и обведите кружком его номер. Арифметическим полиномом не является

Ответ: 1)

35. Выберите верный, на Ваш взгляд, ответ и обведите кружком его номер. Выберите справедливые равносильности

36. Решите задачу. Заполнить таблицу Поста

Ответ:

37. Выберите верный, на Ваш взгляд, ответ и обведите кружком его номер.

Если формула А и формулы А1,...Aj находятся в некотором отношении Ri, то А называется __________________ из формул А1,...Aj ,полученным по правилу Ri

1. Непосредственным следствием
2. последовательным выводом
3. следованием
4. доказательством

38. Выберите верный, на Ваш взгляд, ответ и обведите кружком его номер. Формула А называется ________ теории Т, если в ней существует вывод, в котором последней формулой является А.

1) аксиомой

2) утверждением

3) теоремой

4) леммой

39. Выберите верный, на Ваш взгляд, ответ и обведите кружком его номер. Формула А называется __________ множества формул Г тогда и только тогда, когда существует такая последовательность формул А1,...,Аn, что Аn есть А, и для любого i ,1<=i<=n ,  Аi есть либо аксиома, либо формула из Г, либо непосредственное следствие некоторых предыдущих формул.

1) заключением

2)выводом

3) доказательством

4) следствием

40. Всякая выводимая (из пустой системы гипотез) формула исчисления высказываний

1. тождественно-истинна
2. тождественно-ложна
3. выполнима
4. постоянна

41. Выберите верный, на Ваш взгляд, ответ и обведите кружком его номер.

Пусть P(x)- некоторый предикат, принимающий значение истина или ложь для каждого элемента х множества М. Под выражением (∃x)P(x) будем подразумевать высказывание истинное

1) когда для любого элемента множества М P(x) истинно, ложно в противном случае

2) когда существует элемент множества М, для которого P(x) истинно, ложно в противном случае

3) когда существует элемент множества М, для которогоP(x)ложно, истинно в противном случае

4) когда P(x) – истинно, для любого х из множества М, ложно в противном случае

42. Выберите верный, на Ваш взгляд, ответ и обведите кружком его номер.

Тезис Чёрча

1. Множество всех рекурсивных функций совпадает с множеством всех алгоритмических функций
2. Множество всех рекурсивных функций совпадает с множеством всех вычислимых функций
3. Для всякой вычислимой функции может быть построена машина Тьюринга
4. Всякая машина Тьюринга вычисляет рекурсивную функцию
5. Для всякой рекурсивной функции может быть построена машина Тьюринга

43. Выберите верный, на Ваш взгляд, ответ и обведите кружком его номер.

Тезис Тьюринга

1. Множество всех рекурсивных функций совпадает с множеством всех алгоритмических функций
2. Множество всех рекурсивных функций совпадает с множеством всех вычислимых функций
3. Для всякой вычислимой функции может быть построена машина Тьюринга
4. Всякая машина Тьюринга вычисляет рекурсивную функцию
5. Для всякой рекурсивной функции может быть построена машина Тьюринга

44. Начальное состояние головки машины Поста:

1. против самой левой метки на ленте;

2. против пустой клетки левее самой левой метки на ленте;

3. против пустой клетки правее самой правой метки на ленте;

4. против самой правой метки на ленте.

45. Начальное состояние головки машины Тьюринга:

1. против самой левой метки на ленте;

2. против пустой клетки левее самой левой метки на ленте;

3. против пустой клетки правее самой правой метки на ленте;

4. против самой правой метки на ленте.

46. Выберите верный, на Ваш взгляд, ответ и обведите кружком его номер.

Свойство алгоритма записываться в виде только тех команд, которые находятся в Системе Команд Исполнителя, называется:

1. понятность;
2. определенность;
3. дискретность;
4. результативность.

47. Выберите верный, на Ваш взгляд, ответ и обведите кружком его номер.

Свойство алгоритма записываться только директивами однозначно и одинаково интерпретируемыми разными исполнителями:

1. дискретность;
2. понятность
3. определенность;
4. результативность

48. Выберите верный, на Ваш взгляд, ответ и обведите кружком его номер.

Свойство алгоритма, что при точном исполнении всех предписаний процесс должен прекратиться за конечное число шагов с определенным ответом на поставленную задачу:

1. понятность;
2. детерминированность;
3. дискретность;
4. результативность.

49. Выберите верный, на Ваш взгляд, ответ и обведите кружком его номер.

Сколько существует команд  у машины Поста:

1. 2;
2. 4;
3. 6;
4. 8.

50. Выберите верный, на Ваш взгляд, ответ и обведите кружком его номер.

В машине Тьюринга предписание L для лентопротяжного механизма означает:

1. переместить ленту вправо;
2. переместить ленту влево;
3. остановить машину;
4. занести в ячейку символ.

51. Решите задачу. Определить степень вершины V3:

52. Выберите верный, на Ваш взгляд, ответ и обведите кружком его номер.

Мосты - это ребра

1. (1,2)  (5,7)  (8,9)  
2. (4,5)  (6,7)  (8,10)
3. (2,4)  (7,10)  (11,12)
4. (1,3)  (3,2)  (9,11)

53. Решите задачу.  Для данного орграфа определить полустепень исхода вершины v2:

54. Решите задачу. Для данного орграфа определить полустепень захода вершины v2:

55. Решите задачу. Найти матрицу смежности орграфа

56. Решите задачу. Найти матрицу смежности графа

57. Решите задачу. Найти матрицу инцидентности орграфа

58. Решите задачу. Найти матрицу инцидентности графа

59. Выберите верный, на Ваш взгляд, ответ и обведите кружком его номер.

В данном мультиграфе существует:

1. эйлеров цикл
2. эйлерова цепь
3. нет ни эйлеровойцепи ни цикла

60. Выберите верный, на Ваш взгляд, ответ и обведите кружком его номер.

В данном мультиграфе существует:

1. эйлеров цикл
2. эйлерова цепь
3. нет ни эйлеровой цепи ни цикла

Дата ________________________________

Подпись студента _____________________