Дискретная математика с элементами математической логики.дпо
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;
2
6. Графы 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. Какие из пар связок образуют полную систему связок?3
0. – множество натуральных чисел. Определить истинное высказывание: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