Intersección de ámbitos: Cuantificador y predicado

Question

Me encontré con una expresión en lógica de predicados que me hizo preguntarme si era realmente válida desde el punto de vista sintáctico y, en ese caso, semánticamente correcta.

Para una frase como "Todo perro persigue a un gato", hay dos lecturas. (a) Una en la que todos los perros persiguen al menos a un gato y (b) otra en la que al menos un gato es perseguido por todos los perros.

(a) $\forall x\in \{x : dog(x)\}:\ \exists y\in \{x : cat(x)\}:\ chase(x, y)$

(b) $\exists y\ \in\ \{x : cat(x)\}:\ \forall x\ \in\ \{x : dog(x)\} :\ chase(x,y)$

Estas dos representaciones significan lo mismo:

(a) $\forall x.[ dog(x) \rightarrow \exists y.[ cat(y) \land chases(x, y) ] ]$

(b) $\exists y.[ cat(y) \rightarrow \forall x.[ dog(x) \land chases(x, y) ] ]$

La expresión con la que me encontré es la siguiente:

$$\forall x.(dog(x) \rightarrow \exists y.(cat(y) \land chase(x))(y))$$

Esto me parece raro. Para hacerlo más aparente dejemos que se transforme más:

Es lo mismo que:

$$\forall x.[ dog(x) \rightarrow \exists y.[ cat(y) \land chase(x) ] (y) ]$$

que es lo mismo que:

$$\forall x.[ dog(x) \rightarrow \exists y.[ cat(y) \land chase(x, ] y) ]$$

En primer lugar, ¿es sintácticamente válido tener "cuantificador[ functor( ] )"? Entonces, ¿tener proyecciones superpuestas de nodos sintácticos en el árbol sintáctico de la expresión?

Y si la expresión es sintácticamente válida... ¿qué significa? No tiene ningún sentido para mí.

Answer 1

Antes de responder a su pregunta, debo cubrir algunos aspectos de un lenguaje formal de primer orden.

En particular, la definición de su sintaxis. Por lo que dije anteriormente aquí y aquí :

Supongo que se refiere a un lenguaje de primer orden $L_\Sigma=<\Sigma,V,\neg,\rightarrow,\forall>$ , donde

• $\Sigma$ es un triple $<R,F,C>$ la firma de $L$ , donde $R=\{R_n\}_{n \in \mathbb{N}}$ y $F=\{F_n\}_{n \in \mathbb{N}}$ son familias de conjuntos y $C$ es un conjunto. Los elementos de $R$ se llaman $n$ -símbolos de relación primaria, los elementos de $F$ se llaman $n$ -símbolos de la función primaria, los elementos de $C$ se denominan símbolos constantes. Decimos que $\Sigma$ es la firma de $L$ .
• $V$ es un conjunto, llamado los símbolos variables de $L_\Sigma$ .

Ahora dejemos que $L_\Sigma^*$ denotan el conjunto de todas las cadenas de $L_\Sigma$ .

La definición habitual del conjunto de fórmulas bien formadas de $L_\Sigma$ Llámalo $FORM_{L_\Sigma}$ es entonces:

Definición ( FORMULARIO ) El conjunto FORMULARIO de fórmulas bien formadas de $L_\Sigma$ es el conjunto que satisface:

1. $R(a_1,...,a_n) \in FORM$ si $a_1,...,a_n \in TERM$
2. $(\neg\alpha) \in FORM$ si $\alpha$ es un wff
3. $(\alpha \rightarrow \beta) \in FORM$ si $\alpha$ y $\beta$ son wff
4. $(\forall v (\alpha)) \in FORM$ si $v \in V$ y $\alpha$ es un wff
5. Ninguna cadena que no se obtenga mediante (1),(2),(3) o (4) está en FORMULARIO .

Dos observaciones:

• Asumo la definición del conjunto de términos de $L_\Sigma$ , $TERM$ . Puedes probar como ejercicio.

• El cuantificador existencial se define como $$ \exists x \alpha \equiv \neg \forall x \neg \alpha$$

Ahora, mira (1), y (4). ¿Nos permite esta definición obtener las frases que has pedido?