Autor Tema: Sobre el uso de Tablas de Verdad

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

26 Diciembre, 2011, 09:28 pm
Leído 8120 veces

argentinator

  • Consultar la FIRMAPEDIA
  • Administrador
  • Mensajes: 7,723
  • País: ar
  • Karma: +0/-0
  • Sexo: Masculino
  • Vean mis posts activos en mi página personal
    • Mis posts activos (click aquí)

En la lógica proposicional está bastante claro el papel que juegan las tablas de verdad a la hora de definir "verdad semántica".

Sin embargo no tengo claro qué papel juegan en la lógica de primer orden.
¿Se usan realmente, o no se usan para nada?

En tal caso, dado que toda la matemática está básicamente apoyada en la lógica de primer orden, ¿qué papel juegan las tablas de verdad en las demostraciones cotidianas de la matemática? ¿Es formalmente válido recurrir a las tablas de verdad para justificar un razonamiento?


26 Diciembre, 2011, 09:54 pm
Respuesta #1

Carlos Ivorra

  • Administrador
  • Mensajes: 11,059
  • País: es
  • Karma: +0/-0
  • Sexo: Masculino
    • Página web personal
Supongo que te refieres a si, por ejemplo, es lícito deducir de la tabla de verdad que escribió Fran Colegiales en

http://rinconmatematico.com/foros/index.php/topic,48433.msg203473.html#msg203473

que \( A\Rightarrow \lnot B \) es equivalente a \( B\Rightarrow \lnot A \)

donde A y B no son variables proposicionales, sino que representan dos fórmulas del lenguaje de la teoría de conjuntos, como por ejemplo \( x\in A \) y \( x\in B \).

Lo que prueba esa tabla es que la fórmula  \( (A\Rightarrow \lnot B)\Leftrightarrow (B\Rightarrow \lnot A) \) es verdadera en cualquier modelo de la teoría de conjuntos (más aún, de cualquier modelo del lenguaje de la teoría de conjuntos, aunque no cumpla sus axiomas) y el teorema de completitud de Gödel te asegura entonces que es un teorema lógico, es decir, que puede demostrarse formalmente incluso sin apoyarse en los axiomas de la teoría de conjuntos.

Ahora bien, esto no es una demostración formal, sino una demostración metamatemática no constructiva de que existe una demostración formal de esa equivalencia. La tabla de verdad no te da un criterio para encontrar explícitamente esa demostración. A mí me vale. A ti, no sé. Tú verás.


26 Diciembre, 2011, 10:43 pm
Respuesta #2

argentinator

  • Consultar la FIRMAPEDIA
  • Administrador
  • Mensajes: 7,723
  • País: ar
  • Karma: +0/-0
  • Sexo: Masculino
  • Vean mis posts activos en mi página personal
    • Mis posts activos (click aquí)
Sí, las dudas me surgieron a partir de ahí, porque en realidad el tema tiene más vueltas que la pregunta de Fran  Colegiales.

No me había anticipado a una situación como esta.

Resulta que me he acostumbrado a usar las reglas de inferencia sin apelar a las tablas de verdad,
pero en mis inicios en la matemática aprendí a razonar con ayuda de las tablas de verdad.

Pero si viene alguien y me muestra un razonamiento hecho con tablas de verdad, ¿qué le digo? ¿Qué está bien? ¿Qué está mal?

Tengo problemas en el modo pedagógico de encararlo, porque quiero evitar el tener que recurrir a todo el formalismo de los lenguajes formales, y sin embargo tampoco quiero enseñar cosas que son formalmente incorrectas.

_________________

Lo adecuado, creo yo, es tratar de acostumbrar al auditorio a reemplazar paulatinamente las Tablas de Verdad con las fórmulas proposicionales. De hecho, hay modos sistemáticos de hacerlo.
Pero todo esto requiere una discusión previa que quería evitar.

No sé cuánto tiempo podré seguir esquivando el bulto. Algún capítulo concreto sobre lógica tendré que poner.

