Autor Tema: ¿Probar dilema constructivo solo usando leyes lógicas y reglas de inferencia?

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

23 Abril, 2020, 10:48 am
Respuesta #10

geómetracat

  • Moderador Global
  • Mensajes: 1,891
  • País: es
  • Karma: +0/-0
  • Sexo: Masculino
Ok. Ocurre que no "debería" usar más de un método sino que con uno solo es suficiente para la asignatura. El libro lo ha de llamar "Método demostrativo", y dice (citado textualmente):

MÉTODO DEMOSTRATIVO
Es un método más formal y ordenado, que elabora una lista numerada de proposiciones lógicas con el objetivo de llegar a tener en algún elemento de la lista a la conclusión del razonamiento. Las proposiciones que se pueden incorporar a la lista pueden ser únicamente por tres motivos:
a) Ser premisas.
b) Ser equivalencias lógicas de otras proposiciones anteriores de la lista.
c) Obtenerse a partir de otras proposiciones anteriores de la lista a través de reglas de inferencia.

En cada renglón, debe justificarse a la derecha de dónde provino señalando el o los renglones que se han utilizado.

El objetivo es llegar en algún renglón a obtener la conclusión. Si se llega, significa que el razonamiento es válido.

Las reglas de inferencia son pequeños razonamientos que ya se sabe que son válidos, y sirven para probar la validez de razonamientos mas complejos. Cada una de ellas, tiene un nombre que la identifica y dos siglas (MP, MT, etcétera).

Todo esto está muy bien, pero el problema ahí es que no queda bien especificado con qué reglas de inferencia empiezas. Por ejemplo, antes has dado una lista (MP,MT, silogismos hipotéticos, etc). Pero si no me equivoco únicamente a partir de esa lista es imposible demostrar, por ejemplo, la involución que usas en tu denostración.

Por eso hay que especificar muy bien y completamente el cálculo deductivo que vas a usar, si no tienes todos los números para hacerte un lío. Otro ejemplo: ¿cómo demuestras la equivalencia del condicional (que también usas) únicamente a partir de las reglas que has enunciado? No creo que sea un cálculo completo.

Citar
La LC es que si tenemos \( A \) y tenemos \( B \), entonces tenemos \( A\land B \).

Gracias.

Citar
El cálculo deductivo es el que en la materia se dice "método demostrativo" supongo. En caso contrario pues no, no hemos visto ningún otro cálculo ni el teorema de completitud. Si quieres le pregunto al profesor cómo demostraría el dilema constructivo sin tener que recurrir a nuevas hipótesis temporales.

Le puedes preguntar cómo demuestra que puede demostrar cualquier tautología a partir únicamente de las reglas que mencionaste antes.

Citar
Gracias!! Creo que la línea \( 8 \) debería decir \( s \text{ (Eliminación Implicador 2,7)} \).

En efecto, gracias. Ahora lo corrijo.

Citar
Si el \( | \) indica que las hipótesis no han sido descartadas aun, ¿significa que en la línea \( 10 \) ya han sido descartadas \( \text{H1} \) y \( \text{H2} \)? ¿Cómo lo sabes?

Se descartan con la eliminación de la disyunción. Hay básicamente dos maneras de descartar hipótesis: introducción del implicador (si de una hipótesis \( p \) obtienes \( q \) entonces tienes una prueba de \( p \to q \) sin hipótesis) y eliminación de la disyunción (si tienes \( p\vee q \), a partir de la hipótesis \( p \) puedes probar \( r \) y a partir de la hipótesis \( q \) puedes probar \( r \), entonces tienes una prueba de \( r \) sin hipótesis).
La ecuación más bonita de las matemáticas: \( d^2=0 \)

25 Abril, 2020, 08:35 pm
Respuesta #11

manooooh

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

En cuanto a la demostración de razonamientos, el libro propone 3 métodos:

1) Directo.
2) Condicional asociado.
3) Demostrativo. (Ya visto.)


Obviamente si demostramos que un razonamiento es válido por algún camino, también deberíamos poder demostrar por otro camino.

1) Partiendo de la verdad de las premisas, se va trabajando con ellas hasta llegar a la conclusión.

Ejemplo: \( p\lor v,v\to m,\neg m\therefore p \). Solamente analizaremos los casos en que todas las premisas son verdaderas:

