# I First order logic - help with translation algorithm between

Tags:
1. Jun 5, 2016

### ENgez

given a dictionary $$\Sigma = \left \{f(),g(),R(,),c_0,c_1,c_2 \right \}$$ and a sentence $\phi$ over $\Sigma$, I need to find an algorithm to translate $\phi$ to $\psi$ over $\Sigma'$ where $\Sigma' = \left \{Q(,,,), = \right \}$ (Q is a 4-place relation symbol), so that $\psi$ is valid iff $\phi$ is valid.

I understand that I am supposed to eliminate function symbols using the equality relation in $\Sigma'$, so that $f()$ in $\Sigma$ is translated to a relation symbol $\ F(,)$ , so that $\ F(a,b)$ holds iff $\ f(a)=b$ (and likewise for $g()$).

the constants can be translated to 1-ary relation symbols.

Therefore, I have an intermediate dictionary
$$\Sigma'' = \left \{F(,),G(,),R(,),C_0(),C_1(),C_2(), = \right \}$$

I need to somehow encode the six relation symbols (3 binary and 3 unary) in $Q(,,,)$. Is there a particular way to do this, is this related to equivalence classes?

thank you.

2. Jun 10, 2016