En logique, un connecteur logique est un opérateur booléen utilisé dans le calcul des propositions.

Comme dans toute approche logique, il faut distinguer un aspect syntaxique et un aspect sémantique.

Syntaxe

D'un point de vue syntaxique, les connecteurs sont des opérateurs dans un langage formel pour lesquels un certain nombre de règles définissent leur usage^[1], au besoin complétées par une sémantique.

Sémantique

Logique classique

Si l'on se place dans la logique classique, l'interprétation des variables se fait dans les booléens ou dans une extension multivalente^[2] de ceux-ci.

Table des connecteurs logiques. (organisés par valeur de vérité)

Connecteurs logiques organisés en un diagramme de Hasse.

Dans le cas de la logique bivalente classique le tableau suivant recense les seize fonctions booléennes associées aux entrées P et Q, ces entrées sont les variables ou prémisses des formules.

Fonction booléenne	Notations	Formules équivalentes	Table de vérité	Diagramme de Venn
Proposition P	P		Q 0 1 P 0   0 0 1   1 1
Proposition Q	Q		Q 0 1 P 0   0 1 1   0 1
Négation de P	¬P ~P		Q 0 1 P 0   1 1 1   0 0
Négation de Q	¬Q ~Q		Q 0 1 P 0   1 0 1   1 0
Disjonction (OU)	P ${\displaystyle \lor }$ Q P ∨ Q P OR Q	P ${\displaystyle \leftarrow }$ ¬Q ¬P → Q ¬P ↑ ¬Q	Q 0 1 P 0   0 1 1   1 1
Conjonction (ET)	P ${\displaystyle \wedge }$ Q P & Q P · Q P AND Q	P ${\displaystyle \not \rightarrow }$¬Q ¬P ${\displaystyle \not \leftarrow }$ Q ¬P ${\displaystyle \downarrow }$ ¬Q	Q 0 1 P 0   0 0 1   0 1
Disjonction réciproque (NON-OU)	P ↓ Q P NOR Q	P ${\displaystyle \not \leftarrow }$ ¬Q ¬P ${\displaystyle \not \rightarrow }$ Q ¬P ${\displaystyle \wedge }$ ¬Q	Q 0 1 P 0   1 0 1   0 0
NON-ET	P ↑ Q P | Q P NAND Q	P → ¬Q ¬P ← Q ¬P ${\displaystyle \lor }$ ¬Q	Q 0 1 P 0   1 1 1   1 0
Contradiction	${\displaystyle \bot }$FALSE	P ${\displaystyle \wedge }$ ¬P	Q 0 1 P 0   0 0 1   0 0
Tautologie	${\displaystyle \top }$TRUE	P ${\displaystyle \vee }$ ¬P	Q 0 1 P 0   1 1 1   1 1
Implication	P → Q P ${\displaystyle \supset }$ Q	P ↑ ¬Q ¬P ${\displaystyle \lor }$ Q ¬P ← ¬Q	Q 0 1 P 0   1 1 1   0 1
Implication réciproque	P ${\displaystyle \leftarrow }$ Q P ${\displaystyle \subset }$ Q	P ${\displaystyle \lor }$ ¬Q ¬P ↑ Q ¬P → ¬Q	Q 0 1 P 0   1 0 1   1 1
Non-implication	P ${\displaystyle \not \rightarrow }$ Q P ${\displaystyle \not \supset }$ Q	P ${\displaystyle \wedge }$ ¬Q ¬P ↓ Q ¬P ${\displaystyle \not \leftarrow }$ ¬Q	Q 0 1 P 0   0 0 1   1 0
Non-implication réciproque	P ${\displaystyle \not \leftarrow }$ Q P ${\displaystyle \not \subset }$ Q	P ↓ ¬Q ¬P ${\displaystyle \wedge }$ Q ¬P ${\displaystyle \not \rightarrow }$ ¬Q	Q 0 1 P 0   0 1 1   0 0
Équivalence	P ${\displaystyle \leftrightarrow }$ Q P ≡ Q P ${\displaystyle \odot }$ Q P XNOR Q P IFF Q	P ${\displaystyle \not \leftrightarrow }$ ¬Q ¬P ${\displaystyle \not \leftrightarrow }$ Q ¬P ${\displaystyle \leftrightarrow }$ ¬Q	Q 0 1 P 0   1 0 1   0 1
Disjonction exclusive (OU exclusif)	P ${\displaystyle \not \leftrightarrow }$ Q P ${\displaystyle \not \equiv }$ Q P ${\displaystyle \oplus }$ Q P XOR Q	P ${\displaystyle \leftrightarrow }$ ¬Q ¬P ${\displaystyle \leftrightarrow }$ Q ¬P ${\displaystyle \not \leftrightarrow }$ ¬Q	Q 0 1 P 0   0 1 1   1 0

Systèmes complets de connecteurs

En logique classique, avec le tiers exclu, la sémantique est donnée (via le théorème de complétude du calcul propositionnel) par les tables de vérité.

Une logique p-valente possède ${\displaystyle p^{(p^{n})}}$ connecteurs n-aires. Cela correspond aux nombres de formules distinctes (c'est-à-dire deux à deux non équivalentes) que l'on peut écrire avec n propositions atomiques distinctes (p₁, p₂, ... p_n) dans une logique p-valente.

La logique bivalente usuelle a donc ${\displaystyle 2^{(2^{n})}}$ connecteurs n-aires.

Ces logiques ont donc une infinité de connecteurs, pris indépendamment de leur arité.

On appelle « système complet de connecteur » un ensemble de connecteurs d'une logique qui suffit à définir tous les autres^[3].

Pour la logique propositionnel classique, les connecteurs usuels que sont la négation, la conjonction, la disjonction, l'implication et l'équivalence forment ensemble un système complet de connecteurs.

On démontre, via les notions de forme normale conjonctive et forme normale disjonctive, que {négation, conjonction, disjonction}, ensemble de connecteurs au plus binaires, est un système complet de connecteurs pour la logique propositionnelle classique. Pour exemple : P ⇒ Q équivaut à ¬P ${\displaystyle \lor }$ Q (lire non(P) ou Q).

La généralisation à des logiques classiques p-valentes a été faite par Emil Post en 1921 dans Introduction à une théorie générale des propositions élémentaires. Il montre qu'avec un connecteur unaire qui fait une permutation circulaire sur les p valeurs de vérité (qui peuvent être notées 0, 1, 2, ... p-1) et qu'avec deux connecteurs binaires, l'un prenant le max de deux valeurs de vérité et l'autre le min de deux valeurs de vérité, on peut écrire toute formule de calcul propositionnel.

Dans le cas de la logique bivalente classique, l'infinité des connecteurs peut être ramené à un seul, binaire. Parmi les 16 connecteurs binaires, deux sont des systèmes complets de connecteurs, les deux barres de Sheffer.

Notes et références