Logique classique

La logique classique est un système logique formel développé à partir de la fin du XIX^e siècle, au cours de la crise des fondements des mathématiques.

Appelée simplement logique à ses débuts^{[réf. nécessaire]}, c'est l'apparition d'autres systèmes logiques formels, notamment de la logique intuitionniste, qui a suscité l'adjonction de l'adjectif classique au terme logique. À cette époque, le terme de logique classique fait référence à la logique aristotélicienne.

La logique classique est caractérisée par des postulats qui la fondent et la différencient de la logique intuitionniste, exprimés dans le formalisme du calcul des propositions ou du calcul des prédicats :

• Le tiers exclu énonce que pour toute proposition mathématique considérée, elle-même ou sa négation est vraie : $A\lor \neg A$

• Le raisonnement par l'absurde : $\lnot \neg A\Rightarrow A$

• La contraposition : ${\big (}\neg B\Rightarrow \neg A{\big )}\Rightarrow {\big (}A\Rightarrow B{\big )}$

• L'implication matérielle : $(A\Rightarrow B)\Leftrightarrow (\neg A\lor B)$

• La loi de Peirce : $((A\Rightarrow B)\Rightarrow A)\Rightarrow A$

Ces principes sont équivalents par raisonnement intuitionniste, c’est-à-dire que l'on peut montrer que n'importe lequel d'entre eux permet de déduire les autres en utilisant les règles intuitionnistes.

Ces ajouts permettent également de dériver une loi de De Morgan supplémentaire par rapport à la logique intuitionniste, en l'occurrence $\neg (A\land B)\Rightarrow (\neg A\lor \neg B)$.

Ces principes contribuent au fait que les modèles calculatoires de la logique classique sont beaucoup plus complexes que ceux de la logique intuitionniste.

Le principe

$(A\Rightarrow B)\vee (B\Rightarrow A)$

est valide en logique classique, et n'est pas démontrable en logique intuitionniste, mais son adjonction à la logique intuitionniste n'engendre pas la logique classique.

Règles de raisonnement

Toute conclusion se fait selon un socle de prémisses, fusionnées avec une opération binaire ${\circ }$ dite de fusion. Il est généralement implicite que $\circ$ est associative, ce qui signifie que pour toutes formules logiques $P,$ $Q$ et $R,$ $(P\circ (Q\circ R))=((P\circ Q)\circ R),$ ce qui permet notamment d'écrire $(P_{1}\circ \cdots \circ P_{n})$ sans risque d'ambiguïté structurelle.

Il se peut que ce socle de prémisses soit ${\textbf {1}}$, le contexte neutre, auquel cas nous écrirons la conclusion «$p$» au lieu de «$p$ selon ${\textbf {1}}$». On appelle alors théorème toute formule déductible à partir du contexte neutre. Le rôle du contexte neutre est aussi plus structurel, car ${\textbf {1}}$ est l'élément neutre pour $\circ$, ce qui signifie que pour toute formule $p,$ $(P\circ {\textbf {1}})=P$ et $({\textbf {1}}\circ P)=P.$

Règles d'identité

Pour toute formule $p$, on a $p$ selon $p$, il s'agit de la règle d'axiome. C'est une forme de réflexivité.

La règle de coupure décrit quant à elle que de $p$ selon $(P_{1}\circ \cdots \circ P_{m})$ d'une part, $q$ selon $(p\circ P_{m+1}\circ \cdots \circ P_{n})$ d'autre part, on déduit $q$ selon $(P_{1}\circ \cdots \circ P_{n}).$ C'est une forme de transitivité.

Règles structurelles

La règle de permutation décrit que si $p$ selon $(P_{1}\circ \cdots \circ P_{n}),$ alors pour toute permutation ${\displaystyle \sigma$ :[\![1;n]\!]\mathbin {\overset {\sim }{\to }} [\![1;n]\!],} $p$ selon $(P_{\sigma (1)}\circ \cdots \circ P_{\sigma (n)})$.

La règle de contraction s'applique aussi, qui décrit quant à elle que si $q$ selon $(p\circ p\circ P_{1}\circ \cdots \circ P_{n}),$ alors $q$ selon $(p\circ P_{1}\circ \cdots \circ P_{n}).$ La règle de contraction rend cette logique insensible aux ressources, pour reprendre le vocabulaire associé à la logique linéaire.

