69
правок
Изменения
Нет описания правки
Рассмотрим язык <tex>L \in \Pi_2</tex>, <tex>L = \{z:\forall x </tex> <tex>\exists y </tex> <tex> \phi(x, y, z)\}</tex>.<br/>
Рассмотрим формулу <tex>\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_{|xz|}(x, z), z)\}</tex>.<br/>Покажем что <tex>\forall x</tex> <tex> \phi(x,D_{|xz|}(x, z), z)</tex> <tex>\Leftrightarrow</tex> <tex>\exists D</tex> <tex> \forall x</tex> <tex>\phi(x, D(x, z), z)</tex>.
Очевидно, из первого следует второе, так как <tex>\exists D = D_{|z|}</tex>.
Если первое ложно, то <tex>\exists x</tex><tex>\forall y</tex> <tex>\phi(x, y, z) = 0</tex>, а значит <tex>\forall D \phi (x, D_{|z|}(x, z), z)</tex>, то есть второе ложно.
Итого, язык <tex>L=\{z:\exists D</tex> <tex>\forall x</tex> <tex>\phi(x, D(x, z), z)\}</tex>, значит <tex>L \in \Sigma_2</tex>.
}}