Como \( v(\neg m)=\mathrm{V} \) por ser premisa entonces \( v(m)=\mathrm{F} \).
Luego, como \( v(v\to m)=\mathrm{V} \) por ser premisa, entonces \( v(v)=\mathrm{F} \).
Por último, como \( v(p\lor v)=\mathrm{V} \) por ser premisa, pero \( v(v)=\mathrm{F} \) entonces debe ser \( v(p)=\mathrm{V} \).
Y esta es la conclusión que resulta ser necesariamente verdadera.



2) Consiste en armar un condicional cuyo antecedente es la conjunción de todas las premisas, y su consecuente es la conclusión. Luego debe demostrarse que dicho condicional es verdadero. Si lo es, el razonamiento será válido.

Para el mismo caso del ejemplo anterior, el condicional asociado es \( [(p\lor v)\land(v\to m)\land(\neg m)]\to p \).

¿Cómo demostramos que dicho condicional es verdadero siempre?

Para probar que es verdadero, podemos hacer la tabla de verdad y verificar que sea una tautología, o sea que todos los renglones sean verdaderos.

Si queremos hacerlo por un camino más rápido, podemos tratar de encontrar algún renglón que sea falso (si ello ocurriera el razonamiento sería inválido). Si resultara imposible hallar un renglón falso, quedará garantizada la validez del razonamiento.

Intentemos ver si es posible que el condicional sea falso . La única posibilidad es que simultáneamente las premisas sean verdaderas y la conclusión falsa. Suponiendo \( p \) falsa, entonces de \( p\lor v \), \( v \) debe ser verdadera. Del hecho que \( v\to m \) es verdadera por premisa, resulta que \( m \) es verdadera. Pero por otro lado, la premisa \( \neg m \) es verdadera, de donde \( m \) es falsa.

Vemos que existe una contradicción, es imposible que \( m \) sea verdadera y falsa a la vez. Esto nos indica que nunca el condicional puede ser falso. Por lo tanto el razonamiento es válido.



3) Con el mismo ejemplo:

\(
\begin{array}{lll}
1)&p\lor v&\text{Premisa}\\
2)&v\to m&\text{Premisa}\\
3)&\neg m&\text{Premisa}\\
4)&\neg v&\text{Modus Tollens 2,3)}\\
4)&p&\text{Silogismo disyuntivo 1,4)}\\
\end{array}
 \)



Por lo tanto, geómetracat, por ejemplo para demostrar que el razonamiento \( \neg(\neg p)\therefore p \) es siempre válido, construimos la tabla de verdad del condicional asociado:

\(
\begin{array}{c|c|c|c}
p&\neg p&\neg(\neg p)&\neg(\neg p)\to p\\\hline
\mathrm{V}&\mathrm{F}&\mathrm{V}&\mathrm{V}\\
\mathrm{F}&\mathrm{V}&\mathrm{F}&\mathrm{V}\\
\end{array}
 \)

Como todos los 2 renglones son verdaderos, entonces el razonamiento es válido. Si hubiésemos encontrado uno que era falso, entonces el razonamiento era inválido.

NOTA IMPORTANTE: Los métodos 1 y 2 NO funcionan cuando el razonamiento HABLA en general (o sea cuando usamos CUANTIFICADORES). En ese caso el único método válido es el demostrativo.



geómetracat, esto es lo que explicamos a los alumnos. Me había olvidado de mencionar los primeros 2 "métodos". ¿Ahora sí consideras que es un cálculo completo? Gracias!

Se descartan con la eliminación de la disyunción. Hay básicamente dos maneras de descartar hipótesis: introducción del implicador (si de una hipótesis \( p \) obtienes \( q \) entonces tienes una prueba de \( p \to q \) sin hipótesis) y eliminación de la disyunción (si tienes \( p\vee q \), a partir de la hipótesis \( p \) puedes probar \( r \) y a partir de la hipótesis \( q \) puedes probar \( r \), entonces tienes una prueba de \( r \) sin hipótesis).

Ocurre que no llego a entender bien cómo funciona. ¿Cómo es eso de la eliminación de la disyunción y la introducción del implicador? Creo que eso no lo hemos usado en ninguno de los 3 métodos, te agradecería que me corrijas y puedas decirme si con esos 3 métodos son suficientes para explicar a los alumnos un cálculo completo. Ya que es así cómo el profesor lo explica.

Saludos

25 Abril, 2020, 09:22 pm
Respuesta #12