Règles d'inférence

La déduction combinée de $p$ selon $(P_{1}\circ \cdots \circ P_{n})$ d'une part et de $q$ selon $(P_{1}\circ \cdots \circ P_{n})$ d'autre part, équivaut à la déduction de $(p\land q)$ selon $(P_{1}\circ \cdots \circ P_{n}).$

Pour introduire une disjonction, on a $(p\lor q)$ selon $p$ d'une part, $(p\lor q)$ selon $q$ d'autre part.

Pour éliminer une disjonction, on passe par la disjonction de cas. On sait vérifie les deux cas, à partir d'un même socle de prémisses pour chaque cas et ce, en déduisant la même conclusion : on a donc $r$ selon $(p\circ P_{1}\circ \cdots \circ P_{n})$ et $r$ selon $(q\circ P_{1}\circ \cdots \circ P_{n}).$ Puisqu'on a déduit $r$ dans les deux cas, on déduit alors $r$ selon $((p\lor q)\circ P_{1}\circ \cdots \circ P_{n}).$

Pour introduire une négation, on établit une forme de raisonnement par l'absurde. Pour cela, on part de $q$ selon $(p\circ P_{1}\circ \cdots \circ P_{m})$ et $\neg q$ selon $(p\circ P_{m+1}\circ \cdots \circ P_{n}).$ On en déduit que $p$ mène à une contradiction dans le contexte de prémisses combiné, c'est-à-dire $\neg p$ selon $(P_{1}\circ \cdots \circ P_{n}).$

Pour éliminer une négation, on procède par élimination. On a $\neg p$ selon $(P_{1}\circ \cdots \circ P_{m})$ d'une part et $(p\lor q)$ selon $(P_{m+1}\circ \cdots \circ P_{n})$ d'autre part. De là, on combine les contextes de prémisses et on déduit $q$ selon $(P_{1}\circ \cdots \circ P_{n}).$

Enfin, pour distinguer la logique classique du fragment extensionnel de la logique intuitionniste, il nous faut introduire la règle d'élimination de la double négation, à savoir que $p$ selon $\neg \neg p.$ La règle d'introduction de la double négation, à savoir que $\neg \neg p$ selon $p,$ est dérivable des autres règles.

L'équivalence logique $(p\equiv q)$ est par ailleurs exprimable comme $((p\land q)\lor (\neg p\land \neg q))$, tandis que la disjonction exclusive $(p\mathbin {\overline {\lor }} q)$ s'exprime comme $\neg (p\equiv q).$

On établit aussi l'implication matérielle, écrite $(p\Rightarrow q)$ ou, plus spécifiquement, $(p\supset q)$, afin de la différencier de l'implication dans d'autres systèmes logiques, qui peut être caractérisée comme $(\neg p\lor (p\land q)),$ ce qui est fréquemment décrite comme une conditionnelle indicative, portée sur la combinaison de faits pour produire une proposition factuelle, plutôt qu'une conditionnelle subjonctive qui permettrait de raisonner sur des hypothèses contingentes voire contrefactuelles.

Logique classique et tables sémantiques

Démontrer que la logique classique n'est pas triviale

La sémantique de la logique classique se fait par une sémantique fonctionnelle, principalement avec des tables à deux valeurs, permettant alors de vérifier sa non-trivialité et de vérifier la non-dérivabilité de certaines conclusions à partir de socles de prémisses spécifiques.

En général, on commence par établir un ensemble de valeurs $V$ qui seront assignables à chaque variable propositionnelle, assignations qui permettront d'établir des classes d'équivalence sur les formules logiques en traitant chaque opération logique comme des lois internes sur $V$. Pour ce faire, il faut également une relation binaire $\prec$ sur $V$ pour modéliser le «selon», faire de $\circ$ une loi de composition interne sur $V$ et, enfin, traduire chaque règle syntaxique ci-haute en utilisant toutes ces opérations internes et cette relation binaire. Puisque tout théorème est déductible du contexte vide, ${\textbf {1}},$ repérable par son statut d'élément neutre pour $\circ ,$ nous définirons $V^{+}=\{v\in V~|~{\textbf {1}}\prec v\}$ l'ensemble des valeurs désignées.