26 Diciembre, 2011, 10:58 pm
Respuesta #3

Carlos Ivorra

  • Administrador
  • Mensajes: 11,059
  • País: es
  • Karma: +0/-0
  • Sexo: Masculino
    • Página web personal
Pero si viene alguien y me muestra un razonamiento hecho con tablas de verdad, ¿qué le digo? ¿Qué está bien? ¿Qué está mal?

Un matemático da por demostrado un teorema en cuanto tiene un argumento lógico que le convence de que no puede ser falso (técnicamente, en un modelo que cumpla sus axiomas, aunque esto no suelen tenerlo presente). Ciertamente, un argumento no formalizado podría tener un error sutil que no se aprecie hasta que uno se pone a formalizar la prueba, pero si uno ha construido una tabla de verdad, no se ha equivocado en las cuentas y no se equivoca al constatar que le queda al final una columna de "uves", es imposible que pueda haber error alguno: la afirmación no puede ser falsa. Es cierto que de ahí a encontrar una demostración formal hay un paso, pero cualquier matemático aceptará el argumento como concluyente (con lo que está aceptando tácitamente el teorema de completitud, pero es que el teorema de completitud es un teorema, y los teoremas están para eso, para usarlos cuando conviene).

Por poner un ejemplo más claro: cualquier matemático aceptará que \( 2=2 \) aunque no conozca ninguna prueba formal de esta afirmación a partir de un sistema de axiomas lógicos (muchos matemáticos no conocen ningún sistema de axiomas lógicos en particular). Su "argumento", si insistes en pedirle uno, será: "eso se tiene que poder demostrar a partir de unos axiomas adecuados, y si no se puede, eso no significa que la afirmación no sea correcta, sino que los axiomas no están bien elegidos. Si te pones a hacer cuentas y me dices que algo falla, lo que falla son tus axiomas, no mi afirmación".

26 Diciembre, 2011, 11:17 pm
Respuesta #4

argentinator

  • Consultar la FIRMAPEDIA
  • Administrador
  • Mensajes: 7,723
  • País: ar
  • Karma: +0/-0
  • Sexo: Masculino
  • Vean mis posts activos en mi página personal
    • Mis posts activos (click aquí)
De lo que dijiste al principio entiendo que has usado la "lógica proposicional" a nivel "metamatemático" para justificar una deducción de, digamos, la "lógica de 1er orden".

El "teorema de completitud" de la lógica proposicional sería ahora un teorema "metametamatemático".

Al "interpretar" cada variable proposicional "p" de la lógica proposicional como una "fórmula del lenguaje de 1er orden", ¿qué es lo que se está haciendo? ¿Vale eso como una especie de "modelo" de la lógica proposicional?
¿O en realidad es sólo un procedimiento puramente informal?

O sea, el modo en que estás usando el teorema de completitud, además de ser metamatemático, ¿es informal? ¿O puede formalizarse en algún nivel?





26 Diciembre, 2011, 11:57 pm
Respuesta #5

Carlos Ivorra

  • Administrador
  • Mensajes: 11,059
  • País: es
  • Karma: +0/-0
  • Sexo: Masculino
    • Página web personal
De lo que dijiste al principio entiendo que has usado la "lógica proposicional" a nivel "metamatemático" para justificar una deducción de, digamos, la "lógica de 1er orden".

No. No uso la lógica proposicional para nada. Uso la definición de verdad en un modelo. Dado un modelo \( M \) y fijada una aplicación \( v \) que asigne a cada variable un elemento de \( M \) (que aquí es irrelevante), por definición se tiene que si \( A \) y \( B \) son fórmulas cualesquiera (no variables proposicionales), entonces

\( M\vDash (A\Rightarrow  B)[v] \) si y sólo si no \( M\vDash A[v] \) o  \( M\vDash B[v] \),

