FOL substitution - is it possible to substitute two variables with each other? e.g. $\theta=\{x/y,y/x\}$?
Given the usual substitution function $[x/y]$ s.t. 


  $M[x/y]$ is the result of substituting all free occurrences of '$y$' with '$x$' in $M$,


your desired function can be defined as follows:


  $M [x//y] =_{df} M[x'/y][y/x][x/x']$ provided $x'$ doesn't occur in $M$.


Example. Let $C = m(P,X,Y)←m(Q,X,Z),m(R,Z,Y)$. Then:

\begin{align*}
D &amp;= C~[Q~//~R]\\
&amp;= [m(P,X,Y)←m(Q,X,Z),m(R,Z,Y)][Q'/R][R/Q][Q/Q'] \\
&amp;= [m(P,X,Y)←m(Q,X,Z),m(Q',Z,Y)][R/Q][Q/Q']\\
&amp;= [m(P,X,Y)←m(R,X,Z),m(Q',Z,Y)][Q/Q']\\
&amp;= m(P,X,Y)←m(R,X,Z),m(Q,Z,Y)
\end{align*}