Les tautologies

Les tables précédentes permettent d’évaluer n’importe quelle proposition moléculaire $P$ dont les atomes sont composés par les opérateurs $\thicksim$ , $\wedge$ , $\vee$ , $\doublevee$ , $\supset$ et $\equiv$ que nous venons de définir. Si $P$ contient deux atomes, il y aura $2^{2}=4$ éventualités à examiner.

Exemple

$P$ = $df$ $p\supset(p\vee q)$

On a, en disposant les calculs en ligne :
$\begin{tabular}{l|cccc} $p$ & 1 & 1 & 0 & 0\tabularnewline $q$ & 1 & 0 & 1 & 0\tabularnewline \hline $\thicksim p$ & 0 & 0 & 1 & 1\tabularnewline $p\vee q$ & 1 & 1 & 1 & 0\tabularnewline \hline $\thicksim p\supset\left(p\vee q\right)$ & 1 & 1 & 1 & 0\tabularnewline \end{tabular}$

Si $P$ contient trois atomes, on aura $2^{3}=8$ éventualités à étudier, ce que nous ferons en adoptant l’ordre canonique qui figure dans l’exemple suivant :

Exemple

$\left(p\vee q\right)\supset\thicksim\left(q\wedge m\right)$ $\begin{tabular}{r|cccccccc} $p$ & 1 & 1 & 1 & 1 & 0 & 0 & 0 & 0\tabularnewline $q$ & 1 & 1 & 0 & 0 & 1 & 1 & 0 & 0\tabularnewline $m$ & 1 & 0 & 1 & 0 & 1 & 0 & 1 & 0\tabularnewline \hline $p\vee q$ & 1 & 1 & 1 & 1 & 1 & 1 & 0 & 0\tabularnewline $q\wedge m$ & 1 & 0 & 0 & 0 & 1 & 0 & 0 & 0\tabularnewline $\thicksim\left(q\wedge m\right)$ & 0 & 1 & 1 & 1 & 0 & 1 & 1 & 1\tabularnewline \hline $\left(p\vee q\right)\supset\thicksim\left(q\wedge m\right)$ & 0 & 1 & 1 & 1 & 0 & 1 & 1 & 1\tabularnewline \end{tabular}$

D’une façon générale, si $P$ contient les $n$ atomes $p_{1}$ , $p_{2}$ , $\text{\ldots}$ , $p_{n}$ , il faudra envisager $2^{n}$ éventualités. Nous adopterons l’ordre canonique suivant. Les atomes étant ordonnés une fois pour toutes (pratiquement, on choisit l’ordre alphabétique), on écrit les suites :

$p_{1}:\frac{2^{n}}{2}$ valeurs 1, suivies de $\frac{2^{n}}{2}$ valeurs 0 ;

$p_{2}:\frac{2^{n}}{4}$ valeurs 1, suivies de $\frac{2^{n}}{4}$ valeurs 0, suivies de $\frac{2^{n}}{4}$ valeurs 1, suivies de $\frac{2^{n}}{4}$ valeurs 0 ;

$p_{3}:\frac{2^{n}}{8}$ valeurs 1, suivies de $\frac{2^{n}}{8}$ valeurs 0, etc.

$p_{n}:$ une suite alternée d e1 et de 0.

Les calculs deviennent assez rapidement fastidieux, mais ils n’offrent jamais de difficultés de principe et, à toute proposition composée de $n$ atomes, on sait faire correspondre une suite ordonnée de $2^{n}$ valeurs 1 et 0.

Exemples $\begin{tabular}{rcl} à $p$ & correspond la suite & 1 0\tabularnewline à $\thicksim p$ & la suite & 0 1\tabularnewline à $p\wedge q$ & la suite & 1 0 0 0 \tabularnewline à $\left(p\vee q\right)\supset\thicksim\left(q\wedge m\right)$ & la suite & 0 1 1 1 0 1 1 1 \tabularnewline \end{tabular}$

Remarque

L’introduction d’un ordre canonique permet de donner l’évaluation d’une proposition $P$ sans préciser chaque fois à quelles valeurs des atomes correspondent les 1 et les 0 de $P$ . Ainsi, pour $p\wedge q$ par exemple, on peut se contenter de donner le quadruple (1 0 0 0).

