Постройте минимальные УБДР для функции f(x1, x2, x3, x4)= (x1 ∨ x2) + ( x3 ∨ x4) относительно двух упорядочений переменных:

a) x1 < x2 < x3 < x4 и

b) x1 < x3 < x2 < x4.

Определите сложности этих двух схем.

Правильный ответ:

• # В доказательстве теоремы 10.1 для построения м.Т., реализующей оператор примитивной рекурсии F(x,y) = R( g1, f3), требовалась м.Т. M1, которая переводит конфигурацию вида |x* |y в конфигурацию |y * |x* ∧ *|g(x) , используя м.Т. Mg, вычисляющую функцию g(x). Какие из следующих программ м.Т. выполняют требуемую работу, т.е. могут быть использованы в качестве программы для M1 ? P1 = Коп# ; par# (par* (Чист, Пуст); Зам(*,∧ ) , par* (Пуст ,Чист); Зам(*,∧ ) ); par# (Пуст, Коп* ); par* (Пуст, +1; +1; Зам(|,∧ ); Зам(|,* )); par* (Пуст, Пуст, Mg); Зам( #,* ) P2 = Коп# ; par# (par* (Чист, Пуст); Зам(*,∧ ) , par* (Пуст ,Чист); Зам(*,∧ ) ); par# (Пуст, Коп# ); par# (Пуст, Пуст, Mg ; +1; +1; Зам(|,∧ ); Зам(|,* )); Зам( #,* ); Зам( #,* ) P3 = Коп* ; par* (Чист, Пуст, Пуст ,Чист); Зам(*,∧ ); Зам(*,# ); Зам(*,∧ ); par# (Пуст, Mg ; +1; +1; Зам(|,∧ ); Зам(|,* )); Зам( #,* ) В этих определениях участвуют следующие простые машины Тьюринга: Копa – копирует вход после разделительного символа a : w ⇐ w a w;Зам(a, b) – заменяет первое слева вхождение символа a на b: w1a w2 ⇐ w1 b w2 ( a ∉ w1 );Пуст – не изменяет аргумент: w ⇐ w ;Чист – стирает аргумент: w ⇐ ∧ ;+1 – прибавляет 1 к аргументу: |x ⇐ |x+1
• # Пусть задана логическая схема S=(V, E) : V= {a (X), b(Y), c(Z), d(V), e(∧), f(¬),g(¬),h(∧), i(∧), k(¬), m(∨) } (после имени вершины в скобках указана ее метка - переменная или булева функция), E= { (a, e), (b, f), (c, g), (d, e), (d, i), (e, k), (f, h), (g,, h), (h, i),(i, m), (k, m) }. Какие из следующих линейных программ вычисляют в переменной Z ту же функцию F(X,Y,Z,V), что и схема S в вершине m? P1: P2: P3: V = X ∧ V; f = ¬Y; Y = ¬Y; V = ¬V; g = ¬Z; Z = ¬Z; Y = ¬Y; e = X ∧ V; Z = Y ∧Z; Z = ¬Z; k = ¬e; Z = Z ∧V; Y = Y ∧ Z; h = f ∧ g; V = X ∧ V; Z = Y ∧ V; i = h ∧ V; V = ¬V; Z = V ∨ Z . Z = h ∨ k. Z = Z ∧ V.
• # [Большая Картинка] Какую булеву функцию реализует эта диаграмма? (В ответах функции заданы последовательностями 8 нулей и единиц - их значениями на лексикографически упорядоченных наборах значений аргументов x1, x2 и x3)
• # Пусть задан недетерминированный конечный автомат M = < {a, b}, {0, 1, 2, 3, 4 ,5}, 0, F={4, 5}, Φ> с программой Φ: 0 b →​ 1, 0 →​ 2, 1 a →​ 2, 1 b →​ 4, 2 →​ 3, 2 →​ 5, 3 a →​ 4, 3 b →​ 2, 4 →​ 5 Какой из следующих НКА получится из M после применения процедуры устранения пустых переходов?
• # Пусть заданы три функции: f(x,y,z) = xy +z, g(x,y) = 2x - y, h(x) =2x2 Какую функцию F(x1,x2) задает выражение [g; [f; I22 , I22 , I21 ], [h;[s1; I22 ]] ?