Prove that

There is a representable relation Tr such that for a formula $\displaystyle \alpha$ and a $\displaystyle v$ which encodes a truth assignment for $\displaystyle \alpha$ (or more), $\displaystyle <\sharp \alpha, v > \in \text{Tr}$ iff that truth assignment satisfies $\displaystyle \alpha$.

http://cs.nyu.edu/courses/fall03/G22...c/lec12_h4.pdf (slide 6-10)

======================================

There are several cases to be considered.

Case 1. $\displaystyle \alpha$ is an atomic formula.

There is representable function $\displaystyle tr$ such that for a formula $\displaystyle \alpha$, $\displaystyle tr(\sharp\alpha) = <\sharp B_0, \ldots, \sharp B_n>$ and $\displaystyle v=<<\sharp B_0, e_0>,\ldots, <\sharp B_n, e_n>>$, where each $\displaystyle B_i$ is a prime constituents of $\displaystyle \alpha$ and each $\displaystyle e_i=0 \text{ or } 1$.

I am trying the first case, but I am stuck here.

Any help will be appreciated.