2 of 2

25.4 Distribution for Quantifiers (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.

We say that a distribution equivalence holds for a quantifier and a connective if entailments like in the problem above hold in both directions.

What we can see from that problem 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.

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

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)