I've been given a series of questions about the distribution of quantification across logical operators. For example:
Is $\;\forall x \in S \;(p(x) \; or \; q(x))\;$ the same as $\;(\forall x \in S \; p(x)) \; or \; (\forall x \in S \; q(x))$?
Most of these make pretty good intuitive sense to me (in the above, for example, obviously these are not "the same" as for the first it is sufficient for a member have either $p$ or $q$, but for the latter it is necessary that all members have either $p$ or all members have $q$). I'm stuck, however, on "distribution" across implication:
Is $\;\forall x \in S \;(p(x) \; \implies \; q(x))\;$ the same as $\;(\forall x \in S \; p(x)) \; \implies \; (\forall x \in S \; q(x))$?
I ask that you not provide the answer, but a method for dissecting this. It seems like they should be the same, however this is just a "gut feeling" that I've failed to quantify. I've been given the following example situation to use:
Let $S$ be a collection of two coins, one with an $H$ on top and a $T$ on bottom, and one with an $H$ on top and a $Q$ on bottom. Let $p(x)$ denote "$x$ has an $H$ on top" and $q(x)$ denote "$x$ has a $Z$ on bottom".
This hasn't helped much, though.
So, to get an intuition for logical formulae I can't quite get my head around, I usually try to rewrite them into something that's easier for me to reason about.
If you're using classical FOL, then you could apply $(\varphi \Rightarrow \psi) \Leftrightarrow (\neg \varphi \vee \psi)$ and $\neg (\forall x \in A. \phi) \Leftrightarrow (\exists x \in A. \neg\phi)$ to obtain
"Is $\forall x \in A. \neg P(x) \vee Q(x)$ the same as $(\exists x \in A. \neg P(x)) \vee (\forall x \in A. Q(x))$?"
and see if that is more intuitive.
Also, if you know a method of proving formulae, you could also just try to directly show $$\big(\forall x \in A. \neg P(x) \Rightarrow Q(x)\big) \Leftrightarrow \big((\forall x \in A. \neg P(x)) \Rightarrow (\forall x \in A. Q(x))\big)$$ and $$\big(\forall x \in A. \neg P(x) \Rightarrow Q(x)\big) \not\Leftrightarrow \big((\forall x \in A. \neg P(x)) \Rightarrow (\forall x \in A. Q(x))\big)$$ and see if one works. If a proof fails, that can help you come up with a counterexample model.