Дискретная математика Тест МУ им. Витте ( МУИВ) (Решение → 1245)

90 вопросов с ответами

Последний раз тест был сдан на 77 баллов из 100 "Хорошо".

!!! ВАЖНО!!! ТАК КАК ВОПРОСОВ МНОГО ОЦЕНКА ВАРЬИРУЕТСЯ ОТ (63 БАЛЛОВ ДО 87 БАЛЛОВ)!!!

Год сдачи -2017-2021.

После покупки Вы получите файл с ответами на вопросы которые указаны ниже:

***(Если нужна помощь с другими предметами или сдачей тестов онлайн, пишите в личные сообщения)

1. Определить форму следующей формулы A vBC vD :

*КНФ;

*ДНФ;

*не ДНФ и не КНФ.

2. Если выразите конъюнкцию АvВ через импликацию и отрицание, получим:

*1

*2

*3

3. Отношение "быть старше": "х старше у" является:

*рефлексивным;

*транзитивным.

*симметричным;

4. Является ли высказывание «Солнце встает на западе» предикатом?:

*нет.

*да;

5. Можно ли для функции F(S1,S2,S3) заданной так, что на всех наборах значений переменных S1,S2,S3 она принимает значение 0, построить какую-либо совершенную нормальную форму?

*нельзя построить ни одной совершенной нормальной формы.

*можно СКНФ;

*можно СДНФ;

6. Могут ли быть при правильном рассуждении все посылки истинными, если заключение ложно?

*да;

*нет;

*иногда да,

*иногда нет.

7. Задано отображение f множества X={ x1,x2,x3,x4} в множество Y={ y1,y2,y3}: f(x1)=y1, f(x2)=y2, f(x3)=y2, f(x4)=y3 Отображение f будет являться:

*инъективным;

*сюръективным;

*биективным.

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

*1,1

*1,0

*0,1

*0,0

9. Сколько ребер имеет полный неориентированный граф с числом вершин равным n?

*1/2n(n-1)

*n(n-1)

*n^2(n-1)

10. Отношение X <Y, заданное на множестве действительных чисел обладает свойством:

*транзитивности.

*симметричности;

*рефлексивности;

11. Граф ... содержит эйлерову цепь, соединяющую две различные вершины

*G2

*G4

*G1

*G3

12. Могут ли две релейно-контактные схемы, соответствующие одной и той же функции проводимости, иметь различное число реле?

*нет;

*никогда не могут.

*да;

13. Сколько сомножителей содержит СКНФ, построенная по функции f(1,1,1)= f(1,0,1)=0?

*2;

*8.

*6;

14. Какой граф называется сетью?

*ориентированный граф без циклов с одним входом и одним выходом.

* неориентированный граф с одним входом;

*несвязный граф, компонентами связности которого являются деревья;

* ориентированный граф с циклами;

15. Какой из данных графов правильно пронумерован?

*G1

*G2

*G3

16. Может ли сюръективное отображение являться инъективным?

*никогда;

*всегда;

*может являться, но может и нет.

17. Если высказывания эквивалентны, существуют ли между ними отношения следствия?

*не существуют;

*могут существовать, а могут и не существовать.

*существуют;

18. Количество «нулевых» значений таблицы истинности формулы

*3.

*0;

*5;

19. Результат конъюнкции предикатов P(x)=(x>2) и Q(x)=(x<2) на множестве действительных чисел:

*x=2

*0

*1

20. Следующее высказывание может быть интерпретировано как сложное высказывание: "Неверно, что первым пришел Петр или Павел". Какой из формул может быть записано это высказывание?

21. Отношение " y кратно x ", заданное на множестве положительных целых чисел, является:

*симметричным;

*антирефлексивным;

*антисимметричным.

22. Через какие вершины проходит путь минимальной длины от входа к выходу:

*a-b-d-c-e-f;

*a-b-e-f;

*a-c-e-f.

23. На множестве всех треугольников на плоскости рассматривается отношение подобия. Данное отношение является отношением:

*эквивалентности.

*порядка;

*толерантности;

24. Релейно-контактной схеме

соответствует формула алгебры высказываний:

25. Пусть – мощность множества, являющегося объединением конечных множеств A и B, если множества пересекаются, Как соотносятся m1 и m2?

m1 <m2.

m1 =m2;

m1 >m2;

26. Графы G1 и G2 заданы матрицами смежности A1 и A2 соответственно. С помощью какой операции был получен граф G , заданный матрицей A ?

*пересечение;

*декартово произведение.

*объединение;

27. Через какие вершины проходит путь максимальной длины от входа к выходу:

*a-b-e-f;

*a-b-d-f.

*a-b-d-c-e-f;

28. Пусть N2 и N3 – множество натуральных чисел, кратных 2 и 3 соответственно. Если n=1,2..., то множество ?

* (6n±1);

* (6n);

