Контрольная «Теория алгоритмов»

№1. Перечислите свободные и связанные вхождения каждой из переменных в следующей формуле:

(«х)[(«z)(Р(x,z) → Q(y))Ù($y)(R(x,y,z))].

№2. Выяснить, будут ли равносильны следующие формулы:

(«х)(F(x) → G(x)) и («х)F(x) → («х)G(x).

№3. Привести к п.н.ф. следующую формулу логики предикатов:

В ≡ $х»уР(х,у) Ú $х»уQ(х,у).

№4. Докажите, что имеют место следующие выводимости, построив соответствующие выводы из гипотез:

F → G, F → (G → H), F ├ H.

№5. Машина Тьюринга задается следующей функциональной схемой:

Определите, в какое слово перерабатывает машина слово 1111*11, исходя из начального стандартного состояния.

№6. Нормальный алгоритм в алфавите А = {a, b} задается схемой:         ba → ab, ab → Λ. Примените его к слову abaabb.