Hola,
La definición recursiva es la siguiente ( \( Var(\varphi) \) representa el conjunto de todas las variables, libres o no, de \( \varphi \) y \( Free(\varphi) \) el conjunto de sus variables libres):
Si \( \varphi \) es atómica (esto es, de la forma \( t_1=t_2 \) o \( Rt_1...t_n \)) entonces \( Free(\varphi)=Var(\varphi) \).
Si \( \varphi = \neg \psi \) entonces \( Free(\varphi) = Free(\psi) \)
Si \( \varphi = \psi_1 * \psi_2 \), donde * es cualquier conector binario (\( \wedge, \vee, \rightarrow, \leftrightarrow \)) entonces \( Free(\varphi) = Free(\psi_1) \cup Free(\psi_2) \)
Si \( \varphi = Qx \psi \) donde Q es un cuantificador (\( \exists, \forall \)) entonces \( Free(\varphi) = Free(\psi) - \{x \} \)
Con esto puedes calcular el conjunto de variables libres de cualquier fórmula. Por ejemplo, si \( \varphi = \exists x (Px \vee (Py \rightarrow \forall z Pz) \), tenemos \( Free(\varphi) = Free (Px \vee (Py \rightarrow \forall z Pz) - \{ x \} = (Free(Px) \cup Free(Py \rightarrow \forall z Pz)) - \{ x \} = ( \{ x \} \cup Free(Py) \cup Free( \forall z Pz) ) - \{x \} = ( \{x \} \cup \{y \} \cup ( Free(Pz) - \{z \} ) ) - \{x \} = ( \{ x, y \} \cup ( \{ z \} - \{ z \}) ) - \{x \} = \{ x,y \} - \{x \} = \{y \} \)
, así que la única variable libre es y.
Por supuesto no hace falta ser tan explícito ni llegar a tal nivel de detalle, y de hecho en cuanto te has acostumbrado las variables libres y ligadas se ven a ojo, simplemente mirando qué variables caen bajo el alcance de un cuantificados (estas son las ligadas) y cuales no (estas son las libres).
Saludos