Skip to main content
added 239 characters in body
Source Link
rus9384
  • 2.8k
  • 3
  • 17
  • 30

At first let's look at what cases first formula is true. Since conjunction requires both operands to be true, we know (through simplification):

(∀x)(Fx)

This means

Fx ⇔ 1

Now, since Fx is tautologyalways true, we get

(Fx & Gy) ⇔ (1 & Gy) ⇔ (Gy)

and

(∀x)(∃y)(Fx & Gy) ⇔ (∃y)(Gy)

as well as

(∃y)(∀x)(Fx & Gy) ⇔ (∃y)(Gy)

Therefore

(∀x)(∃y)(Fx & Gy) ⇔ (∃y)(∀x)(Fx & Gy)

Deducibility follows from equivalence (but not necessarily the opposite):

(∀x)(∃y)(Fx & Gy) ⊢ (∃y)(∀x)(Fx & Gy)

At first let's look at what cases first formula is true. Since conjunction requires both operands to be true, we know:

(∀x)(Fx)

Now, since Fx is tautology, we get

(Fx & Gy) ⇔ (Gy)

and

(∀x)(∃y)(Fx & Gy) ⇔ (∃y)(Gy)

as well as

(∃y)(∀x)(Fx & Gy) ⇔ (∃y)(Gy)

At first let's look at what cases first formula is true. Since conjunction requires both operands to be true, we know (through simplification):

(∀x)(Fx)

This means

Fx ⇔ 1

Now, since Fx is always true, we get

(Fx & Gy) ⇔ (1 & Gy) ⇔ (Gy)

and

(∀x)(∃y)(Fx & Gy) ⇔ (∃y)(Gy)

as well as

(∃y)(∀x)(Fx & Gy) ⇔ (∃y)(Gy)

Therefore

(∀x)(∃y)(Fx & Gy) ⇔ (∃y)(∀x)(Fx & Gy)

Deducibility follows from equivalence (but not necessarily the opposite):

(∀x)(∃y)(Fx & Gy) ⊢ (∃y)(∀x)(Fx & Gy)

Source Link
rus9384
  • 2.8k
  • 3
  • 17
  • 30

At first let's look at what cases first formula is true. Since conjunction requires both operands to be true, we know:

(∀x)(Fx)

Now, since Fx is tautology, we get

(Fx & Gy) ⇔ (Gy)

and

(∀x)(∃y)(Fx & Gy) ⇔ (∃y)(Gy)

as well as

(∃y)(∀x)(Fx & Gy) ⇔ (∃y)(Gy)