Quelques propriétés de la logique des propositions

Après qu’on a construit un logique, et plus généralement un système formel quelconque, il convient d’en dégager les principales propriétés. Celles-ci doivent naturellement être démontrées. Elles font alors l’objet de théorèmes qui portent sur le système : nous les appellerons des épithéorèmes. Démontrer un épithéorème exige de disposer de certains moyens logiques. S’ils se veulent rigoureux, ceux-ci ne sont pas élémentaires et dépassent le cadre de cet ouvrage. Nous allons cependant énoncer un certain nombre d’épithéorèmes relatifs à la logique des propositions et en esquisser des preuves simples.

Remarquons d’abord que nous avons affaire à deux notions de théorèmes. Au fascicule I, nous avons dit qu’un théorème était une expression qui pouvait se déduire, par les règles du système, de la classe d’hypothèses vide. Si $P$ est un théorème en ce sens, nous noterons provisoirement $\vdash_{1}\, P$ . Par ailleurs, nous venons de donner une autre définition de la notion de théorème. Si $P$ est un théorème en ce second sens, nous écrirons $\vdash_{2}\, P$ . La question qui se pose est de savoir, non pas si les deux notions sont les mêmes (en fait, elles sont formulées différemment), mais si la classe des théorèmes au sens 1 est la même que celle des théorèmes au sens 2. Comme, par définition, deux classes sont égales si elles contiennent les mêmes éléments, il suffit de se demander si, chaque fois que l’on a $\vdash_{1}\, P$ on a aussi $\vdash_{2}\, P$ et réciproquement. La réponse à cette question est affirmative.

Epithéorème 1 : $\vdash_{1}\, P$ si et seulement si $\vdash_{2}\, P$ .

La preuve doit être double. Il faut montrer :

I. Si $\vdash_{1}\, P$ alors $\vdash_{2}\, P$ .
II. Si $\vdash_{2}\, P$ alors $\vdash_{1}\, P$ .

Commençons par esquisser la preuve de II. Dire que $\vdash_{2}\, P$ , c’est dire que l’on a pu obtenir $P$ à partir d’axiomes en appliquant la règle (R1). Or il est facile de montrer que les trois schémas d’axiomes sont des métathéorèmes au sens 1 (V. I, p. 22). Il suffit, par exemple, d’écrire avec des majuscules la déduction de l’exemple 2 de la page 15 (Fascicule I), pour obtenir (A1). D’autre part, la règle (R1) n’est rien d’autre que la règle $\supset$ e. Donc, tout ce qui sera théorème au sens 2, le sera au sens 1.

Esquissons maintenant la preuve de I. Nous avons vu qu’il était possible, dans le cadre de l’axiomatique précédente, de déduire des règles à partir des schémas d’axiomes. Il est clair que l’on peut procéder de même à partir de schémas de théorèmes ou métathéorèmes. Supposons, ce qui est le cas mais que nous ne démontrerons pas, que l’on ait :

$\vdash_{2}\, P \supset (Q \supset (P\wedge Q))$ .

On aura immédiatement, par une double application de (R1) : $P$ , $Q\vdash_{2}\, P\wedge Q$ , ce qui n’est qu’une autre écriture pour la règle $\wedge$ i.

En conséquence de ce premier épithéorème, nous écrirons dès maintenant $\vdash P$ pour dire que $P$ est un théorème, aussi bien au sens 1 qu’au sens 2.

Examinons les relations entre la classe des théorèmes et celle des tautologies et, pour cela, notons provisoirement par $\vdash_{t}\: P$ , le fait que $P$ est une tautologie. Nous avons tout d’abord :

Epithéorème 2 : Si $\vdash P$ , alors $\vdash_{t}\: P$ .

Dire que $\vdash P$ , c’est dire que $P$ a son origine dans un ou plusieurs axiomes. Mais, il est aisé de s’assurer que tous les axiomes du système sont des tautologies. En effet, quelles que soient les propositions $P$ , $Q$ et $M$ , elles seront dans notre interprétation, vraies ou fausses. On aura donc pour (Al) par exemple :

$\begin{tabular}{c|cccc} $P$ & 1 & 1 & 0 & 0\tabularnewline $Q$ & 1 & 0 & 1 & 0\tabularnewline \hline $P\supset Q$ & 1 & 1 & 0 & 1\tabularnewline \hline $P\supset\left(P\supset Q\right)$ & 1 & 1 & 1 & 1\tabularnewline \end{tabular}$

