Раздел 2. Комбинаторный анализ

Б) нет.

9. Является ли множество несобственным подмножеством самого себя?

а) да;

б) нет.

10. Множества равны, если они содержат:

а) одни и те же элементы;

б) одинаковое количество элементов.

11. Являются ли понятия мощности множества и его кардинального числа идентичными?

а) да;

б) нет.

12. Булеан множества А={{1, 2}, 3} определяется как:

а) ;

б) ;

в) ;

Г) .

13. Какое из утверждений верно для всех множеств А, В, С:

а) если и , то ;

б) если и , то ;

в) если и , то ;

г) ни одно не верно.

14. Какой закон определяется формулой ?

а) элиминации;

б) Порецкого;

в) Де Моргана;

г) инволюции.

15. Чему равно выражение :

а) ;

б) ;

в) ;

Г) .

16. Могут ли повторяться компоненты вектора?

а) да;

б) нет.

17. Длина вектора определяется:

а) числом различных элементов;

б) числом координат.

18. Верно ли: ?

а) да;

б) нет.

19. Какое из соответствий называется взаимно-однозначным:

а) сюръективное, инъективное и функциональное?

б) сюръективное и инъективное?

в) всюду определенное, сюръективное, инъективное и функциональное?

20. Является ли отображение биективным, если оно сюръективно и инъективно?

а) да;

б) нет.

21. Отображение А в В это:

а) частично определенная функция;

б) всюду определенная функция;

в) сюръективное соответствие;

г) инъективное соответствие.

22. Указать определение инъективного соответствия

а) ;

б) ;

в) ;

г) .

23. Какая из формул не задает функцию:

а) ;

б) ;

в) ;

г) .

24. Проекция соответствия на первую ось равна

а)

б)

в)

г)

25. Проекция соответствия на вторую ось равна

а)

б)

в)

г)

26. Указать проекцию множества A={(3,3,5), (3,3,6), (3,5,5), (3,5,6), (8,3,5), (8,3,6), (8,5,5), (8,5,6)} на третью ось

а) PrA={3,8},

б) PrA={3,5},

в)PrA={5,6}.

27. Верно ли: |Аn| = |A|n?

а) да

б) нет.

28. Отношением степени n называется:

а) произвольное подмножество данного множества;

б) подмножество декартова произведения двух множеств;

в) подмножество декартова произведения любого конечного

количества множеств;

г) подмножество декартовой степени множества;

д) результат объединения данных множеств;

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

29. В каком случае и являются совместимыми?

а) ;

б) ;

В) .

30. Для каких из операций над отношениями выполнение условия совместимости является не обязательным:

а) ;

б) ;

в) \ ;

Г) .

31. Отношения являются совместимыми:

а) всегда;

б) если они имеют разные степени;

в) если они имеют одинаковые степени;

г) если они бинарные.

32. Какие из операций реляционной алгебры применимы к отношениям :

а) ;

б) ;

в) \ ;

Г) .

д) все;

е) ни одна не применима.

33. Какие из операций реляционной алгебры применимы к отношениям :

а) ;

б) ;

в) \ ;

г) ;

д) все;

е) ни одна не применима.

34. Операция выбора представляет собой построение:

а) «горизонтального» подмножества отношения;

б) «вертикального» подмножества отношения;

в) «диагонального» подмножества отношения;

г) «бинарного» подмножества отношения;

35. Операция проекции представляет собой построение:

а) «горизонтального» подмножества отношения;

б) «вертикального» подмножества отношения;

в) «диагонального» подмножества отношения.

36. Операция проекции по двум доменам представляет собой построение:

а) «горизонтального» подмножества отношения;

б) «вертикального» подмножества отношения;

в) «диагонального» подмножества отношения;

г) бинарного подмножества отношения.

37. Операция проекции по одному домену представляет собой построение:

а) «горизонтального» подмножества отношения;

б) «вертикального» подмножества отношения;

в) «диагонального» подмножества отношения;

г) бинарного подмножества отношения;

