Question

Derive the following using all known inferences rules and equivalences
including QE.

Remember that equivalences afford you greater power than derivation rules, because
you are permtted to substitute equivalent sub formlas within a wff. For example, all the
moves on the left below are legitimate inferences even though the first conditional is the
main operator. However, it is important to remember that you must always be operating
on a true self-contained wff. The moves on the right are not legitimate because they are
being performed on ∃y(Gx → Fy) which is not a wff. (Note: step 4 on the left hand side
is using an inference rule incorrectly because the ∀ is not the main operator.)
1. ∀xFx → ∃y(Gy → Fy) A
2. ∀xFx → ∃y(~Fy → ~Gy) 1, Trans
3. ∀xFx → ∃y(~~Fy v ~Gy) 2, MI
4. ∀xFx → ∃y~(Fy & Gy) 3, DM
5. ∀xFx → ~∀y(Fy & Gy) 4, QE
6. ~∃x~Fx → ~∀y(Fy & Gy 5, QE

1. ∀xFx → ∃y(Gx → Fy) A
2. ∀xFx → ∃y(~Fy → ~Gx) 1, Trans
3. ∀xFx → ∃y(~~Fy v ~Gx) 2, MI
4. Fa → ∃y(~~Fy v ~Gx) 3, ∀E
etc.

Also: (1) be aware of the power of the equivalence rule Double Negation (DN). With this
rule you no longer require ~E; (2) Be aware of the power of the contradiction rule
(CON). There will be times when a ~I proof will involve an existential elimination, and
you may which to discharge the existential hypothesis with a contradiction such as (Fc
& ~Fc.) If c happens to violate the restrictions on ∃E, the CON rule will allow you to
simply substitute a different contradiction such as (P & ~P), since anything follows from
a contradiction, even another contradiction.

1. ∼∃xFx, ~Fc → ∀y~Gy ├ ∀y∀z~(Fy v Gz)

2. ~∃x∃yGxy ├ ∃xGxx → ~∀yFy

3. ├ ∃xFx v ∃x~Fx

Answer 1