Autor Tema: Formalización de la lógica

0 Usuarios y 2 Visitantes están viendo este tema.

22 Octubre, 2020, 02:05 am
Respuesta #10

manooooh

  • $$\Large \color{#9c57a6}\pi\,\pi\,\pi\,\pi\,\pi\,\pi$$
  • Mensajes: 3,350
  • País: ar
  • Karma: +1/-0
  • Sexo: Masculino
Hola

Bien, te han puesto un ejemplo de fórmula con una variable libre y otra ligada, sin que importe nada más. En particular, sin fijar ningún modelo en particular, y sin que importe que en los modelos más habituales sea falsa. Da igual que la fórmula sea verdadera o falsa para ilustrar las nociones de variable libre y ligada. Pero entonces no tiene sentido entrar a elucubrar sobre qué valores pueden tomar las variables. En primer lugar haría falta fijar un modelo (o al menos una teoría axiomática) que determinara qué clase de objetos recorren las variables.

Pues para que lo nombren y luego no se use en el resto del curso, ¿qué sentido tuvo ponerlo? Por "usar" me refiero a hacer mención explícita en por lo menos un ejercicio, pero es que ni eso, con un ejemplo terminan esa parte del tema. No me parece adecuado desde el punto de vista del aprendizaje.

Lo que ocurre es que ahora como ayudante veo un poco mejor cómo se enseña esa asignatura. En particular, he notado que en el tema de lógica, nunca usamos predicados de más de 1 variable porque quizás "no sea el objetivo de la materia complicarse las cosas con más variables" y está bien, pero yo como curioso leo "variables libres y ligadas" y en todo el resto de la materia no lo nombran y entonces me pica la curiosidad por saber más.

En las teorías de conjuntos usuales todo son conjuntos. Los elementos de los conjuntos son también conjuntos. No hay nada más que conjuntos.

Claro. Al fin y al cabo que siempre acabaremos ahí.

Tienes que especificar el lenguaje formal que consideras y los axiomas que consideras. Por ejemplo, la fórmula \( \forall A\, A\subset A \), puede interpretarse como un teorema de ZFC, en cuyo caso \( A \) es un conjunto simplemente porque en ZFC todo son conjuntos, o también como un teorema de NBG, en cuyo caso \( A \) recorrería todas las clases, tanto las que son conjuntos como las que no.

No sé a qué te refieres exactamente con "conjunto universal". Se le puede dar sentido de varias formas, pero ninguna es estándar. En las teorías de conjuntos usuales, como ZFC, no hay ningún conjunto universal. Si te refieres al universo de un modelo, entonces sería muy retorcido ponerlo explícito en la fórmula.

Sinceramente no creo que usemos algún modelo con nombre y apellido, sino que por lo menos yo veo que usamos una teoría estándar, de libros clásicos introductorios y nada más.

Pero tu última oración creo que da en la tecla de por qué se ven demostraciones de conjuntos sin que se escriba al "conjunto universal" como parte del ejercicio.

¿Qué son conjuntos numéricos principales?

Los naturales, enteros, racionales y reales. En todos ellos podemos definir una suma y un producto habituales sin que nadie nos pregunte, por ejemplo, "Oye, ¿cómo demuestras la propiedad de cerradura en la adición de esos conjuntos numéricos?" sino que se los toma como "base" para otras operaciones más complejas, como por ejemplo en \( \Bbb{Z} \) si se definiera la operación \( a*b=a\cdot b+2 \).

Si consideras la fórmula \( \forall x\, x+y<5 \), no tiene sentido decir si es verdadera o falsa si no fijamos un modelo. Pongamos por ejemplo el modelo \( M \) cuyo universo son los números naturales (daría igual considerar números reales, por ejemplo). Se entiende que \( + \) se interpreta como la suma de números naturales, etc. Ahora necesitas fijar una valoración \( v \) que a cada variable le asigne un objeto de \( M \). Entonces, se cumple \( M\vDash \forall x\,x+y<5[v] \) si y sólo si para todo número natural \( n \), se cumple que \( n+v(y)<5 \), pero eso no es cierto sea cual sea \( v(y) \). Siempre puedes encontrar un número natural \( n \) por ejemplo \( n=6 \), de modo que \( n+v(y)>5 \).

Y esto significa que la fórmula es falsa en el modelo \( M \).

Vale, creo que voy entendiendo.

Y si ahora escribo \( \forall x\in\Bbb{R}\,\exists y\in\Bbb{N}\cup\{0\}\, x+y<5 \), ¿esta fórmula tendría un modelo asociado de forma natural, implícita? ¿Cuál sería y cómo lo has deducido? Aquí ya no hay variables libres; todas están ligadas.

Pues no sé. Nunca he manejado esa jerga. En la lógica de primer orden no hay necesidad de jugar con clasificaciones de ese tipo. Lo que hay de fondo es que, en general, para determinar si una fórmula es satisfecha o no en un modelo tienes que fijar una valoración que interprete sus variables libres, aunque no siempre. La fórmula \( x\in y\lor x\notin y \) es verdadera en cualquier modelo, sin que importe que tiene variables libres.

Hombre pues claro, una tautología siempre es verdadera (y por lo que te entendí, agregaría "en cualquier modelo"). Lo mismo ocurre con una contradicción como \( x\in y\land x\notin y \).

Lo interesante, creo yo, es estudiar fórmulas de las que de antemano no se sepa cuál será su valor de verdad.

Esa \( \phi \) representa una fórmula. Geómetracat estaba siendo más formal y yo más informal. Es como si te digo que la derivada del seno es el coseno y geómetracat dice que \( (\sin x)' = \cos x \).

Por ejemplo, \( \forall x\in y\, x\subset y \) es un ejemplo de fórmula con un cuantificador acotado. Es la definición de conjunto transitivo. La \( \phi \) de geómetracat es \( \phi\equiv x\subset y \). La fórmula es de tipo \( \forall x\in y\, \phi \), con la \( \phi \) que te he dicho.

Yo había dicho, más informalmente, que ahí hay un cuantificador acotado porque aparece en la forma \( \forall x\in y \), dando por hecho que hay que poner algo detrás para que la fórmula esté completa.

Muchas gracias.

A ver pongo unos ejemplos:

- La fórmula \( \exists x\in\{1,2,3\}\colon x>2 \) tiene a \( x \) como variable ligada (por el \( \exists \)), y el \( \exists \) es un cuantificador acotado pues tiene el \( \in\{1,2,3\} \).

- La fórmula \( \exists x\colon x>2 \) tiene a \( x \) como variable ligada (por el \( \exists \)), ¿y se puede decir que el cuantificador \( \exists \) es un "cuantificador libre" por no tener una pertenencia?

Si existe tal "Cuantificador libre", entonces podríamos armar una tabla de doble entrada como la siguiente (para teoría de conjuntos):

\(
\begin{array}{c|c|c}
\text{Fórmula con...}&\text{Cuantificador libre}&\text{Cuantificador acotado}\\\hline
\text{Variable libre}&x>2&\text{¿\(x>2\)?}\\\hline
\text{Variable ligada}&\exists x\colon x>2&\exists x\in\{1,2,3\}\colon x>2\\
\end{array}
 \)

Me genera dudas el de variable libre y cuantificador acotado, porque al ser variable libre hay ausencia de cuantificador, así que supuse que cuando una variable es libre se puede hablar tanto de cuantificador libre o acotado. ¿Es correcto?

Gracias y saludos

22 Octubre, 2020, 10:22 am
Respuesta #11

Carlos Ivorra

  • Administrador
  • Mensajes: 9,674
  • País: es
  • Karma: +0/-0
  • Sexo: Masculino
    • Página web personal
Sinceramente no creo que usemos algún modelo con nombre y apellido, sino que por lo menos yo veo que usamos una teoría estándar, de libros clásicos introductorios y nada más.

Pero tu última oración creo que da en la tecla de por qué se ven demostraciones de conjuntos sin que se escriba al "conjunto universal" como parte del ejercicio.

Pues a mí me da la sensación de que hacéis una mezcla muy poco ortodoxa entre sintaxis y semántica, pero no sé. No conozco los detalles, ni la finalidad con la que tratáis la lógica.

Y si ahora escribo \( \forall x\in\Bbb{R}\,\exists y\in\Bbb{N}\cup\{0\}\, x+y<5 \), ¿esta fórmula tendría un modelo asociado de forma natural, implícita? ¿Cuál sería y cómo lo has deducido? Aquí ya no hay variables libres; todas están ligadas.

Me cuesta responderte, porque todo lo que planteas me resulta demasiado impreciso. Hace falta conjeturar una interpretación posible de lo que quieres decir para dar una respuesta posible. Literalmente, yo veo la fórmula

 \( \forall x\in\Bbb{R}\,\exists y\in\Bbb{N}\cup\{0\}\, x+y<5 \),

y, salvo que me digan otra cosa, entiendo que es una fórmula del lenguaje de la teoría de conjuntos, que deberá ser interpretada en modelos de la teoría de conjuntos. Es posible definir lenguajes y teorías axiomáticas que tengan como modelos naturales los cuerpos, o los cuerpos ordenados, etc., pero entonces sobraría el \( x\in\Bbb{R} \), si es que quieres tomar a \( \Bbb{R} \) como modelo, ya que en tal caso bastaría escribir \( \forall x \), y tendría que tratarse de una teoría en la que fuera posible definir los números naturales, o que contara al menos con un relator que deba interpretarse como la pertenencia a \( \Bbb{N} \), pero todo eso son cosas que habría que aclarar antes de plantearse qué modelos tiene esa sentencia.

Insisto en que no acabo de entender cómo concibes tú estas cosas, paro a mí me resulta muy chocante (chirriante, diría incluso) que escribas una fórmula con notación conjuntista (con pertenencias, uniones, conjuntos numéricos) y a la vez preguntes por modelos naturales para esa fórmula, como si presupusieras que el lenguaje en que está escrita no es el lenguaje de la teoría de conjuntos (que podría no serlo, pero haría falta especificar muchas cosas en tal caso para que se entendiera qué es esa fórmula).

Pues no sé. Nunca he manejado esa jerga. En la lógica de primer orden no hay necesidad de jugar con clasificaciones de ese tipo. Lo que hay de fondo es que, en general, para determinar si una fórmula es satisfecha o no en un modelo tienes que fijar una valoración que interprete sus variables libres, aunque no siempre. La fórmula \( x\in y\lor x\notin y \) es verdadera en cualquier modelo, sin que importe que tiene variables libres.

Hombre pues claro, una tautología siempre es verdadera (y por lo que te entendí, agregaría "en cualquier modelo"). Lo mismo ocurre con una contradicción como \( x\in y\land x\notin y \).

Lo interesante, creo yo, es estudiar fórmulas de las que de antemano no se sepa cuál será su valor de verdad.

Yo te ponía un ejemplo de cómo una fórmula puede ser verdadera aunque tenga variables libres. Que te parezca más o menos interesante es otra cosa. No es necesario que sea una tautología. Por ejemplo, \( x^2\geq 0 \) es verdadera cuando tomas como modelo a los números reales.

- La fórmula \( \exists x\in\{1,2,3\}\colon x>2 \) tiene a \( x \) como variable ligada (por el \( \exists \)), y el \( \exists \) es un cuantificador acotado pues tiene el \( \in\{1,2,3\} \).

Los cuantificadores acotados se definen para establecer una jerarquía de fórmulas según su complejidad, de modo que el nivel más bajo de la jerarquía lo forman las fórmulas cuyos cuantificadores están todos acotados. En ese contexto, es frecuente que se exija que la "cota" de cada cuantificador sea una variable y no un término cualquiera, es decir que no valdría \( x\in\{1,2,3\} \) como cota. En algunos contextos se pueden permitir cotas algo más generales, pero no es lo habitual.

- La fórmula \( \exists x\colon x>2 \) tiene a \( x \) como variable ligada (por el \( \exists \)), ¿y se puede decir que el cuantificador \( \exists \) es un "cuantificador libre" por no tener una pertenencia?

Se dice que el cuantificador no está acotado.

Me genera dudas el de variable libre y cuantificador acotado, porque al ser variable libre hay ausencia de cuantificador, así que supuse que cuando una variable es libre se puede hablar tanto de cuantificador libre o acotado. ¿Es correcto?

Si no hay cuantificadores, entonces no hay cuantificadores. No puedes decir que haya cuantificadores no acotados. Como te decía, este concepto se usa para introducir una jerarquía de fórmulas que empieza con las fórmulas de tipo \( \Delta_0 \), que son las que no tienen cuantificadores no acotados. Una fórmula sin cuantificadores es \( \Delta_0 \).

22 Octubre, 2020, 09:12 pm
Respuesta #12

manooooh

  • $$\Large \color{#9c57a6}\pi\,\pi\,\pi\,\pi\,\pi\,\pi$$
  • Mensajes: 3,350
  • País: ar
  • Karma: +1/-0
  • Sexo: Masculino
Hola

Pues a mí me da la sensación de que hacéis una mezcla muy poco ortodoxa entre sintaxis y semántica, pero no sé. No conozco los detalles, ni la finalidad con la que tratáis la lógica.

Es la asignatura Matemática Discreta en 1er año de Ingeniería. Así que es probable que nos interese más las aplicaciones prácticas como grafos, árboles, recurrencia más allá de las demostraciones. Pero quiero ser el ingeniero más matemático, y eso puede llevarme a buen camino... o no.

Insisto en que no acabo de entender cómo concibes tú estas cosas, paro a mí me resulta muy chocante (chirriante, diría incluso) que escribas una fórmula con notación conjuntista (con pertenencias, uniones, conjuntos numéricos) y a la vez preguntes por modelos naturales para esa fórmula, como si presupusieras que el lenguaje en que está escrita no es el lenguaje de la teoría de conjuntos (que podría no serlo, pero haría falta especificar muchas cosas en tal caso para que se entendiera qué es esa fórmula).

Claro. Debe ser porque confundo "Modelo" con "Conjunto universal/de discurso".

Yo te ponía un ejemplo de cómo una fórmula puede ser verdadera aunque tenga variables libres. Que te parezca más o menos interesante es otra cosa. No es necesario que sea una tautología. Por ejemplo, \( x^2\geq 0 \) es verdadera cuando tomas como modelo a los números reales.

De acuerdo, y una cosa más. ¿Una tautología (ídem contradicción) se dice así porque es una fórmula siempre verdadera (falsa) en al menos un modelo, o en todos los modelos? Quiero pensar que se dice "Esta fórmula es una tautología en este modelo, pero puede que en otro no".

Los cuantificadores acotados se definen para establecer una jerarquía de fórmulas según su complejidad, de modo que el nivel más bajo de la jerarquía lo forman las fórmulas cuyos cuantificadores están todos acotados. En ese contexto, es frecuente que se exija que la "cota" de cada cuantificador sea una variable y no un término cualquiera, es decir que no valdría \( x\in\{1,2,3\} \) como cota. En algunos contextos se pueden permitir cotas algo más generales, pero no es lo habitual.

Entonces si tomamos el ejemplo de conjunto transitivo \( \forall x\in y\, x\subset y \) es una fórmula con un cuantificador acotado, ¿es así porque la \( y \) es una variable (puede tomar diversos valores), en cambio \( \{1,2,3\} \) es un caso particular?

Compararé esa definición con la siguiente propiedad a ver si me ayudas a sacar conclusiones:

a) Definición de conjunto transitivo \( \forall x\in y\, x\subset y \)

b) Propiedad transitiva de la inclusión \( \forall A\,\forall B\,\forall C\, A\subset B\land B\subset C\to A\subset C \)

Demostración de b)
\( \forall x\colon x\in A\to x\in B\to x\in C \)
[cerrar]