д) некоторого отношения степени n;

е) множества элементов, не являющегося отношением.

38. Какое из отношений является бинарным:

а) ;

б) ;

в) .

39. Если матрица, описывающая бинарное отношение, содержит на главной диагонали и нули и единицы, то отношение:

а) рефлексивно;

б) антирефлексивно;

в) не рефлексивно.

40. Если все вершины графа, описывающего отношение, имеют петли, то отношение:

а) рефлексивно;

б) антирефлексивно;

в) не рефлексивно.

41. Если в графе, описывающем отношение, имеется хотя бы одна пара вершин, соединенных одной дугой, является ли данное отношение симметричным?

а) да;

б) нет.

42. Классы эквивалентности:

а) попарно пересекаются;

б) попарно не пересекаются.

43. Верно ли, что любые два элемента из одного класса эквивалентности эквивалентны?

а) да;

б) нет.

44. Верно ли, что любые два элемента из разных классов эквивалентности не эквивалентны?

а) да;

б) нет.

45. Если отношение антирефлексивно, антисимметрично и транзитивно, оно является:

а) отношением нестрогого порядка;

б) отношением строгого порядка;

в) не является отношением порядка.

46. Если любые два элемента множества M, на котором задано отношение порядка, сравнимы, М является:

а) неупорядоченным;

б) линейно упорядоченным;

в) частично упорядоченным;

47. Среди следующих отношений, заданных на множестве отрезков, укажите отношение порядка:

а) отрезок х равен отрезку у;

б) отрезок х короче отрезка у в 2 раза;

в) отрезок х длиннее отрезка у.

48. Дано множество . Какие из утверждений верны:

а) ;

б) ;

в) ;

Г) .

49. Определить мощность множества :

а) ;

б) ;

в) ;

г) .

50. Определить мощность булеана множества :

а) ;

б) ;

в) ;

Г) .

51. Указать формулу, соответствующую закону элиминации:

а) ;

б) ;

в) ;

Г) .

52.Указать несобственные подмножествами множества :

а) ;

б) ;

в) ;

г) ;

д) .

53. Множества имеют одинаковую мощность, если они содержат:

а) одни и те же элементы;

б) одинаковое количество элементов.

54. Кардинальное число определяет:

а) количество элементов булеана данного множества;

б) количество элементов данного множества.

55. Булеан множества определяется как:

а) ;

б) ;

в) ;

г) .

56. Какой закон определяется формулой ?

а) элиминации;

б) Порецкого;

в) Де Моргана;

г) инволюции

57. Чему равно выражение :

а) ;

б) ;

в) ;

г) ;

д) ;

е) .

58. Чему равна мощность булеана множества :

а) ;

б) ;

в) ;

г) .

59. Операция объединения двух множеств есть совокупность элементов:

а) различных для этих множеств;

б) принадлежащих одному или другому множеству;

в) принадлежащих обоим множествам.

60. Операция пересечения двух множеств есть совокупность:

а) элементов, одинаковых для этих множеств;

б) элементов, различных для этих множеств;

в) элементов, принадлежащих одному или другому множеству.

61. Операция симметрической разности обозначается символом:

а) ;

б) ;

в) ;

г) .

62. Размерность вектора есть:

а) количество всех его компонентов;

б) количество различных его компонентов.

63. Какое из данных соответствий является всюду определенным:

а) б) в)

64. Какое из данных соответствий является функциональным:

а) б) в)

65. Какое из данных соответствий является инъективным:

а) б) в)

66. Какое из данных соответствий является биективным:

а) б) в) г)

67. Какие соответствия не являются инъективными:

а) б) в) г)

68. Какие соответствия не являются функциональными:

а) б) в) г)

69. Какие соответствия являются сюръективными:

а) б) в) г)

70. Какие соответствия являются всюду определенными:

а) б) в) г)

71. Какой из законов не обязательно присутствует в определении решетки:

а) коммутативный;

б) дистрибутивный;

в) элиминации;

г) ассоциативный?

72. Какой закон в дополнение к обязательным определяет решетку как булеву алгебру:

а) дистрибутивный;

б) коммутативный;

в) элиминации;

г) ассоциативный?

73. Решетка определяется на:

а) произвольном множестве;

б) линейно упорядоченном множестве;

в) частично упорядоченном множестве;

г) неупорядоченном множестве?

74. Какое из условий определяет дедекиндову решетку:

а) ;

б) ;

в) ;

г) ,

д) ,

е)

75. Какое из условий определяет дистрибутивную решетку в дополнение к свойству модулярности:

а) ;

б) ;

в) ;

г) ,

д) ,

е)

Раздел 2. Комбинаторный анализ

1. Число перестановок из 5 элементов равно:

а) 5; б) 25; в) 120; г) 1.

2. Имеет ли подстановка неподвижную точку

а) да;

б) нет.

3. Имеет ли подстановка инверсии

а) да;

б) нет.

4. Являются ли перестановки с повторениями различными: А Б С, А Б А?

а) да;

б) нет.

5. Являются ли перестановки различными:

А А Б, А Б А; А В С, А В А;

а) да;

б) нет.

6. Сколькими способами можно расставить на полке 4 книги?

а) 4

б) 4!

в)

г) .

7. Являются ли перестановки с повторениями различными: А А Б, А Б А?

а) да;

б) нет.

8. Выбрать верный вариант:

а) при k<n

б) при k>n

9. Биномиальные коэффициенты определяются формулой:

а)

б)

в)

г)

10. Полиномиальные коэффициенты определяются формулой:

а)

б)

в)

г)

11. Выбрать верный вариант:

а)

б)

в)

12. Выбрать верный вариант:

а)

б)

в)

13. Выбрать верный вариант:

а)

б)

в)

14. Свойство симметрии биномиальных коэффициентов определяется как:

а)

б)

в)

15. Сколько существует способов выбрать 3 книги из 5?

а) 0;

б) 1;

в) ;

г) .

16. Являются ли сочетания с повторениями различными: МАМА, МАША?

а) да;

б) нет.

17. Являются ли сочетания с повторениями различными: ПАПА, АППА?

а) да;

б) нет.

18. Какие из сочетаний с повторениями являются различными?

а) МАМА, МАША;

б) ПАПА, АППА;

в) ПАРА, РАПА.

19. Какие из размещений являются идентичными:

а) abcba, abcba;

б) abc, cba;

в) abce, abc.

20. Какие из сочетаний являются идентичными:

а) 123, 232;

б)abc, cba;

в) КСМ, МСК.

21. Сколькими способами можно рассадить 4 человека на n местах?

а) 4

б) 4!

в)

г)

д)

22. Указать формулу для определения числа размещений:

а)

б)

в)

23. Какие комбинаторные конфигурации являются упорядоченными:

а) перестановки;

б) размещения;

в) сочетания.

24. В каком случае мощность множества больше:

а) в размещении без повторений;

б) в размещении с повторениями;

в) одинаково.

25. Является ли размещение перестановкой:

а) никогда;

б) всегда;

в) да, при k<n;

г)да, при k=n.

Раздел 3. Булева алгебра

1. Сколько двоичных наборов содержит таблица истинности функции f(a,b,c)?

а) 2;

б) 3;

в) 7;

г) 8?

2. Какая из формул допускает упрощение:

а) ;

б) ;

в) ;

г) ?

3. Какая из формул представляет закон элиминации:

а) ;

б) ;

в) ;

г) ?

4. Чему равно логическое выражение :

а) 0;

б) ;

в) ;

г) 1?

5. Предельное дизъюнктивное разложение функции по теореме Шеннона есть

а) СКНФ;

б) СДНФ;

в) ДНФ;

г) КНФ?

6. На каком входном наборе конъюнкция двух переменных равна единице:

а) 0,0;

б) 0,1;

в) 1,0;

г) 1,1.

7. На каком входном наборе дизъюнкция двух переменных равна единице:

а) 0,0;

б) 0,1;

в) 1,0;

г) 1,1.

8. Конъюнкция некоторого числа переменных равна единице, когда:

а) все переменные равны единице;

б) все переменные равны нулю;

в) хотя бы одна переменная равна единице;

г) хотя бы одна переменная равна нулю.

9. Дизъюнкция некоторого числа переменных равна единице, когда:

а) все переменные равны единице;

б) все переменные равны нулю;

в) хотя бы одна переменная равна единице;

г) хотя бы одна переменная равна нулю.

10. Чему равно выражение :

а) ;

б) ;

в) ;

Г) ?

11. Какой элемент реализует функцию логического сложения:

а)

б)

в)

г)

12. Какой элемент реализует функцию логического умножения:

а)

б)

в)

г)

13. Какой функциональный элемент соответствует сумме по модулю 2:

а)

б)

в)

г)

14. Какой элемент соответствует функции равнозначности:

а)

б)

в)

г)

15. Функция является самодвойственной?

а) да;

б) нет.

16. Функция является:

а) сохраняющей единицу;

б) сохраняющей ноль;

в) монотонной?

17. Функция является:

а) самодвойственной;

б) сохраняющей единицу;

в) сохраняющей ноль;

г) монотонной?

18. Какие из кубов представляют точку:

а) 0-куб;

б) 1-куб;

в) 2-куб;

г) любой.

19. Какие из кубов задают отрезок:

а) 0-куб;

б) 1-куб;

в) 2-куб;

г) любой.

20. Какие из кубов представляют плоскость:

а) 0-куб;

б) 1-куб;

в) 2-куб;

г) любой.

21. Указать куб, который геометрически можно интерпретировать как плоскость:

а) Х00;

б) 0ХХ;

в) 101;

г) любой.

22. Указать куб, который геометрически можно интерпретировать как отрезок:

а) Х0Х;

б) 01Х;

в) 101;

г) любой.

23. Указать куб, который геометрически можно интерпретировать как точку:

а) 100;

б) 0ХХ;

в) 10Х;

г) любой.

24. Куб 1Х1 геометрически можно интерпретировать как:

а) плоскость;

б) отрезок;

в) точку.

25. Указать, какие кубы склеиваются:

а) Х00, Х10 ;

б) 011, 100;

в) 10Х, 01Х;

г) ни одна пара не склеивается.

26. Склеивание кубов 010 и 011 дает:

а) Х00;

б) 0ХХ;

в) 101;

г) 01Х.

27. Куб ХХ1 является

а) 1-кубом;

б) 2-кубом;

в) 0-кубом.

28. Куб 00Х является

а) 1-кубом;

б) 2-кубом;

в) 0-кубом.

29. Куб 011 является

а) 1-кубом;

б) 2-кубом;

в) 0-кубом.

30. Каждая импликанта в СДНФ соответствует

а) нулевому значению функции;

б) значению функции, равному единице.

31. Каждая импликанта в СКНФ соответствует

а) нулевому значению функции;

б) значению функции, равному единице.

32. Первая производная функции по переменной x равна . Какие значения сигналов не являются условием возможной активизации выхода при изменении сигнала x:

а) 1,0;

б) 0,1;

в) 1,1;

г) 0,0 ?

33. Альтернативное понятие для минимизации есть:

a) факторизация;

б) поглощение;

в) булевизация;

г) разложение.

34. Поставить в соответствие функциям их таблицы истинности:

1) а b c d

2) а b c d

3) а b c d

4) а b c d

35. Поставить в соответствие кубическим покрытиям их таблицы истинности:

1) а b c d

2) а b c d

3) а b c d

4) а b c d

36. Разложение булевой функции по Шеннону предназначено для:

а) факторизации;

b) максимизации;

c) минимизации;

d) получения таблицы истинности

e) построения СДНФ;

f) получения СКНФ.

Ответ: b,d,e,f

37. Какая из формул разложения Шеннона приводит к получению СКНФ:

a) ;

b)

c)

d)

9. Какие из приведенных уравнений истинны:

а)

б)

в)

г)

д)

38. Кубическое покрытие (КП) логического элемента есть:

а) таблица переходов;

b) таблица истинности;

c) неполная таблица истинности;

d) минимизированная таблица истинности.

39. Какие из следующих утверждений истинны:

а) кубическое покрытие не может быть таблицей истинности;

b) куб обозначает плоскость, если он имеет два символа Х;

c) КП дискретного элемента не может иметь на выходных координатах символы Х;

d) число кубов в покрытии может быть больше числа строк таблицы истинности.

40. Какие из схем реализуют функцию

1) все

2) ни одна

3) а

4) b

5) c

6) d

41. Какая из функций соответствует минимальной ДНФ для заданной карты Карно:

a)

б)

в)

г)

д) все

е) ни одна

Раздел 4. Теория графов

1. Ребра называются смежными, если они

а) инцидентны одной и той же вершине

б) параллельны

в) являются кратными

2. Если две вершины соединены одной дугой, они называются

а) инцидентными

б) коинцидентными

в) смежными

3. Какие из графов являются подграфами данного графа G

а) б) в) г)

4. Если любые две вершины графа можно соединить простой цепью, то граф называется:

а) связным;

б) несвязным;

в) деревом;

г) остовом.

5. Сколько вершин содержит гамильтонов цикл графа с 5 вершинами?

а) 5

б) 4

в) 6

6. Граф содержит 7 дуг. Его эйлеров цикл будет состоять из

а) 6 дуг

б) 7 дуг

в) 8 дуг

7. Эйлеров цикл

а) содержит каждое ребро только один раз;

б) содержит каждую вершину только один раз;

в) проходит через все вершины и ребра графа только один раз.

8. Гамильтонов цикл

а) содержит каждое ребро только один раз;

б) содержит каждую вершину только один раз;

в) проходит через все вершины и ребра графа только один раз.

9. В эйлеровом графе все вершины

а) четной степени;

б) нечетной степени.

10. В полуэйлеровом графе допускаются

а) 3 вершины нечетной степени;

б) 2 вершины нечетной степени;

в) 1 вершина нечетной степени.

11. Какой алгоритм определяет гамильтоновы циклы графа:

а) Гильберта-Мура;

б) Флери;

в) Робертса-Флореса;

г) Дейкстры.

12. Какой из циклов графа с множеством вершин {a,b,c,d,e,f} является гамильтоновым?

а) abeca

б) fbecdf

в)abecdfa

г) abcdfca

13. Какой граф является гамильтоновым:

а)

б)

в)

14. В алгебраической форме представления графов аксиома о единичном элементе формулируется следующим образом:

а)

б)

в)

г)

15. В алгебраической форме представления графов имеет ли место свойство коммутативности относительно операции конкатенации для ориентированных графов?

а) да

б) нет.

16. Правило минимизации фрагмента графа:

а) ;

б) ;

в) .

17. Какая из аксиом абстрактной математической решетки не содержится в АФПГ:

а) ассоциативность;

б) дистрибутивность;

в) аксиома о единичном элементе;

г) аксиома о нулевом элементе.

18.Задача коммивояжера решается при помощи:

а) алгоритма Гильберта-Мура;

б) метода ветвей и границ;

в) алгоритма Краскала;

г) метода динамического программирования.

19. Увеличение нижней границы стоимостей решений в левых узлах поддерева осуществляется за счет:

а) выбора в преобразованной матрице стоимостей нуля, который при замене его на бесконечность позволяет вычесть наибольшее суммарное количество из строки и столбца, на пересечении которых он находится;

б) вычитания из строк и столбцов матрицы после понижения ее порядка минимальных элементов.

20. Выбор в преобразованной матрице стоимостей нуля, который при замене его на бесконечность позволяет вычесть наибольшее суммарное количество из строки и столбца, на пересечении которых он находится, определяет увеличение нижней границы стоимостей решений

