4.2: Traducir a la lógica de primer orden

Ahora tenemos todas las piezas de. Traducir aserciones (no importa lo complicado que sea) del inglés a la notación matemática solo será cuestión de conocer la forma correcta de combinar predicados, constantes, cuantificadores, conectivos y conjuntos. Considera estas aseveraciones:

5. Cada moneda en mi bolsillo es una moneda de diez centavos.
6. Alguna moneda sobre la mesa es una moneda de diez centavos.
7. No todas las monedas de mi bolsillo son monedas de diez centavos.
8. Ninguna de las monedas sobre la mesa son monedas de diez centavos.

Al proporcionar una clave de simbolización, necesitamos especificar\(\mathcal{U}\). Ya que no estamos hablando de nada además de monedas, podemos dejar\(\mathcal{U}\) ser el conjunto de todas las monedas. (No es necesario incluir todas las monedas en\(\mathcal{U}\), pero, como estamos hablando de las monedas en mi bolsillo y las monedas en la mesa,\(\mathcal{U}\) deben al menos contener todas esas monedas). Como no estamos hablando de ninguna moneda específica, no necesitamos definir ninguna constante. Ya que estaremos hablando explícitamente de las monedas en mi bolsillo y las monedas en la mesa, será útil tener estas definidas como conjuntos. La clave de simbolización también necesita decir algo sobre las monedas de diez centavos; hagámoslo con un predicado. Entonces definimos esta clave:

\(\mathcal{U}\): El conjunto de todas las monedas.

\(P\): El conjunto de todas las monedas en mi bolsillo.

\(T\): El conjunto de todas las monedas sobre la mesa.

\(D(x)\)es una moneda de diez centavos.

La aserción 5. se traduce de manera más natural con un cuantificador universal. Habla de todas las monedas que tengo en el bolsillo (es decir, los elementos del conjunto\(P\)). Significa que, para cualquier moneda en mi bolsillo, esa moneda es una moneda de diez centavos. Entonces podemos traducirlo como\(\forall p\in P, D(p)\).

Aserción 6. dice que hay alguna moneda sobre la mesa, tal que la moneda es una moneda de diez centavos. Entonces lo traducimos como\(\exists t \in T, D(t)\).

La aserción 7. se puede parafrasear como, “No es el caso que cada moneda de mi bolsillo sea una moneda de diez centavos”. Entonces podemos traducirlo como\(\neg(\forall p \in P, D(p))\). Esto es simplemente la negación de.

La aserción 8. se puede parafrasear como, “No es el caso que alguna moneda sobre la mesa sea una moneda de diez centavos”. Esto se puede traducir como\(\neg\bigl(\exists t\in T, D(t) \bigr)\). Es la negación de la Aserción 6.

OBSERVACIÓN\(4.2.1\).

Alternativamente, podríamos haber definido un conjunto\(D\), el conjunto de todas las monedas de diez centavos, en lugar del predicado\(D(x)\). En este caso:

• Aserción 5. se traduciría como\(\forall p \in P, \ p \in D\).
• Aserción 6. se traduciría como\(\exists t \in T, \ t \in D\).
• Aserción 7. se traduciría como\(\neg (\forall p \in P, \ p \in D)\).
• Aserción 8. se traduciría como\(\neg (\exists t \in T, \ t \in D)\).

Cualquiera de los dos enfoques es perfectamente legítimo.

Sin embargo, si necesitamos cuantificar más de diez centavos, entonces es mucho mejor usar un conjunto que un predicado. Por ejemplo, simbolizemos la afirmación “Cada centavo está en mi bolsillo”.

• Si\(D\) es el conjunto de todas las monedas de diez centavos, podemos escribir:\(\forall d \in D, \ d \in P\).
• Es menos sencillo si usamos el predicado\(D(x)\), porque no podemos decir directamente “para todas las monedas de diez centavos” (ya que el conjunto de todas las monedas de diez centavos no está disponible). La traducción debe considerar todas las monedas, y luego decir que las que son monedas de diez centavos están en mi bolsillo:\(\forall x, \bigl( D(x) \Rightarrow d \in P \bigr)\).

Por esta razón (y otras), los matemáticos tienden a usar conjuntos, en lugar de predicados, y nosotros haremos lo mismo.

