Une déduction logique: $\frac{\begin{matrix} p\implies q \\ q\implies r \end{matrix}}{\therefore p\implies r} $ sans utiliser les tables de vérité

Aug 18 2020

Prouvez la validité de l'inférence suivante (NE PAS utiliser de tables de vérité):

$$\frac{\begin{matrix} p\implies q \\ q\implies r \end{matrix}}{\therefore p\implies r} $$ J'ai dessiné une table de vérité qui montre que la proposition: $((p\implies q) \land (q\implies r)) \implies (p\implies r)$est une tautologie, mais n'a pas réussi à manipuler les locaux en utilisant des règles d'inférence logique pour afficher le résultat.
Veuillez donner quelques conseils.

Réponses

7 GrahamKemp Aug 19 2020 at 01:51

En utilisant une notation légèrement différente (Sequent Calculus), nous pouvons construire l'arbre de preuve de déduction naturelle suivant:

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


Ainsi, nous concluons que l'inférence est valide: $$\left\lvert\!\begin{split} &p\to q\\&q\to r\\\hline &p\to r\end{split}\right.$$


Les règles utilisées - où $\Gamma, \Delta$sont des listes de déclarations, et$\varphi, \psi$ sont des instructions uniques - sont:

  • $\textsf{ID}$: Identité (ou hypothèse) $\qquad\begin{split}~\\\hline\Gamma,\varphi&\vdash\varphi\end{split}$

    Trivically: vous pouvez dériver une déclaration si elle est supposée avec une liste supplémentaire (éventuellement vide) d'hypothèses.

  • ${\to}\mathsf E$: Élimination conditionnelle: $\qquad\begin{split}\Gamma&\vdash\varphi\\\Delta&\vdash \varphi\to \psi\\\hline\Gamma\cup\Delta&\vdash \psi\end{split}$

    Si un conditionnel peut être dérivé d'une liste d'énoncés et que son antécédent peut être dérivé d'une autre liste, alors nous pouvons en déduire que le conséquent peut être dérivé de l'union des listes.

  • ${\to}\mathsf I$: Introduction conditionnelle: $\qquad\begin{split}\Gamma,\varphi&\vdash \psi\\\hline\Gamma&\vdash\varphi\to\psi\end{split}$

    Si un conséquent peut être dérivé d'une liste d'énoncés comprenant un antécédant, alors nous pouvons en déduire que le conditionnel respectif peut être dérivé de la liste.

    Cette inférence est un exemple de décharge d' une hypothèse. À la fin d'une preuve, toutes les hypothèses, à l'exception des locaux, doivent avoir été correctement déchargées.


Ici, nous avons supposé trois déclarations, les deux prémisses avec l'ajout de l'antécédent de notre conclusion. Nous rejetons cette troisième hypothèse après avoir réussi à dériver le conséquent.

6 rain1 Aug 18 2020 at 20:11

Nous voulons prouver

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

Introduisez p dans le contexte:

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

Mettre ensemble $p\implies q$ et $p$ déduire $q$:

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

Mettre ensemble $q\implies r$ et $q$ déduire $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

Utilisez la tautologie $$(p\implies q)\implies((q\implies r)\implies(p\implies r))$$à la place et appliquez Modus Ponens deux fois avec les locaux donnés. Sinon, utilisez la tautologie$$\varphi\implies(\psi\implies (\varphi\land\psi))$$ de conclure $$\frac{\begin{matrix} \varphi \\ \psi\end{matrix}}{(\varphi\land\psi)} $$ puis utilisez la tautologie que vous avez donnée pour prouver $$\frac{\begin{matrix} p\implies q \\ q\implies r \end{matrix}}{ p\implies r} $$


Par souci d'exhaustivité: compte tenu des prémisses, ajoutez la tautologie ci-dessus, concluez

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

et alors

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

ce qui complète la preuve. Pour l'alternative, utilisez d'abord la règle donnée pour obtenir

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

puis en utilisant l'autre tautologie que nous avons

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

Utilisez modus ponens deux fois et conditionnez l'introduction:

$p\implies q$ et $p$ veux dire $q$ est vrai (première utilisation). $q\implies r$ et $q$ est vrai signifie $r$est vrai. (deuxième utilisation). Tellement donné$p \implies q$ et $q\implies r$ puis par introduction conditionnelle $p$ être vrai signifie $r$est vrai. Alors$p\implies r$.

D'accord, je pense que je l'ai compris:

Si nous prenons la notation $\phi\vdash \psi$ pour signifier "devions-nous supposer $\phi$ nous pouvons dériver $\psi$ puis:

$p\implies q$ (donné)

$p \implies r$ (qiven)

$p\vdash p$ (supposer quelque chose, c'est assumer quelque chose. $\mu\vdash \mu$ est toujours vrai parce que si nous supposons $\mu$ nous pouvons dériver $\mu$... parce que nous supposons que c'est vrai. Cela ne veut pas dire que nous réclamons , il est vrai (comme vos demandes dans les commentaires au sujet de « rester dans les locaux initiaux » impliquez vous croyez); c'est-à-dire sous un hypothétique si c'était vrai on pourrait en déduire. Bien sûr, si ce n'est pas vrai, ce que nous en tirons ne sera pas pertinent.)

$p\vdash p\implies q$ ($p\implies q$ est une vérité donnée si nous supposons $p$ou pas. Pour chaque vraie déclaration$T$ puis $\mu\vdash T$sera toujours vrai. Et je suppose$\mu\vdash F$ sera toujours faux.)

$p\vdash q$ (modus ponens)

$p\vdash q\to r$ ($q\implies r$ est une vérité donnée si nous supposons $p$ ou pas)

$p\vdash r$ (modus ponens)

$p\implies r$ (Introduction conditionnelle;)

(c'est une règle de base. En anglais, si en supposant $\mu$ nous pouvons dériver $\psi$ puis $\mu \implies \psi$ doit être vrai.)

2 Maurocurto Aug 18 2020 at 21:19

Voici une preuve utilisant les règles de déduction naturelle:

$\vdash((p\implies q)\land(q\implies r))\implies (p\implies r)$

  1. $((p\implies q)\land(q\implies r))$ - supposition
  2. $\mid\underline{\quad p}$ - supposition
  3. $\mid\quad p\implies q$ - règle Élimination de $\land$ dans $1.$
  4. $\mid\quad q$ - règle Élimination de $\implies$ dans $2.,\,3.$
  5. $\mid\quad q\implies r$ - règle Élimination de $\land$ dans $1.$
  6. $\mid\quad r$ - règle d'élimination de $\implies$ dans $4.,\,5.$
  7. $p\implies r$ - règle Introduction de $\implies$ dans $2.,\,6.$ (fermer l'hypothèse 2.)
  8. $((p\implies q)\land(q\implies r))\implies (p\implies r)$ - règle Introduction de $\implies$ dans $1.,\,7.$ (hypothèse proche $1.$)