Prove that

There is a representable relation Tr such that for a formula and a which encodes a truth assignment for (or more), iff that truth assignment satisfies .

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

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

There are several cases to be considered.

Case 1. is an atomic formula.

There is representable function such that for a formula , and , where each is a prime constituents of and each .

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

Any help will be appreciated.