1) ¿Son dos fórmulas?

2) ¿Pertenecen al lenguaje de la teoría de conjuntos?

3) ¿a) es un caso general de b)?

4) ¿a) tiene 1 cuantificador acotado y b) tiene 3 cuantificadores no acotados?

5) ¿a) tiene 1 variable ligada y 1 libre y b) tiene 3 variables ligadas?

Muchas gracias.

Saludos

22 Octubre, 2020, 10:57 pm
Respuesta #13

Carlos Ivorra

  • Administrador
  • Mensajes: 9,674
  • País: es
  • Karma: +0/-0
  • Sexo: Masculino
    • Página web personal
De acuerdo, y una cosa más. ¿Una tautología (ídem contradicción) se dice así porque es una fórmula siempre verdadera (falsa) en al menos un modelo, o en todos los modelos? Quiero pensar que se dice "Esta fórmula es una tautología en este modelo, pero puede que en otro no".

Puede haber variantes, pero el uso que yo conozco de la palabra "tautología" en el contexto de la lógica de primer orden se restringe a las fórmulas que resultan de sustituir variables proposicionales por fórmulas de primer orden en una tautología del cálculo proposicional.

Así, \( x=y\lor x\neq y \) es una tautología, pero \( x=y\rightarrow y=x \) no lo es, a pesar de que es una fórmula verdadera en todo modelo. Yo a esto lo llamo una fórmula lógicamente válida, pero no una tautología, y diría que la distinción es usual.