geómetracat

  • Moderador Global
  • Mensajes: 1,891
  • País: es
  • Karma: +0/-0
  • Sexo: Masculino
Los dos primeros "métodos" que explicas son completos, aunque son más bien semánticos (fíjate que hablas de valuaciones y de tablas de verdad). Con esos no tengo ningún problema.

Mi problema es con el tercer método, o más bien con la especificación del método. Imagínate que tuvieras que programarlo en un ordenador, así que debes dar una especificación completa. Puedes decir que una demostración es una sucesión de fórmulas donde cada una es una premisa o se sigue usando una regla de inferencia. Así tienes un cálculo tipo Hilbert.

Ahora bien, el problema es: ¿qué reglas de inferencia están permitidas usar? Antes me dijiste que Modus Ponens, Modus Tollens, silogismos hipotéticos, silogismos disyuntivos y ley de combinación.
Pero yo diría que únicamente con esto no vas a poder demostrar cualquier inferencia verdadera. Por ejemplo, ¿cómo demostrarías la ley de involución a partir únicamente de esas reglas?

Y por otro lado, falta algún axioma o premisa, de otra forma nunca podrás realizar inferencias sin premisas (demostrar tautologías). Por ejemplo, ¿cómo vas a demostrar la fórmula \( p \to p \), que es una tautología?

En definitiva, me parece bien la descripción general del método deductivio que dan ahí, pero la especificación concreta es un tanto vaga. Para especificar un cálculo deductivo necesitas especificarlo con mucha precisión (imagina que fueras a programarlo), y con lo que pones no queda claro.

Sobre lo último: usaba un cálculo deductivo concreto, llamado "deducción natural", que está especificado en el enlace de la Wikipedia que puse y que es muy conocido y usado (recuerdo haberlo usado en otros hilos contigo).

Pero si quieres usar el método del libro puedes olvidarte de él. De hecho, es mejor no mezclar cálculos deductivos (como los tableaux del principio, que son otro cálculo distinto) para no hacerse un lío.
La ecuación más bonita de las matemáticas: \( d^2=0 \)

28 Abril, 2020, 07:32 pm
Respuesta #13

manooooh

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

Los dos primeros "métodos" que explicas son completos, aunque son más bien semánticos (fíjate que hablas de valuaciones y de tablas de verdad). Con esos no tengo ningún problema.

Muchas gracias por esto.

Ahora bien, el problema es: ¿qué reglas de inferencia están permitidas usar? Antes me dijiste que Modus Ponens, Modus Tollens, silogismos hipotéticos, silogismos disyuntivos y ley de combinación.

De acuerdo.

Pero yo diría que únicamente con esto no vas a poder demostrar cualquier inferencia verdadera. Por ejemplo, ¿cómo demostrarías la ley de involución a partir únicamente de esas reglas?

Y por otro lado, falta algún axioma o premisa, de otra forma nunca podrás realizar inferencias sin premisas (demostrar tautologías). Por ejemplo, ¿cómo vas a demostrar la fórmula \( p \to p \), que es una tautología?

Le acabo de preguntar al profesor y me dijo que para demostrar \( p\therefore p \) (su condicional asociado es \( p\to p \)) por el 3er método es muy sencillo:

\(
\begin{array}{lll}
1)&p&\text{Premisa}
\end{array}
 \)

Y ya! Porque llegamos a la conclusión que era \( p \).

Para demostrar la ley involutiva nos valemos del cálculo proposicional, en particular la propiedad ya demostrada (ley lógica) \( \neg(\neg p)\equiv p \):

\(
\begin{array}{lll}
1)&\neg(\neg p)&\text{Premisa}\\
2)&p&\text{Involución 1)}
\end{array}
 \)

y ya llegamos a la conclusión.

En cuanto a la programación, supongo que el punto de corte para demostrar la validez del razonamiento es que ocurra una de estas 3 cosas:

a) Ser premisas.
b) Ser equivalencias lógicas de otras proposiciones anteriores de la lista. (Aquí entran muchas, por ejemplo la involución.)
c) Obtenerse a partir de otras proposiciones anteriores de la lista a través de reglas de inferencia.

unidas mediante disyunciones inclusivas ||, Or o como se llame en el lenguaje.

¿Ahora sí ves un método programable computacionalmente? Recuerda que por este método nos valemos de las 3 herramientas.

Gracias por la paciencia.

Saludos

28 Abril, 2020, 09:52 pm
Respuesta #14