Pour la logique classique, c'est à partir de la structure engendrée par ces règles qu'on peut obtenir une structure algébrique dite d'algèbre de Boole. Dans ces structures, $\circ$ et $\land$ sont confondues. Dans le cas fini, l'élément neutre de $\land$ n'est autre que le maximum de $V$ selon la relation $\prec$ qui s'avère être une relation d'ordre. De fait, la seule valeur désignée sera ce même élément maximal.

À noter que toute algèbre de Boole finie est isomorphe à l'ensemble des parties ${\mathcal {P}}(E)$ d'un ensemble fini $E$, muni de la relation d'inclusion ensembliste $\subseteq$ pour $\prec ,$ l'opération d'intersection $\cap$ pour la conjonction $\land$ et, de fait, la fusion ${\circ },$ l'opération d'union $\cup$ pour la disjonction inclusive $\lor$ et, enfin, le complémentaire à $E$ pour la négation $\neg .$

L'exemple de modèle polyvalent non-trivial le plus simple pour la logique classique est alors l'algèbre de Boole à deux éléments, à isomorphisme près l'algèbre des parties du singleton :

$\land$ $\varnothing$ $\{*\}$ $\varnothing$ $\varnothing$ $\varnothing$ $\{*\}$ $\varnothing$ $\{*\}$

$\lor$ $\varnothing$ $\{*\}$ $\varnothing$ $\varnothing$ $\{*\}$ $\{*\}$ $\{*\}$ $\{*\}$

$p$ $\neg p$ $\varnothing$ $\{*\}$ $\{*\}$ $\varnothing$

Modèles non-bivalents

Si le modèle bivalent est inférentiellement équivalent aux règles de la logique classique établies précédemment, il l'est aussi au modèle tétravalent ci-dessous avec pour seule valeur désignée $\{a;b\}.$

$\land$ $\varnothing$ $\{a\}$ $\{b\}$ $\{a;b\}$ $\varnothing$ $\varnothing$ $\varnothing$ $\varnothing$ $\varnothing$ $\{a\}$ $\varnothing$ $\{a\}$ $\varnothing$ $\{a\}$ $\{b\}$ $\varnothing$ $\varnothing$ $\{b\}$ $\{b\}$ $\{a;b\}$ $\varnothing$ $\{a\}$ $\{b\}$ $\{a;b\}$

$\lor$ $\varnothing$ $\{a\}$ $\{b\}$ $\{a;b\}$ $\varnothing$ $\varnothing$ $\{a\}$ $\{b\}$ $\{a;b\}$ $\{a\}$ $\{a\}$ $\{a\}$ $\{a;b\}$ $\{a;b\}$ $\{b\}$ $\{b\}$ $\{a;b\}$ $\{b\}$ $\{a;b\}$ $\{a;b\}$ $\{a;b\}$ $\{a;b\}$ $\{a;b\}$ $\{a;b\}$

$p$ $\neg p$ $\varnothing$ $\{a;b\}$ $\{a\}$ $\{b\}$ $\{b\}$ $\{a\}$ $\{a;b\}$ $\varnothing$

Nous remarquerons que malgré la tétravalence de ce modèle, nous avons tout de même la loi du tiers exclu : pour tout $p\subseteq \{a;b\},$ nous avons effectivement que $(p\lor \neg p)=(p\cup \complement _{\{a;b\}}p)=\{a;b\},$ qui est bien une (la) valeur désignée du modèle. En particulier, $(\{a\}\lor \neg \{a\})=\{a;b\}$, bien que ni $\{a\}$ n'est désignée, ni $\neg \{a\}$ n'est désignée. Tout cela montre que la loi du tiers exclu n'est pas à confondre avec le principe de bivalence et que, d'autre part, ce dernier principe n'est pas inhérent à la logique classique.

Il existe aussi des modèles sains et complets non-booléens pour la logique classique. Un exemple trivalent peut être donné comme suit, avec pour valeurs 0, 1 et 2, dont 2 pour seule valeur désignée.

$\land$ 0 1 2 0 0 0 0 1 0 1 1 2 0 1 2

$\lor$ 0 1 2 0 0 1 2 1 1 1 2 2 2 2 2

$v$ $\neg v$ 0 2 1 2 2 0

Entre la logique classique et la logique intuitionniste

Plusieurs logiques intermédiaires (en), aussi appelées superintuitionistes, existent entre la logique classique.