Répartissons les évaluations en trois catégories, selon (1) qu’il y figure des 1 et des 0 (2) qu’il n’y figure que des 1 et (3) qu’il n’y figure que des 0. Il existe des propositions qui correspondent à chacune de ces catégories. Toutes celles que nous venons de voir sont des exemples de la première. Comme le montrent les calculs suivants $p\vee\thicksim p$ , $p\supset\left(q\supset p\right)$ sont des exemples de la deuxième et $p\vee\thicksim p$ , $p\wedge\thicksim\left(p\vee q\right)$ des exemples de la troisième.

Calculs $\begin{tabular}{ccc} \begin{tabular}{r|cc} \multicolumn{3}{c}{$p\vee\thicksim p$}\tabularnewline $p$ & 1 & 0\tabularnewline $\thicksim p$ & 0 & 1\tabularnewline \hline $p\vee\thicksim p$ & 1 & 1\tabularnewline \end{tabular} & \hspace{1cm} & % \begin{tabular}{r|cccc} \multicolumn{5}{c}{$p\supset\left(q\supset p\right)$}\tabularnewline $p$ & 1 & 1 & 0 & 0\tabularnewline $q$ & 1 & 0 & 1 & 0\tabularnewline \hline $q\supset p$ & 1 & 1 & 0 & 1\tabularnewline \hline $p\supset\left(q\supset p\right)$ & 1 & 1 & 1 & 1\tabularnewline \end{tabular}\tabularnewline \begin{tabular}{r|cc} \multicolumn{3}{c}{$p\wedge\thicksim p$}\tabularnewline $p$ & 1 & 0\tabularnewline $\thicksim p$ & 0 & 1\tabularnewline \hline $p\wedge\thicksim p$ & 0 & 0\tabularnewline \end{tabular} & & % \begin{tabular}{r|cccc} \multicolumn{5}{c}{$p\wedge\thicksim\left(p\vee q\right)$}\tabularnewline $p$ & 1 & 1 & 0 & 0\tabularnewline $q$ & 1 & 0 & 1 & 0\tabularnewline \hline $p\vee q$ & 1 & 1 & 1 & 0\tabularnewline \hline $\thicksim\left(p\vee q\right)$ & 0 & 0 & 0 & 1\tabularnewline \hline $p\supset\left(q\supset p\right)$ & 0 & 0 & 0 & 0\tabularnewline \end{tabular}\tabularnewline \end{tabular}$

Toute proposition dont l’évaluation ne contient que des 1 est une tautologie et toute proposition dont l’évaluation ne contient que des 0 est une contradiction. Il est clair que si $P$ est une tautologie, $\thicksim P$ sera une contradiction et réciproquement. D’autre part, puisque une proposition atomique $p$ prend soit la valeur 1 soit la valeur 0, seules des propositions moléculaires peuvent être des tautologies ou des contradictions. Si $P$ est une tautologie, nous écrirons $\vdash P$ .

Remarques

1. Affirmer, comme nous venons de le faire, qu’une proposition atomique, ne peut être ni une tautologie, ni une contradiction, c’est s’appuyer sur une décision propre au système logique construit et non pas constater un fait d’expérience. La proposition « les célibataires sont des gens mariés » est atomique, en ce sens qu’elle ne contient aucun des opérateurs précédents et elle exprime cependant une contradiction. Toutefois, on sait que, analysée dans la logique des prédicats, elle s’écrira :

$\left(\forall x\right)\left(\thicksim ax\supset ax\right)$ où $ax$ =df $x$ est marié et où être célibataire =df être non marié.

Cette divergence repose sur le fait que « être une expression atomique » n’a pas le même sens dans la logique des propositions et dans celle des prédicats.

2. Nous avons utilisé le même signe $\vdash$ pour dire qu’une proposition était une tautologie et pour dire qu’elle était un théorème (I, p. 21). Il est possible, en prenant des exemples, de s’assurer que si $P$ est un théorème alors $P$ est une tautologie et réciproquement. Toutefois la pratique qui consiste à écrire dans les deux cas $\vdash P$ exigerait la démonstration d’un épi-théorème. Une telle démonstration, si elle se voulait rigoureuse, sortirait du propos de cet ouvrage, mais nous y reviendrons cependant en 1.7.

3. Puisqu’une tautologie est vraie, quelles que soient les valeurs de ses atomes, on peut de nouveau dire qu’elle est « vraie dans tous les mondes possibles ». Elle ne fournit ainsi aucune information sur le monde lui-même.

Exemple