En cualquier caso, si entendemos por "tautología" lo que yo llamo fórmulas lógicamente válidas, son las que son verdaderas en todos los modelos. Si una fórmula es verdadera en un modelo, pero en otros no, pues eso, es una fórmula verdadera en ese modelo.

Entonces si tomamos el ejemplo de conjunto transitivo \( \forall x\in y\, x\subset y \) es una fórmula con un cuantificador acotado, ¿es así porque la \( y \) es una variable (puede tomar diversos valores), en cambio \( \{1,2,3\} \) es un caso particular?

No sé a qué llamas en este contexto un "caso particular". Simplemente, \( \{1,2,3\} \) no es una variable. Pero \( y \) no es una variable porque pueda tomar distintos valores. También \( \mathcal Py \) puede tomar distintos valores y no es una variable, ni serviría para acotar cuantificadores.

1) ¿Son dos fórmulas?

Sí.

2) ¿Pertenecen al lenguaje de la teoría de conjuntos?

Sí.

3) ¿a) es un caso general de b)?

No hay ninguna relación entre a) y b).

4) ¿a) tiene 1 cuantificador acotado y b) tiene 3 cuantificadores no acotados?

Sí.

5) ¿a) tiene 1 variable ligada y 1 libre y b) tiene 3 variables ligadas?

