1

Let P(x) and Q(x) be arbitrary predicates. Which of the following statements is always TRUE?

1.((∀x(P(x) ∨ Q(x)))) ⟹ ((∀xP(x)) ∨ (∀xQ(x)))

2.(∀x(P (x) ⟹ Q (x))) ⟹ ((∀xP(x)) ⟹ (∀xQ(x)))

3.(∀x(P(x)) ⟹ ∀x (Q(x))) ⟹ (∀x(P(x) ⟹ Q(x)))

4.(∀x(P(x)) ⇔ (∀x (Q(x)))) ⟹ (∀x(P(x) ⇔ Q(x)))

How to approach such questions ,I tried with the second option and I couldn't get that how is it valid since for all quantifier is not distributive over disjunction so how can we write ∀x(~P(x)∨Q(x)) as ∀x(~P(x))∨∀x(Q(x)) , so If I try converting from LHS to RHS then I will have to distribute for all quantifier over disjunction which I can't do so how is option 2 valid ?

radhika
  • 361
  • These would actually be much easier to read if you got rid of unnecessary parentheses. Keep the necessary ones! but you don't have to write $\forall x(P(x))$, for example, as $\forall x,P(x)$ will do; similarly, in $(\forall x(...))$ the outermost parens aren't needed. – BrianO Jan 26 '16 at 10:29
  • Only 2. is always true. You've converted it incorrectly. The consequent (conclusion) of 2. is equivalent to $\neg \forall x P(x) \lor \forall x Q(x) \equiv \exists x \neg P(x) \lor \forall x Q(x)$. – BrianO Jan 26 '16 at 10:31
  • I couldn't get the fact that in option 2, P(x)-->Q(x) is written as ~P(x)∨Q(x) , so now we have in LHS as ∀x(P (x) ⟹ Q (x)), so now how can I distribute for all quantifier over disjunction ? – radhika Jan 27 '16 at 17:11

1 Answers1

2

It's probably better to prove 2 using say, natural deduction, rather than to try to manipulate symbols.

Intuitively, this is just "All humans are mortals; therefore, if everything is a human, then everything is mortal." If you were to draw a Venn diagram, from $\forall x(P(x) \to Q(x))$, you'd have two circles, with the $P$ circle entirely contained within the $Q$ circle. If $\forall x P(x)$, then everything in the universe is a $P$: there's no gap between the $P$ an $Q$ circles, $P$ fills $Q$. So everything is a $Q$.

  1. $\forall x (P(x) \to Q(x)) \quad\text{assumption}$
  2. $\forall x P(x)\quad\quad\quad\quad\,\,\text{assumption}$
  3. $P(a) \quad\quad\quad\quad\quad\text{instantiate $\forall$ in 2}$
  4. $P(a)\to Q(a) \quad\quad\text{instantiate $\forall$ in 1}$
  5. $Q(a) \quad\quad\quad\quad\quad\text{from 3, 4 by modus ponens}$
  6. $\forall x Q(x) \quad\quad\quad\quad\text{eliminate arbitrary a}$
  7. $(\forall x P(x) \to \forall xQ(x)) \quad\quad\text{discharge assumption 2}$
  8. $\forall x (P(x) \to Q(x)) \to (\forall x P(x) \to \forall xQ(x)) \quad\text{discharge assumption 1}$
BrianO
  • 16,579