Is there a prop.-logic formula $P$ s.t. $\forall x(\phi(x)\lor\psi(x))\iff P(\forall x\phi(x),\exists x\phi(x), \forall x\psi(x),\exists x\psi(x))$?

81 Views Asked by At

I could prove (hopefully correctly) that $$ \forall x (\varphi(x) \land \psi(x)) \equiv \forall x \varphi(x) \land \forall x \psi(x) $$ ($\forall$ distributes over $\land$), and $$ \forall x (\varphi(x) \lor \psi(x)) \vdash \forall x \varphi(x) \lor \exists x \psi(x) $$ which is just an implication but not an equivalence, since it is not symmetric in $\varphi$ and $\psi$, as it should be.

The idea is to write an equivalent of $\forall x (\varphi(x) \lor \psi(x))$ in terms of $\forall x \varphi(x), \exists x \varphi(x), \forall x \psi(x)$ and $ \exists x \psi(x)$ connected only by logical connectors $\land,\lor,\to,\neg$. In other words: is there a propositional logic formula $P$ such that $$ \forall x (\varphi(x) \lor \psi(x) ) \equiv P(\forall x \varphi(x), \exists x \varphi(x), \forall x \psi(x),\exists x \psi(x)) $$ ?

My Attempt: I thought about symmetrising the implied formula above as $$ [\forall x \varphi(x) \lor \exists x \psi(x)] \lor [\forall x \psi(x) \lor \exists x \varphi(x)] $$ since this may weaken the implication, lol.

2

There are 2 best solutions below

2
On

No, there's no such function $P$: If the language has one constant symbol $c$ and a model has at least two elements, let $\varphi$ and $\psi$ be defined as follows:

If $Q=\forall$ and $P(F,F) = T$: $\varphi(x)= \psi(x)=\neg(x=x)$.

If $Q=\forall$ and $P(F,F) = F$: $\varphi(x)= (x=c)$ and $\psi(x)=\neg(x=c)$.

If $Q=\exists$ and $P(T,T) = T$: $\varphi(x)= \psi(x)=(x=c)$.

If $Q=\exists$ and $P(T,T) = F$: $\varphi(x)= \psi(x)=(x=x)$.

In each of the cases above the truth value of $\forall x (\varphi(x) \lor \psi(x))$ is different from the truth value of $P(Q x \varphi(x), Q x \psi(x))$, so they can't be equivalent.

0
On

Ok, second try, similar idea, same conclusion (there's no such function $P$):

Suppose the language has two constant symbols $c_1$ and $c_2$. Let $$\varphi(x)=(x=c_1),$$ $$\psi(x)=(x=c_2),$$ $$A = \forall x (\varphi(x) \lor \psi(x)),$$ $$B = P(\forall x \varphi(x), \exists x \varphi(x), \forall x \psi(x),\exists x \psi(x))$$

If $P(F,T,F,T)=F$ then, in a model with exactly two elements, $A$ is true and $B$ is false.

If $P(F,T,F,T)=T$ then, in a model with more than two elements, $A$ is false and $B$ is true.