Sí.

23 Octubre, 2020, 12:44 am
Respuesta #14

manooooh

  • $$\Large \color{#9c57a6}\pi\,\pi\,\pi\,\pi\,\pi\,\pi$$
  • Mensajes: 3,350
  • País: ar
  • Karma: +1/-0
  • Sexo: Masculino
Hola

Puede haber variantes, pero el uso que yo conozco de la palabra "tautología" en el contexto de la lógica de primer orden se restringe a las fórmulas que resultan de sustituir variables proposicionales por fórmulas de primer orden en una tautología del cálculo proposicional.

Así, \( x=y\lor x\neq y \) es una tautología, pero \( x=y\rightarrow y=x \) no lo es, a pesar de que es una fórmula verdadera en todo modelo. Yo a esto lo llamo una fórmula lógicamente válida, pero no una tautología, y diría que la distinción es usual.

En cualquier caso, si entendemos por "tautología" lo que yo llamo fórmulas lógicamente válidas, son las que son verdaderas en todos los modelos. Si una fórmula es verdadera en un modelo, pero en otros no, pues eso, es una fórmula verdadera en ese modelo.

No comprendo la distinción entre una fórmula lógicamente válida y una tautología porque no entiendo qué quieres decir con "fórmulas que resultan de sustituir variables proposicionales por fórmulas de primer orden en una tautología del cálculo proposicional".

No sé a qué llamas en este contexto un "caso particular". Simplemente, \( \{1,2,3\} \) no es una variable. Pero \( y \) no es una variable porque pueda tomar distintos valores. También \( \mathcal Py \) puede tomar distintos valores y no es una variable, ni serviría para acotar cuantificadores.

Ah, pues no entiendo qué representa la \( \in y \) en \( \forall x\in y\, x\subset y \). ¿Resulta un metasímbolo o algo así?

No comprendo por qué \( \mathcal Py \) no lo consideramos "variable", porque a cada \( y \) (que entiendo es un conjunto), se le asigna \( \mathcal Py \) formado por todos los subconjuntos de \( y \). Así que si \( y \) es un conjunto (no importa cuál, por eso varía) también lo es su conjunto de partes (depende de qué conjunto sea \( y \)).

No hay ninguna relación entre a) y b).

