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

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

15 Abril, 2020, 10:09 am
Leído 1472 veces

manooooh

  • Matemático
  • Mensajes: 2,961
  • País: ar
  • Karma: +1/-0
  • Sexo: Masculino
Hola!

Me gustaría saber si el dilema constructivo, enunciado en forma de razonamiento así:

\(
\begin{array}{l}
p\to q\\
r\to s\\
p\vee r\\\hline
q\vee s
\end{array}
 \)

se puede demostrar SIN tener que agregar nuevas hipótesis a la demostración, como sugiere este enlace: https://www.umsu.de/trees/ (al final de la url agregar #p→q,r→s,p∨s|=q∨s).

Pregunta sobre agregar nuevas hipótesis
En realidad nunca entendí cómo lo de agregar nuevas premisas o supuestos hacen que el razonamiento ORIGINAL siga siendo válido. O sea, supongamos que a un razonamiento le agrego \( p\wedge q \) por ser supuesto (no estaba en el razonamiento original). Entonces voy y deduzco la conclusión, pero ¿qué ocurriría si NO se cumple ese supuesto que agregué? Ahí no podría decirse nada acerca de la validez porque quién soy yo para modificar el razonamiento, si puse más hipótesis es mi problema, o sea que en el caso de que NO sea cierto el nuevo supuesto, entonces a la borda todo lo escrito. ¿No? ???
[cerrar]

La demostración que propone:


Entiendo que además supone \( \neg(q\lor s)\equiv\neg q\land\neg s \) (la conclusión pero negada), divide la conjunción, y llega a una contradicción, pero no entiendo cómo deduce el paso 8).

Sin agregar hipótesis, que sería en general lo que cualquier estudiante no avanzado hace, es trabajar con los condicionales:

\(
\begin{array}{lll}
1)&p\to q&\text{Premisa}\\
2)&r\to s&\text{Premisa}\\
3)&p\vee r&\text{Premisa}\\
4)&\neg p\lor q&\text{Equivalencia implicador 1)}\\
5)&\neg r\lor s&\text{Equivalencia implicador 2)}\\
\end{array}
 \)

y a partir de la deducción 5) ya no puedo avanzar por ningún lado. Conozco que \( A\lor B,\;\neg A\therefore B \) por si sirve de algo.

¿Podría hacerse sin agregar supuestos?



Otra pregunta:

En el libro que sigo no se hizo mención a esta regla de inferencia, pero cuando hice la asignatura el profesor sí la escribió. ¿Podría decirse que el libro está incompleto, o puede decirse que el dilema constructivo se deduce de otra regla de inferencia más general?

Gracias!!
Saludos y #QuedateEnTuCasa

15 Abril, 2020, 11:19 am
Respuesta #1

geómetracat

  • Moderador Global
  • Mensajes: 1,667
  • País: es
  • Karma: +0/-0
  • Sexo: Masculino
No entiendo a qué te refieres con agregar nuevas hipótesis. La demostración que pones es una demostración con un tableau semántico, y hasta donde yo sé es la manera óptima de hacerlo con tableaux, pero no veo que se agregue ninguna hipótesis en ningún sitio.  ???

Sobre lo otro, no sé muy bien qué estás buscando. Una demostración, ¿en qué cálculo deductivo? ¿Deducción natural, cálculo tipo Hilbert, ...?
No sé, clarifica mejor el problema que le ves a la demostración que das y a qué te refieres exactamente con "sin tener que agregar nuevas hipótesis" y lo hablamos.
La ecuación más bonita de las matemáticas: \( d^2=0 \)

15 Abril, 2020, 08:19 pm
Respuesta #2

manooooh

  • Matemático
  • Mensajes: 2,961
  • País: ar
  • Karma: +1/-0
  • Sexo: Masculino
Hola, muchas gracias por responder

Con agregar nueva hipótesis me refiero concretamente a la línea 4. Esa línea no forma parte de ninguna línea de nuestro razonamiento original, así que agregaron una nueva premisa.