de modo que la afirmación \( M\vDash (A\Rightarrow  B)[v] \) será verdadera o falsa en función de si las afirmaciones \( M\vDash A[v] \) y  \( M\vDash B[v] \) son verdaderas o falsas exactamente como describe la tabla de verdad de \( \Rightarrow \).

De este modo, la tabla de verdad que citaba antes demuestra (teniendo en cuenta la definición de verdad en un modelo) que la fórmula \( (A\Rightarrow \lnot B)\Leftrightarrow (B\Rightarrow \lnot A) \) es verdadera en cualquier modelo (para cualquier interpretación de las variables) sean cuales sean las fórmulas \( A \) y \( B \). Aquí \( A \) y \( B \) son variables metamatemáticas que representan fórmulas arbitrarias, pero, si lo prefieres, puedes sustituirlas por dos fórmulas concretas, por ejemplo \( x\in A \) y \( x\in B \), en el ejemplo al que hacía referencia.

El "teorema de completitud" de la lógica proposicional sería ahora un teorema "metametamatemático".

Bueno, yo usaba el teorema de completitud usual para la lógica de primer orden. Lo que dices sería una posibilidad, y ahora mismo no te sabría decir si aportaría algo, porque no sé si el teorema de completitud para la lógica proposicional es "más constructivo" que el de la lógica de primer orden. Es probable que sí, pero en cualquier caso yo estaba usando el teorema de completitud usual para la lógica de primer orden.

Al "interpretar" cada variable proposicional "p" de la lógica proposicional como una "fórmula del lenguaje de 1er orden", ¿qué es lo que se está haciendo? ¿Vale eso como una especie de "modelo" de la lógica proposicional?
¿O en realidad es sólo un procedimiento puramente informal?

No sería descabellado plantear algo así, pero no era lo que yo estaba planteando. Yo consideraba dos fórmulas arbitrarias (del lenguaje de la teoría de conjuntos) \( A \) y \( B \) y razonaba con ellas como tales, basándome en la definición usual de verdad en un modelo, sin apoyarme en la teoría particular de la lógica proposicional. De todos modos, insisto en que "sumergir" la lógica proposicional en la lógica de predicados de primer orden para estudiar la relación entre ambas es algo que tiene perfecto sentido hacer.

O sea, el modo en que estás usando el teorema de completitud, además de ser metamatemático, ¿es informal? ¿O puede formalizarse en algún nivel?

Lo estoy usando a nivel metamatemático como se usa siempre que quieres justificar algo sobre si algo puede o no demostrarse "de verdad". Naturalmente, puedes formalizar el teorema de completitud y considerarlo como un teorema de la teoría de conjuntos, pero un teorema de la teoría de conjuntos te dice bien poco sobre si una afirmación "de verdad" es o no un teorema lógico. Para sacar conclusiones por ese camino tendrías que suponer que la teoría de conjuntos es consistente, una hipótesis que en realidad no hace falta para concluir que la fórmula del ejemplo es un teorema lógico.

27 Diciembre, 2011, 12:16 am
Respuesta #6

argentinator

  • Consultar la FIRMAPEDIA
  • Administrador
  • Mensajes: 7,723
  • País: ar
  • Karma: +0/-0
  • Sexo: Masculino
  • Vean mis posts activos en mi página personal
    • Mis posts activos (click aquí)
Es verdad Carlos, disculpame que interpreté mal lo que dijiste.
Cito el párrafo:


Lo que prueba esa tabla es que la fórmula  \( (A\Rightarrow \lnot B)\Leftrightarrow (B\Rightarrow \lnot A) \) es verdadera en cualquier modelo de la teoría de conjuntos (más aún, de cualquier modelo del lenguaje de la teoría de conjuntos, aunque no cumpla sus axiomas) y el teorema de completitud de Gödel te asegura entonces que es un teorema lógico, es decir, que puede demostrarse formalmente incluso sin apoyarse en los axiomas de la teoría de conjuntos.


Al releerla de nuevo, veo que estás aplicando directamente el teorema de completitud para lógicas de 1er orden, y la fórmula en cuestión sería "demostrable".

