Introduction et Élimination des Conjonctions et Disjonctions

Une des techniques de la logique classique consiste en l’introduction et l’élimination des conjoncteurs et des disjoncteurs. Bien que ces techniques soient exécutées de manière plus ou moins intuitive, leur justification n’est pas totalement triviale, mais elles peuvent être obtenues à partir des règles de la logique propositionnelle que nous avons déjà démontrées dans les cours précédents. Formellement, les techniques d’introduction et d’élimination des conjoncteurs et des disjoncteurs sont les suivantes :

Et leurs démonstrations à partir de la logique propositionnelle sont les suivantes :

∨-Introduction

∨-Élimination

∧-Introduction

∧-Élimination

Techniques de Contradictions et Tautologies

Règle du Tiers Exclu ou Tautologie (tau)

Une autre caractéristique de la logique classique est la propriété du tiers exclu (tertium non datur). Elle stipule que si l’on a deux affirmations, dont l’une nie l’autre, alors nécessairement l’une des deux doit être vraie ; autrement dit, la conjonction de deux affirmations dont l’une nie l’autre forme nécessairement une tautologie. Formellement, cela s’exprime en écrivant :

\vdash (\neg\alpha \vee\alpha)

Et sa démonstration est facile à obtenir.

Une autre manière de formuler le principe du tiers exclu est à travers la loi de non-contradiction, qui stipule qu’une affirmation ne peut être vraie et fausse en même temps et qui est formulée formellement de la manière suivante :

\vdash \neg(\neg\alpha \wedge \alpha)

Cette propriété n’a pas besoin de démonstration, non pas parce qu’elle est auto-évidente en soi, mais parce qu’elle est obtenue directement en appliquant la définition de la conjonction au principe du tiers exclu.

Règle de Contradiction ou Principe d’Explosion

Une autre propriété connue de la logique classique est le principe d’explosion, qui est généralement formulé par la phrase « des prémisses contradictoires, on peut conclure n’importe quoi ». Sa formulation est généralement présentée de l’une des deux manières suivantes :

\{(\neg\alpha \wedge \alpha)\}\vdash \beta

\{\alpha, \neg\alpha\}\vdash \beta

La démonstration de cette règle est simple :

∨-Élimination3

Le modus ponens peut être écrit de deux manières différentes. L’une des formes que nous connaissons déjà est \{\alpha,(\alpha \rightarrow \beta)\}\vdash \beta. L’autre est un peu moins familière :

\{\alpha\}\vdash\beta \; \wedge \; \vdash \alpha \; \Longrightarrow \; \vdash \beta

En se concentrant sur cette deuxième forme, il est possible de visualiser une expansion de cette règle que nous appelons ∨-Élimination3, car elle ressemble à une simplification obtenue à partir d’une disjonction. Elle dit que si \gamma peut être inférée à partir de \alpha et à partir de \beta (les deux à la fois) et que la disjonction entre \alpha et \beta est un théorème, alors \gamma est un théorème. Cela se résume formellement à travers l’écriture suivante :

\{\alpha\}\vdash\gamma\; \wedge \; \{\beta\}\vdash\gamma \; \wedge \; \vdash (\alpha \vee \beta) \Longrightarrow \vdash \gamma

La démonstration de cette technique de la logique classique est la suivante :

Preuve par les cas (cas)

Une autre technique de la logique classique est la preuve par les cas. Si une expression \beta peut être inférée d’une autre expression \alpha ainsi que de sa négation, alors l’expression \beta est nécessairement un théorème. Cela se représente formellement par l’écriture : \alpha \vdash \beta \; \wedge \; \neg\alpha \vdash \beta \Longrightarrow \vdash \beta. Sa démonstration est la suivante :

\begin{array}{rll} (1) & \alpha \vdash \beta &; Prémisse\\ (2) & \neg \alpha \vdash \beta &; Prémisse \\ (3) & \vdash \alpha \vee \neg\alpha &; TAU \\ (4) & \vdash \beta &; \vee-Élimination3(1,2,3) \end{array}

Réduction à l’Absurde (absurdo)

Une des techniques de la logique classique les plus utilisées dans les démonstrations, en particulier en mathématiques, est la réduction à l’absurde. Elle consiste en ce que si, à partir d’une expression \alpha, on infère une contradiction (une affirmation et sa négation), alors la négation de \alpha est une tautologie. Formellement, cela s’exprime comme suit : \{\alpha\}\vdash \beta \; \wedge \; \{\alpha\}\vdash \neg\beta \Longrightarrow \vdash \neg\alpha. Et cela peut être démontré par le raisonnement suivant :