Y de ahí mi pregunta de por qué es válido agregar una nueva línea que NO se deduce de ninguna de las anteriores si perfectamente esa nueva premisa podría no cumplirse.

Con respecto a la demostración, me gustaría demostrarlo siguiendo el método usado aquí: http://rinconmatematico.com/foros/index.php?topic=109773.msg433850#msg433850

Saludos

15 Abril, 2020, 10:14 pm
Respuesta #3

geómetracat

  • Moderador Global
  • Mensajes: 1,667
  • País: es
  • Karma: +0/-0
  • Sexo: Masculino
La línea 4 no es ninguna nueva premisa. La línea 4 es la negación de la conclusión que quieres demostrar. Así es como funciona el método de los tableaux semánticos: empiezas con las premisas y la negación de la conclusión y vas aplicando reglas hasta que llegas a una contradicción en todas las ramas.

Al margen de esto, añadir una nueva premisa es inválido, claro. Pero insisto que no es lo que pasa aquí, es simplemente cómo funciona el método de los tableaux.


Mañana si puedo pongo una demostración en la línea del otro hilo, con deducción natural. Pero la idea es sencilla: si supones \( p \) usando 1 obtienes \( q \), luego también \( q \vee s \). Si supones \( r \), usando 2 obtienes \( s \) y por tanto también \( q \vee s \). Ahora usas esto junto con 3 y la regla de eliminación de la disyunción te da \( q \vee s \).
La ecuación más bonita de las matemáticas: \( d^2=0 \)

15 Abril, 2020, 11:47 pm
Respuesta #4

manooooh

  • Matemático
  • Mensajes: 2,961
  • País: ar
  • Karma: +1/-0
  • Sexo: Masculino
Hola geómetracat

La línea 4 no es ninguna nueva premisa. La línea 4 es la negación de la conclusión que quieres demostrar. Así es como funciona el método de los tableaux semánticos: empiezas con las premisas y la negación de la conclusión y vas aplicando reglas hasta que llegas a una contradicción en todas las ramas.

Ahhh. No sé por qué di por hecho que esa página trataba más o menos con el método que suelo usar y que les muestro en el foro. Gracias por explicarlo.

No entiendo cómo no existe contradicción entre estas dos frases:

Al margen de esto, añadir una nueva premisa es inválido, claro. (...)

(...) Pero la idea es sencilla: si supones \( p \) (...)

Ahí parece que en la demostración es lícito agregar como hipótesis/premisa/suposición (ponle el nombre que quieras) la proposición \( p \), pero eso contradice el hecho de que es ilegal agregar nuevas hipótesis. ¿De qué me estoy perdiendo?

De hecho he revisado un poco hilos anteriores y aquí vuelves a decir que, según entiendo, "añadir una nueva premisa es inválido":

En este caso en nada. Trataba de darle una explicación al hecho de que hayas metido una suposición "por la cara" (en sistemas de deducción natural puedes hacerlo, pero después debes descartarla usando la regla de introducción del implicador). Mejor olvida todo esto y quédate con que no puedes introducir suposiciones arbitrarias.

Espero hasta mañana.

Saludos

16 Abril, 2020, 11:24 pm
Respuesta #5

geómetracat

  • Moderador Global
  • Mensajes: 1,667
  • País: es
  • Karma: +0/-0
  • Sexo: Masculino
Ah, sí, puedes añadir hipótesis pero después descartarlas (con la regla de eliminación de la disyunción en este caso). Esto lo puedes hacer en deducción natural. Lo importante es que al final de la demostración no hayan quedado hipótesis nuevas sin descartar. Sin eso, no puedes demostrar algunas cosas en deducción natural.

Hay que distinguir entre añadir premisas extra para demostrar lo que sea, que es inválido, de usar hipótesis "temporalmente", que luego descartas, en deducción natural, que es perfetctamente legítimo.
La ecuación más bonita de las matemáticas: \( d^2=0 \)

17 Abril, 2020, 05:57 pm
Respuesta #6