De plus, si $\vdash P$ , il est engendré à partir d’axiomes qui sont des tautologies, par la seule règle (R1). Or celle-ci conserve, si l’on peut dire, la vérité. En effet, ses deux prémisses $P$ et $P\supset Q$ sont des tautologies. Considérons alors la table de $\supset$ :

$\begin{tabular}{c|c|c} \multicolumn{3}{c}{$P\supset Q$}\tabularnewline \hline 1 & 1 & 1\tabularnewline 1 & 0 & 0\tabularnewline 0 & 1 & 1\tabularnewline 0 & 1 & 0\tabularnewline \end{tabular}$

Sa deuxième ligne est exclue par la condition $val(P\supset Q)=1$ . Ses lignes 3 et 4 sont exclues par la condition $val(P)=1$ . Il ne reste donc que la première ligne et l’on voit que $val(Q)=1$ .

L’épithéorème 2 a deux corollaires importants.

Définition. Un système formel, dont un signe, disons $\sim$ , est interprété comme la négation est non contradictoire, s’il est impossible d’y démontrer à la fois $P$ et $\sim P$ .

Corollaire 1. La logique des propositions est non contradictoire.

Supposons, en effet, que $\vdash P$ . Alors, par l’épithéorème 2, on $\vdash_{1}\, P$ . Il s’ensuit que $\sim P$ n’a que que des 0 dans son évaluation et que $\sim\vdash_{1}\, P$ , c’est-à-dire que $P$ n’est pas une tautologie. Par contraposition, l’épithéorème 2, montre que $\sim\vdash\sim P$ , donc que $\sim P$ n’est pas un théorème.

Remarque

La contraposée d’un théorème de la forme « si $P$ alors $Q$ » est l’expression « si $\sim Q$ alors $\sim P$ ». Les deux formes sont logiquement équivalentes.

La définition de la non-contradiction exige que le système soit interprété. Qu’en est-il des systèmes purement formels ? Pour faire face à ce problème, on pose :

Définition. Un système est consistant, s’il possède au moins une ebf qui n’est pas un théorème.

Corollaire 2. Le système de la logique des propositions est consistant.

En effet, nous avons vu que $\vdash\left(p\supset p\right)$ . Par l’épithéorème 2, on $\vdash_{1}\, p\supset p$ . En conséquence $\sim\vdash_{1}\sim\left(p\supset p\right)$ et par la contraposée de l’épithéorème, $\sim\left(p\supset p\right)$ est un exemple d’ebf qui n’est pas un théorème.

Remarque

On peut prouver que si un système est non contradictoire, il est toujours consistant, mais que la réciproque n’est pas vraie. La condition de noncontradiction est donc « plus forte » que celle de consistance.

Epithéorème 3 : Si $\vdash_{1}\, P$ alors $\vdash\, P$ .

La marche de la preuve, qui est assez longue, est la suivante :

1) Démontrer que si $P^{*}$ est la fnc de $P$ , on a le métathéorème $\vdash P\equiv P^{*}$ .
2) Si $\vdash_{1}\, P^{*}$ alors chacune de ses disjonctions est aussi une tautologie. Si l’une d’elles ne l’était pas, il se pourrait en effet que la conjonction ne soit pas toujours vraie.
3) Démontrer $\vdash p\vee\sim p$ . Comme on a la règle dérivée $P\vdash P\vee Q$ , toute disjonction élémentaire sera un théorème. Mais comme on a aussi la règle dérivée $P$ , $Q\vdash P\wedge Q$ , toute fnc tautologique sera un théorème. Donc $\vdash\, P^{*}$
4) Démontrer que $P\equiv P^{*}\vdash P^{*}\supset P$ . Alors, par les points (1), (3) et (R1), il vient $\vdash\, P$ .

Cet épithéorème a aussi deux corollaires importants.

Définition. Un système interprété est complet au sens faible, si l’on peut y démontrer toutes les ebf qui correspondent à des vérités dans l’interprétation choisie.

Corollaire 1. Si l’on considère que toute tautologie est une vérité logique, le calcul des propositions est complet au sens faible.