Pero entonces no sé cómo funciona esto que decís de que "de las tablas de verdad se puede deducir que la fórmula en cuestión es verdadera en cualquier modelo".

_________

Pero no me creo la primer parte...

A simple vista todo tiene sentido, y las tablas de verdad son muy creíbles, y me resultaría extraño que estuvieran mal,
pero no sé si es "legal".

Lo que escribiste parece bastante convincente, lástima que soy tan bruto con esto de los modelos.


Dado un modelo \( M \) y fijada una aplicación \( v \) que asigne a cada variable un elemento de \( M \) (que aquí es irrelevante), por definición se tiene que si \( A \) y \( B \) son fórmulas cualesquiera (no variables proposicionales), entonces

\( M\vDash (A\Rightarrow  B)[v] \) si y sólo si no \( M\vDash A[v] \) o  \( M\vDash B[v] \),

de modo que la afirmación \( M\vDash (A\Rightarrow  B)[v] \) será verdadera o falsa en función de si las afirmaciones \( M\vDash A[v] \) y  \( M\vDash B[v] \) son verdaderas o falsas exactamente como describe la tabla de verdad de \( \Rightarrow \).

De este modo, la tabla de verdad que citaba antes demuestra (teniendo en cuenta la definición de verdad en un modelo) que la fórmula \( (A\Rightarrow \lnot B)\Leftrightarrow (B\Rightarrow \lnot A) \) es verdadera en cualquier modelo (para cualquier interpretación de las variables) sean cuales sean las fórmulas \( A \) y \( B \).


Cuando decís "la tabla de verdad demuestra", ¿realmente "demuestra"?
¿Este uso de la tabla de verdad es parte de los cálculos usuales de la metamatemática, o es sólo un recurso informal?

No entiendo qué estás haciendo exactamente con eso ahí.

27 Diciembre, 2011, 12:44 am
Respuesta #7

Carlos Ivorra

  • Administrador
  • Mensajes: 11,059
  • País: es
  • Karma: +0/-0
  • Sexo: Masculino
    • Página web personal
Pero entonces no sé cómo funciona esto que decís de que "de las tablas de verdad se puede deducir que la fórmula en cuestión es verdadera en cualquier modelo".

Veamos:

\(
\begin{array}{|c|c|c|c|}
M\vDash A[v]&M\vDash B[v]&M\vDash\lnot B[v]&M\vDash(A\Rightarrow \lnot B)[v]\\
\hline
V&V&F&F\\
V&F&V&V\\
F&V&F&V\\
F&F&V&V\\
\hline
\end{array}
 \)

Interpretación: Tenemos dos fórmulas A y B (que pueden ser \( x\in A \) y \( x\in B \) o cualesquiera otras) y un modelo M. Cada una de las fórmulas (fijada una interpretación de las variables) es verdadera o falsa en M, luego tenemos los cuatro casos que indican las dos primeras columnas de la tabla.

La tercera columna se deduce de la definición de \( M\vDash \lnot B[v] \), que se cumple si y sólo si no se cumple  \( M\vDash B[v] \), y la cuarta columna se deduce de la definición de \( M\vDash (A\Rightarrow \lnot B)[v] \), que se cumple si la premisa es falsa o la conclusión verdadera.

Añadiendo más columnas a la tabla y razonando del mismo modo se llega a que, en los cuatro casos se cumple

\( M\vDash ((A\Rightarrow \lnot B)\Leftrightarrow (B\Rightarrow \lnot A))[v] \)

(porque en su columna quedarán cuatro uves.)

Por lo tanto, la fórmula es verdadera en cualquier modelo.

Pero no me creo la primer parte...

No sé a qué te refieres.

A simple vista todo tiene sentido, y las tablas de verdad son muy creíbles, y me resultaría extraño que estuvieran mal,
pero no sé si es "legal".

