First order logic - position of quantifier

150 Views Asked by At

When you have a statement with →, does it matter if you use a quantifier before or after the implication?

ex. the statement "Every man loves a king" (2 different semantic interpretations)

  1. Every man loves a king and these kings may all differ from each other. ∀x IsMan(x) → ∃y (IsKing(y) ∧ Loves(x,y))
  2. There is a single king that every man loves. ∃y, ∀x (IsKing(y) ∧ IsMan(x)) → Loves(x,y)

For #1, would it be equally correct to write it as ∀x, ∃y, (IsMan(x) ∧ IsKing(y)) → Loves(x,y)?

And for #2, what about ∃y IsKing(y) → ∀x (IsMan(x) ∧ Loves(x,y))?

1

There are 1 best solutions below

0
On

Yes, the order of quantifier matters to decide the satisfiability/validity of a formula.

One way to be sure of it is to know that (A → B) is the same as (not A or B) and that (not (∀x x))is the same as (∃x (not x)).

Thus, when you have (∃x, ∀y x → y) it is the same as (∀x ∃y ((not x) or y)).

Which is different from (∃x, x → ∀y y) which can then be ((∀x (not x) or (∀y y)).