Connecteur logique - Logical connective

Diagramme de Hasse des connecteurs logiques.

En logique , un connecteur logique (également appelé opérateur logique , connecteur de proposition ou opérateur de proposition ) est une constante logique utilisée pour connecter deux ou plusieurs formules. Par exemple, dans la syntaxe de la logique propositionnelle , le connecteur binaire peut être utilisé pour joindre les deux formules atomiques et , rendant la formule complexe .

Les connecteurs communs incluent la négation , la disjonction , la conjonction et l' implication . Dans les systèmes standard de la logique classique , ces connecteurs sont interprétés comme des fonctions de vérité , bien qu'ils reçoivent une variété d'interprétations alternatives dans les logiques non classiques . Leurs interprétations classiques sont similaires aux significations des expressions en langage naturel telles que l' anglais « pas », « ou », « et » et « si », mais pas identiques. Les divergences entre les connecteurs du langage naturel et ceux de la logique classique ont motivé des approches non classiques de la signification du langage naturel ainsi que des approches qui associent une sémantique compositionnelle classique à une pragmatique robuste .

Un connecteur logique est similaire, mais non équivalent, à une syntaxe couramment utilisée dans les langages de programmation appelée opérateur conditionnel .

Aperçu

Dans les langages formels , les fonctions de vérité sont représentées par des symboles non ambigus. Cela permet aux déclarations logiques de ne pas être comprises de manière ambiguë. Ces symboles sont appelés connectifs logiques , les opérateurs logiques , les opérateurs propositionnelle , ou, dans la logique classique , vérifonctionnels connectifs . Pour les règles qui permettent de construire de nouvelles formules bien formées en joignant d'autres formules bien formées à l'aide de connecteurs fonctionnels de vérité, voir formule bien formée .

Les connecteurs logiques peuvent être utilisés pour lier plus de deux instructions, on peut donc parler de connecteur logique n- aire .

Connecteurs logiques communs

Symbole, nom
Table de vérité
diagramme de Venn
Les connecteurs zéro (constantes)
?? Vérité / tautologie 1 Place Rouge.svg
?? Faux / contradiction 0 Carré vierge.svg
Connecteurs unaires
P  = 0 1
Proposition P 0 1 Venn01.svg
?? Négation 1 0 Venn10.svg
Connecteurs binaires
P  = 0 1
Q  = 0 1 0 1
Proposition P 0 0 1 1 Venn0101.svg
Proposition Q 0 1 0 1 Venn0011.svg
?? Conjonction 0 0 0 1 Venn0001.svg
?? Déni alternatif 1 1 1 0 Venn1110.svg
?? Disjonction 0 1 1 1 Venn0111.svg
?? Refus conjoint 1 0 0 0 Venn1000.svg
Matériel conditionnel 1 1 0 1 Venn1011.svg
Exclusif ou 0 1 1 0 Venn0110.svg
?? Biconditionnel 1 0 0 1 Venn1001.svg
?? Implication inverse 1 0 1 1 Venn1101.svg
Plus d'information

Liste des connecteurs logiques courants

Les connecteurs logiques couramment utilisés incluent :

Les noms alternatifs pour biconditionnel sont iff , xnor et bi-implication .

Par exemple, le sens des déclarations il pleut (noté P ) et je suis à l'intérieur (noté Q) est transformé, lorsque les deux sont combinés avec des connecteurs logiques :

  • Il ne pleut pas ( P )
  • Il pleut et je suis à l'intérieur ( )
  • Il pleut ou je suis à l'intérieur ( )
  • S'il pleut, alors je suis à l'intérieur ( )
  • Si je suis à l'intérieur, alors il pleut ( )
  • Je suis à l'intérieur si et seulement s'il pleut ( )

Il est également courant de considérer la formule toujours vraie et la formule toujours fausse comme conjonctives :

  • Vraie formule (⊤, 1, V [préfixe] ou T)
  • Fausse formule (⊥, 0, O [préfixe] ou F)

