1. Система булевых функций { f1 ,f2 , … fn  } называется полной, если :
2. Любая булева функция, тождественно не равная нулю, представима и притом единственным образом в виде :
3. Если многочлен Жегалкина функции не содержит ни одной конъюнкции переменных то функция называется:
4. Если функция f(x1 ,…., xn ) несамодаойственна то из неё путём подстановки вместо аргументов хi переменных х или 7х можно получить:
5. Если функция f(x1 ,…., xn ) немонотонна то из неё путём подстановки вместо аргументов хi констант и переменной х можно получить:
6. Если система функций целиком не содержится ни в одном из классов Т0, Т1, S, M, L то:
7. Функцию Х & Y всегда можно получить из суперпозиции функций системы { 0, 1, X, Y, 7X, 7Y, f(X1,…Xn ) }  если:
8. Конъюнкцией двух высказываний А и В называется такое высказывание, которое:
9. Дизъюнкцией двух высказываний А и В называется такое высказывание, которое:
10. Импликацией двух высказываний  А à  В называется такое высказывание, которое:
11. Эквивалентностью двух высказываний А и В называется такое высказывание, которое:
12. Если сложное высказывание истинно при любых наборах значений элементарных высказываний то оно называется:
13. Правило вывода – правило заключения (Modus Ponens) это :
14. Пусть S - множество высказываний , K , L - высказывания, тогда:
15. Обобщенное склеивание дизъюнктов – это:
16. Пусть C = A V L , D = B V 7L тогда резольвентой дизъюнктов С и D называется дизъюнкт:
17. Высказывание о предметных переменных X1 ,… Xn  - это:
18. Предикаты, определенные на предметной области , :
19. Пусть Р(х) – одноместный предикат. Высказывание \-/Х Р(х) будет:
20. Пусть Р(х) – одноместный предикат. Высказывание ЭХ Р(х) будет:
21. Какая из следующих равносильностей не верна:
22. Какая формула находится в предваренной нормальной форма ( ПНФ ):
23. Какая формула находится в сколемовской нормальной форма ( СНФ ):
24. Какая формула не является дизъюнктом:
25.   Дизъюнкт, не содержащий ни одного литерала, называется:
26. Система булевых функций q(t) = x(t) & q(t-1) ; z(t) = x(t) V q(t-1); q(0) = 1 задаёт:
27. Какое свойство автомата не нужно для того чтобы он был совершенным
(полным) автоматом Мура:
28. Какой автомат обязательно содержит автоматно полная система автоматов:
29. Какая запись не может являться командой машины Тьюринга с состоянием останова qZ :
30. Какая конфигурация машины Тьюринга является правильной конфигурацией:
31. Для слова 101 в алфавите А = { 0 , 1 } Гёделевским номером будет число:
32.   Если f( x1,…, xn , 0 ) = g( x1,…, xn  ) ,f( x1,…,xn , y+1) = h(x1,…,xn , y, f(x1,…,xn , y)) то эта операция называется:
33. Какая из следующих рекурсивных функций не является базисной (элементарной) :
34. Какое свойство не является характерным свойством алгоритмов:
35. Что не является математическим определением алгоритма:
36. Пусть алфавит А = { a , b , c , d } . Что не будет являться формулой подстановки в алфавите А:
37. Класс функций, вычислимых по Тьюрингу, совпадает с классом функций, вычислимых по Маркову, и совпадает с :



 
 Булевы функции

1. Сколько существует булевых функций, сохраняющих ноль и единицу?

2. Сколько существует различных самодвойственных булевых функций от n переменных (часть переменных может быть фиктивна)?

3. Сколько существует монотонных функций от 3 переменных?

4. Постройте диаграмму Хассе для проверки монотонности функций от 4 переменных.

5. Выразите штрих Шеффера через стрелку Пирса и, наоборот. Объясните свои выкладки на основе теоремы Поста.

6. Сколько существует линейных булевых функций, сохраняющих ноль?

7. Сколько существует линейных булевых функций, сохраняющих единицу?

 
 

  Исчисление высказываний и предикатов. Метод резолюций.