а) в левых узлах поддерева;

б) в правых узлах поддерева.

21. Вычитание из строк и столбцов матрицы после понижения ее порядка минимальных элементов определяет увеличение нижней границы стоимостей решений:

а) в левых узлах поддерева;

б) в правых узлах поддерева.

22. Увеличение нижней границы стоимостей решений в правых узлах поддерева осуществляется за счет:

а) выбора в преобразованной матрице стоимостей нуля, который при замене его на бесконечность позволяет вычесть наибольшее суммарное количество из строки и столбца, на пересечении которых он находится;

б) вычитания из строк и столбцов матрицы после понижения ее порядка минимальных элементов.

23. Какой алгоритм осуществляет построение оптимального дерева бинарного поиска:

а) Краскала;

б) Флери;

в) Робертса-Флореса;

г) Гильберта-Мура.

24. Глубина элемента а₂ в дереве равна

а) 0;

б) 1;

в) 2;

г) 3.

25. Степень вершины а₂ в графе равна

а) 0;

б) 1;

в) 2;

г) 3.

26. В оптимальном дереве бинарного поиска поиск завершается успешно в случае, когда:

а) корень отсутствует;

б) искомый элемент равен корню.

27. В оптимальном дереве бинарного поиска успешный поиск завершается

а) в листьях дерева;

б) во внутренних вершинах.

28. Алгоритм построения ОДБП организован:

а) снизу вверх;

б) сверху вниз.

29. Алгоритм построения ОДБП демонстрирует эффективность

а) метода ветвей и границ;

б) метода перебора Робертса-Флореса;

в) метода динамического программирования;

г) алгебраического метода поиска гамильтонового цила.

30. Стоимость дерева определяется формулой

а)

б)

в)

31. Алгоритм Краскала осуществялет:

а) построение дерева кратчайших путей;

б) построение оптимального дерева бинарного поиска;

в) построение кратчайшего остова.

32. В графе из n вершин остов содержит:

а) n+1 ребро;

б)n-1 ребро;

в) nребер;

г) 2nребер.

33. Дерево есть:

а) связный граф;

б) граф без циклов;

в) остовный подграф графа;

г) связный граф без циклов.

34. Простая цепь это:

а) маршрут минимальной стоимости;

б) маршрут, где нет повторяющихся вершин;

в) маршрут, где нет повторяющихся ребер;

г) маршрут, где нет повторяющихся вершин и ребер.

35. Расстояние между вершинами есть

а) сумма длин ребер, входящих в путь;

б) длина кратчайшего пути.

36. Алгоритм Дейкстры определяет:

а) кратчайший остов графа;

б) построение дерева кратчайших путей;

в) построение оптимального дерева бинарного поиска;

г) эйлеровы циклы графа.

37. В алгоритме Дейкстры текущие числовые метки

а) неубывают;

б) невозрастают;

в) равны нулю;

г) отрицательные.

38. В алгоритме Дейкстры текущая числовая метка определяется

а) сложением двух предыдущих;

б) вычитанием двух предыдущих;

в) по минимуму из двух предыдущих;

г) сложением с постоянной меткой и сравнением с предыдущей.

39. Постоянные метки в алгоритме Дейкстры

а) убывают;

б) возрастают;

в) неубывают.

40. Постоянно помеченные вершины

а) повторяются;

б) не повторяются.

41. Определение постоянно помеченной вершины включает:

а) вычисление текущих меток для всех вершин и нахождение минимума среди них;

б) вычисление текущих меток для всех вершин и нахождение максимума среди них;

в) вычисление текущих меток для всех вершин и нахождение их среднего арифметического.

42. Мощность замкнутого теоретико-множественного алфавита, порожденного шестиэлементным универсумом равна:

а) 36;

б) 64;

в) 32.

43. Можно ли модель цифрового объекта представить ориентированным графом?

а) да

б) нет

44. Комбинационная схема является конечным автоматом:

а) да

б) нет