* (6n±2);

29. Какие из пар связок образуют полную систему связок?

30. – множество натуральных чисел. Определить истинное высказывание:

31. Всегда ли биективное отображение сюръективно?

*может быть сюръективным, но может и не быть им.

*всегда;

*никогда;

32. Пусть на множестве M задано отношение A: "х знаком с у". Почему на основе данного соотношения нельзя разбить множество M на непересекающиеся классы?

*отношение A не транзитивно.

*отношение A не симметрично;

*отношение A не рефлексивно;

33. Сколько слагаемых содержит СДНФ, построенная по функции F(S1,S2,S3) , заданной так, что на всех наборах значений переменных S1,S2,S3 она принимает значение 1?

*2;

*8.

*4;

34. Как присваиваются метки вершинам ориентированного графа при нахождении пути по алгоритму Форда:

35. Вопрос:

36. Сколько ребер имеет дерево, содержащее n вершин?

*n-1

*n^2

*2^n

37. Какое свойство не является свойством дерева?

*граф связен и все его ребра являются перешейками;

*всякая пара вершин графа соединена только одной цепью;

*граф связен и содержит циклы.

38. Определите значение следующего выражения на множестве действительных

*1

*0

*1<x<2

39. Количество «единичных» значений таблицы истинности формулы составляет

*3.

*5;

*0;

40. – множество натуральных чисел. Равносильны ли предикаты ?

*нет;

*да.

41. Отношение равенства площадей, заданное на множестве всех треугольников на плоскости является отношением:

*толерантности;

*порядка.

*эквивалентности;

42. Выделим в бесконечном несчетном множестве M счетное подмножество . В каком отношении находятся мощности множеств M\A и M?

*мощность множества M равна мощности множества M\A ;

*мощность множества M меньше мощности множества M\A ;

*мощность множества M больше мощности множества M\A ;

43. Содержит ли конечное множество A собственное подмножество, эквивалентное всему множеству A?

*иногда содержит, иногда нет.

*всегда содержит;

*никогда не содержит;

44. Для предиката P(x,y)=(x+y)=0 , заданного на множестве действительных чисел, укажите набор значений кванторов

*0,1

*1,1

*1,0

*0,0

45. Чему равно хроматическое число графа?

*3

*6

*1

*2

46. Вопрос:

47. Мощность какого множества больше X или Y, если X – исходное конечное множество, Y – множество подмножеств множества X?

*мощность X равна мощности Y.

*мощность X больше мощности Y;

*мощность X меньше мощности Y;

48. Выразите дизъюнкцию A v B через импликацию и отрицание:

49. Сколько ребер требуется выбрать при нахождении кратчайшего дерева по алгоритму Краскала, если граф содержит n вершин?

*n

*n-1

*n+1

50. Логической функции f (0,0,0) = f(0,0,l) = f (1,0,0) = 0 , соответствует формула алгебры высказываний

*1

*2

*3

51. Чему равно цикломатическое число графа?

*5

*6

*4

*1

52. Определить форму следующей формулы

*СКНФ;

*не СДНФ и не СКНФ.

*СДНФ;

53. Определите, каким отношением следования связаны предикаты P(x)= (|x| <3) и Q(x)=(x^2-3x+2=0) на множестве действительных чисел:

*P(x) —>Q(x);

*не связаны

*Q(x) —> P(x) ;

54. Пусть А=1, В = 0, С = 1, К = (А —>В)^С ^(А <->С) тогда …

*К=1;

*К=2;

*К=0.

55. Отношение «х - победитель у» является ...

*антирефлексивным

*симметричным

*транзитивным

*антисимметричным

56. Полный неориентированный граф с числом вершин n=4 …

*обладает эйлеровым циклом

*не обладает эйлеровым циклом

*может обладать эйлеровым циклом – это зависит от числа дуг

57. Решите уравнение

варианты ответов

*1

*2

*3

*4

58. Если A – множество всех книг во всех библиотеках России, а B – множество всех книг в библиотеке МГУ по различным отделам науки и искусства, тогда A\B есть множество …

*всех книг в библиотеках России без книг по различным отделам науки и искусства в МГУ

*книг по искусству в библиотеке МГУ

*всех книг в российских библиотеках

*книг в библиотеке МГУ по искусству и науке, кроме математических

59. Бинарное отношение, заданное на множестве натуральных чисел соотношением X=Y(mod3) (остатки от деления на 3 равны), является отношением …

*толерантности

*порядка

*эквивалентности

60. Полный неориентированный граф с числом вершин n=5 …

*обладает эйлеровым циклом

*не обладает эйлеровым циклом

*может обладать эйлеровым циклом – это зависит от числа дуг

*может обладать эйлеровым циклом – это зависит от количества вершин с нулевыми степенями

61. Преобразовывая формулу , нужно производить операции в следующем порядке:

*1

*2

*3

