Grande Encyclopédie Larousse 1971-1976Éd. 1971-1976
C

calcul des propositions (suite)

Propriétés principales des foncteurs

Le calcul des propositions, quelle que soit sa présentation, conduit à reconnaître un certain nombre de propriétés aux divers foncteurs. Voici les plus importants.
(1) ⋁ et ⋀ a sont commutatifs :
(P ⋁ Q) ↔ (Q ⋁ P) (P ⋀ Q)) ↔ (Q ⋀ P).
(2) ⋁ et ⋀ sont associatifs :
(P ⋁ (Q ⋁ M)) ↔ ((P ⋁ Q) ⋁ M)
(P ⋀ (Q ⋀ M)) ↔ ((P ⋀ Q) ⋀ M).
(3) ⋁ et ⋀ sont idempotents :
(P ⋁ P) ↔ P (P ⋀ P) ↔ P.

Remarques.
Le foncteur de la Inconditionnelle ≡ est aussi commutatif et associatif. Il n’est pas idempotent, et le foncteur de la conditionnelle ne jouit d’aucune de ces propriétés.
(4) ⋁ et ⋀ sont distributifs l’un par rapport à l’autre :
(P ⋁ (Q ⋀ M)) ↔ ((P ⋁ Q) ⋀ (P ⋁ M))
(P ⋀ (Q ⋁ M)) ↔ ((P ⋀ Q) ⋁ (P ⋀ M))

On retrouve enfin les « principes » de la logique traditionnelle :
(5) P ↔ P
principe d’identité.

principe de la non-contradiction.

principe du tiers exclu.

principe de la double négation.


Syntaxe et sémantique

Nous avons présenté le calcul des propositions de trois façons : par les tables de vérité, à l’aide de règles de déduction et sous la forme d’un système axiomatique. Chaque fois, cependant, nous avons donné une signification bien déterminée aux signes utilisés : p, q, ... représentaient des propositions, 1 et 0 le vrai et le faux, la négation, ⋀ la conjonction, ⋁ la disjonction, etc. En d’autres termes, nous avons adopté un point de vue sémantique. On peut toutefois remarquer que, une fois les tables de 1 et de 0 posées, une fois les règles et les axiomes (ou les schémas d’axiomes) donnés, il est possible de calculer sans se référer à la signification des divers signes utilisés. Faire ainsi abstraction de l’interprétation des signes et ne retenir que la façon de les manipuler, c’est se placer au point de vue syntaxique.

Supposons que p, q, ... représentent des interrupteurs électriques et que val (p) = 1 signifie « l’interrupteur p est fermé », tandis que val (p) = 0 signifie « l’interrupteur p est ouvert ». Comme le montrent les figures suivantes, la table de p ⋀ q, c’est-à-dire (1 0 0 0), est représentée par un montage de p et de q en série, tandis que la table de p ⋁ q, soit (1 1 1 0), est représentée par un montage en parallèle.

Dans le premier cas, le courant ne passe dans le circuit que si p et q sont fermés, donc si val (p) = val (q) = 1. Dans le second cas, le courant ne passe pas dans le circuit si val (p) = val (q) = 0. L’opérateur pourrait se réaliser à l’aide d’un électro-aimant. Si val (p) = 1, alors et réciproquement.

Il est clair que les ordinateurs n’utilisent pas d’interrupteurs mécaniques. Leurs fonctions logiques n’en reposent pas moins sur une interprétation électrique du calcul des propositions.


Propriétés du calcul

Chaque fois que l’on s’est donné un calcul, il est possible de le considérer comme un objet et d’en dégager certaines propriétés. Celles-ci doivent naturellement être établies par des raisonnements convenables. Elles donnent donc lieu à des « théorèmes » qui portent sur le système lui-même et que nous appellerons en conséquence des épithéorèmes. Nous allons énoncer quelques épithéorèmes du calcul des propositions et, éventuellement, esquisser leurs preuves. Nous admettrons que les deux notions de théorème, celle qui découle des règles de déduction et celle qui est définie à partir des schémas d’axiomes, se recouvrent.


Épithéorème 1

Si P est un théorème, P est une tautologie, donc si ⊩ P alors ⊢ P.

Dire que P est un théorème, c’est dire que P résulte des schémas d’axiomes par application de la règle R. Mais il est facile de voir que, quelles que soient les valeurs que l’on attribue aux variables syntaxiques des schémas d’axiomes, la proposition qui en résulte est une tautologie.

Exemple. Prenons A ⊩ P ⊃ (Q ⊃ P). La proposition qui prendra la place de P sera vraie ou fausse. Il en ira de même pour la proposition qui prendra la place de Q. On aura donc la table de vérité ci-contre, qui montre que P ⊃ (Q ⊃ P) est bien un schéma de tautologie.

Quant à la règle R, elle ne s’applique qu’à des expressions qui sont des tautologies. Donc ses prémisses P ⊃ Q et P sont des propositions vraies, et la table de ⊃ fait voir que Q est alors nécessairement vraie.


Corollaire 1

Si P est un théorème, n’est pas un théorème. Dire, en effet, que P est un théorème, c’est dire que P est une tautologie. Donc a toujours la valeur 0 et, par contraposition de l’épithéorème 1, n’est pas un théorème.

Par définition, on dit que le calcul est non contradictoire ou aussi sémantiquement consistant.


Corollaire 2

Il existe au moins une ebf qui n’est pas un théorème, ce qu’on traduit en disant que le calcul est (syntaxiquement) consistant.

En effet, nous avons vu que ⊩ p ⊃ p. Donc, par le corollaire 1, n’est pas un théorème.


Épithéorème 2

Si P est une tautologie, P est un théorème, donc si ⊢ P alors ⊩ P.

La preuve comporte plusieurs étapes, dont voici le principe :
(1) On remplace P par sa forme normale conjonctive complète P*. On sait qu’elle lui est équivalente donc ⊩ P* ≡ P ;
(2) Puisque, par hypothèse, P est une tautologie, P* en est aussi une. Mais, pour qu’une conjonction soit vraie, chaque facteur doit être vrai. Or, ces facteurs sont formés de disjonctions, et, pour que chacune d’elles soit vraie, il faut qu’elle comporte au moins une proposition p et sa négation Mais on sait que est un théorème du calcul. Il en va de même de Il est donc possible de démontrer séparément chacune des disjonctions de P et, par la règle ⋀i, de démontrer P* ;
(3) Puisque, de plus, P* ↔ P et que ⊩ P*, on aura aussi ⊩ P.


Corollaire 1

Le calcul est sémantiquement complet ou encore complet au sens faible, en ce sens que toute « vérité logique ». comprise comme « expression tautologique », y est démontrable.