OBSERVACIÓN\(4.2.2\).

Si hubiéramos definido el predicado\(P(x)\) (para “\(x\)está en mi bolsillo”) en lugar del conjunto correspondiente\(P\), habríamos necesitado traducir como\(\forall x, \bigl( P(x) \implies D(x) \bigr)\): es decir, “para cualquier moneda, si está en mi bolsillo, entonces es una moneda de diez centavos”. Ya que la aseveración se trata de monedas que están a la vez en mi bolsillo y que son monedas de diez centavos, podría ser tentador traducirlas usando\(\eand\). No obstante, la aseveración\(\forall x, \bigl(P(x) \eand D(x) \bigr)\) significaría que todo en está tanto en mi bolsillo como en una moneda de diez centavos: Todas las monedas que existen son monedas de diez centavos en mi bolsillo. Esto sería una locura decirlo, y significa algo muy diferente a. Sin embargo, este problema se evita por completo cuando usamos sets. Así,\(P\) definir como un conjunto, más que un predicado, es el mejor enfoque en este problema (y de manera similar para\(T\)).

Ejemplo\(4.2.3\).

Ahora podemos traducir la deducción de página, la que motivó la necesidad de cuantificadores:

Merlín es un mago. Todos los asistentes llevan sombreros graciosos.
\(\therefore\)Merlín lleva un divertido sombrero.

\(\mathcal{U}\): El conjunto de todas las personas.
\(W\): El conjunto de todos los magos.
\(H\): El conjunto de todas las personas que llevan un sombrero divertido.
\(m\): Merlín

Traduciendo, obtenemos:

Hipótesis:\ [\ comenzar {alineado}
&m\ en W\\
&\ para todo w\ en W, (w\ en H)
\ final {alineado}\]

Conclusión:\(m \in H\)

Esto captura la estructura que quedó fuera cuando traducimos la deducción en, y esta es una deducción válida en. Podremos demostrarlo rigurosamente después de haber discutido las reglas de introducción y eliminación para\(\forall\) (y\(\exists\)) en Sección\(4.4\).

Ejercicio\(4.2.4\).

Usando la clave de simbolización dada, traduzca cada afirmación en inglés a la lógica de primer orden.

\(\mathcal{U}\): El conjunto de todos los animales.
\(A\): El conjunto de todos los caimanes.
\(R\): El conjunto de todos los reptiles.
\(Z\): El conjunto de todos los animales que viven en el zoológico.
\(M\): El conjunto de todos los monos.
\(x\)♥\(y\): \(x\) loves \(y\).
\(a\): Amos
\(b\): Gorila
\(c\): Cleo

1. Amos, Bouncer y Cleo viven en el zoológico.
2. Bouncer es un reptil, pero no un cocodrilo.
3. Si a Cleo le encanta Bouncer, entonces Bouncer es un mono.
4. Si tanto Bouncer como Cleo son caimanes, entonces Amos los ama a ambos.
5. Algún reptil vive en el zoológico.
6. Todo caimán es un reptil.
7. Cada animal que vive en el zoológico es un mono o un cocodrilo.
8. Hay reptiles que no son caimanes.
9. A Cleo le encanta un reptil.
10. Bouncer ama a todos los monos que viven en el zoológico.
11. Todos los monos que ama Amos lo aman de nuevo.
12. Si algún animal es un cocodrilo, entonces es un reptil.
13. Cada mono que ama a Cleo también es amado por Amos.
14. Hay un mono que ama a Bouncer, pero Bouncer no corresponde a este amor.

Ejercicio\(4.2.5\).

Usando la clave de simbolización dada, traduzca cada afirmación en inglés a la lógica de primer orden.

\(\mathcal{U}\): El conjunto de todos los animales.
\(D\): El conjunto de todos los perros.
\(S\): El conjunto de todos los reptiles.
\(Z\): El conjunto de todos los animales a los que les gusta nadar.
\(x\)\(L\)\(y\): \(x\) is larger than \(y\).
\(b\): Bertie
\(e\): Emerson
\(f\): Fergis

