More Examples

• Sample problems:
  1. $\forall x P(x)$ ____________________
  2. $\exists x P(x)$ ____________________
  3. $\forall x \neg P(x)$ ____________________
  4. $\exists x \neg P(x)$ ____________________
  5. $\neg \forall x P(x)$ ____________________
  6. $\neg \exists x P(x)$ ____________________
  7. $\neg \forall x \neg P(x)$ ____________________
  8. $\neg \exists x \neg P(x)$ ____________________

• $\exists x \forall y P(x) \not= \forall y \exists x P(x)$
  • $\forall x \exists y Loves(x,y)$ Everyone Loves Someone
  • $\exists y \forall x Loves(x,y)$ There is one person everyone loves

• $\forall x [P(x) \wedge Q(x)] = \forall x P(x) \wedge \forall x Q(x)$
  ($\forall$ Distributes over AND only)
• $\exists x [P(x) \vee Q(x)] = \exists x P(x) \vee \exists x Q(x)$
  ($\exists$ Distributes over OR only)

• UNIVERSAL INSTANTIATION
  • $\mbox{if } \forall x P(x) \mbox{ then } P(t)$ where t is a term
  • If something is true of everything, then it is true for any particular thing.
  • Example:
    • $\forall y Hates(Jane,y) \rightarrow Hates(Jane,Jill)$
    • $\forall y Hates(Jane,y) \rightarrow Hates(Jane,y)$

• EXISTENTIAL INSTANTIATION
  • $if P(A) THEN \exists x P(x)$
  • If something is true of one specific thing, then it can be
    generalized to state that one thing exists.

Sample Proof (using Universal Instantiation)

$Canary(Tweety)$	$\nabla$
$\forall x Canary(x) \rightarrow Color(x, Yellow)$	$\nabla$
$Canary(Tweety) \rightarrow Color(Tweety, Yellow)$	UI
$Color(Tweety,Yellow)$	Modus Ponens