Section Progress:

24.4 Quantifier Distribution (Dist)

When distributing quantifiers over connectives, like & or v, we have to be careful. Sometimes the quantifiers distribute and sometimes they don’t.

To figure it out, we need to evaluate each possible entailment. For example, let’s start with the quantifiers and conjunction.

See if you can answer these questions.

What we can see from this is that the Universal quantifier distributes over &, but the Existential does not.

Ax(P(x)&Q(x)) ⇔ AxP(x)&AxQ(x)

Now let’s consider the quantifiers and disjunction.

What we can see from this is that the Existential quantifier distributes over v, but the Universal does not.

Ex(P(x)vQ(x)) ⇔ ExP(x)vExQ(x)

Distribution (Dist)
Ax(P(x)&Q(x)) ⇔ AxP(x)&AxQ(x)
Ex(P(x)vQ(x)) ⇔ ExP(x)vExQ(x)

We cannot do distribution over the conditionals directly, because there is a complication.

P→Q is equivalent to ~PvQ, so in a sense there is a “hidden” negation sign in front of the antecedent. So if we try to distribute over arrow, we also have to deal with DeMorgan’s for Quantifiers.

So when dealing with quantifiers and conditionals in equivalences, it is often safest to first transform the conditionals into their Boolean form, and proceed from there.


25.4 Distribution for Quantifiers (Dist)