calcul des propositions (suite)

Le tableau ci-contre fournit la liste exhaustive de toutes les applications possibles. On remarquera que les seize applications ainsi obtenues sont arrangées de telle sorte que l’on peut passer de f_i à f_17–i par l’opérateur de négation. On passe de f₃, par exemple, à f₁₄ en remplaçant les 1 par des 0 et réciproquement.

On retrouve naturellement les foncteurs déjà étudiés. Ainsi, f₂ fournit la table de p ⋀ q, f₈ celle de p ≡ q, f₉ celle de f₁₂ celle de p ⋁ q et f₁₄ celle de p ⊃ q. f₁₅ est l’incompatibilité que l’on note généralement p | q et que l’on peut lire « pas à la fois p et q » ; c’est donc une non-conjonction. Les autres foncteurs n’ont pas de non bien fixé, mais leur ensemble permet une remarque fondamentale.

L’ensemble π de toutes les propositions composées de deux atomes p et q est un ensemble infini dénombrable, puisqu’il est possible de réitérer l’un et l’autre des atomes autant de fois que l’on veut. Mais, en même temps, la table de vérité d’une telle proposition sera nécessairement l’un des seize quadruples ordonnés de la forme (a b c d), où a, b, c, d ∈ {1, 0}. En conséquence, il existe une partition de π en seize classes. Celles-ci sont d’ailleurs des classes d’équivalence, par la relation d’équivalence ↔ ci-dessus. Soit, pour prendre un exemple, les deux propositions

Elles ont toutes deux la table (1 0 1 1). Formons alors la biconditionnelle Comme on le voit, il s’agit d’une tautologie : et l’on a bien par définition

Désignons par [1 0 1 1] la classe de toutes les propositions qui ont la table de vérité (1 0 1 1). On pourra aussi désigner cette classe par [p ⊃ q], par etc., c’est-à-dire par la mise entre crochets d’une proposition quelconque qui lui appartient, proposition qui est alors considérée comme un représentant de la classe d’équivalence tout entière. Cela va permettre d’ordonner les seize classes.

Posons pour cela

Donc la classe qui contient P est « plus petite ou égale » à la classe qui contient Q si et seulement si la proposition qui représente la première classe implique celle qui représente la seconde. Comme tous les éléments de la classe [P] sont équivalents entre eux et qu’il en va de même pour tous ceux de la classe [Q], on pourrait dire aussi que si et seulement si tout élément de [P] implique tout élément de [Q].

Les seize classes s’ordonnent alors selon le diagramme suivant. Tout élément qui est situé à un niveau supérieur ou au niveau d’un autre élément est plus grand (au sens de la relation ) que ce second élément. Les connexions, lues de bas en haut, marquent donc la relation . Comme celle-ci est transitive, il est superflu d’indiquer toutes les connexions. Ainsi, puisque et que il s’ensuit nécessairement ce qui suit : que Cela signifie, il faut le noter particulièrement, que soit encore que Notons enfin qu’à toute classe marquée en rouge correspond, par l’opérateur de négation, une classe marquée en vert et que les représentants des classes, s’ils n’ont pas de signes spéciaux, ont été choisis en fonction des remarques du paragraphe suivant.

Remarques.

1. La classe [1 1 1 1] contient toutes les tautologies, et sa complémentaire [0 0 0 0] toutes les contradictions.

2. La classe [1 1 0 0] pourrait se désigner par [p (q)], que l’on pourrait lire « p abstraction faite de q ». On aurait des symboles analogues pour [1 0 1 0] soit [q (p)], [0 0 1 1] soit

D’un point de vue algébrique, nous sommes en présence d’un ensemble E de seize éléments. Cet ensemble est muni d’une relation d’ordre. Soit x, y et z des variables sur E. À tout x et à tout y, on peut faire correspondre un et un seul élément qui est le plus petit élément qui les domine tous deux. C’est leur supremum.

Exemples. est le supremum de
[p | q] est le supremum de

D’une façon analogue, à tout x et à tout y, on peut faire correspondre un et un seul élément qui est le plus grand élément qu’ils dominent tous deux. C’est leur infimum.

Exemples. [p ≡ q] est l’infimum de [q ⊃ p] et de [p ⊃ q].
[p ⋀ q] est l’infimum de [p ⊃ q] et de [p ⋀ q].

Cela suffit à montrer que E est muni de la structure de treillis. Mais il y a plus. Introduisons les deux opérations suivantes entre les éléments de E :
[P] ⋃ [Q] = df [P ⋁ Q] et [P] ⋂ [Q] = df [P ⋀ Q].
On montre alors que le treillis est distributif c’est-à-dire que
x ⋂ (y ⋃ z) = (x ⋂ y) ⋃ (x ⋂ z)
et x ⋃ (y ⋂ z) = (x ⋃ y) ⋂ (x ⋃ z).
Enfin, quel que soit x, on peut trouver y tel que
x ⋃ y = [1 1 1 1] et x ⋂ y = [0 0 0 0].
Par exemple,

Le treillis est complémenté. Ces conditions conduisent, par définition, à affirmer que l’on a affaire à un treillis booléen.

Il serait évidemment possible d’étudier d’une façon analogue les foncteurs unaires en les traitant comme des applications f : V → V. On trouverait quatre foncteurs distincts et f₃ correspondrait à la négation. Les classes d’équivalence engendrées par ces foncteurs peuvent aussi être organisées en un treillis booléen.

Quant aux foncteurs à plus de deux arguments, il est superflu de les introduire, dans la mesure où il est possible d’en rendre compte avec les précédents.

Formes normales

Comme on peut le voir sur le diagramme précédent, toute proposition qui appartient à une classe de niveau n a tout juste n valeurs 1 dans sa table de vérité. Cela permet de dire que toute proposition composée de deux atomes est équivalente à une disjonction dans laquelle figurent une ou plusieurs des conjonctions élémentaires Ainsi, p ≡ q, par exemple, a une table qui contient 1 en première et en quatrième place. On pourra donc écrire :

La notion de conjonction élémentaire s’étend à un nombre quelconque k de propositions atomiques. Chacune comporte les k atomes, soit sous forme d’affirmation, soit sous forme de négation. Ainsi, si k = 3, sont deux des 2³ conjonctions élémentaires possibles. Dès lors, à toute proposition moléculaire P correspond une disjonction de conjonctions élémentaires qui lui est équivalente et qu’on nomme sa forme normale disjonctive complète.