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

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

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

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

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

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
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. Пусть на множес

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

35. Вопрос:

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

*n-1

*n^2

*2^n

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

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

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

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

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

*1

*0

*1

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. Чему равно цикломатическое число графа?