geómetracat

  • Moderador Global
  • Mensajes: 1,891
  • País: es
  • Karma: +0/-0
  • Sexo: Masculino
Pero lo que haces es "trampa". Por ejemplo, en tu denostración de \( p \to p \), no estás realmente demostrando \( p \to p \) sin premisas, estás demostrando que de la premisa \( p \) se deduce \( p \), que es diferente. Es decir, yo te pido que demuestres \( \vdash p \to p \) y tú me demuestras \( p \vdash p \).
Es decir, si decimos que una demostración de una proposición es una lista de premisas y proposiciones que se deducen de las anteriores a partir de reglas, que acaba en la proposición que queremos demostrar, esta definición no se cumple en tu demostración por dos motivos: 1) usas una premisa que no teníamos (yo te pedía probar \( p \to p \) sin premisas) y 2) la última proposición de la lista no es \( p \to p \).
Podrías pasar de una a otra usando el teorema de deducción (que dice que \( \Gamma, p \vdash q \) si y solo si \( \Gamma \vdash p \to q \)), pero no lo has mencionado entre las reglas a usar.

Lo mismo pasa con involución. Dices que puedes usar cualquier equivalencia lógica. Pero si es así, las demostraciones son inútiles. El único sentido de tener un cálculo deductivo es tener un número fijo (idealmente pequeño) de axiomas y reglas que te permita demostrar cualquier inferencia verdadera. Si ya de entrada puedes usar cualquier equivalencia (hay infinitas) esto no tiene mucho sentido. Es decir, para que esto sea una noción de demostración útil debes restringir las reglas de inferencia o equivalencias lógicas que puedes usar, de manera que solos ea demostrable a partir de las reglas que especificas a priori. Si no, cuando me enfrente a cualquier demostración siempre podré decir "ah, es que me olvidé de esta regla" y eso es trampa.

De nuevo, piensa en que tuvieras que especificar la noción de demostración a un ordenador: no le puedes especificar un número infinito de reglas (todas las equivalencias lógicas).
La ecuación más bonita de las matemáticas: \( d^2=0 \)

28 Abril, 2020, 10:19 pm
Respuesta #15

manooooh

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

Pero lo que haces es "trampa". Por ejemplo, en tu denostración de \( p \to p \), no estás realmente demostrando \( p \to p \) sin premisas, estás demostrando que de la premisa \( p \) se deduce \( p \), que es diferente. Es decir, yo te pido que demuestres \( \vdash p \to p \) y tú me demuestras \( p \vdash p \).

Es que la definición de razonamiento incluye la noción de premisas y conclusión:

Razonamiento (definicón) Es un conjunto de proposiciones en el cual una de ellas, llamada CONCLUSIÓN, se afirma sobre la base de las demás llamadas PREMISAS.

Si no hay premisas no hay razonamiento (en nuestra asignatura). Quizás por eso no encaje lo que dices.

Es decir, si decimos que una demostración de una proposición es una lista de premisas y proposiciones que se deducen de las anteriores a partir de reglas, que acaba en la proposición que queremos demostrar, esta definición no se cumple en tu demostración por dos motivos: 1) usas una premisa que no teníamos (yo te pedía probar \( p \to p \) sin premisas) y 2) la última proposición de la lista no es \( p \to p \).
Podrías pasar de una a otra usando el teorema de deducción (que dice que \( \Gamma, p \vdash q \) si y solo si \( \Gamma \vdash p \to q \)), pero no lo has mencionado entre las reglas a usar.

Pero ésto: \( p\to p \) es una proposición que está dada en forma de condicional. Un razonamiento consta de premisas y conclusión. ¿Dónde hay una premisa ahí? Pues la intenté "buscar" sabiendo que se traduce en \( p\therefore p \), pero si tú dices que no es equivalente pues entonces ésto: \( p\to p \) no será un razonamiento sino una proposición sin más.

(...) Dices que puedes usar cualquier equivalencia lógica. Pero si es así, las demostraciones son inútiles. (...)

Quizás me expresé mal, perdón. No me refería a "cualquier equivalencia lógica" sino a una lista muy precisa de 14 leyes. Las listo sin escribirlas porque llevaría tiempo:

Las 14 leyes lógicas
  • Involución.
  • Conmutatividad.
  • Asociatividad.
  • Distributividad.
  • Idempotencia.
  • De Morgan.
  • Absorción.
  • Identidad.
  • Dominación.
  • Bicondicional.
  • Condicional.
  • Tercero excluido.
  • Simplificación.
  • Adición
