Connecteur logique

Un article de Wikipédia, l'encyclopédie libre.
Sauter à la navigation Sauter à la recherche
Page d'aide sur l'homonymie Pour l’article homonyme, voir Connecteur logique (linguistique).

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[modifier | modifier le code]

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[modifier | modifier le code]

Logique classique[modifier | modifier le code]

Si l'on se place dans la logique classique, c'est-à-dire dans une logique où l'interprétation des variables se fait dans les booléens ou dans une extension multivalente[2] de celle-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.

Fonction booléenne Notation Formules équivalentes Table de vérité Diagramme de Venn
Proposition P P
  Q
0 1
P 0   0 0
1   1 1
Venn0101.svg
Proposition Q Q
  Q
0 1
P 0   0 1
1   0 1
Venn0011.svg
Négation de P ¬P
~P
  Q
0 1
P 0   1 1
1   0 0
Venn1010.svg
Négation de Q ¬Q
~Q
  Q
0 1 Logique formelle
P 0   1 0
1   1 0
Venn1100.svg
Disjonction
(OU)
P Q
P  Q
P OR Q
P ¬Q
¬PQ
¬P ↑ ¬Q
  Q
0 1
P 0   0 1
1   1 1
Venn0111.svg
Conjonction
(ET)
P Q
P & Q
P · Q
P AND Q
P ¬Q
¬P Q
¬P ¬Q
  Q
0 1
P 0   0 0
1   0 1
Venn0001.svg
Disjonction réciproque
(NON-OU)
PQ
P NOR Q
P ¬Q
¬P Q
¬P ¬Q
  Q
0 1
P 0   1 0
1   0 0
Venn1000.svg
NON-ET PQ
P | Q
P NAND Q
P → ¬Q
¬PQ
¬P ¬Q
  Q
0 1
P 0   1 1
1   1 0
Venn1110.svg
Contradiction FALSE P ¬P
  Q
0 1
P 0   0 0
1   0 0
Venn0000.svg
Tautologie TRUE P ¬P
  Q
0 1
P 0   1 1
1   1 1
Venn1111.svg
Implication PQ
P Q
P ↑ ¬Q
¬P Q
¬P ← ¬Q
  Q
0 1
P 0   1 1
1   0 1
Venn1011.svg
Implication réciproque P Q
P Q
P ¬Q
¬PQ
¬P → ¬Q
  Q
0 1
P 0   1 0
1   1 1
Venn1101.svg
Non-implication P Q
P Q
P ¬Q
¬PQ
¬P ¬Q
  Q
0 1
P 0   0 0
1   1 0
Venn0100.svg
Non-implication réciproque P Q
P Q
P ↓ ¬Q
¬P Q
¬P ¬Q
  Q
0 1
P 0   0 1
1   0 0
Venn0010.svg
Équivalence P Q
PQ
P Q
P XNOR Q
P IFF Q
P ¬Q
¬P Q
¬P ¬Q
  Q
0 1
P 0   1 0
1   0 1
Venn1001.svg
Disjonction exclusive
(OU exclusif)
P Q
P Q
P Q
P XOR Q
P ¬Q
¬P Q
¬P ¬Q
  Q
0 1
P 0   0 1
1   1 0
Venn0110.svg

Logiques non classiques[modifier | modifier le code]

Logique intuitionniste[modifier | modifier le code]

Une sémantique possible de la logique intuitionniste se fait dans les modèles de Kripke. Grosso modo, un modèle de Kripke est un graphe étiqueté, dont les nœuds sont appelés des « mondes », les étiquettes sont des formules et la relation sous-jacente est dite relation d'accessibilité. Dans ces graphes, la sémantique d'une formule dont le connecteur principal est est un modèle de Kripke avec un monde étiqueté par la formule . La sémantique de la formule est définie à partir des sémantiques des composants de la formule. Si la formule est , la sémantique de se fera à partir des sémantiques de et . Dire que dans le modèle de Kripke , la formule étiquette le monde , s'écrit . Dans ce cas est un modèle de .

Un exemple[modifier | modifier le code]

Par exemple, supposons que la formule soit . Son connecteur principal est . La définition de la sémantique de fonctionne ainsi : pour pouvoir dire que , il faut que, dans le modèle , pour tout monde , accessible à partir de , autrement dit tel que , on ait : implique .

Logiques modales[modifier | modifier le code]

Il faut dans ce cadre expliquer comment les connecteurs se comportent vis-à-vis des modalités.

Systèmes complets de connecteurs[modifier | modifier le code]

En logique classique, avec 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 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 (p1, p2, ... pn) dans une logique p valente.

La logique bivalente usuelle a donc connecteurs binaires. Ces logiques ont donc une infinité de connecteurs.[pas clair]

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 usuellement présentés : négation, implication, conjonction, disjonction, équivalence, forment 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, forme un ensemble complet de connecteurs pour la logique propositionnelle classique. Pour exemple p ⇒ q, équivaut à 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. Où 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 les deux connecteurs binaires, l'un prenant le max de deux valeurs de vérité, 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[modifier | modifier le code]

  1. Par exemple la règle de tiers exclu est ou non satisfaite.
  2. Une logique p-valente possède connecteurs n-aires.
  3. La logique intuitionniste n'a pas de système complet de connecteurs<