Distribution of Quantifiers
over Conjunction and Disjunction

Note: In what follows,

"LHS" refers to the left-hand side of an equivalence;
"RHS" refers to the right-hand side.

Theorem:

1. ∀x[P(x) ∧ Q(x)] ≡ (∀xP(x) ∧ ∀xQ(x))

2. ∀x[P(x) ∨ Q(x)] is not ≡ (∀xP(x) ∨ ∀xQ(x))

3. ∃x[P(x) ∧ Q(x)] is not ≡ (∃xP(x) ∧ ∃xQ(x))

4. ∃x[P(x) ∨ Q(x)] ≡ (∃xP(x) ∨ ∃xQ(x))

I.e., the universal quantifier distributes over conjunction, but not disjunction, and the existential quantifier distributes over disjunction, but not conjunction.

proof:

1. See Rosen, p. 39

2. Counterexample:
   Let domain = Z
   Let P(x) = x is even
   Let Q(x) = x is odd

   Then: tval(LHS) = T, but tval(RHS) = F

3. Counterexample:
   Let domain = Z
   Let P(x) = x is even
   Let Q(x) = x is odd

   Then: tval(LHS) = F, but tval(RHS) = T

4. To prove this, we need a rule of inference that, from p, we can infer (p ∨ q)
   (i.e., (p → (p ∨ q)) is a tautology)
   (this is the rule that we will soon be calling "addition" or "∨-introduction").

   Show: LHS & RHS always have same tval:

   Case 1: Suppose tval(LHS) = T, & show tval(RHS) = T:

   Since tval(LHS) = T, there is some x in the domain that satisfies (P(x) ∨ Q(x)). Call it "a".

   That is, tval(P(a) ∨ Q(a)) = T.

   Case 1a: Suppose tval(P(a)) = T

   Then tval(∃xP(x)) = T
   So, by the rule of inference above,
   tval(∃xP(x) ∨ ∃xQ(x)) = T

   Case 1b: Suppose tval(Q(a)) = T

   Then tval(∃xQ(x)) = T
   So, by the rule of inference above,
   tval(∃xP(x) ∨ ∃xQ(x)) = T

   So, in either case, the tval(RHS) of the original equivalence = T

   Case 2: Suppose tval(RHS) = T & show tval(LHS) = T:

   Since tval(RHS) = T, and it is a disjunction, then at least one of its disjuncts must have tval = T:

   So, either tval(∃xP(x)) = T or tval(∃xQ(x)) = T.

   If tval(∃xP(x)) = T, there's something in the domain that is P; call it "a". So: tval(P(a)) = T

   If tval(∃xQ(x)) = T, there's something in the domain that is Q; call it "b". So: tval(Q(b)) = T

   Case 2a: Suppose tval(P(a)) = T

   Then by the rule of inference, tval(P(a) ∨ Q(a)) = T
   So, tval(∃x(P(x) ∨ Q(x)) = T.

   Case 2b: Suppose tval(Q(b)) = T

   Then by the rule of inference, tval(P(b) ∨ Q(b)) = T
   So, tval(∃x(P(x) ∨ Q(x)) = T

   So, in either case, the tval(LHS) of the original equivalence = T

QED.