Autor Tema: Satisfiabilidad, verdad y modelos.

0 Usuarios y 1 Visitante están viendo este tema.

31 Octubre, 2012, 01:00 am
Leído 2983 veces

yotas

  • Sé valiente, no voluble, no maleable.
  • $$\Large \color{#c88359}\pi\,\pi\,\pi\,\pi$$
  • Mensajes: 725
  • Karma: +0/-0
  • Sexo: Masculino
  • Plop, plop.
¡Buenas buenas!

Tengo problemas para realizar dos demostraciones, bueno que una es un hint de la otra... El enunciado dice:

(VIII) Si las variables libres (si las hay) en una wf \( \mathcal{A} \) ocurren en la lista \( x_i_1, ... , x_i_k \), y si la secuencias \( s \) y \( s' \) tienen las mismas componentes en las \( i_1,..., i_k \)-ésimas componentes, entonces \( s \) satisface \( \mathcal{A} \) si y sólo si \( s' \) satisface \( \mathcal{A} \). [hint: Use inducción en el número de conectivos y cuantificadores en \( \mathcal{A} \). Primero pruebe el siguiente lema: si las variables en un término \( t \) ocurren en la lista \( x_i_1, ..., x_i_k \) y si \( s \) y \( s' \) tienen las mismas componentes en las \( i_1,...,i_k \)-ésimas posición, entonces \( s^*(t)=(s')^*(t) \). En particular, si \( t \) no contiene ninguna variable, \( s^*(t)=(s')^*(t) \) para cualquier secuencia \( s \) y \( s' \).]

Esto se explica en el libro Introduction to Mathematical Logic de Elliott Mendelson tercera edición capítulo 2. Quantification theory numeral 2. Interpretations, Satisfiability, Thruth and Models.

Comentario: me parece curioso no haber podido encontrar alguna traducción para la palabra satisfiability.

¡Gracias por las respuestas y comentarios!
Citar
Creo debes tener un problema en tu mente por el cual complicas las cosas y las afirmaciones más sencillas.

Sí, es un problema muy frecuente en este foro. Se llama saber matemáticas.

31 Octubre, 2012, 01:38 am
Respuesta #1

Carlos Ivorra

  • Administrador
  • Mensajes: 11,956
  • País: es
  • Karma: +0/-0
  • Sexo: Masculino
    • Página web personal
Podrías explicar que son \( s \) y \( s' \). Diría que hay en juego un modelo del que no hablas. En cualquier caso, parece que sea, con otra notación, el resultado demostrado en el tercer teorema empezando desde el final demostrado en este post.

31 Octubre, 2012, 02:06 am
Respuesta #2

yotas

  • Sé valiente, no voluble, no maleable.
  • $$\Large \color{#c88359}\pi\,\pi\,\pi\,\pi$$
  • Mensajes: 725
  • Karma: +0/-0
  • Sexo: Masculino
  • Plop, plop.
Podrías explicar que son \( s \) y \( s' \). Diría que hay en juego un modelo del que no hablas. En cualquier caso, parece que sea, con otra notación, el resultado demostrado en el tercer teorema empezando desde el final demostrado en este post.

Hasta ahí sólo se ha dado una definición del concepto de modelo, no se habla de ninguno en particular. El resultado del teorema no lo entiendo, y no le veo relación - o lo estoy buscando mal-.

Las \( s \) y \( s' \) son secuencias infinitas del conjunto dominio de interpretación. Y la 'función' \( s* \) es una 'función' que asigna a cada variable \( x_i \) el elemento \( s_i \) y a cada funtor \( f^n_i(t_1,..., t_n) \) le asigna el valor de la operación de aridad \( n \) \( (f^n_i)^M(s*(t_1),..., t_n) \) en el modelo \( M \).

No sé si eso se entenderá así. Sí se está hablando de un modelo \( M \), con un dominio de interpretación \( D \). Pero sigue siendo aún arbitrario.  ;D



Citar
Creo debes tener un problema en tu mente por el cual complicas las cosas y las afirmaciones más sencillas.

Sí, es un problema muy frecuente en este foro. Se llama saber matemáticas.

31 Octubre, 2012, 07:34 am
Respuesta #3

Fernando Revilla

  • "Há tantos burros mandando em homens de inteligência, que, às vezes, fico pensando que a burrice é uma ciência." -Antonio Aleixo.
  • Administrador
  • Mensajes: 12,575
  • País: es
  • Karma: +0/-0
  • Sexo: Masculino
  • "Las matemáticas son demasiado humanas."- Brouwer
    • Fernando Revilla
Comentario: me parece curioso no haber podido encontrar alguna traducción para la palabra satisfiability.

Puedes traducirla por "satisfacción". Algunos libros de Lógica en inglés hablan de satisfiability and truth, otros de satisfaction and truth.

31 Octubre, 2012, 11:11 am
Respuesta #4

Carlos Ivorra

  • Administrador
  • Mensajes: 11,956
  • País: es
  • Karma: +0/-0
  • Sexo: Masculino
    • Página web personal
No sé si eso se entenderá así. Sí se está hablando de un modelo \( M \), con un dominio de interpretación \( D \). Pero sigue siendo aún arbitrario.  ;D

A eso me refería, a que todo lo que decías debía entenderse en relación a un modelo M con dominio D, cosa que no estaba dicha en ningún sitio. El teorema del que hablas es el mismo que el que yo demuestro en el hilo que te he indicado, con meros cambios de notación:

Tú distingues entre el modelo M y su universo D. Yo llamo a ambos M, por abuso de lenguaje. Las funciones que tú representas por \( s \) (que asignan a a cada variable \( x_i \) un objeto \( s_i \) del domino del modelo) yo las represento por \( v \) y escribo \( v(x_i) \) donde tú escribes \( s_i \). Lo que tú representas por \( (f_i^n)^M \) yo lo represento por \( I(f_i^n) \) (aunque yo escribo \( f \) en lugar de \( f_i^n \), sin explicitar los valores de i, n en cada momento. La función que tú llamas \( s*(t) \) yo la llamo \( M(t)[v] \) (dejando explícito el modelo M que está implícito en tu notación), y la relación \( s \) satisface \( \mathcal A \) (en un modelo implícito M) yo la represento por \( M\vDash \phi [v] \) (porque yo uso letras griegas en lugar de caligráficas para las fórmulas).

Salvo que, como ves, la notación es radicalmente distinta, el resultado del que hablas es el mismo que aparece en mi hilo. Se trata de probar que si dos valoraciones v y w (con tu notación s y s') coinciden sobre las variables libres de una fórmula \( \phi \) o \( \mathcal A \), entonces \( M\vDash \phi [v] \) si y sólo si \( M\vDash \phi [w] \) o, con tu notación, \( s \) satisface \( \mathcal A \) si y sólo si \( s' \) satisface \( \mathcal A \).

Bueno: verás que escribo cosas como \( \ulcorner\phi\urcorner \) en lugar de \( \phi \), pero en este contexto, si te olvidas de todos los ángulos \( \ulcorner\ \urcorner \) como si no estuvieran no pasa nada.

21 Febrero, 2013, 10:20 pm
Respuesta #5

Kaspar Hauser

  • $$\Large \color{#5372a0}\pi\,\pi$$
  • Mensajes: 79
  • Karma: +0/-0
  • Sexo: Masculino
Comentario: me parece curioso no haber podido encontrar alguna traducción para la palabra satisfiability.

Figura en el diccionario RAE:

factible.

(Del lat. factibĭlis).

1. adj. Que se puede hacer.

También:

 satisfacer.

(Del lat. satisfacĕre).

MORF. conjug. c. hacer, salvo el imper.: satisfaz o satisface; part. irreg. satisfecho.

Por eso deduzco que un adjetivo que se deriva de "satisfacer" debe construirse a partir de "factible": "satisfactible". Igual el sustantivo: "satisfactibilidad".

Es sólo una deducción informal no lógica :)

Por otra parte, la noción de satisfactibilidad es muy anterior a la teoría de modelos. Viene del álgebra elemental: ningún valor real satisface la ecuación
\( x^2 + 1 = 0 \).

De allí viene el uso que le da Tarski en sus trabajos, para caracterizar la noción de satisfacción de una fórmula abierta por una constante: se obtiene una sentencia verdadera.

Mendelson introduce primero la noción de Interpretación, y luego la noción de modelo como una interpretación que satistace una teoría: la que hace verdadera una teoría. Porque la definición de modelo como algo que existe sólo si satisface una teoría es un poco extraña. Pues si tengo una teoría consistente, y por lo tanto un modelo, y le agrego un axioma que la hace inconsistente, el modelo desaparece. En cambio, la interpretación permite que sigua teniendo un "significado", aunque ya no sea consistente.

Saludos


01 Marzo, 2013, 09:20 am
Respuesta #6

Raúl Aparicio Bustillo

  • $$\Large \color{#9c57a6}\pi\,\pi\,\pi\,\pi\,\pi\,\pi$$
  • Mensajes: 3,113
  • Karma: +0/-3
  • Sexo: Masculino
Sólo un comentario: no sé yo si mirar el diccionario en teorías matemáticas es lo más adecuado. Yo busqué la definición de conjunto por curiosidad un día y bueno, ahí está.

 Claro, que tampoco tiene mucho sentido un diccionario dando los axiomas de una teoría de conjuntos.

 El diccionario no puede ser preciso en grado total en muchos términos, se convertiría en una enciclopedia de miles de tomos ( tendría que ser una especie de Wikipedia) imagino que pasara lo mismo en otras ciencias ( en física lo puedo garantizar, y eso que el concepto de energía no es tan complicado de definir [ es otra de las palabrejas que busqué en su tiempo] xD

01 Marzo, 2013, 03:30 pm
Respuesta #7

yotas

  • Sé valiente, no voluble, no maleable.
  • $$\Large \color{#c88359}\pi\,\pi\,\pi\,\pi$$
  • Mensajes: 725
  • Karma: +0/-0
  • Sexo: Masculino
  • Plop, plop.
Sólo un comentario: no sé yo si mirar el diccionario en teorías matemáticas es lo más adecuado. Yo busqué la definición de conjunto por curiosidad un día y bueno, ahí está.
Jajajajajajajajajaja. Increiblemente gracioso.   ;D
Citar
Creo debes tener un problema en tu mente por el cual complicas las cosas y las afirmaciones más sencillas.

Sí, es un problema muy frecuente en este foro. Se llama saber matemáticas.