Даны утверждения A, B, C, D, из которых ровно одно ложно. Требуется выяснить, следует ли из них утверждение E. Перечислите высказывания, к которым нужно применить метод резолюций, чтобы получить ответ.

До скольких кванторов можно уменьшить набор кванторов в следующем выражении, чтобы его смысл не изменился: (Ax)(Ay)(Az)P(x)R(y)S(z) (здесь A-квантор всеобщности, а предикаты соединены конъюнкцией).

Укажите все логические связки, которые могут быть поставлены вместо # так, чтобы формула исчисления предикатов была истинна (здесь A-квантор всеобщности, а E-квантор существования):

(Ax)(P(x)#Q(x)) = (Ax)P(x)# (Ax)Q(x)

(Ax)(P(x)#Q(x)) => (Ax)P(x)# (Ax)Q(x)

(Ax)(P(x)#Q(x)) => (Ex)P(x)# (Ax)Q(x)

Введем новый квантор Q, который определяется так (Qx)P(x)=(Ex)P(x)&(Ex)!P(x) (здесь E-квантор существования, & - конъюнкция, ! - отрицание). Будет ли верна следующая формула: (Qx)(Ey)P(x;y)=(Ey)(Qx) P(x;y). Проверьте другие формулы, аналогичные формулам, рассмотренным в курсе лекций. Указание. Проверьте формулу на множестве M={a; b}, выразив новый квантор через известные логические связки.

 

Языки и грамматики

1. Является ли автоматным язык, полученный симметричной разностью двух языков? Докажите.

2. Является ли язык палиндромов (слова, читающиеся справа налево и слева направо одинаково)

a. автоматным?

b. контекстно-свободным?



Математическая теория алгоритмов

Постройте конечный автомат для вычитания 1 из числа, заданного в двоичной системе (на вход подаются цифры исходного числа в обратном порядке, то есть, начиная с цифр младших разрядов).

Постройте конечный автомат для возведения в куб степени двойки в двоичной системе (цифры подаются слева направо, например, на входе 100, на выходе 1000000).

Можно ли построить конечный автомат для возведения в куб произвольного в двоичной системе? Ответ обоснуйте.

Постройте машину Тьюринга для перевода числа из единичной системы в двоичную.

Постройте нормальный алгорифм Маркова для перевода числа из единичной системы в двоичную.

Опишите с помощью частично-рекурсивных функций алгоритм

определения четности числа (результат 0, если число чётное и 1, если нечётное);

вычитания из большего числа m меньшего числа n;

деления нацело m на n.
 

Прикладная теория алгоритмов

Сколько модификаций пометок будет сделано при реализации алгоритма Дейкстры для пути с n вершинами?

Если источник совпадает с концом пути

Если источник не совпадает с концом пути, но инцидентен ребру, инцидентному концу пути

Если источник лежит ровно посередине пути (пути от источника до обоих концов имеют одинаковое число ребер)

Сколько модификаций пометок будет сделано при реализации алгоритма Дейкстры для бинарного дерева с 2n-1 вершинами?

Если источник находится в корнем дерева

Если источник является листом дерева

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

Неориентированный граф изображен многоугольником с n вершинами. Все ребра имеют вес 1. Сколько модификаций пометок будет сделано в процессе выполнения алгоритма Флойда?

Неориентированный взвешенный граф изображен многоугольником с n вершинами. Какое наибольшее и наименьшее количество модификаций пометок будет сделано в процессе выполнения алгоритма Форда-Беллмана, если граф не имеет циклов отрицательной длины?

Граф имеет n вершин и m ребер, причем имеется k ребер одинакового минимального веса, а остальные ребра имеют разные веса. Укажите значения k, для которых минимальное остовное дерево единственно.

Взвешенный неориентированный связный граф имеет n вершин и m ребер, причем имеется k ребер одинакового максимального веса, а остальные ребра имеют разные веса. Укажите значения k, для которых минимальное остовное дерево единственно.

Все ребра взвешенного неориентированного связного графа имеют разную длину. При каком условии алгоритмы Прима и Краскала будут генерировать одинаковую последовательность ребер отбираемых в остовное дерево (одинаковым должен быть не только набор ребер, но и порядок, в котором эти ребра выбираются).
 

////////////////////////////