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 3032 veces

manooooh

  • $$\Large \color{#9c57a6}\pi\,\pi\,\pi\,\pi\,\pi\,\pi$$
  • Mensajes: 3,351
  • 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: 2,344
  • 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

  • $$\Large \color{#9c57a6}\pi\,\pi\,\pi\,\pi\,\pi\,\pi$$
  • Mensajes: 3,351
  • 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: 2,344
  • 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

  • $$\Large \color{#9c57a6}\pi\,\pi\,\pi\,\pi\,\pi\,\pi$$
  • Mensajes: 3,351
  • 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: 2,344
  • 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

  • $$\Large \color{#9c57a6}\pi\,\pi\,\pi\,\pi\,\pi\,\pi$$
  • Mensajes: 3,351
  • 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: 2,344
  • 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

  • $$\Large \color{#9c57a6}\pi\,\pi\,\pi\,\pi\,\pi\,\pi$$
  • Mensajes: 3,351
  • 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

  • $$\Large \color{#9c57a6}\pi\,\pi\,\pi\,\pi\,\pi\,\pi$$
  • Mensajes: 3,351
  • 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