Изменения

Рассмотрим формулу <tex>\psi(x, z) = \exists y</tex> <tex>\phi(x, y, z)</tex> как экземпляр задачи <tex>SAT</tex>.<br/>Тогда определение языка <tex>L</tex> можно переписать так: <tex>L=\{z: \forall x</tex> <tex> \phi(x,D_{|\psi(x, z)|}(\psi(x, z)), z)\}</tex>.<br/>Покажем что <tex>(\forall x</tex> <tex> \phi(x,D_{|\psi(x, z)|}(\psi(x, z)), z)</tex> <tex>)\Leftrightarrow</tex> <tex>(\exists DG : </tex> <tex> \forall x</tex> <tex>\phi(x, DG(\psi(x, z)), z))</tex>.<br>Очевидно, из первого следует второе, так как <tex>\exists D G = D_{|\psi(x, z)|}</tex>.Если первое ложно, то <tex>\exists x= x_0 : </tex><tex>\forall y</tex> <tex>\phi(x, y, z) = 0</tex>, а значит <tex>\forall D G </tex> <tex>\exists x = x_0 : \phi (x, D_{|z|}G(\psi(x, z)), z)</tex>, то есть второе ложно.Итого, язык <tex>L=\{z:\exists DG : </tex> <tex>\forall x</tex> <tex>\phi(x, DG(\psi(x, z)), z)\}</tex>, значит <tex>L \in \Sigma_2</tex>.