Histoire des notations

  • Négation: le symbole ¬ paru dans Heyting en 1929 (comparer à Frege symbole de ⫟ dans son Begriffsschrift ); le symbole ~ est apparu dans Russell en 1908 ; une notation alternative consiste à ajouter une ligne horizontale au-dessus de la formule, comme dans ; une autre notation alternative consiste à utiliser un symbole premier comme dans P'.
  • Conjonction : le symbole ∧ est apparu dans Heyting en 1929 (comparer à l' utilisation par Peano de la notation ensembliste de l' intersection ∩) ; le symbole & est apparu au moins dans Schönfinkel en 1924 ; le symbole . vient de l'interprétation de Boole de la logique comme une algèbre élémentaire .
  • Disjonction : le symbole ∨ est apparu chez Russell en 1908 (comparé à l' utilisation par Peano de la notation ensembliste de l' union ∪) ; le symbole + est également utilisé, malgré l'ambiguïté venant du fait que le + de l'algèbre élémentaire ordinaire est un exclusif ou lorsqu'il est interprété logiquement dans un anneau à deux éléments ; ponctuellement dans l'historique un + avec un point dans le coin inférieur droit a été utilisé par Peirce ,
  • Implication : le symbole → est visible chez Hilbert en 1917 ; ⊃ a été utilisé par Russell en 1908 (comparé à la notation C inversée de Peano) ; ⇒ a été utilisé dans Vax.
  • Biconditionnel : le symbole ≡ a été utilisé au moins par Russell en 1908 ; ↔ a été utilisé au moins par Tarski en 1940 ; ⇔ a été utilisé dans Vax ; d'autres symboles apparaissent ponctuellement dans l'histoire, comme ⊃⊂ à Gentzen , ~ à Schönfinkel ou ⊂⊃ à Chazal.
  • Vrai : le symbole 1 vient de l'interprétation de Boole de la logique comme algèbre élémentaire sur l' algèbre booléenne à deux éléments ; d'autres notations incluent (à trouver dans Peano).
  • Faux : le symbole 0 vient aussi de l'interprétation de Boole de la logique comme anneau ; d'autres notations incluent (à trouver dans Peano).