47. Можно ли без логического элемента НЕ построить модель триггера?

а) да

б) нет

48. Является ли элемент 3И-НЕ, имеющий обратную связь, элементом памяти?

а) да

б) нет

49. Структуры “булев граф” и “булево дерево”:

а) являются идентичными

б) обе имеют сходящиеся разветвления

в) отличаются наличием сходящихся разветвлений

50. Структура “булев граф”

а) имеет сходящиеся разветвления

б) не имеет сходящихся разветвлений

51. Структура “булево дерево”

а) имеет сходящиеся разветвления

б) не имеет сходящихся разветвлений

52. СДНФ соответствует схеме типа “булево дерево”:

а) да

б) нет

55. Состояние конечного автомата не может измениться без наличия изменения на входах

а) да

б) нет

56. Множество {0, 1, X, } является самым минимальным теоретико-множественным замкнутым алфавитом.

а) да

б) нет

57. Поведение триггера описывается булевыми функциями

а) да

б) нет

58. Значения функции 2ИЛИ равны соответственно 0-Х-1 при подаче последовательности наборов 0Х-ХХ-Х1:

а) да

б) нет

59. Число кубов в КП всегда меньше количества строк таблицы истинности

а) да

б) нет

60. Минимальное число кубов в КП ПЭ 16ИЛИ-НЕ равно 16

а) да

б) нет

61. Можно ли по КП ПЭ записать ДНФ?

а) да

б) нет

62. Существуют ли кубы, для которых результаты выполнения операций минимизации (оператор сограней) и поглощения равны?

а) да

б) нет

63. Переменная, определенная символом X в кубе покрытия, является в ПЭ

а) несущественной

б) существенной

64. Может ли КП неконстантной булевой функции иметь один куб?

а) да

б) нет

65. КП не может иметь координаты, определенные символом .

а) да

б) нет

66. Реакция выходов комбинационной схемы на двоичный вектор не может иметь символов X

а) да

б) нет

67. Сколько кубов содержит минимальная кубическая форма представления сильносвязного графа, имеющего четыре вершины:

а) 16;

б) 8;

в) 1?

68. Количество дуг в графе, определенное кубом LL, равно:

а) 8;

б) 12;

в) 9.

69. Можно ли символами двухтактного алфавита описать поведение элемента 2ИЛИ-НЕ?

а) да

б) нет

71. Может ли КП элемента быть равно таблице истинности?

а) да

б) нет

74. В тривиальном автомате функция выходов не зависит от состояния автомата

а) да

б) нет

76. Существует ли ПЭ (примитивный элемент), имеющий минимальное кубическое покрытие без символов X?

а) да

б) нет

77. Возможна ли минимизация векторов

01X01X10

11X01110

а) да

б) нет

78. Выполнима ли операция поглощения для векторов

SE010XFP

JE010XSH

а) да

б) нет

79. Может ли граф, имеющий две вершины, описываться кубом КФПГ, равным FF?

а) да

б) нет

80. Какое минимальное число символов необходимо для описания информационных процессов?

а) один

б) два

в) четыре

81. Сколько двоичных векторов содержит куб 01X10X10?

а) один

б) два

в) четыре

82. КП – это минимизированная таблица истинности, записанная в алфавите {0,1,X}

а) да

б) нет

83. Всегда ли можно по КП ПЭ восстановить его таблицу истинности?

а) да

б) нет

84. Можно ли однозначно по КФПГ восстановить исходный граф?

а) да

б) нет

85. Два различных графа не могут иметь одинаковые КФПГ

а) да

б) нет

86. Можно ли с помощью КФПГ описать несвязные вершины?

а) да

б) нет

87. Может ли граф, имеющий две вершины, описываться кубом FL?

а) да

б) нет

88. Граф несвязных вершин нельзя описывать с помощью КФПГ

а) да

б) нет

89. Неориентированный граф можно описывать с помощью КФПГ

а) да

б) нет

90. Любой сильносвязный граф может быть представлен одним кубом

а) да

б) нет