Is it possible to simplify: $[\forall x (Px\to Qx)]\lor [\forall x(Px\to Rx)]$?

Question

Let $P, Q, R$ be propositions. Consider:

$\big[\forall x \big(P(x)\implies Q(x)\big)\big]\lor \big[\forall x\big(P(x)\implies R(x)\big)\big]$

Given the fact"$\forall x$" and "$ P(x)$" appear twice, what is the best way to simplify this logic statement?

For example, I guess there exists $S$ such that $\big[\forall x \big(P(x)\implies Q(x)\big)\big]\lor \big[\forall x\big(P(x)\implies R(x)\big)\big]$ = $\forall x(P(x)\implies S(x)).$ If $S$ does not exist, then I guess the concerned statement is not simplifiable.

Rigorous definition for "simplification": the simplified statement should reduce the total number of syntaxes or the total number of propositions. The original statement contains four propositions: $Q, R,$ and two $P$s. A new statement include three propositions is a "simplification". Any rules, including arbitrary order quantifiers, are allowed (though I don't think they are useful).

Answer 1

No, it is not possible.

I will rephrase the problem (and slightly generalise it). Is there some expression $S(x)$, which is built up from $P(x)$, $R(x)$, and $Q(x)$ using propositional operators (eg $\land, \lor, \neg$, etc.) but not using quantifiers, such that $\forall x (P(x) \to Q(x)) \lor \forall x (P(x) \to R(x))$ is logically equivalent to $\forall x (S(x))$?

The answer is no. For suppose this were possible.

Consider the two-point model $\{0, 1\}$. Let $P(x)$ always be true, let $R(x)$ be $x = 1$, and let $Q(x)$ be $x = 0$.

The trick is to consider the two sub-models $\{0\}$ and $\{1\}$. On both of these submodels, we see that $\forall x (P(x) \to Q(x)) \lor \forall x (P(x) \to R(x))$ holds. Therefore, on both of these submodels, we have $\forall x (S(x))$. That is, we have both $S(0)$ and $S(1)$.

Thus, in our original model $\{0, 1\}$, we have $\forall x (S(x))$. Therefore, we should have either $\forall x (P(x) \to Q(x))$ or $\forall x (P(x) \to R(x))$. But we clearly do not have either.

If we allow $S$ to contain quantifiers, we could define $S(x) = P(x) \to \forall x (P(x) \to R(x)) \lor \forall x (P(x) \to Q(x))$. Then $\forall x (P(x) \to R(x)) \lor \forall x (P(x) \to R(x))$ would be logically equivalent to $\forall x (S(x))$. I am extremely hard-pressed to call this a “simplification”. There may be other ways to rewrite the original expression, but they will inevitably require at least 2 quantifiers just as the original expression does.

Answer 2

The given formula $$∀x(Px→Qx)∨∀x(Px→Rx)\tag1$$ is logically equivalent to $$∀x∀y \Big(¬Px∨¬Py∨Qx∨Ry\Big)\tag2$$ and to $$∀x∀y \Big(¬(Px∧Py)∨Qx∨Ry\Big).\tag3$$

Between formulae 1 and 2 (which have the same string length), the latter seems more straightforward and is in Prenex form, while the former has fewer applications of connectives/quantifiers; which formula is more “simplified”?

---

In this previous example, the expanded form $$∀f{\in}A\;\Big(∃x\;f(x)=0\implies ∀y\;f(y)\ge0\;∨\;∀z\;f(z)\le0 \Big),\tag B$$ is human-friendlier (simpler to understand) than the shorter, Prenex form $$∀x\;∀y\;∀f{\in}A\;\Big(f(x)=0\implies f(y)\ge0\;∨\;f(y)\le0 \Big);\tag A$$ which formula is more “simplified”?

I think your Question becomes more interesting with the generalisation in Mark Saving's Answer.

Answer 3

If you allow the use of bounded quantifiers, then you can simplify this in a manner of speaking.

$$ (\forall x \mathop. P(x) \to Q(x)) \lor (\forall x \mathop. P(x) \to R(x)) $$

Is equivalent to

$$ (\forall x : P \mathop. Q(x)) \lor (\forall x : P \mathop. R(x)) $$

But that's as far as you can go.

The candidate below doesn't work because it includes the case where $P = \{q, r\}$ where $q$ is a $Q$ and $r$ is an $R$.

$$ (\forall x : P \mathop. Q(x) \lor R(x)) \;\; \text{loses information!}$$