Дискретная математика (тест с ответами Синергия/МОИ/ МТИ /МОСАП)

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

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

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

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

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

Если нужна помощь с другими предметами или сдачей тестов онлайн, пишите в личные сообщения https://studwork.ru/info/147162

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;

*

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

 и

?

*да.

*нет;

92. U – множество всех параллелограммов на плоскости, – множество квадратов, – множество прямоугольников. Что представляет собой множество ?

*множество прямоугольников, но не квадратов.

*множество ромбов;

*множество квадратов;

93. Будет ли пустое множество Ø каким-либо подмножеством некоторого множества?

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

*не будет никаким подмножеством.

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

94. Взаимнооднозначное соответствие между множеством A={1,6,11,16,...} и натуральным рядом устанавливается формулой?

Взаимнооднозначное соответствие между множеством A={7,10,13,16,19,...} и натуральным рядом устанавливается формулой?

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

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

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

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

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

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

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

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

97. Чему равно число внутренней устойчивости графа?

*4

*2

*1

*6

98. Чему равно число внешней устойчивости графа?

*9

*2

*1

*4

99. Чему равен путь минимальной длины от входа к выходу?

*8

*7

*6

100. Чему равен путь максимальной длины от входа к выходу?

*20

*9

*11

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

102. Существует ли СКНФ у тождественно истинной формулы алгебры высказываний?

*да;

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

*нет;

103. Существует ли СДНФ у невыполнимой формулы?

*да;

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

*нет;

104. Соответствуют ли различные релейно-контактные схемы одному и тому же высказыванию?

*всегда;

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

*никогда;

105. Совпадают ли дистрибутивные законы Булевой алгебры и алгебры действительных чисел?

*один совпадает, другой – нет.

*оба совпадают;

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

106. Сколько собственных подмножеств имеет конечное множество Ø?

107. Сколько несобственных подмножеств имеет конечное множество, состоящее из n элементов?

*n.

*2;

*1;

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

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

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

*1

*X=2

*1 при

;

*0

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

*1

*1 при

*0

112. Предикат "1=0" является:

*бинарным.

*тернарным;

*0-местным;

*унарным;

113. Почему множество действительных чисел и множество натуральных чисел не являются эквивалентными?

*не существует биективного отображения между этими множествами.

*множество действительных чисел неупорядочено;

*множество натуральных чисел неупорядочено;

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

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

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

*порядка;

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

:

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

*СКНФ;

*СДНФ;

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

:

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

*СКНФ;

*СДНФ;

117. Определите фиктивные переменные логической функции

:

*x

*z

*y

118. Определите существенные переменные логической функции

:

*z

*y

*x

119. Определите минимальное число ребер, которое нужно удалить, чтобы граф стал древом:

*4

*1

*5

120. Определите минимальное число ребер, которое нужно удалить, чтобы граф стал древом:

*1

*4

*5

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

*0

*x > 1

*1

122. Обладают ли свойством двойственности формулы поглощения?

*нет;

*одна обладает, другая нет.

*да;

123. Обладает ли эйлеровым циклом полный неориентированный граф с числом вершин n=5?

*нет;

*зависит от числа дуг.

*да;

124. Обладает ли эйлеровым циклом полный неориентированный граф с числом вершин n=4?

*да;

*зависит от числа дуг.

*нет;

125. Несвязный граф, компонентами связности которого являются деревья, называется:

*лесом.

*частичным графом;

*сетевым графом;

*прадеревом;

126. На каком графе выделен частичный граф-дерево:

*G2

*G3

*G1

127. Можно ли некоторое высказывание записать в виде релейно-контактной схемы?

*нет;

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

*да;

128. Можно ли в любом бесконечном множестве выделить счетное подмножество?

*можно;

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

*нельзя;

129. Могут ли равносильные высказывания быть записаны в виде некоторой релейно-контактной схемы?

*могут, но не всегда.

*не могут;

*могут;

130. Минимальная полная система логических связок содержит:

*одну связку;

*четыре связки.

*две связки;

*три связки;

131. Какой из данных графов является сетью?

*G2

*G3

*G1

132. Какой из данных графов является планарным?

*G3

*G2

*G1

133. Какой из данных графов является деревом?

*G3

*G1

*G2

134. Какой граф, соответствует данной матрице смежности?

135. Каково число слагаемых СДНФ формулы S(x1, … ,xn)=1?

136. Каково значение X, определяемое уравнением

137. Какие переменные в предикате  являются связными?

138. Какие переменные в предикате  являются свободными?

139. Какие из высказываний S1,S2,S3, состоящих из двух элементарных высказываний А и В, равносильны? S1: "Если А, то не В".S2: "А или не В". S3: "Неверно, что А и В".

*S1=S2

*S2=S3

*S1=S3

140. Если СДНФ формулы S(X1,X2,X3) содержит 3 слагаемых, сколько сомножителей содержит ее СКНФ?

*5.

*4;

*3;

141. Если при проверке правильности рассуждения получен результат P—> Q ≠0, где P – конъюнкция посылок, Q – заключение, то, в таком случае, данное рассуждение является:

*может быть правильным, а может быть и неправильным.

*неправильным;

*правильным;

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

*да;

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

*нет;

143. Если на главной диагонали матрицы смежности стоит единица, то:

*из данной вершины выходит дуга, заканчивающаяся в другой вершине;

*в данной вершине находится петля.

*в данную вершину входит дуга, начинающаяся в другой вершине;

144. Если матрица смежности симметрична, то граф является:

*ориентированным с петлями.

*неориентированным;

*ориентированным с нечетным числом дуг;

145. Если к некоторому бесконечному множеству M прибавить счетное множество A, то в каком соотношении будут находиться мощности множеств M U A и M?

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

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

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

146. Для сетевого графа, соответствующего некоторому проекту, скорейшее время завершение всего проекта совпадает с длиной:

*максимального пути от входа к выходу;

*произвольного пути от входа к выходу.

*минимального пути от входа к выходу;

147. Для сетевого графа, соответствующего некоторому проекту, критический путь представляет собой:

*путь минимальной длины от входа к выходу;

*путь произвольной длины от входа к выходу.

*путь максимальной длины от входа к выходу;

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

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

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

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

149. Граф G получен из графов G1 и G2 путем операции:?

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

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

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

150. Вытекает ли из равенства A\B=C, что A=B U C ?

*в общем случае неверно, но в частном случае возможно.

*да;

*нет;

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

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

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

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

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

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

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

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

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

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