Ah, yo las veía relacionadas pero se ve que simplemente son dos cosas distintas porque refieren a cosas distintas, no porque una tenga cuantificadores no acotados y el otro uno acotado y cosas del estilo.

Saludos

23 Octubre, 2020, 12:56 am
Respuesta #15

Carlos Ivorra

  • Administrador
  • Mensajes: 9,674
  • País: es
  • Karma: +0/-0
  • Sexo: Masculino
    • Página web personal
No comprendo la distinción entre una fórmula lógicamente válida y una tautología porque no entiendo qué quieres decir con "fórmulas que resultan de sustituir variables proposicionales por fórmulas de primer orden en una tautología del cálculo proposicional".

En el cálculo proposicional, las variables representan proposiciones. Por ejemplo, \( p\lor \lnot p \) es una fórmula del cálculo proposicional y es una tautología, porque su tabla de verdad dice que siempre es verdadera. Si en lugar de la variable proposicional \( p \) pones cualquier fórmula de primer orden, como \( x\in \mathbb R \), obtienes una tautología, como \( x\in \mathbb R\lor x\notin \mathbb R \).

En cambio, \( x=y\rightarrow y=x \) no puede obtenerse de ese modo a partir de una tautología de la lógica proposicional. Por eso no es una tautología.

Ah, pues no entiendo qué representa la \( \in y \) en \( \forall x\in y\, x\subset y \). ¿Resulta un metasímbolo o algo así?

Es el relator de pertenencia de toda la vida en teoría de conjuntos. Un conjunto es transitivo cuando todos sus elementos son también subconjuntos suyos.

No comprendo por qué \( \mathcal Py \) no lo consideramos "variable", porque a cada \( y \) (que entiendo es un conjunto), se le asigna \( \mathcal Py \) formado por todos los subconjuntos de \( y \). Así que si \( y \) es un conjunto (no importa cuál, por eso varía) también lo es su conjunto de partes (depende de qué conjunto sea \( y \)).

No he dicho que \( \mathcal Py \) no sea variable, sino que no es una variable. Una variable es \( y \), pero \( \mathcal Py \) es la variable \( y \) precedida de \( \mathcal P \). Lo que te digo es que no puedes acotar un cuantificador con una \( \mathcal P \) ni nada parecido.