Una inferencia lógica: $\frac{\begin{matrix} p\implies q \\ q\implies r \end{matrix}}{\therefore p\implies r} $ sin usar tablas de verdad

Aug 18 2020

Demuestre la validez de la siguiente inferencia (NO use tablas de verdad):

$$\frac{\begin{matrix} p\implies q \\ q\implies r \end{matrix}}{\therefore p\implies r} $$ Dibujé una tabla de verdad que muestra que la proposición: $((p\implies q) \land (q\implies r)) \implies (p\implies r)$es una tautología, pero no logró manipular las premisas utilizando reglas de inferencia lógica para mostrar el resultado.
Por favor, dé algunos consejos.

Respuestas

7 GrahamKemp Aug 19 2020 at 01:51

Usando una notación ligeramente diferente (cálculo secuencial), podemos construir el siguiente árbol de prueba de deducción natural:

$$\dfrac{\dfrac{\dfrac{\dfrac{}{p\vdash p}{\tiny\textsf{ID}}~\dfrac{}{p\to q\vdash p\to q}{\tiny\textsf{ID}}}{p,p\to q\vdash q}{\tiny{\to}\mathsf E}~\dfrac{}{q\to r\vdash q\to r}{\tiny\textsf{ID}}}{p,p\to q,q\to r\vdash r}{\tiny{\to}\mathsf E}}{p\to q,q\to r\vdash p\to r}{\tiny{\to}\mathsf I}$$

Así concluimos que la inferencia es válida: $$\left\lvert\!\begin{split} &p\to q\\&q\to r\\\hline &p\to r\end{split}\right.$$

Las reglas utilizadas, donde $\Gamma, \Delta$son listas de declaraciones, y$\varphi, \psi$ son declaraciones únicas, son:

$\textsf{ID}$: Identidad (o suposición) $\qquad\begin{split}~\\\hline\Gamma,\varphi&\vdash\varphi\end{split}$

Trivialmente: puede derivar una declaración si se asume junto con una lista adicional (posiblemente vacía) de suposiciones.
${\to}\mathsf E$: Eliminación condicional: $\qquad\begin{split}\Gamma&\vdash\varphi\\\Delta&\vdash \varphi\to \psi\\\hline\Gamma\cup\Delta&\vdash \psi\end{split}$

Si un condicional puede derivarse de una lista de enunciados, y su antecedente puede derivarse de otra lista, entonces podemos inferir que el consecuente puede derivarse de la unión de las listas.
${\to}\mathsf I$: Introducción condicional: $\qquad\begin{split}\Gamma,\varphi&\vdash \psi\\\hline\Gamma&\vdash\varphi\to\psi\end{split}$

Si un consecuente puede derivarse de una lista de enunciados que incluyen un antecedente, entonces podemos inferir que el condicional respectivo puede derivarse de la lista.

Esta inferencia es un ejemplo de descartar una suposición. Al final de una prueba, todas las suposiciones, salvo las premisas, deben haberse descargado adecuadamente.

Aquí hemos asumido tres afirmaciones, las dos premisas con la adición del antecedente de nuestra conclusión. Descartamos ese tercer supuesto después de hacer con éxito nuestra derivación del consecuente.

6 rain1 Aug 18 2020 at 20:11

Queremos probar

$$\frac{\begin{matrix} p\implies q \\ q\implies r \end{matrix}}{p\implies r}$$

Introduce p en el contexto:

$$\frac{\begin{matrix} p\implies q \\ q\implies r \\ p \end{matrix}}{r}$$

Juntar $p\implies q$ y $p$ deducir $q$:

$$\frac{\begin{matrix} p\implies q \\ q\implies r \\ p \\ q \end{matrix}}{r}$$

Juntar $q\implies r$ y $q$ deducir $r$:

$$\frac{\begin{matrix} p\implies q \\ q\implies r \\ p \\ q \\ r \end{matrix}}{r}$$

QED

4 mrtaurho Aug 18 2020 at 20:16

Usa la tautología $$(p\implies q)\implies((q\implies r)\implies(p\implies r))$$en su lugar, aplique Modus Ponens dos veces con las premisas dadas. Alternativamente, use la tautología$$\varphi\implies(\psi\implies (\varphi\land\psi))$$ para concluir $$\frac{\begin{matrix} \varphi \\ \psi\end{matrix}}{(\varphi\land\psi)} $$ y luego usa la tautología que diste para probar $$\frac{\begin{matrix} p\implies q \\ q\implies r \end{matrix}}{ p\implies r} $$

En aras de la completitud: dadas las premisas, agregue la tautología anterior concluir

$$\frac{\begin{matrix} p\implies q \\ q\implies r \\ (p\implies q)\implies((q\implies r)\implies(p\implies r)) \end{matrix}}{(q\implies r)\implies(p\implies r)}$$

y entonces

$$\frac{\begin{matrix} p\implies q \\ q\implies r \\ (p\implies q)\implies((q\implies r)\implies(p\implies r))\\ (q\implies r)\implies(p\implies r) \end{matrix}}{p\implies r}$$

que completa la prueba. Para la alternativa, primero use la regla dada para obtener

$$\frac{\begin{matrix} p\implies q \\ q\implies r \end{matrix}}{( p\implies q)\land(q\implies r)}$$

y luego, utilizando la otra tautología, tenemos

$$\frac{\begin{matrix} p\implies q \\ q\implies r \\( p\implies q)\land(q\implies r)\\ (( p\implies q)\land(q\implies r))\implies (p\implies r) \end{matrix}}{p\implies r}$$

2 fleablood Aug 18 2020 at 20:40

Utilice modus ponens dos veces e introducción de la condición:

$p\implies q$ y $p$ medio $q$ es cierto (primer uso). $q\implies r$ y $q$ es verdadero significa $r$es verdad. (segundo uso). Tan dado$p \implies q$ y $q\implies r$ luego por introducción condicional $p$ ser verdadero significa $r$es verdad. Entonces$p\implies r$.

Está bien, creo que lo tengo:

Si tomamos la notación $\phi\vdash \psi$ que significa "si asumiéramos $\phi$ podemos derivar $\psi$ luego:

$p\implies q$ (dado)

$p \implies r$ (qiven)

$p\vdash p$ (asumir algo es asumir algo. $\mu\vdash \mu$ siempre es cierto porque si asumimos $\mu$ podemos derivar $\mu$... porque asumimos que es verdad. Esto no quiere decir que estemos afirmando que es cierto (ya que sus afirmaciones en el comentario sobre "permanecer en las premisas iniciales" implican que usted cree); es decir bajo un hipotético si fuera cierto podríamos derivar. Por supuesto, si no es cierto, lo que obtenemos no será relevante).

$p\vdash p\implies q$ ($p\implies q$ es una verdad dada si asumimos $p$o no. Por cada declaración verdadera$T$ luego $\mu\vdash T$siempre será verdad. Y supongo$\mu\vdash F$ siempre será falso.)