Las tablas de verdad reflejan literalmente la definición de verdad en un modelo, son una forma de comprobar que una fórmula es siempre verdadera ni más ni menos legal que usar el algoritmo usual de la suma o de la multiplicación (me refiero a poner los números uno debajo del otro y empezar con las unidades, y pasar las decenas que sobren a la segunda columna, etc.) para calcular una suma o una multiplicación. Son sólo una forma de disponer los cálculos en dos dimensiones que es más "visual" que razonar en una dimensión.

Cuando decís "la tabla de verdad demuestra", ¿realmente "demuestra"?
¿Este uso de la tabla de verdad es parte de los cálculos usuales de la metamatemática, o es sólo un recurso informal?

No entiendo qué estás haciendo exactamente con eso ahí.

Creo que lo que acabo de decir responde a eso. Creo que es como si preguntas si el disponer los números así:

\( \begin{array}{ccc}
1&2&4\\
3&2&5\\
\hline
4&4&9
\end{array} \)

es formal o informal, o si demuestra que \( 124+325=449 \). Teóricamente la demostración sería:

\( 124+325=10^2+2\cdot 10+4+3\cdot 10^2+2\cdot 10+5 = 4\cdot 10^2+4\cdot 10+5 = 449 \)

¿Es equivalente? ¿Las dos formas son legales? ¿Las dos formas son formales? Ciertamente, trabajar en dos dimensiones rompe todos los esquemas teóricos sobre lo que es un lenguaje formal, pero ¿eso no da igual?

27 Diciembre, 2011, 01:21 am
Respuesta #8

argentinator

  • Consultar la FIRMAPEDIA
  • Administrador
  • Mensajes: 7,723
  • País: ar
  • Karma: +0/-0
  • Sexo: Masculino
  • Vean mis posts activos en mi página personal
    • Mis posts activos (click aquí)
Es que no me refiero a la "verticalidad" de las tablas de verdad,
sino al uso de las reglas del álgebra de Boole 2-valuada que ya está implícito en las tablas de verdad.

Me parece que el problema es que todavía tengo "pegada" la idea de que si estoy usando tablas de verdad, necesariamente tengo que tener una lógica proposicional en alguna parte.

Pero quitando ese prejuicio de la mente pareciera que todo marcha.

___________

En resumen, a ver si entiendo la cuestión:

* En lógica de 1er orden se hacen asignaciones de valores de verdad en cada modelo M, acorde a diversas situaciones.

* Cuando se tiene una fórmula expresada sólo con conectores básicos entre subfórmulas, sin cuantificadores, uno puede estudiar una tal fórmula en forma genérica, asignando valores de verdad tal como vos hiciste, para un modelo M arbitrario, una interpretación cualquiera, y eso nos lleva a usar tablas de verdad, cuyos valores se calculan como de costumbre.

* De ahí se deduce la validez en todo modelo, y por completitud, se deduce la demostrabilidad de la fórmula.


27 Diciembre, 2011, 01:30 am
Respuesta #9

Carlos Ivorra

  • Administrador
  • Mensajes: 11,059
  • País: es
  • Karma: +0/-0
  • Sexo: Masculino
    • Página web personal
En resumen, a ver si entiendo la cuestión:

* En lógica de 1er orden se hacen asignaciones de valores de verdad en cada modelo M, acorde a diversas situaciones.

* Cuando se tiene una fórmula expresada sólo con conectores básicos entre subfórmulas, sin cuantificadores, uno puede estudiar una tal fórmula en forma genérica, asignando valores de verdad tal como vos hiciste, para un modelo M arbitrario, una interpretación cualquiera, y eso nos lleva a usar tablas de verdad, cuyos valores se calculan como de costumbre.

* De ahí se deduce la validez en todo modelo, y por completitud, se deduce la demostrabilidad de la fórmula.

Exacto. El único matiz es que las subórmulas (A y B en el ejemplo) podrían perfectamente tener cuantificadores. Lo importante es que haya un "esqueleto exterior" sin cuantificadores.