« Il y a des hommes sur la planète Mars ou il n’y a pas d’hommes sur la planète Mars », soit $p\vee q$ , ne nous renseigne absolument pas sur la planète en question.

On dit volontiers pour cela que les tautologies sont vides de sens. En fait, elles expriment des lois logiques en explicitant la façon dont les opérateurs ont utilisés.

Il est de nouveau possible de définir les relations d’implication et d’équivalence entre propositions. Nous poserons encore :

$\begin{tabular}{rccccc} $P$ implique $Q$ & =df & $P\rightarrow Q$ & =df & $\vdash P\supset Q$ & (I, p. 26).\tabularnewline $P$ est équivalente à $Q$ & =df & $P\leftrightarrow Q$ & =df & $\vdash P\equiv Q$ & ( I, p. 27).\tabularnewline \end{tabular}$

La relation d’équivalence permet d’énoncer les principales propriétés des opérateurs que nous avons introduits jusqu’ici. Pour les vérifier, il suffit de remplacer toute expression de la forme $P\leftrightarrow Q$ par $\vdash P\equiv Q$ et de s’assurer par le calcul que cette dernière proposition est bien une tautologie. Nous avons :
(0) $\thicksim\thicksim p \longleftrightarrow p$ , {\em principe de la double négation} ;
(1) les opérations $\wedge$ , $\vee$ , $\vee\negthickspace\vee$ et $\equiv$ {\em sont commutatives} : $p\vee q \leftrightarrow q\vee p$ , $p\wedge q \leftrightarrow q\wedge p$ , $p\vee\negthickspace\negthickspace\vee q \leftrightarrow q\vee\negthickspace\negthickspace\vee p$ , $p\equiv q \leftrightarrow q\equiv p$ ;

(2) Elles sont {\em associatives}
$(p\wedge q)\wedge m\leftrightarrow p\wedge(q\wedge m)$ , $p\vee\left(q\vee m\right)\leftrightarrow\left(p\vee q\right)\vee m$
$(p\vee\negthickspace\negthickspace\vee q)\vee\negthickspace\negthickspace\vee m\leftrightarrow p\vee\negthickspace\negthickspace\vee(q\vee\negthickspace\negthickspace\vee m)$ , $p\equiv\left(q\equiv m\right)\leftrightarrow\left(p\equiv q\right)\equiv m$ ;

3. Les opérations $\wedge$ et $\vee$ sont {\em idempotentes} :
$p\vee p \leftrightarrow p$ , $p\wedge p \leftrightarrow p$ ;
4. Les opérations $\wedge$ et $\vee$ sont {\em distributives} l’une par rapport à l’autre :\\
$p\wedge\left(q\vee m\right)\leftrightarrow\left(p\wedge q\right)\vee\left(p\wedge m\right)$ \\
$p\vee\left(q\wedge m\right)\leftrightarrow\left(p\vee q\right)\wedge\left(p\vee m\right)$

L’opération $\supset$ ne jouit d’aucune des trois premières propriétés et l’opération~ $\equiv$ n’est pas idempotente~ : $p\equiv p$ est une tautologie.

Remarque

Une expression comme $p\wedge q\leftrightarrow q\wedge p$ n’est pas homogène. En signes $p$ , $q$ et $\wedge$ font partie du système que nous étudions. Mais le $\leftrightarrow$ est une abréviation de la langue de communication. Il sert à dire : « est équivalente à ». Ce fait nous a permis d’économiser les parenthèses où, pour éviter des confusions, il faudrait écrire $\vdash\left(p\wedge q\right)\equiv\left(q\wedge p\right)$ puisque $\equiv$ est aussi un signe du calcul, nous avons pu nous contenter d’écrire $p\wedge q\leftrightarrow q\wedge p$ . Nous utiliserons systématiquement cette pratique dans ce qui suit.

La relation d’équivalence permet aussi de montrer que les opérateurs définis par les tables qui précèdent ne sont pas indépendants les uns des autres. Ainsi on aura :
$\begin{tabular}{ccccccc} $\vdash\left(p\wedge q\right)$ & $\equiv$ & $\thicksim\left(\sim p\vee\sim q\right)$ & soit & $\left(p\wedge q\right)$ & $\leftrightarrow$ & $\thicksim\left(\sim p\vee\sim q\right)$\tabularnewline $\vdash\left(p\vee q\right)$ & $\equiv$ & $\thicksim\left(\sim p\wedge\sim q\right)$ & soit & $\left(p\vee q\right)$ & $\leftrightarrow$ & $\thicksim\left(\sim p\wedge\sim q\right)$\tabularnewline $\vdash\left(p\vee\negthickspace\negthickspace\vee q\right)$ & $\equiv$ & $\left(\left(p\vee q\right)\wedge\sim\left(p\wedge q\right)\right)$ & soit & $\left(p\vee\negthickspace\negthickspace\vee q\right)$ & $\leftrightarrow$ & $\left(\left(p\vee q\right)\wedge\sim\left(p\wedge q\right)\right)$\tabularnewline \end{tabular}$

Les deux premières équivalences correspondent aux lois de Morgan (I. p38). Assurons-nous de la troisième~ : \label{De_Morgan}

$\begin{tabular}{r|cccc} $p$ & 1 & 1 & 0 & 0\tabularnewline $q$ & 1 & 0 & 1 & 0\tabularnewline \hline $p\vee\negthickspace\negthickspace\vee q$ & 0 & 1 & 1 & 0\tabularnewline $p\vee q$ & 1 & 1 & 1 & 0\tabularnewline $p\wedge q$ & 1 & 0 & 0 & 0\tabularnewline $\thicksim\left(p\wedge q\right)$ & 0 & 1 & 1 & 1\tabularnewline $\left(p\vee q\right)\wedge\sim\left(p\wedge q\right)$ & 0 & 1 & 1 & 0\tabularnewline \hline Proposition & 1 & 1 & 1 & 1\tabularnewline \end{tabular}$

On aura encore : $p\supset q\leftrightarrow\sim p\vee q\leftrightarrow\sim\left(p\wedge\sim q\right)$ \\ et $p\equiv q\leftrightarrow\left(p\supset q\right)\wedge\left(q\supset p\right)$ .

Introduisons enfin un nouvel opérateur $\mid$ tel que $p\mid q$ s’interprète comme « pas à la fois $p$ et $q$ ».

Cela conduit à poser la table :

$\begin{tabular}{|c|c||c|} \hline $p$ & $q$ & $p\mid q$\tabularnewline \hline 0 & 0 & 1 \tabularnewline 0 & 1 & 1 \tabularnewline 1 & 0 & 1 \tabularnewline 1 & 1 & 0 \tabularnewline \hline \end{tabular}$

Il est facile de s’assurer que l’on a alors les équivalences suivantes :

$\thicksim p\leftrightarrow p\mid p$ \qquad{} $p\vee q\leftrightarrow\left(p\mid p\right)\mid\left(q\mid q\right)$ \qquad{} $p\wedge q\leftrightarrow\left(p\mid q\right)\mid\left(p\mid q\right)$ .

Remarque

L’opérateur $\downarrow$ dont l’évaluation est (0 0 0 1) conduit aux équivalences :

$\sim p\leftrightarrow p\downarrow p$ \qquad{} $p\vee q\leftrightarrow\left(p\downarrow q\right)\downarrow\left(p\downarrow q\right)$ \qquad{} $p\wedge q\leftrightarrow\left(p\downarrow p\right)\downarrow\left(q\downarrow q\right)$ .

On voit ainsi qu’un seul opérateur, soit $\mid$ , soit $\downarrow$ , permet de définir tous les autres par des équivalences.

Bien que représentant des lois logiques, les tautologies ne permettent pas d’effectuer des déductions. Toutefois, si une déduction est effectuée, elles permettent de s’assurer de sa correction.

Exemple

« Ceux qui veulent la paix préparent la guerre. Vous ne préparez pas la guerre, donc vous ne voulez pas la paix ».

Nous poserons :

$\begin{tabular}{ccl} $p$ & =$df$ & vouloir la paix\tabularnewline $q$ & =$df$ & préparer la guerre\tabularnewline \end{tabular}$

Le raisonnement part des deux prémisses $p\supset q$ et $\sim q$ et il conclut $\sim p$ . Il suffit de voir si la conjonction des prémisses implique la conclusion, donc si $\left(p\supset q\right)\wedge\sim q\rightarrow\sim p$ ou encore si $\vdash\left(\left(p\supset q\right)\wedge\sim q\right)\supset\sim p$ .
C’est bien le cas, ce qui montre tout à la fois que le raisonnement est correct et qu’il ne suffit pas d’être logique pour faire le bonheur des peuples.