*4

62. Пустое множество Ø … подмножеством некоторого множества

*будет собственным

*будет несобственным

*не будет никаким

*не всегда является

63. Высказывание «Неверно, что первым пришел Петр или Павел» может быть интерпретировано как сложное высказывание и записано формулой «…»

*1

*2

*3

*4

64. Если из высказывания S1 следует S2 и, наоборот, из S2 следует S1 , то высказывания S1 и S2 … эквивалентными

*являются

*не являются

*могут являться, а могут и не являться

65. Дистрибутивные законы булевой алгебры и алгебры действительных чисел …

*совпадают

*не совпадают

*совпадают в частном случае

66. Конечное множество, состоящее из n элементов, имеет …

*1 несобственное подмножество

*2 несобственных подмножества

*n несобственных подмножеств

*n2 несобственных подмножеств

67. Пустое множество … подмножеством некоторого множества

*будет собственным

*будет несобственным

*не будет никаким

*не всегда является

68. Выражение Выражение S = (A—>B)^ (B—>C) —>(A—>C)...... высказыванием

*является тождественно истинным

*является тождественно ложным

*является переменным

*не является

69. Полный неориентированный граф с числом вершин, равным n, имеет ребер

*1

*2

*3

*4

70. Высказывание «Если a- четное число, b- нечетное число, то их произведение делится на 2» в символической форме имеет вид «…»

*1

*2

*3

*4

71. Матрица смежности для графа имеет вид: …

*1

*2

*3

72. Пусть А=1, В = 1, С = 1, К = (А —>В)^С ^(А <->С) тогда …

*K=2

*K=1

*K=0

73. Если заданы два нечетких отношения R1 и R2 :и , то результат операции дополнения R1 равен …

*1

*2

*3

74. Если заданы два нечетких множества A=1|x1+0,3|x2+0,1|x3 и B=0,7|x1+0|x2+0,5|x3, то результат операции дополнения равен …

*1

*2

*3

*4

75. Значение X, определяемое уравнением

76. Если заданы два нечетких множества A=1|x1+0,3|x2+0,1|x3 и B=0,7|x1+0|x2+0,5|x3, то результат операции дополнения равен …

*1

*2

*3

*4

77. Если заданы два нечетких отношения R1 и R2 : и , то результат операции пересечения равен …

*1

*2

*3

*4

78. Отношение |x-y|<1 , заданное на множестве действительных чисел, является отношением …

*толерантности

*порядка

*эквивалентности

79. Если на множестве всех треугольников на плоскости рассматривается отношение подобия, то данное отношение является отношением …

*толерантности

*порядка

*эквивалентности

80. Если даны два высказывания - S1 («Если треугольники равны, то равны их стороны») и S2 («Стороны треугольников равны тогда и только тогда, когда равны треугольники»), - то можно утверждать, что ...

*из S1 следует S2

*из S2 следует S1

*ни одно из высказываний не следует из другого

81. Если заданы два нечетких множества –A=1|x1+0,3|x2+0,1|x3 и B=0,7|x1+0|x2+0,5|x3 операции пересечения равен

*1

*2

*3

*4

82. Выражение S = (ABvB)<->B ... высказыванием

*является тождественно истинным

*является тождественно ложным

*является переменным

*не является

83. Если отношение А на множестве М рефлексивно, симметрично и транзитивно, то разбить множество М на непересекающиеся классы ...

*можно

*нельзя

*можно, но не всегда

*можно только в том случае, если А - отношение порядка

84. Логической функции f (0,0,0) = f(0,0,l) = f (1,0,0) = 1 соответствует формула алгебры высказывании

*1

*2

*3

85. Решите уравнение

варианты ответов

*1

*2

*3

*4

86. Граф ... обладает эйлеровым циклом

*G1

*G2

*G3

*G4

87. Высказывание «Произведение целых чисел a и b не делится на 2 в том и только в том случае, если a или b-нечетное» в символической форме имеет вид «…»

*1

*2

*3

*4

88. Если на множестве М задано отношение А «х знаком с у», тогда на основе данного соотношения нельзя разбить множество М на непересекающиеся классы, потому что отношение А ...

*нерефлексивно

*несимметрично

*нетранзитивно

*не антирефлексивно

89. Высказывание «Если а - четное число, b - нечетное число, то их произведение делится на 2» в символической… форме имеет вид «...»

*1

*2

*3

*4

90. Вопрос:

*y;

*x;

*

1 Важно!. Информация по изучению курса

2 Тема 1. Множества

3 Тема 2. Отношения на множествах

4 Тема З. Алгебра высказываний

5 Тема 4. Нормальные формы формул алгебры высказываний

6 Тема 5. Исчисление высказываний

7 Тема 6. Алгебра предикатов

8 Тема 7. Графы

9 Тема 8. Деревья

10 Тема 9. Экстремальные задачи на графах