Discrete Structures

Distribution of Quantifiersover Conjunction and Disjunction

 Last Update: 3 February 2009 Note: or material is highlighted

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.