Конспект установочных лекций по комплексному курсу Информатика, Теория информации



Проблема выполнимости для булевских выражений - часть 3


Образованное нами булевское выражение Еx точно тогда выполнимо, когда переменные Ci,z с присвоенными им значениями true

передают корректное вычисление.

В частности, Еx, естественно, должно быть таким, чтобы были справедливы следующие высказывания:

(1)"

i, l £ i < (p(n)+l)^2: $ x:Ci,x;

(2)        bо есть начальная конфигурация Т-машины М с входом х;

(3)        bр(n) есть принимающая конечная конфигурация;

(4)        bi ® bi+1 справедливо по заданному правилу.

Ex соответствует конъюнкции этих четырех высказываний. Точнее говоря, справедливо:

" i: ($ х: Ci,x) Ù Ø$ х, у,  у ¹ х: Ci,x Ù Ci,у.

(1)        Это записывается посредством формулы логики высказываний вида

Ф1Ù...ÙФ(р(n)+1)^2,

где

Фr =  ( Cr,a1 Ú Cr,a2 Ú…Ú Cr,ak) Ù (i,j(i¹j)(ØCr,i Ú ØCr,j))

(2)        Пусть х == <a1 ... аn> есть вход для Т-машины М. Приведенное выше высказывание (2) соответствует конъюнкции следующих высказываний:

(2i) cq,# Ù Cp(n)+i,# ,

(2ii) ci,yi Ú...Úc1,yk^,

 причем yi„ ..., у^ соответствуют знакам, которые кодируют знак а^ состояние qo и номер правила из k возможных, которое исходит из начального состояния qo и знака ai под головкой;

 (2iii)  " i Π {2, ..., п}: Ci,ai.

Остальные знаки а^, ..., an являются корректными.

 (2iv)  " i Π {n+1,..., р(n)}: Ci,#.

Выражение (3) говорит о том, что bр(n) является конечным состоянием. Как описание формулы логики высказываний получаем:

$ i, р(n)*р(n)+1) < i £ (р(n)+1)^2: ($ x Π F: Ci,x),

причем F обозначает множество новых (введенных нами) знаков, которые представляют конечное состояние.

(4)        То, что bi+1 вытекает из bi с помощью законного шага вычислений, проверяется высказыванием

"j, Р(n) < j < (р(n)+1)^2: $ w, х, у, w, x, y, :

Cj-l - (p(n)+l),w Ù Cj - (p(n)+l),x  Ù  Cj+l-(p(n)+l),y Þ Cj-l,w Ù Cj,x Ù Cj+l,y),




Содержание  Назад  Вперед