manooooh

  • Matemático
  • Mensajes: 2,961
  • País: ar
  • Karma: +1/-0
  • Sexo: Masculino
Hola

Ahora voy entendiendo. Es válido agregar hipótesis si y sólo si luego las descartamos, usando la introducción del implicador, pero no me queda muy en claro cómo se usa esta regla de inferencia. ¿Podrías poner un ejemplo? Quizás el del asunto de este mensaje valga.

También creo que lo que pretendes hacer en el caso de agregar nuevas hipótesis es hacerlo pero dentro de una "subproof", de modo tal que esta subproof acabe cuando descartamos todas las hipótesis nuevas que pusimos, de vuelta necesitaría ver este ejercicio usando esto.

Por último, comentar que esto de suponer nuevas hipótesis no es lo que se ve en los cursos de mi universidad, tenía entendido que se debía deducir las reglas de inferencia vistas, que son únicamente:

Modus Ponens y Tollens, silogismos hipotéticos y disyuntivos, y la ley de combinación.

Saludos

17 Abril, 2020, 08:04 pm
Respuesta #7

geómetracat

  • Moderador Global
  • Mensajes: 1,667
  • País: es
  • Karma: +0/-0
  • Sexo: Masculino
Ahora voy entendiendo. Es válido agregar hipótesis si y sólo si luego las descartamos, usando la introducción del implicador, pero no me queda muy en claro cómo se usa esta regla de inferencia. ¿Podrías poner un ejemplo? Quizás el del asunto de este mensaje valga.

También creo que lo que pretendes hacer en el caso de agregar nuevas hipótesis es hacerlo pero dentro de una "subproof", de modo tal que esta subproof acabe cuando descartamos todas las hipótesis nuevas que pusimos, de vuelta necesitaría ver este ejercicio usando esto.

Bueno, primero hay que aclarar una cosa importante. Hay muchos cálculos deductivos posibles para la lógica proposicional (al igual que para la lógica de primer orden), y cada uno tiene sus reglas y/o sus axiomas. Con esto quiero decir que los detalles de las demostraciones dependen de qué cálculo uses, y es importante tener esto claro y usar uno concreto cada vez. Si empiezas a mezclar varios cálculos te harás un lío y no entenderás nada.

Uno de estos cálculos es la deducción natural. En ese caso puedes hacer hipótesis y descartarlas después, etc. Pero en otros cálculos (como los tableaux, o los cálculos tipo Hilbert) no puedes hacer hipótesis nuevas (no hay noción de descartar hipótesis). Por eso, a la hora de hacer demostraciones formales es importante especificar primero bien el cálculo deductivo que vayas a usar.

A mí para estas cosas me gusta usar deducción natural (o tableaux) porque lo encuentro más sencillo. Las deducciones con cálculos tipo Hilbert, por ejemplo, suelen ser tremendamente antiintuitivas.

Te dejo un enlace de la Wikipedia sobre deducción natural:
https://en.m.wikipedia.org/wiki/Natural_deduction
Ahí están todas las reglas. Aunque ahí usan notación de árbol para las demostraciones yo usaré aquí notación lineal.

Una demostración sería entonces:

\( 1. p \to q \text{ (Premisa)} \)
\( 2. r \to s \text{ (Premisa)} \)
\( 3. p \vee r \text{ (Premisa)} \)
\( |4. p \text{ (Hipótesis H1)} \)
\( |5. q \text{ (Eliminación Implicador 1,4)} \)
\( |6. q \vee s \text{ (Introducción disyunción 5)} \)
\( ||7. r \text{ (Hipótesis H2)} \)
\( ||8. s \text{ (Eliminación Implicador 2,8)} \)
\( ||9. q \vee s \text{ (Introducción disyunción 8)} \)
\( 10. q \vee s \text{ (Eliminación disyunción 3,4-6,7-9)} \)

donde el \( | \) marca dónde están activas (no han sido descartadas aún) las hipótesis.
 