Figure 1: Contre-modèle de Kripke de $(A\Rightarrow B)\vee (B\Rightarrow A)$

Figure 2: Contre-modèle de Kripke de $A\vee \neg A$

Par exemple, la logique de Gödel-Dummett (en) est la logique obtenue par ajout de l'axiome $(A\Rightarrow B)\vee (B\Rightarrow A)$ à la logique intuitionniste. Il s'agit effectivement d'une logique qui n'est plus la logique intuitionniste, car $(A\Rightarrow B)\vee (B\Rightarrow A)$ n'est pas dérivable dans ce système. Cependant, il ne s'agit pas encore de la logique classique, car le tiers exclu n'est pas une conséquence de cette formule.

Les modèles de Kripke permettent de comprendre la différence entre logique classique et logique intuitionniste.

La figure 1 montre un contre modèle de Kripke ${\mathcal {M}}$ de la proposition $(A\Rightarrow B)\vee (B\Rightarrow A)$. Ça n'est pas un modèle de Kripke de $(A\Rightarrow B)\vee (B\Rightarrow A)$ parce que ${\mathcal {M}},w_{1}\nvDash (A\Rightarrow B)\vee (B\Rightarrow A)$. En effet,

${\mathcal {M}},w_{2}\nvDash A\Rightarrow B$

${\mathcal {M}},w_{3}\nvDash B\Rightarrow A$

donc

${\mathcal {M}},w_{1}\nvDash (A\Rightarrow B)$

${\mathcal {M}},w_{1}\nvDash (B\Rightarrow A)$

d'où l'affirmation ci-dessus. Par conséquent, la proposition $(A\Rightarrow B)\vee (B\Rightarrow A)$ n'est pas dérivable en logique intuitionniste.

Tous les modèles de Kripke linéaires, c'est-à-dire tous les modèles dans lesquels chaque monde a un seul autre monde accessible, sont des modèles de Kripke de $(A\Rightarrow B)\vee (B\Rightarrow A)$, ce qui en fait des modèles sains pour la logique de Gödel-Dummett. C'est le cas de la figure 2. En revanche ce modèle ${\mathcal {M}}'$ n'est pas un modèle de $A\vee \neg A$, car

${\mathcal {M}}',w_{1}\nvDash A$

${\mathcal {M}}',w_{1}\nvDash \neg A$

Puisque $A\vee \neg A$ n'est pas valide dans tous les modèles de $(A\Rightarrow B)\vee (B\Rightarrow A)$, $A\vee \neg A$ n'est pas dérivable en logique de Gödel-Dummett. Plus généralement la logique classique ne peut pas être engendrée par l'ajout de $(A\Rightarrow B)\vee (B\Rightarrow A)$ à la logique intuitionniste. Notons en passant que nous avons aussi montré que $A\vee \neg A$ n'est pas valide en logique intuitionniste.

Une autre logique intermédiaire qu'on peut citer est la logique de De Morgan, qu'on obtient à partir de la logique intuitionniste en ajoutant la dernière loi de De Morgan $\neg (A\land B)\Rightarrow (\neg A\lor \neg B)$ ou la loi du tiers exclu affaiblie $\neg \neg A\lor \neg A.$ Ce système logique permet en particulier de prouver toutes les lois de De Morgan, mais reste non-classique car la loi du tiers exclu y est toujours indépendante. À vrai dire, il s'agit même d'une sous-logique de la logique de Gödel-Dummett, puisque toutes les lois de De Morgan sont dérivables dans celle-ci.

Démonstration

Nous voulons montrer $\neg A\lor \neg B$ selon $\neg (A\land B)$ en logique de Gödel-Dummett. Nous allons pour cela utiliser un lemme qu'on appelle règle d'affaiblissement :

${\begin{array}{llr}1&B{\text{ selon }}\Gamma \\2&A{\text{ selon }}A&ax\\3&\neg \neg A{\text{ selon }}A&{\neg }{\neg }_{i}(2)\\4&(\neg A\lor B){\text{ selon }}\Gamma &{\lor }_{i}(1)\\\blacksquare &B{\text{ selon }}\Gamma ,A&{\neg }_{e}(3,4)\end{array}}$

Cela nous servira pour pouvoir appliquer les règles de conjonction dans la preuve suivante :