1. Bertie es un perro al que le gusta nadar.
2. Bertie, Emerson y Fergis son todos perros.
3. Emerson es más grande que Bertie, y Fergis es más grande que Emerson.
4. A todos los perros les gusta nadar.
5. Cada animal al que le gusta nadar es un perro.
6. Hay un perro que es más grande que Emerson.
7. Ningún animal al que le guste nadar es más grande que Emerson.
8. Cualquier animal al que no le guste nadar es más grande que Bertie.
9. No hay ningún animal que sea más grande que Bertie, sino más pequeño que Emerson.
10. No hay ningún perro que sea más grande que Bertie, sino más pequeño que Emerson.
11. Ningún perro es más grande que él mismo.

Ejercicio\(4.2.6\).

Para cada deducción, escriba una clave de simbolización y traduzca la deducción a Lógica de Primera Oder.

1. Nada en mi escritorio escapa a mi atención. Hay una computadora en mi escritorio. Por lo tanto, hay una computadora que no se me escapa a mi atención.
2. Todos mis sueños son en blanco y negro. Los viejos programas de televisión son en blanco y negro. Por lo tanto, algunos de mis sueños son viejos programas de televisión.
3. Ni Holmes ni Watson han estado en Australia. Una persona podía ver a un canguro sólo si había estado en Australia o en un zoológico. A pesar de que Watson no ha visto un canguro, Holmes sí. Por lo tanto, Holmes ha estado en un zoológico.
4. Nadie espera la Inquisición española. Nadie conoce los problemas que he visto. Por lo tanto, cualquiera que espere la Inquisición española conoce los problemas que he visto.
5. Cada antílope es más grande que una caja de pan. Lo que estoy pensando no es más grande que una caja de pan, y es o bien un antílope o un melón. Por lo tanto, estoy pensando en un melón.

4.2A. Cuantificadores múltiples

Ejemplo\(4.2.7\).

Considera la siguiente clave de simbolización y las aseveraciones que la siguen:

\(\mathcal{U}\): El conjunto de todas las personas.
\(D\): El conjunto de todos los amigos de Karl.
\(S\): El conjunto de todos los vecinos de Imre.
\(x\)\(L\)\(y\): \(x\) likes \(y\).
\(i\): Imre.
\(k\): Karl.

9. Todos los vecinos de Imre como todos los amigos de Karl.
10. Al menos a uno de los amigos de Karl le gusta al menos uno de los vecinos de Imre.
11. A todos los amigos de Karl les gusta al menos uno de los vecinos de Imre.
12. Está uno de los vecinos de Imre, que es amigo de Karl y al que le gustan todos los vecinos de Imre.

Solución

Empezando a traducir Aserción 9., comenzamos con todos los vecinos de Imre:\(\forall n \in N.\) Ahora nos gustaría decir\(n \mathrel{L}f\), donde\(f\) representa a cada uno de los amigos de Karl. Antes de que podamos hacer esto, necesitamos introducir la variable\(f\), y darle el significado deseado y el cuantificador apropiado:\(\forall f \in F\). Así, Aserción 9. puede traducirse como\(\forall n \in N, \bigl(\forall f \in F, (n \mathrel{L}f)\bigr)\).

Para Asertion 10., comenzamos con al menos uno de los amigos de Karl. Otra forma de decir esto es que hay algún amigo de Karl:\(\exists f \in F\). De igual manera, ahora necesitamos introducir al menos a uno de los vecinos de Imre:\(\exists n \in N\). La traducción concluida es\(\exists f \in F, \bigl(\exists n \in N, (f \mathrel{L}n)\bigr)\bigr)\).

Para Aserción 11., comenzamos con todos los amigos de Karl:\(\forall f \in F\). Ahora necesitamos al menos uno de los vecinos de Imre:\(\exists n \in N\). La traducción concluida es\(\forall f\in F, \bigl(\exists n\in N, (f \mathrel{L} n)\bigr)\).