L’épithéorème 3 dit, en effet, que toute tautologie est un théorème.

Mais il est de nouveau possible d’introduire une notion de complétude qui n’exige pas d’interpréter le système.

Définition. Un système est complet au sens fort, si l’adjonction à ses schémas d’axiomes d’un schéma d’ebf qui n’y est pas démontrable, le rend inconsistant.

Corollaire 2. Le système de la logique des propositions est complet au sens fort.

Soit en effet, un schéma d’ebf $P$ qui n’est pas démontrable. Posons (A4) $P$ . Soit de nouveau $P^{*}$ la \textsc{fnc} de $P$ . Nous aurons $\vdash P\equiv P^{*}$ et par (A4) et (R1), il viendra $\vdash\, P^{*}$ et par l’épithéorème 3, $P^{*}$ est une tautologie. Par ailleurs, puisque par hypothèse $\sim\vdash P$ , $P^{*}$ doit contenir au moins une disjonction qui ne contient pas un atome et sa négation, disons qui ne contient pas $p$ et $\sim p$ . Soit $D$ =df $Q_{1}\vee\text{\ldots}\vee Q_{n}$ cette disjonction.

Comme on a la règle dérivée $P\wedge Q\vdash Q$ on aura en particulier $P^{*}\vdash D$ ( $P^{*}$ est une conjonction qui, entre autres facteurs, contient $D$ ). Et comme on a $P^{*}$ , par (R1) on a $\vdash D$ , soit $\vdash Q_{1}\vee\text{\ldots}\vee Q_{n}$ . Les $Q_{i}$ ( $i$ = 1, 2, …, $k$ ) sont soit des atomes, soit la négation d’un atome.

Si $Q_{1}$ est un atome qui n’est pas précédé d’une négation, substituons-lui $p$ . Si $Q$ est un atome précédé d’une négation, substituons-lui $\sim p$ . En éliminant les doubles négations, on aura $\vdash p\vee\text{\ldots}\vee p$ et donc $\vdash p$ .

Un raisonnement analogue montre qu’on peut aussi obtenir $\vdash\sim p$ . En conséquence le système est contradictoire. Mais il est aussi inconsistant, par la règle : $P$ , $\sim P\vdash Q$ .

Remarque

La terminologie utilisée laisse entendre, ce qu’on peut démontrer, qu’un système peut être complet au sens faible sans l’être au sens fort (V. 2.4).

Si l’on réunit les épithéorèmes 2 et 3, on est conduit à :

Epithéorème 4 : $\vdash P$ si et seulement si $\vdash_{t}P$ .

Il en découle aussi un corollaire intéressant.

Définition. Un système est décidable si, étant donné une de ses ebf quelconque, il existe un algorithme qui permet de décider si cette ebf est un théorème du système ou non.

Corollaire. Le système de la logique des propositions est décidable.

L’algorithme est le suivant. Soit $P$ l’ebf donnée, on calcule son évaluation.

Si elle ne contient que des 1, alors $\vdash_{t}P$ et $\vdash P$ . Sinon $\sim\vdash_{t}P$ et $\sim\vdash P$ .

Remarques

1. Nous avons donné trois présentations de la logique des propositions : par les règles de déduction, par les tables de vérité et par une axiomatisation. Les tables de vérité fournissent les manipulations les plus aisées. Malheureusement, elles ne peuvent s’étendre à la logique des prédicats. C’est la présentation axiomatique qui conduit aux manipulations les plus difficiles. Il y faut souvent beaucoup de pratique et d’imagination. C’est toutefois elle qui se prête le mieux à la réflexion sur la logique. Enfin la méthode de la déduction naturelle est celle qui est généralisable et qui semble la plus commode à utiliser.
2. Les raisonnements de ce paragraphe manquent de rigueur. Il ne faut les tenir que pour des indications, propres tout au plus à faire pressentir le genre de démarches auxquelles conduit ce qu’on appelle la métalogique (V. la bibliographie).

La négation

Notation pour les ensembles

JR01

L'ordinateur. Oscar d'or 1970

Toutes directions

Algotaf

Détour de maths

Helpman

Le blog de Mathilde

Philo en terminale

Scilicet

Le site de Sacha

Time protocole (entp)

Archives radio

Quelques propriétés de la logique des propositions