Certains auteurs ont utilisé des lettres pour les connecteurs à un moment donné de l'histoire : u. pour la conjonction (le "und" de l'allemand pour "et") et o. pour la disjonction (l'allemand "oder" pour "ou") dans les travaux antérieurs de Hilbert (1904); N p pour négation, K pq pour conjonction, D pq pour déni alternatif, A pq pour disjonction, X pq pour déni conjoint, C pq pour implication, E pq pour biconditionnel dans Łukasiewicz (1929) ; cf. Notation polonaise .

Redondance

Un tel connecteur logique comme l' implication inverse « ← » est en fait le même qu'un conditionnel matériel avec des arguments échangés ; ainsi, le symbole de l'implication inverse est redondant. Dans certains calculs logiques (notamment en logique classique ), certaines déclarations composées essentiellement différentes sont logiquement équivalentes . Un exemple moins trivial de redondance est l'équivalence classique entre ¬ P  ∨  Q et P  →  Q . Par conséquent, un système logique classique n'a pas besoin de l'opérateur conditionnel "→" si "¬" (pas) et "∨" (ou) sont déjà utilisés, ou peut utiliser le "→" uniquement comme sucre syntaxique pour un composé ayant une négation et une disjonction.

Il existe seize fonctions booléennes associant les valeurs de vérité d' entrée P et Q à des sorties binaires à quatre chiffres . Ceux-ci correspondent à des choix possibles de connecteurs logiques binaires pour la logique classique . Différentes implémentations de la logique classique peuvent choisir différents sous-ensembles de connecteurs fonctionnellement complets .

Une approche consiste à choisir un ensemble minimal et à définir d'autres connecteurs par une forme logique, comme dans l'exemple avec le conditionnel matériel ci-dessus. Voici les ensembles d'opérateurs fonctionnels minimaux complets de la logique classique dont les arités ne dépassent pas 2 :

Un élément
{↑}, {↓}.
Deux éléments
, , , , , , , , , , , , , , , , , .
Trois éléments
, , , , , .

Une autre approche consiste à utiliser avec des droits égaux des connecteurs d'un certain ensemble pratique et fonctionnel, mais pas minimal . Cette approche nécessite plus d' axiomes propositionnels , et chaque équivalence entre les formes logiques doit être soit un axiome, soit prouvable sous forme de théorème.

La situation est cependant plus compliquée en logique intuitionniste . De ses cinq connecteurs, {∧, , →, ¬, ⊥}, seule la négation "¬" peut être réduite à d'autres connecteurs (voir Faux (logique) § Faux, négation et contradiction pour en savoir plus). Ni la conjonction, ni la disjonction, ni le conditionnel matériel n'ont de forme équivalente construite à partir des quatre autres connecteurs logiques.

Langage naturel

Les connecteurs logiques standard de la logique classique ont des équivalents approximatifs dans les grammaires des langues naturelles. En anglais , comme dans de nombreuses langues, de telles expressions sont généralement des conjonctions grammaticales . Cependant, ils peuvent également prendre la forme de complémenteurs , de suffixes verbaux et de particules . Les dénotations de connecteurs de langues naturelles sont un sujet de recherche majeur en sémantique formelle , domaine qui étudie la structure logique des langues naturelles.

Les significations des connecteurs du langage naturel ne sont pas précisément identiques à leurs équivalents les plus proches dans la logique classique. En particulier, la disjonction peut recevoir une interprétation exclusive dans de nombreuses langues. Certains chercheurs ont pris ce fait comme preuve que la sémantique du langage naturel n'est pas classique . Cependant, d'autres maintiennent la sémantique classique en posant des comptes pragmatiques de l'exclusivité qui créent l'illusion de la non-classicité. Dans de tels comptes, l'exclusivité est généralement traitée comme une implicature scalaire . Les énigmes connexes impliquant la disjonction incluent les inférences de libre choix , la contrainte de Hurford et la contribution de la disjonction dans les questions alternatives .

D'autres divergences apparentes entre le langage naturel et la logique classique incluent les paradoxes de l'implication matérielle , l' anaphore de l'âne et le problème des conditionnels contrefactuels . Ces phénomènes ont été pris comme motivation pour identifier les dénotations des conditionnels du langage naturel avec des opérateurs logiques, y compris le conditionnel strict , le conditionnel variablement strict , ainsi que divers opérateurs dynamiques .

Le tableau suivant montre les approximations classiques définissables pour les connecteurs anglais.

mot anglais Conjonctif symbole Porte logique
ne pas négation "¬" NE PAS
et conjonction "∧" ET
ou disjonction "∨" OU
si donc implication matérielle "→" IMPLIQUER
...si implication inverse "←"
si et seulement si biconditionnel "↔" XNOR
pas les deux refus alternatif "↑" NAND
ni... ni déni commun "↓" NI
mais non non-implication matérielle "↛" NIMPLEMENT

Propriétés

Certains connecteurs logiques possèdent des propriétés qui peuvent être exprimées dans les théorèmes contenant le connecteur. Certaines de ces propriétés qu'un connecteur logique peut avoir sont :

L'associativité
Dans une expression contenant deux ou plusieurs des mêmes connecteurs associatifs d'affilée, l'ordre des opérations n'a pas d'importance tant que la séquence des opérandes n'est pas modifiée.
Commutativité
Les opérandes du connecteur peuvent être permutés, préservant l'équivalence logique avec l'expression d'origine.
Distributivité
Un connecteur noté · se répartit sur un autre connecteur noté +, si a · ( b + c ) = ( a · b ) + ( a · c ) pour tous les opérandes a , b , c .
Idempotence
Chaque fois que les opérandes de l'opération sont les mêmes, le composé est logiquement équivalent à l'opérande.
Absorption
Une paire de connecteurs ∧, ∨ satisfait la loi d'absorption si pour tous les opérandes a , b .
Monotonie
Si f ( a 1 , ..., a n ) f ( b 1 , ..., b n ) pour tout a 1 , ..., a n , b 1 , ..., b n {0 , 1} telle que a 1b 1 , a 2b 2 , ..., a nb n . Par exemple, , ∧, , ⊥.
Affinité
Chaque variable fait toujours une différence dans la valeur de vérité de l'opération ou elle ne fait jamais de différence. Par exemple, , ↔, , , ⊥.
Dualité
Lire les affectations de valeurs de vérité pour l'opération de haut en bas sur sa table de vérité revient à prendre le complément de la lecture de la table du même ou d'un autre connecteur de bas en haut. Sans recourir aux tables de vérité, il peut être formulé comme a 1 , ..., a n ) = ¬ g ( a 1 , ..., a n ) . Par exemple, .
Préserver la vérité
Le composé que tous ces arguments sont des tautologies est une tautologie elle-même. Par exemple, , ∧, ⊤, →, ↔, ⊂ (voir validité ).
Préservation du mensonge
Le composé de tous ces arguments sont des contradictions est une contradiction elle-même. Par exemple, , ∧, , , ⊄, ⊅ (voir validité ).
Involutivité (pour les connecteurs unaires)
f ( f ( a )) = a . Par exemple la négation dans la logique classique.

