Witam, mam taki program do napisania i niezbytnio wiem jak się do tego zabrać. Prosiłbym o jakieś wskazówki.
Wiemy że \(\displaystyle{ QSAT \in SPACE( n^{2})}\). Zaimplementować poniższą procedurę rekurencyjną, która zwraca wartość \(\displaystyle{ I(\psi)}\) dla danej formuły \(\displaystyle{ \psi}\) i funkcji \(\displaystyle{ I}\) określonej dla zmiennych wolnych formuły \(\displaystyle{ \psi}\) o wartościach w zbiorze {0,1}
\(\displaystyle{ Eval(\phi; I)}\)
1. Input: \(\displaystyle{ \phi; I}\)
2. if \(\displaystyle{ \psi=X}\) then output \(\displaystyle{ I(X)}\) end
3. if \(\displaystyle{ \psi=( \phi _{1} \vee \phi _{2})}\) then
4. ........if \(\displaystyle{ Eval(\phi _{1}; I) = 1}\) then output 1 end
5. ........else output\(\displaystyle{ Eval(\phi _{2}; I)}\) end
6. if \(\displaystyle{ \psi=( \phi _{1} \wedge \phi _{2})}\) then
7. ........ if \(\displaystyle{ Eval(\phi _{1}; I) = 0}\) then output 0 end
8. ........ else output \(\displaystyle{ Eval(\phi _{2}; I)}\) end
9. if \(\displaystyle{ \psi= \neg \phi}\) then output \(\displaystyle{ 1 - Eval(\phi; I)}\) end
10. if \(\displaystyle{ \psi=\exists X\phi}\) then
11. ........if \(\displaystyle{ Eval(\phi; I[X=0])}\) = 1 then output 1 end
12. ........else output \(\displaystyle{ Eval(\phi; I[X=1])}\) end
10. if \(\displaystyle{ \psi=\forall X\phi}\) then
13. ........if \(\displaystyle{ Eval(\phi; I[X=0])}\) = 0 then output 0 end
14. ........else output \(\displaystyle{ Eval(\phi; I[X=1])}\) end
w linni 2. warunek \(\displaystyle{ \psi = X}\) należy rozumieć jako sprawdzenie,czy \(\displaystyle{ \psi}\) jest zmienną logiczną
w linni 12. i następnych wywołanie procedury z argumentem \(\displaystyle{ I[X=1]}\) oznacza podstawienie wartości 1 dla zmiennej \(\displaystyle{ X}\) w funkcji \(\displaystyle{ I}\)