Logique connexive

Une logique connexive est un système logique qui admet plusieurs théorèmes qui contredisent la logique classique, mais mobilisant une notion de l'implication qui se rapproche en certains points du langage ordinaire. Dans une logique connexive, il est absurde de considérer qu'une proposition puisse impliquer, ou être impliquée, par sa propre négation, ce qui s'appelle les thèses d'Aristote. Il est aussi généralement demandé que les propositions « $A$ implique $B$ » et « $A$ implique la négation de $B$ » impliquent la négation l'une de l'autre, cela s'appelle les thèses de Boèce. Les formulations contemporaines tendent également à demander la non-symétrie de l'implication, au sens où « $A$ implique $B$ » n'implique pas nécessairement « $B$ implique $A$ », de sorte à la distinguer de l'équivalence logique.

Histoire

Époque antique

Dans l'Organon, Aristote développe divers raisonnements logiques. On retrouve quelques raisonnements usuels, tels que les raisonnements par l'absurde, usité par exemple ici :

« [...] il est impossible que, si A étant blanc, B doit être grand de toute nécessité, A n’étant pas blanc, B soit encore grand nécessairement. En effet, puisque, cette chose A étant blanche, il y a nécessité que cette autre chose B soit grande, et que, B étant grand, C ne soit pas blanc, il faut nécessairement, si A est blanc, que C ne le soit pas. Et, si l’on suppose deux choses dont il faut nécessairement que l’une soit par l’existence de l’autre, la seconde n’étant pas, il y a nécessité que la première ne soit pas. Donc, B n’étant pas grand, il n’est pas possible que A soit blanc ; mais, si, A n’étant pas blanc, il est nécessaire que B soit grand, il résulte, de toute nécessité, que, B n’étant pas grand, ce même B est grand : ce qui est absurde. »

— Aristote, Premiers Analytiques § 17

En utilisation le style de Fitch pour la déduction naturelle, nous pourrions résumer ce bout de démonstration ainsi, en utilisant les règles de modus ponens et de modus tollens :