[cerrar]

El único sentido de tener un cálculo deductivo es tener un número fijo (idealmente pequeño) de axiomas y reglas que te permita demostrar cualquier inferencia verdadera. Si ya de entrada puedes usar cualquier equivalencia (hay infinitas) esto no tiene mucho sentido. Es decir, para que esto sea una noción de demostración útil debes restringir las reglas de inferencia o equivalencias lógicas que puedes usar, de manera que solos ea demostrable a partir de las reglas que especificas a priori. Si no, cuando me enfrente a cualquier demostración siempre podré decir "ah, es que me olvidé de esta regla" y eso es trampa.

De nuevo, piensa en que tuvieras que especificar la noción de demostración a un ordenador: no le puedes especificar un número infinito de reglas (todas las equivalencias lógicas).

Es cierto, por eso la lista de leyes lógicas que usamos es finita (el resto debe deducirse de ellas).

Saludos

29 Abril, 2020, 01:15 am
Respuesta #16

argentinator

  • Consultar la FIRMAPEDIA
  • Administrador
  • Mensajes: 7,274
  • País: ar
  • Karma: +0/-0
  • Sexo: Masculino
  • Vean mis posts activos en mi página personal
    • Mis posts activos (click aquí)
En efecto \(p\to p\) no es un razonamiento.
Es una proposición.

Usando terminología informática,
una proposición es una "string" (cadena de símbolos o caracteres),
mientras un razonamiento es un "algoritmo" que transforma una lista de "strings" (que llamaríamos premisas) en otra "string" (la conclusión).

Código: [Seleccionar]
string mi_razonamiento(string premisa_list[])
{
    string conclusion = "?";
    // Paso 1
    // Paso 2
    ...
    // Paso N (conclusión finalmente obtenida)

    return conclusion;
}

29 Abril, 2020, 02:50 am
Respuesta #17

manooooh

  • $$\Large \color{red}\pi\,\pi\,\pi\,\pi\,\pi\,\pi\,\pi$$
  • Mensajes: 3,050
  • País: ar
  • Karma: +1/-0
  • Sexo: Masculino
Hola argentinator

En efecto \(p\to p\) no es un razonamiento.
Es una proposición.

Gracias por la confirmación. Lo necesitaba.

Usando terminología informática,
una proposición es una "string" (cadena de símbolos o caracteres),
mientras un razonamiento es un "algoritmo" que transforma una lista de "strings" (que llamaríamos premisas) en otra "string" (la conclusión).

Código: [Seleccionar]
string mi_razonamiento(string premisa_list[])
{
    string conclusion = "?";
    // Paso 1
    // Paso 2
    ...
    // Paso N (conclusión finalmente obtenida)

    return conclusion;
}

Claro, es muy efectivo lo que proponés.

Me pregunto cómo se trataría en el programa un razonamiento que hable en general -- que use cuantificadores. Y más si el conjunto universal es un conjunto infinito (los naturales por ejemplo). Quizás las reglas sean las mismas una vez eliminados los cuantificadores.

De todas maneras en la página que linkeé al principio (https://www.umsu.de/trees/) tiene el source code en GitHub. Y creo que más o menos va en sintonía de lo que escribiste.

Saludos

29 Abril, 2020, 08:43 am
Respuesta #18

geómetracat

  • Moderador Global
  • Mensajes: 1,891
  • País: es
  • Karma: +0/-0
  • Sexo: Masculino
Que \( p \to p \) es una proposición nadie lo discute. La pregunta es si \( \vdash p \to p \) es un razonamiento. Esto ya es una discusión lingüística sobre si un "razonamiento sin premisas" es un razonamiento o no. Pero en cualquier caso, todos los cálculos deductivos que se usan en lógica matemática son capaces de demostrar estos "razonamientos sin premisas". De hecho, las proposiciones que se pueden demostrar sin premisas son exactamente las tautologías.

manooooh, ahora que has especificado las leyes lógicas que usas, eso ya es otra cosa. Pero podrías haberlo dicho desde el principio.  ;)
Ahí tienes básicamente los axiomas de un álgebra de Boole, de manera que probablemente puedas demostrar cualquier razonamiento verdadero usando eso.l
La ecuación más bonita de las matemáticas: \( d^2=0 \)