Por último, para Aserción 12., comenzamos con uno de los vecinos de Imre:\(\exists n \in N\). Ahora necesitamos que esta persona sea amiga de Karl:\(n \in F\). Para la siguiente parte de la oración, necesitamos a todos los vecinos de Imre. Es tentador escribir\(\forall n \in N\), pero ya hemos usado la variable\(n\) para uno en particular de los vecinos de Imre, así que no podemos volver a usarla aquí para significar otra cosa. Usemos\(n'\) en su lugar:\(\forall n' \in N\). Ahora estamos listos para traducir Aserción 12:\[\exists n \in N,\left(n \in F \&\left[\forall n^{\prime} \in N,\left(n L n^{\prime}\right)\right]\right) .\]
(Alternativamente, podríamos haber usado\(n_{1}\) y\(n_{2}\) en lugar de\(n\) y\(n^{\prime}\).)

Al simbolizar aserciones con múltiples cuantificadores, lo mejor es proceder por pequeños pasos. Determinar quién se está discutiendo en la oración, y qué cuantificadores se requieren para introducir estas variables. Parafraseando la afirmación inglesa para que la estructura lógica se simbolice fácilmente en. Después traducir poco a poco, reemplazando la desalentadora tarea de traducir una aserción larga por la tarea más simple de traducir fórmulas más cortas.

OBSERVACIÓN\(4.2.8\).

El signo igual “\(=\)” es parte de toda clave de simbolización (aunque no nos molestemos en incluirla explícitamente). Es un predicado binario y, como cabría esperar, “\(x = y\)” significa “\(x\)es igual a”\(y\). Esto no significa simplemente eso\(x\) y\(y\) se parecen mucho, o que sean indistinguibles, o que tengan todas las mismas propiedades. Más bien, significa que\(x\) y\(y\) son nombres (diferentes) para el mismo objeto.

Advertencia.

Es importante poner los cuantificadores en el orden correcto. Por ejemplo, considere las siguientes aserciones (\(\mathcal{U}\))siendo el conjunto de todos los objetos):

13. \(\forall x,\bigl( \exists y, (x=y)\bigr)\)
14. \(\exists y, \bigl(\forall x, (x=y)\bigr)\)

Son exactamente lo mismo, excepto para cuál de\(\forall x\) y\(\exists y\) es primero, y cuál es el segundo. Obviamente es cierto: “Por cada cosa, hay algo a lo que es igual”. (Es decir, cada cosa es igual a sí misma.) Pero dice: “Hay algo (llamémoslo\(y\)), tal que todo sea igual a”\(y\). No existe tal\(y\), así que esto es obviamente falso.

Ejercicio\(4.2.9\).

Usando la clave de simbolización del ejercicio\(4.2.5\), traduzca cada afirmación en inglés a la lógica de primer orden.

1. Si hay un perro más grande que Fergis, entonces hay un perro más grande que Emerson.
2. Cada perro es más grande que algún perro.
3. Hay un animal que es más pequeño que cada perro.
4. Si hay un animal que es más grande que todos los perros, entonces a Emerson no le gusta nadar.
5. Por cada perro al que le gusta nadar, hay un perro más pequeño al que no le gustan.
6. Cada perro al que le gusta nadar es más grande que todos los perros que no les gustan.
7. Algún animal es más grande que todos los perros a los que les gusta nadar.
8. Si hay un perro al que no le gusta nadar, que hay un perro que es más grande que cada animal al que le gusta nadar.

Ejercicio\(4.2.10\) (harder).

Usando la clave de simbolización dada, traduzca cada afirmación en inglés a la lógica de primer orden.

\(\mathcal{U}\): El conjunto de todas las personas.
\(D\): El conjunto de todos los bailarines de ballet.
\(F\): El conjunto de todas las hembras.
\(M\): El conjunto de todos los machos.
\(x\)\(C\)\(y\): \(x\) is a child of \(y\).
\(x\)\(S\)\(y\): \(x\) is a sibling of \(y\).
\(e\): Elmer
\(j\): Jane
\(p\): Patrick

1. Todo el que baila ballet es hijo de alguien que baila ballet.
2. Todo hombre que baila ballet es hijo de alguien que baila ballet.
3. Todo el que baila ballet tiene una hermana que también baila ballet.
4. Jane es tía.
5. Los hermanos de Patrick no tienen hijos.

4.2B. Singularidad

Decir “hay un fulano único” significa no solo que hay un tal y tal, sino también que solo hay uno de ellos, no hay dos fulanos diferentes. Por ejemplo, decir que “hay una persona única que le debe dinero a Hikaru” significa

