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

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

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

35. Вопрос:

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

*n-1

*n^2

*2^n

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

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

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

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

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

*1

*0

*1