Logical equivalence of a given formula

39 Views Asked by At

Is it true that $$ a(x) \Rightarrow \forall{y} \varphi(x,y) \equiv \forall{y} \left( a(x) \Rightarrow \varphi(x,y) \right), $$

where $a(x)$ is a quantifier free formula with only one free variable $x$ and $\varphi(x,y)$ is a quantifier free formula with free variables $x,y$ ?

In my opinion it's true, but I need to clarify this fact.

2

There are 2 best solutions below

0
On BEST ANSWER

Suppose the one on the left is false. Then we have an $m$ such that $a(m)$ while $\neg\phi(m,n)$ for some $n$, making $a(m) \to \phi(m,n)$ false, and thus also $\forall y (a(m) \to \phi(m,y)$ and also $\forall y (a(x) \to \phi(x,y)$ - the one on the right - false.

Now do the same thing for the case where the one on the left is true, and show that the one on the right also is, proving the biconditional.

Check out this page on Wiki, on the section "Implication" under "converting to prenex normal form".

0
On

$$\begin{align} a(x) \implies \forall y~ \varphi(x, y) &\equiv \lnot a(x) \lor \forall y~ \varphi(x, y) \\ &\equiv \forall y~ (\lnot a(x) \lor \varphi(x, y) \\ &\equiv \forall y~ (a(x) \implies \varphi(x, y)) \end{align}$$

Using $B \lor \forall y A(y) \equiv \forall y ~ B \lor A(y)$ which is the generalization of $B \lor (A(0) \land A(1) \land A(2) \dots) \equiv (B \lor A(0)) \land (B \lor A(1)) \land (B \lor A(2)) \dots $