alguna persona le debe a Hikaru y ninguna otra persona le debe a Hikaru.

Esto se traduce a\[\exists h\in H, \bigl( \forall y, (y \neq h \Rightarrow y \notin H) \bigr);\]
o, equivalentemente,\[\exists h\in H, \bigl( \forall y, ( y \in H \Rightarrow y =h ) \bigr).\]
Desafortunadamente, ambas son expresiones bastante complicadas (y son ejemplos de “cuantificadores múltiples”, porque utilizan ambos\(\exists\) y\(\forall\)). Para simplificar la situación, los matemáticos introducen una notación especial:\[\text { " } \exists ! x \text { " means "there is a unique } x \text {, such that..." }\]

Si\(X\) hay algún conjunto, entonces\(\exists ! x \in X\) "" significa
“hay un único\(x\) en\(X\), tal que.”

Por ejemplo,\(\exists!\, h, h \in H\) significa exactamente lo mismo que la complicada expresión anterior.

Si añadimos

\(R\): El conjunto de personas ricas.

a nuestra clave de simbolización, podemos traducir “Hay una persona rica única que le debe dinero a Hikaru”. A saber, se traduce como:\[\exists!\, r \in R, (r \in H).\]

Ejercicio\(4.2.11\).

Usando la clave de simbolización dada, traduzca cada afirmación en inglés a la lógica de primer orden.

\(\mathcal{U}\): El conjunto de todas las criaturas.
\(H\): El conjunto de todos los caballos.
\(W\): El conjunto de todas las criaturas con alas.
\(B\): El conjunto de todas las criaturas en el campo de Farmer Brown.

1. Hay una criatura alada única que está en el campo de Farmer Brown.
2. Si algún caballo tiene alas, entonces hay un caballo único que está en el campo de Farmer Brown.
3. Si hay un caballo que está en el campo de Farmer Brown, entonces hay un caballo único que está en Farmer Brown's y tiene alas.

Contestar

Agrega textos aquí. No borre primero este texto.

4.2C. Variables enlazadas

Recordemos que una aseveración es una afirmación que es verdadera o falsa. Por ejemplo, considere la siguiente clave de simbolización:

\(\mathcal{U}\): El conjunto de todos los alumnos.
\(M(x)\):\(x\) está tomando una clase de matemáticas.
\(a\): Anna

Entonces:

• \(M(a)\)es una aseveración. O Anna está tomando una clase de matemáticas, o no lo está.
• \(M(x)\)no es una aseveración. La letra\(x\) es una variable, no un objeto en particular. (Llamamos a\(x\) una variable libre.) Si enchufamos un valor particular para\(x\) (como\(a\)), entonces tendremos una aserción. Sin embargo, hasta que se conecte algún valor\(x\), no podemos decir si la expresión es verdadera o falsa. Entonces la expresión no es una aserción si la variable permanece libre.
• \(\exists x, M(x)\)y\(\forall x, M(x)\) son aseveraciones. La letra\(x\) es una variable en ambas expresiones, pero ya no es libre, porque es actuada por el cuantificador. (Llamamos a\(x\) una variable enlazada.)

Un principio importante de es que, en una aserción, cada variable debe estar ligada por algún cuantificador:\[\text { Assertions cannot have free variables. }\]

Ejercicio\(4.2.12\).

Supongamos que\(p\) es una constante, pero todas las demás letras minúsculas representan variables. Para cada una de las siguientes, a. ¿tiene una variable libre? b. ¿Es una afirmación?

1. \(\forall x\in X, (x \mathrel{L} y)\)
2. \((p \in S) \eand \exists y \in Y, (y \mathrel{T} p)\)
3. \(\forall v \in V, \bigl( (\exists!\, y \in Y, v \mathrel{R} y) \Rightarrow (v=z) \bigr)\)
4. \(y \in Y \eand \bigl(\forall x \in X, (x \in T) \bigr)\)
5. \((p \mathrel{L} p) \Rightarrow \exists x, (x \mathrel{L} p)\)
6. \(\forall x \in X, (x \mathrel{L} x)\)

Contestar

Agrega textos aquí. No borre primero este texto.