0

I'm practicing writing FOL sentences and I have the following sentences. The first sentence is the solution I provided and the second is the correct solution ( per the solutions manual).The difference is where I've placed ∃z. I understand there is a difference in scope but I don't understand how that difference is applied to the predicates.

  1. ∀x (Txi => ∃y∃z(Txy ∧ Tyz ∧ Vz))
  2. ∀x (Txi => ∃y(Txy ∧ ∃z(Tyz ∧ Vz))
1
1

Both solutions are correct: Since z does not occur free in Txy, the ∃z has no effect on it, and the two formalizations are logically equivalent.

In general, you can move existential and universal quantifiers between the right-hand side of a conjunction resp. implication and the front, provided that the left-hand side does not contain free occurrences of the binding variable:

A ∧ ∃xB ≡ ∃x(A ∧ B), if x not free in A
A → ∀xB ≡ ∀x(A → B), if x not free in A

You can find a more comprehensive list of when formulas with the quantifier outside vs. inside a subformula are logically equivalent e.g. on the Wikipedia article on prenex normal form.

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.