${\begin{array}{llr}1&((A\Rightarrow B)\lor (B\Rightarrow A))&{\text{G.-D.}}\\2&\neg (A\land B){\text{ selon }}\neg (A\land B)&ax\\3&(A\Rightarrow B){\text{ selon }}(A\Rightarrow B)&ax\\4&A{\text{ selon }}A&ax\\5&B{\text{ selon }}(A\Rightarrow B),A&{\Rightarrow }_{e}(3,4)\\6&A{\text{ selon }}(A\Rightarrow B),A&{\textit {aff}}(4)\\7&(A\land B){\text{ selon }}(A\Rightarrow B),A&{\land }_{i}(6,5)\\8&(A\land B){\text{ selon }}\neg (A\land B),(A\Rightarrow B),A&{\textit {aff}}(7)\\9&\neg (A\land B){\text{ selon }}\neg (A\land B),(A\Rightarrow B),A&{\textit {aff}}({\textit {aff}}(2))\\10&\neg A{\text{ selon }}\neg (A\land B),(A\Rightarrow B)&{\neg }_{i}(7,8)\\11&(\neg A\lor \neg B){\text{ selon }}\neg (A\land B),(A\Rightarrow B)&{\lor }_{i}(9)\\12&(\neg A\lor \neg B){\text{ selon }}\neg (A\land B),(B\Rightarrow A)&{\text{c.f. }}3{-}11\\\blacksquare &(\neg A\lor \neg B){\text{ selon }}\neg (A\land B)&{\lor }_{e}(1,11,12)\end{array}}$

Cela conclut la démonstration.∎

La logique de De Morgan reste toutefois distincte, ayant par exemple un modèle sain à six valeurs où l'axiome $(A\Rightarrow B)\lor (B\Rightarrow A)$ n'est pas vérifié. Pour obtenir celui-ci, il suffit de prendre l'algèbre de Heyting dont l'ensemble sous-jacent a pour éléments $\varnothing ,\{0\},\{0,1\},\{0,2\},\{0,1,2\},\{0,1,2,3\},$ avec pour opérations binaires de suprémum et d'infimum les opérations d'union et d'intersection respectivement.

La loi de Peirce

La loi de Peirce est la proposition $((A\Rightarrow B)\Rightarrow A)\Rightarrow A$. Elle n'est pas valide en logique intuitionniste et son ajout à celle-ci produit la logique classique.

Démonstration

On utilisera ici le lemme disant $\neg A$ selon $(A\Rightarrow \neg A)$.

${\begin{array}{llr}1&(A\Rightarrow \neg A){\text{ selon }}(A\Rightarrow \neg A)&ax\\2&A{\text{ selon }}A&ax\\3&\neg A{\text{ selon }}A,(A\Rightarrow \neg A)&{\Rightarrow }_{e}(1,2)\\4&A{\text{ selon }}A,(A\Rightarrow \neg A)&af(2)\\\blacksquare &\neg A{\text{ selon }}(A\Rightarrow \neg A)&{\neg }_{i}(3,4)\end{array}}$

Nous pouvons alors l'utiliser pour montrer l'élimination de la double négation avec la règle de Peirce.

${\begin{array}{llr}1&\neg \neg A{\text{ selon }}\neg \neg A&ax\\2&\neg A{\text{ selon }}(A\Rightarrow \neg A)&{\text{lemme}}\\3&(\neg A\lor A){\text{ selon }}(A\Rightarrow \neg A)&{\lor }_{i}(2)\\4&A{\text{ selon }}(A\Rightarrow \neg A),\neg \neg A&{\neg }_{e}(1,3)\\5&((A\Rightarrow \neg A)\Rightarrow A){\text{ selon }}\neg \neg A&{\Rightarrow }_{i}(4)\\6&(((A\Rightarrow \neg A)\Rightarrow A)\Rightarrow A)&{\text{Peirce}}\\\blacksquare &A{\text{ selon }}\neg \neg A&{\Rightarrow }_{e}(6,5)\end{array}}$

Il s'agit donc bien de la logique classique. ∎

Elle a la particularité de ne contenir que des implications à la différence des quatre propositions citées plus haut qui contiennent toutes une négation.

Lien externe

• Rappel : Bases de logique, quantificateurs, limites.
• Logique intuitionniste
• Logique minimale