${\begin{aligned}1\quad &\quad \quad {\underline {(A\to B)\land (\neg A\to B)\quad }}\\2\quad &\quad \quad A\to B&{\text{simplification (1)}}\\3\quad &\quad \quad \neg A\to B&{\text{simplification (1)}}\\4\quad &\quad \quad \quad \quad {\underline {\neg B\quad \quad \quad \quad \quad \quad \quad }}\\5\quad &\quad \quad \quad \quad \neg A&{\text{modus tollens (2, 4)}}\\6\quad &\quad \quad \quad \quad B&{\text{modus ponens (3, 5)}}\\7\quad &\quad \quad \neg B\to B&{\text{preuve conditionnelle (4-6)}}\\8\quad &\neg (A\to B)&{\text{par l'absurde (1-7)}}\end{aligned}}$

Dans sa démonstration, en particulier, Aristote affirme que la proposition « non-B implique B » serait absurde : « il résulte, de toute nécessité, que, B n’étant pas grand, ce même B est grand : ce qui est absurde ».

Nous pouvons analyser cette inférence anachroniquement dans le système actuel de la logique classique, où (non-B implique B) est invalidée si l'on peut démontrer B, ce pour deux raisons. En logique classique, toute proposition implique un démontrable quelconque, à savoir $B\to (A\to B)$. De même, la négation d'un démontrable quelconque implique toute proposition (ex falso quodlibet), à savoir $B\to (\neg B\to A)$. Dans les deux cas, on a le théorème classe $B\to (\neg B\to B)$. On appelle ce genre de phénomènes des paradoxes de l'implication matérielle (en).

Il est donc important de remarquer qu'Aristote utilise les thèses suivantes, qui admetteraient pourtant des contre-exemples en logique classique, qu'on appelle thèses d'Aristote, à savoir qu'il est absurde d'affirmer (non-A implique A), et qu'il est absurde d'affirmer (A implique non-A).

L'appellation « connexive » est dérivée d'une remarque donnée par Sextus Empiricus :

« Et ceux qui introduisent la notion de connexion (συνάρτησις) disent qu’un conditionnel est valide quand la contradictoire de son conséquent est incompatible avec son antécédent » »

— Sextus Empiricus, Hypotyposes Pyrrhoniennes, II, l. 10-12.

La logique connexive s'inscrit toutefois, au moins au départ, dans un courant aristotélicien.

Époque médiévale

L'époque médiévale a vu plusieurs développements en logique connexive, en passant de Boèce à Robert de Melun (†1167), en passant par Abélard.

Boèce a notamment donné son nom à deux thèses, qui sont aujourd'hui considérées comme nécessaires pour qualifier une logique de connexive. Celles-ci viennent de l'extrait suivant :

« Si est A, cum sit B, est C; [...] atqui cum sit B, non est C; non est igitur A. »

— Boèce, De Syllogismo Hypothetico Libri Duo, 851B-C.

On peut ré-exprimer cela ainsi :

${\begin{aligned}m\quad &A\to (B\to C)\\n\quad &A\to (B\to \neg C)\\&\neg A\end{aligned}}$

Cela indique que Boèce considère comme contradictoires « B implique C » et « B implique non-C ». À noter que l'extrait d'Aristote précédent y ressemblait fortement, puisqu'il affirme qu'il n'est pas possible d'avoir « B implique C » et « non-B implique C ». Cet extrait de Boèce a été ensuite décliné de différentes manières, mais la formulation que nous retenons de nos jours est celle décrite précédemment, à savoir : les propositions « A implique B » et « A implique la négation de B » impliquent la négation l'une de l'autre.

Abélard souscrivait également à la logique connexive. Dans son Dialectica, celui-ci explique que les conditionnelles « si quelqu'un est un homme, il est un animal » et « si quelqu'un est un homme, il n'est pas un animal » ne peuvent être toutes deux vraies, sinon quoi nous pourrions décliner la proposition inconvéniente suivante : si quelqu'un est un homme, il n'est pas un homme. Par ailleurs, Abélard a lui-même donné son nom à deux thèses, l'un étant la deuxième d'Aristote, et l'autre étant la non-simultanéité de « A implique B » et « A implique non-B », à savoir ce qu'on formalise de nos jours comme le schéma d'axiomes $\neg ((p\to q)\land (p\to \neg q))$.

Robert de Mélun, inspiré d'Abélard, apporte également avec lui et un principe général, caractérisée par la phrase nihil ex falso accidere (trad. « rien ne descend d'une contradiction »). L'auteur anonyme de l'Ars Meliduna, basé sur les travaux de Robert de Mélun, donnait plutôt une interprétation faible de cette phrase, au sens ex impossibili nihil sequitur (d'une impossibilité rien ne suit), tandis que les Meludinenses suivaient plutôt ex falso nihil sequitur (« rien ne suit d'une proposition fausse »).

Approches contemporaines

La définition contemporaine en logique formelle d'une logique connexive est un système formel qui satisfait certaines propriétés spécifiques : Les thèses d'Aristote, les thèses de Boèce, et la non-symétrie de l'implication.

Les thèses d'Aristote réfèrent à deux schémas d'axiomes. L'une dit qu'on peut toujours nier la proposition, (non-A implique A) ; Il s'agit donc du schéma d'axiomes $\neg (\neg A\to A)$. L'autre dit qu'on peut toujours nier la proposition, (A implique non-A) ; Il s'agit du schéma d'axiomes $\neg (A\to \neg A)$.

Les thèses de Boèce réfèrent à deux autres schémas d'axiomes. D'une part, que A implique B, implique toujours la négation de, A implique non-B ; Il s'agit donc du schéma d'axiomes $(A\to B)\to \neg (A\to \neg B)$. D'autre part, que A implique non-B, implique toujours la négation de, A implique B ; Il s'agit donc du schéma d'axiomes $(A\to \neg B)\to \neg (A\to B)$.

Que l'implication soit demandée de ne pas être symétrique, signifie que de A implique B, on n'a pas nécessairement que B implique A. On la décrit par l'invalidation du schéma d'axiomes $(A\to B)\to (B\to A)$. Cela permet deux choses : D'une part, à distinguer l'implication de l'équivalence logique ; D'autre part, à assurer la cohérence du système.

Connexivité totale

Estrada-González et Ramirez-Cámara identifient plusieurs désidératas. Une logique connexive est abélardienne si elle vérifie les schémas d'axiomes suivants : $\neg ((A\to B)\land (\neg A\to B))$ ; $\neg ((A\to B)\land (A\to \neg B))$. Elle est anti-paradoxe, au sens des paradoxes de l'implication matérielle, si les schémas d'axiomes suivants ne sont pas universellement valides : $A\to (B\to A)$ ; $A\to (\neg A\to B)$ ; $A\to (B\to C)$ pour un contingent $A$ et un démontrable $B\to C$. Elle est Kapsner-forte si $A\to \neg A$ est insatisfaisable, et que $A\to B$ et $A\to \neg B$ ne sont pas simultanément satisfaisables. Elle est simplificatrice si sont validés les schémas d'axiomes suivants : $(A\land B)\to A$ ; $(A\land B)\to B$. Elle est conjonction-idempotente sont les schémas d'axiomes sont valides : $(A\land A)\to A$ ; $A\to (A\land A)$.

Une logique connexive qui satisfait tous ces désidératas serait appelée totalement connexive. Cependant, aucun tel système n'a été trouvé jusqu'à aujourd'hui.

Sémantiques fonctionnelles

Certaines sémantiques fonctionnelles ont été développées pour diverses logiques connexives, dont MRS^P, CC1, M3V, CN et de nombreuses autres. Les sémantiques décrites ici sont polyvalentes, avec au moins trois valeurs de vérité. Dans les sémantiques polyvalentes, une valeur désignée est une valeur de vérité qui, essentiellement, prend le rôle de la valeur ${\textsf {vrai}}$ dans la conséquence sémantique, de sorte que si toutes les prémisses ont une valeur désignée alors la conclusion a elle aussi une valeur désignée.

Système C

Développé par Heinrich Wansing en 2005, le système C a été au départ conçu pour traiter la logique modale de façon connexive. Son fragment propositionnel a été ensuite étudié à part comme socle de théorie de la preuve connexive propositionnelle.

Il s'agit d'une logique structurelle comme la logique classique, qui vérifie donc la règle d'axiome, la règle de coupure, la règle de permutation, la règle de contraction et la règle d'affaiblissement. Sur le plan inférentiel, si cette logique admet les mêmes règles d'introduction et d'élimination que la logique classique pour la conjonction, la disjonction, l'implication, on s'inspire de la théorie de la preuve N4 de David Nelson pour développer des règles d'introduction et d'élimination pour la négation de chaque opération, à savoir la négation de la négation (double négation), la négation de la conjonction et la négation de la disjonction. Toutefois, pour la négation de l'implication, les règles diffèrent de N4 en cela qu'elles forcent la connexivité :

${\frac {\Gamma ,p\vdash \neg q}{\Gamma \vdash \neg (p\to q)}}({\neg }{\to }_{i})\quad {\frac {\Gamma \vdash \neg (p\to q)\quad \Delta \vdash p}{\Gamma ,\Delta \vdash \neg q}}({\neg }{\to }_{e})$

Cette logique est toutefois übercohérente, ce qui signifie qu'il existe des paires de théorèmes contradictoires, deux formules universellement valides bien que l'une est la négation de l'autre. On parle aussi de dialethéias, qu'on appelle aussi des vraies contradictions. C'est notamment le cas des théorèmes $((p\land \neg p)\to \neg (p\land \neg p))$ et $\neg ((p\land \neg p)\to \neg (p\land \neg p))$ de C. Toutefois, la logique C n'est pas triviale. En particulier, il en existe un modèle sain à quatre valeurs appelé MC, avec pour valeurs T, B, N et F, avec pour valeurs désignées B et T :

$\land$ T B N F T T B N F B B B F F N N F N F F F F F F

$\lor$ T B N F T T T T T B T B T B N T T N N F T B N F

$\to$ T B N F T T B N F B T B N F N B B B B F B B B B

$v$ $\neg v$ T F B B N N F T

À noter toutefois que cette logique est paracomplète, ce qui signifie qu'elle n'a pas le principe du tiers exclu. En ajoutant la loi du tiers exclu, on obtient la logique CN de négation conditionnelle, dont un modèle fonctionnel à trois valeurs existe, avec pour valeurs T, B et F, tels que les valeurs T et B sont désignées :

$\land$ T B F T T B F B B B F F F F F

$\lor$ T B F T T T T B T B B F T B F

$\to$ T B F T T B F B T B F F B B B

$v$ $\neg v$ T F B B F T