Un'inferenza logica: $\frac{\begin{matrix} p\implies q \\ q\implies r \end{matrix}}{\therefore p\implies r} $ senza usare tabelle di verità

Aug 18 2020

Dimostrare la validità della seguente inferenza (NON utilizzare tabelle di verità):

$$\frac{\begin{matrix} p\implies q \\ q\implies r \end{matrix}}{\therefore p\implies r} $$ Ho disegnato una tabella di verità che mostra che la proposizione: $((p\implies q) \land (q\implies r)) \implies (p\implies r)$è una tautologia, ma non è riuscito a manipolare le premesse usando regole di inferenza logica per mostrare il risultato.
Per favore, dai qualche consiglio.

Risposte

7 GrahamKemp Aug 19 2020 at 01:51

Usando una notazione leggermente diversa - Calcolo sequenziale - possiamo costruire il seguente albero dimostrativo della deduzione naturale:

$$\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}$$

Quindi concludiamo che l'inferenza è valida: $$\left\lvert\!\begin{split} &p\to q\\&q\to r\\\hline &p\to r\end{split}\right.$$

Le regole usate - dove $\Gamma, \Delta$sono elenchi di dichiarazioni e$\varphi, \psi$ sono singole affermazioni - sono:

$\textsf{ID}$: Identità (o ipotesi) $\qquad\begin{split}~\\\hline\Gamma,\varphi&\vdash\varphi\end{split}$

Banalmente: si può derivare un'affermazione se si presume insieme a un elenco aggiuntivo (possibilmente vuoto) di ipotesi.
${\to}\mathsf E$: Eliminazione condizionale: $\qquad\begin{split}\Gamma&\vdash\varphi\\\Delta&\vdash \varphi\to \psi\\\hline\Gamma\cup\Delta&\vdash \psi\end{split}$

Se un condizionale può essere derivato da un elenco di affermazioni e il suo antecedente può essere derivato da un altro elenco, allora possiamo dedurre che il conseguente può essere derivato dall'unione degli elenchi.
${\to}\mathsf I$: Introduzione condizionale: $\qquad\begin{split}\Gamma,\varphi&\vdash \psi\\\hline\Gamma&\vdash\varphi\to\psi\end{split}$

Se un conseguente può essere derivato da un elenco di affermazioni che include un antecedante, allora possiamo dedurre che il rispettivo condizionale può essere derivato dall'elenco.

Questa inferenza è un esempio di come scaricare un'ipotesi. Alla fine di una dimostrazione, tutte le ipotesi, ad eccezione dei locali, devono essere state adeguatamente scaricate.

Qui abbiamo assunto tre affermazioni, le due premesse con l'aggiunta dell'antecedente della nostra conclusione. Scarichiamo questa terza ipotesi dopo aver fatto con successo la nostra derivazione del conseguente.

6 rain1 Aug 18 2020 at 20:11

Vogliamo provare

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

Introduci p nel contesto:

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

Mettere insieme $p\implies q$ e $p$ dedurre $q$:

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

Mettere insieme $q\implies r$ e $q$ dedurre $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 tautologia $$(p\implies q)\implies((q\implies r)\implies(p\implies r))$$invece e applicare Modus Ponens due volte con le premesse date. In alternativa, usa la tautologia$$\varphi\implies(\psi\implies (\varphi\land\psi))$$ concludere $$\frac{\begin{matrix} \varphi \\ \psi\end{matrix}}{(\varphi\land\psi)} $$ e poi usa la tautologia che hai dato per dimostrare $$\frac{\begin{matrix} p\implies q \\ q\implies r \end{matrix}}{ p\implies r} $$

Per completezza: date le premesse aggiungere la suddetta tautologia concludere

$$\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)}$$

e poi

$$\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}$$

che completa la dimostrazione. Per l'alternativa utilizzare prima la regola data per ottenere

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

e poi usando l'altra tautologia che abbiamo

$$\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

Usa il modus ponens due volte e introduzione delle condizioni:

$p\implies q$ e $p$ si intende $q$ è vero (primo utilizzo). $q\implies r$ e $q$ è vero significa $r$è vero. (secondo utilizzo). Così dato$p \implies q$ e $q\implies r$ quindi per introduzione condizionale $p$ essere vero significa $r$è vero. Così$p\implies r$.

Ok, penso di aver capito:

Se prendiamo la notazione $\phi\vdash \psi$ a significare "dovevamo presumere $\phi$ possiamo derivare $\psi$ poi:

$p\implies q$ (dato)

$p \implies r$ (qiven)

$p\vdash p$ (presumere qualcosa significa presumere qualcosa. $\mu\vdash \mu$ è sempre vero perché se assumiamo $\mu$ possiamo derivare $\mu$... perché supponiamo che sia vero. Questo non vuol dire che stiamo sostenendo che è vero (come le tue affermazioni nel commento sul "rimanere nelle premesse iniziali" implicano che tu creda); questo per dire sotto un ipotetico se fosse vero potremmo derivare. Ovviamente se non è vero, ciò che deriviamo non sarà pertinente.)

$p\vdash p\implies q$ ($p\implies q$ è una data verità se assumiamo $p$o no. Per ogni vera affermazione$T$ poi $\mu\vdash T$sarà sempre vero. E credo$\mu\vdash F$ sarà sempre falso.)