Citar
Por último, comentar que esto de suponer nuevas hipótesis no es lo que se ve en los cursos de mi universidad, tenía entendido que se debía deducir las reglas de inferencia vistas, que son únicamente:

Modus Ponens y Tollens, silogismos hipotéticos y disyuntivos, y la ley de combinación.

¿A qué llamas ley de combinación? De todas maneras, con esas reglas no creo que puedas deducir todas las tautologías. ¿No te dieron ningún cálculo deductivo? ¿Te demostraron un teorema de completitud (todas las tautologías se pueden deducir de estas reglas)?

La ecuación más bonita de las matemáticas: \( d^2=0 \)

17 Abril, 2020, 09:42 pm
Respuesta #8

manooooh

  • Matemático
  • Mensajes: 2,961
  • País: ar
  • Karma: +1/-0
  • Sexo: Masculino
Hola

Bueno, primero hay que aclarar una cosa importante. Hay muchos cálculos deductivos posibles para la lógica proposicional (al igual que para la lógica de primer orden), y cada uno tiene sus reglas y/o sus axiomas. Con esto quiero decir que los detalles de las demostraciones dependen de qué cálculo uses, y es importante tener esto claro y usar uno concreto cada vez. Si empiezas a mezclar varios cálculos te harás un lío y no entenderás nada.

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).

¿A qué llamas ley de combinación? De todas maneras, con esas reglas no creo que puedas deducir todas las tautologías. ¿No te dieron ningún cálculo deductivo? ¿Te demostraron un teorema de completitud (todas las tautologías se pueden deducir de estas reglas)?

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

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.

Una demostración sería entonces:

\( 1. p \to q \text{ (Premisa)} \)
\( 2. r \to s \text{ (Premisa)} \)
\( 3. p \vee r \text{ (Premisa)} \)
\( |4. p \text{ (Hipótesis H1)} \)
\( |5. q \text{ (Eliminación Implicador 1,4)} \)
\( |6. q \vee s \text{ (Introducción disyunción 5)} \)
\( ||7. r \text{ (Hipótesis H2)} \)
\( ||8. s \text{ (Eliminación Implicador 2,6)} \)
\( ||9. q \vee s \text{ (Introducción disyunción 8)} \)
\( 10. q \vee s \text{ (Eliminación disyunción 3,4-6,7-9)} \)

donde el \( | \) marca dónde están activas (no han sido descartadas aún) las hipótesis.

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

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?

Gracias y saludos

23 Abril, 2020, 02:46 am
Respuesta #9

manooooh

  • Matemático
  • Mensajes: 2,961
  • País: ar
  • Karma: +1/-0
  • Sexo: Masculino
Hola

Finalmente la demostración sin agregar hipótesis nuevas es:

\(
\begin{array}{lll}
1)&p\to q&\text{Premisa}\\
2)&r\to s&\text{Premisa}\\
3)&p\lor r&\text{Premisa}\\
4)&\neg \neg p\lor r&\text{Involución 3)}\\
5)&\neg p\to r&\text{Equivalencia del condicional 4)}\\
6)&\neg q\to \neg p&\text{Contrarrecíproco 1)}\\
7)&\neg q\to r&\text{Silogismo hipotético 5,6)}\\
8)&\neg q\to s&\text{Silogismo hipotético 2,7)}\\
9)&\neg \neg q\lor s&\text{Equivalencia del condicional 8)}\\
10)&q\lor s&\text{Involución 9)}\\
\end{array}
 \)

Si pueden ayudarme con las preguntas que fueron surgiendo a lo largo de este post agradecido. Muchas gracias!

Saludos

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

geómetracat

  • Moderador Global
  • Mensajes: 1,667
  • 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

  • Matemático
  • Mensajes: 2,961
  • 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,667
  • 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

  • Matemático
  • Mensajes: 2,961
  • 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,667
  • 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

  • Matemático
  • Mensajes: 2,961
  • 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,272
  • 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

  • Matemático
  • Mensajes: 2,961
  • 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,667
  • 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 \)