Find the free variables of $\phi$ and give an equivalent prenex formula

22 Views Asked by At

Let $\mathbb{L}$ be the first order language where $C=\{c_1\}$ is the set of symbols of constant, $F = \{f^1_1,f^2_1, f^2_2\}$ is the set of symbols of function, $P = \{p^1_1,p^2_1\}$ is the set of predicate symbols, and consider the formula, $\phi = (\forall x_1) p^2_1(f^1_1(x_1),c_1) \implies ((\exists x_2)p^2_1(f^2_1(x_1,x_2),x_2)\lor \lnot p^1_1(x_3))$

a) If possible, give an example of a logically valid formula of $\mathbb{L}$ that contains the term $f^2_1$.

How do I know if the formula is logically valid if I have no idea what $f^2_1$ is? Do I have to define it?

b) Indicate what are the possible occurrences of free variables in $\phi$.

$x_1$ and $x_2$?

c) Determine, if possible, a normal prenex formula that is logically equivalent to $\phi$.

Same question as a).

d) If possible, give an example of a formula $\psi$ such that $\mathbb{L}$ such that $\phi \vDash \psi$.

Same question as a).