Дискретная математика (тест с ответами Синергия/МОИ/ МТИ /МОСАП)
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 ?
*в общем случае неверно, но в частном случае возможно.
*да;
*нет;