Pour la logique classique et intuitionniste, le symbole "=" signifie que les implications correspondantes "...→..." et "...←..." pour les composés logiques peuvent être à la fois prouvées sous forme de théorèmes, et le symbole "≤" signifie que "...→..." pour les composés logiques est une conséquence des connecteurs correspondants "...→..." pour les variables propositionnelles. Certaines logiques à plusieurs valeurs peuvent avoir des définitions incompatibles de l'équivalence et de l'ordre (implication).

La conjonction et la disjonction sont toutes deux associatives, commutatives et idempotentes dans la logique classique, la plupart des variétés de la logique multivaluée et de la logique intuitionniste. Il en est de même pour la distributivité de la conjonction sur la disjonction et de la disjonction sur la conjonction, ainsi que pour la loi d'absorption.

Dans la logique classique et certaines variétés de logique à plusieurs valeurs, la conjonction et la disjonction sont duelles, et la négation est auto-duelle, cette dernière est également auto-duelle dans la logique intuitionniste.

Ordre de préséance

Afin de réduire le nombre de parenthèses nécessaires, on peut introduire des règles de priorité : ¬ a une priorité supérieure à ∧, ∧ supérieure à ∨ et ∨ supérieure à →. Ainsi, par exemple, est l'abréviation de .

Voici un tableau qui montre une priorité couramment utilisée des opérateurs logiques.

Cependant, tous les compilateurs n'utilisent pas le même ordre ; par exemple, un ordre dans lequel la disjonction est moins prioritaire que l'implication ou la bi-implication a également été utilisé. Parfois, la priorité entre la conjonction et la disjonction n'est pas spécifiée, ce qui nécessite de la fournir explicitement dans une formule donnée avec des parenthèses. L'ordre de priorité détermine quel connecteur est le "connecteur principal" lors de l'interprétation d'une formule non atomique.

L'informatique

Une approche fonctionnelle de vérité des opérateurs logiques est implémentée sous forme de portes logiques dans les circuits numériques . Pratiquement tous les circuits numériques (l'exception majeure est la DRAM ) sont construits à partir de portes NAND , NOR , NOT et de transmission ; voir plus de détails dans la fonction Vérité en informatique . Les opérateurs logiques sur les vecteurs de bits (correspondant aux algèbres booléennes finies ) sont des opérations au niveau du bit .

Mais toutes les utilisations d'un connecteur logique en programmation informatique n'ont pas une sémantique booléenne. Par exemple, l' évaluation paresseuse est parfois mis en œuvre pour P  ∧  Q et P  ∨  Q , de sorte que ces conjonctions ne sont pas commutative si l' une ou les deux expressions P , Q ont des effets secondaires . De plus, un conditionnel , qui dans un certain sens correspond au connecteur conditionnel matériel , est essentiellement non booléen car pour if (P) then Q;, le conséquent Q n'est pas exécuté si l' antécédent  P est faux (bien qu'un composé dans son ensemble réussisse ≈ "vrai" dans tel cas). Ceci est plus proche des vues intuitionnistes et constructivistes sur le conditionnel matériel - plutôt que des vues de la logique classique.

Voir également

Remarques

Les références

Sources

Liens externes