Nous avons déjà vu la structure d’un raisonnement et des exemples simples. Maintenant, nous mettrons à l’épreuve cette connaissance en raisonnant avec 4 techniques de déduction en logique propositionnelle. À travers cela, nous verrons non seulement que ces choses fonctionnent, mais nous commencerons également à enrichir les procédures qui sortiront l’état rudimentaire dans lequel se trouve le calcul propositionnel présenté jusqu’à présent.

Si \alpha, \beta et \gamma sont des expressions du calcul propositionnel, alors il est possible d’inférer les techniques de déduction suivantes depuis les fondements :

Règle de présomption (Pre)

La règle de déduction la plus simple de toutes est celle de présomption. Elle est obtenue directement en appliquant le réciproque du théorème de déduction sur le théorème \vdash(\alpha\rightarrow\alpha). Si cela vous semble du langage archaïque, tout ce que vous devez savoir se trouve ici.

\{\alpha\}\vdash \alpha

Combinée avec la règle de monotonie, elle vous permettra d’ajouter des expressions pratiques dans vos déductions.

Le Syllogisme Hypothétique (SH)

Le syllogisme hypothétique, ou transitivité de l’implication, est une sorte d’évolution du modus ponens. Sa formulation est la suivante :

\{(\alpha\rightarrow\beta), (\beta\rightarrow\gamma)\}\vdash (\alpha\rightarrow\gamma)

Il existe plusieurs façons d’obtenir cette règle de déduction, nous en verrons quelques-unes sous peu.

Si nous raisonnons à partir des expressions, il sera simple de construire le raisonnement suivant :

Donc \{\alpha,(\alpha\rightarrow\beta),(\beta\rightarrow\gamma)\}\vdash\gamma

Enfin, en appliquant le théorème de déduction sur cette dernière expression, on a :

\{(\alpha\rightarrow\beta),(\beta\rightarrow\gamma)\}\vdash(\alpha\rightarrow \gamma)

Une autre façon d’obtenir la démonstration de cette règle est de raisonner à partir des déductions, en construisant à travers la présomption et la monotonie. Observez le raisonnement suivant à partir des déductions :

Vous devez noter ici que les deux démonstrations sont identiques, seulement elles ont été développées avec des styles différents. En pratique, vous pouvez alterner entre les deux styles selon ce qui vous convient le mieux.

Équivalences de Double Négation (DN)

Les équivalences de double négation reproduisent la notion intuitive que la double négation d’une affirmation est équivalente à la même affirmation. Cela, écrit symboliquement, sera de la forme

\alpha\dashv\vdash\neg\neg\alpha

Voyons maintenant une démonstration :

Donc\{\neg\neg \alpha \} \vdash \alpha

Pour faire la démonstration dans l’autre sens, nous pouvons utiliser celle que nous venons de faire en la réadaptant par une simple substitution, obtenant ce qui suit :

\{\neg\neg \neg \alpha \} \vdash \neg \alpha

Et à partir de cela, nous formons la démonstration dans l’autre sens :

Donc \{\alpha \} \vdash \neg\neg \alpha

Enfin, de ces deux démonstrations, on a \alpha \dashv\vdash \neg\neg \alpha .

Équivalence du Contraposé de l’Implication (CpI)

Cela correspond aux équivalences suivantes

(\alpha \rightarrow \beta) \dashv\vdash (\neg\beta \rightarrow \neg\alpha)

(\neg\alpha\rightarrow\beta)\dashv\vdash (\neg\beta\rightarrow\alpha)

(\alpha\rightarrow\neg\beta) \dashv\vdash (\beta\rightarrow\neg\alpha)

La démonstration de cette première relation se fait de la manière suivante :

D’un côté, elle est obtenue directement depuis le troisième axiome

Donc \{(\neg\beta\rightarrow \neg\alpha)\}\vdash (\alpha \rightarrow \beta)

Et de l’autre côté, la démonstration peut être obtenue à partir du raisonnement suivant :

Donc \{(\alpha \rightarrow \beta)\}\vdash (\neg \beta \rightarrow \neg \alpha )

Donc, des deux raisonnements précédents, on a

(\alpha \rightarrow \beta) \dashv\vdash (\neg \beta \rightarrow \neg \alpha )

Pour démontrer la deuxième, nous pouvons faire les deux raisonnements suivants :

Donc \{(\neg\alpha \rightarrow \beta)\} \vdash(\neg\beta \rightarrow \alpha)

Il reste maintenant à faire la démonstration dans le sens inverse. Nous pouvons le faire par le raisonnement suivant :

Donc \{(\neg\beta\rightarrow\alpha)\}\vdash (\neg\alpha \rightarrow \beta)

Enfin, de ces deux raisonnements, on conclut que (\neg\beta\rightarrow\alpha) \dashv \vdash (\neg\alpha \rightarrow \beta) , ce qui était à démontrer.

La dernière équivalence sera laissée comme exercice. Pour la démontrer, vous pouvez vous guider avec les deux démonstrations déjà données. C’est la meilleure façon de maîtriser les techniques de déduction.