PS-полнота языка верных булевых формул с кванторами (TQBF)

Определение:

[math]TQBF[/math] расшивровывается как True Quantified Boolean Formula. Это язык верных булевых формул с квантилями. [math]TQBF=\{Q_1 x_1 Q_2 x_2 \cdots Q_n x_n \phi(x_1, x_2, \dots, x_n), Q_i \in \{\forall, \exists\}\}[/math]

Чтобы доказать, что [math]TQBF \in PS-complete[/math] необходимо показать что:

Лемма (1):

[math]TQBF \in PS[/math]

Лемма (2):

[math] \forall L \in PS \Rightarrow L \leq_p TQBF[/math]