Булева функция. Количество циклов в системе базисных циклов графа. Многочлен Жегалкина функции

ДИСКРЕТНАЯ МАТЕМАТИКА

1.  Автоматы   и  называются эквивалентными, если:

Ответ: они реализуют один и тот же словарный оператор (или , )

      (для любого состояния автомата  найдется эквивалентное ему состояние r автомата  и наоборот)

2.  Булева функция  равна 0, если , и равна 1 для остальных значений переменных. Сколько простых импликант имеет функция ?

Ответ:2) 12

3.  Булева функция  равна 0, если , и равна 1 для остальных значений переменных. Сколько простых импликант имеет функция?

Ответ: 1) 6

4.  В какой из классов Поста входит функция   (конъюнкция)? Ответ: 3) М

5.  В какой из классов Поста входит функция  (дизъюнкция)? Ответ: 3) М

6.  В какой из классов Поста входит функция ?                        Ответ: 2) L

7.  Деревом называется –

Ответ: 1) связный граф, не имеющий циклов

8.  Декатовым произведением  множеств  и называется:

      Ответ:

9.  Для того чтобы мультиграф обладал эйлеровым циклом, необходимо и достаточно чтобы:

      Ответ: мультиграф был связным и степени всех его вершин были четными

10.  Если дерево имеет  вершин, то число его ребер равно: 

Ответ: 3)

11.  Какая из следующих формул является дизъюнктивной нормальной формой? Ответ:

12.  Какая из следующих формул является конъюнктивной нормальной формой? Ответ: 2)

13.  Какой из классов Поста содержит все функции от одной переменной?      Ответ: Класс L линейных функций

14.  Какой из перечисленных графов обадает эйлеровым циклом?

      Ответ: 1) Полный пятивершинный граф

15.  Количество циклов в системе базисных циклов графа равно:

Ответ:3)  цикломатическому числу графа

16.  Конечный автомат  реализует ограниченно-детерминированный словарный оператор . Пусть –число состояний автомата, а - число остаточных операторов оператора . Какое из следующих неравенств верно для каждого автомата? 

        Ответ: 2)

17.  Конечный автомат  является минимальным автоматом для ограниченно-детерминированного словарного оператора . Пусть  - число состояний автомата, а  - число остаточных операторов оператора . Какое из следующих соотношений справедливо?

        Ответ: 3)

18.  Конъюнкция  называется импликантой булевой функции

Ответ: , если из того, что  следует, что

19.  Критическим путем в сетевом графике называется:

Ответ: 2) путь максимальной длины из начальной вершины в конечную

20.  Найти многочлен Жегалкина функции

Ответ:

21.  Найти многочлен Жегалкина функции

Ответ:

22.  Найти многочлен Жегалкина функции

Ответ: 1)

23.  Последовательность задана рекуррентно . Чему равен ?     

Ответ: 3)

24.  Последовательность задана рекуррентно . Чему равен ?

Ответ: 2) 1

25.  Программа машины Тьюринга содержит следующие инструкции  (- обозначение пустой ячейки ленты, ! – заключительного состояния,  - обозначения перемещения по ленте влево, вправо или отсутствия перемещения). В начальный момент времени на ленту записывается слово 1011 и управляющая головка машины в состоянии устанавливается на правый символ слова. Какое слово будет на ленте после остановки машины?  

Ответ: 2) 1100

26.  Программа машины Тьюринга содержит следующие инструкции  (- обозначение пустой ячейки ленты, ! – заключительного состояния,  - обозначения перемещения по ленте влево, вправо или отсутствия перемещения). В начальный момент времени на ленту записывается слово 111 и управляющая головка машины в состоянии устанавливается на правый символ слова. Какое слово будет на ленте после остановки машины?  

Ответ: 3) Машина не остановится

27.  Производящей функцией последовательности называется функция:

Ответ: 3)

28.  Производящей функцией последовательности (1, -1, 1, -1,…)  является функция:    

Ответ: 1)  

29.  Пусть производящая функция последовательности  равна . Какой будет производящая функция последовательности ?

Ответ: