1.6. Connecteurs logiques

Nous avons défini précédemment le concept de connecteur logique. Énumérons maintenant les principaux connecteurs utiles, au-delà des deux connecteurs nullaires (constantes booléennes) 1 et 0. (A cela s'ajoutera le connecteur conditionnel en 2.4).

Tautologies

Leurs propriétés seront exprimées par des tautologies, qui sont des formules utilisant uniquement des connecteurs et des variables Booléennes (ici écrites A, B, C), et vraies pour toutes les combinaisons de valeurs possibles de ces variables. Ainsi, les tautologies donnent également des formules nécessairement vraies après remplacement de ces variables par des formules les définissant utilisant n'importe quel langage et interprétées dans tout système. De telles définitions des variables booléennes par les formules d'une théorie peuvent restreindre leurs domaines de valeurs possibles dépendant les unes des aux autres.

Les tautologies constituent les règles de l'algèbre booléenne, une théorie algébrique décrivant les opérations sur le type booléen, lui-même naturellement interprété comme la paire d'éléments 0 et 1 (mais admettant également des interprétations plus sophistiquées dépassant le cadre de ce chapitre).

Le connecteur binaire d'égalité entre booléens est noté ⇔ et appelé équivalence : A ⇔ B se lit «A équivaut à B».

Negation

Le seul connecteur unaire utile est la negation ¬, qui échange les booléens (¬A se lit «non A»):
¬1
¬0
¬(¬A) 		⇔ 0
⇔ 1
⇔ A
Il est souvent noté en barrant le symbole principal de son argument, formant avec lui un autre symbole de même format:
x ≠ y
x ∉ E
(A ⇎ B)
 ⇔ ¬(x = y)
⇔ ¬(x ∈ E)
⇔ (A ⇔ ¬B)
 (x est différent de y)
(x n'appartient pas à E)
(Non-équivalence)

Conjonctions, disjonctions

La conjonction ∧ signifie «et», donnant vrai uniquement si ses deux arguments sont vrais;
La disjonction ∨ signifie «ou», donnant vrai sauf si ses deux arguments sont faux.
Chacun est:
Idempotent
(A ∧ A) ⇔ A
(A ∨ A) ⇔ A
 Commutatif
(B∧A) ⇔ (A∧B)
(B∨A) ⇔ (A∨B)
Associatif
((A∧B)∧C) ⇔ (A∧(B∧C))
((A∨B)∨C) ⇔ (A∨(B∨C))
 Distributif sur l'autre
(A ∧ (B∨C)) ⇔ ((A∧B) ∨ (A∧C))
(A ∨ (B∧C)) ⇔ ((A∨B) ∧ (A∨C))

Cette ressemblance (symétrie) de leurs propriétés vient du fait qu'ils sont échangés par négation:

(A ∨ B) ⇎ (¬A ∧ ¬B)
(A ∧ B) ⇎ (¬A ∨ ¬B)

L'inéquivalence ⇎ est aussi appelée «ou exclusif» car (A ⇎ B) ⇔ ((A ∨ B) ∧ ¬(A ∧ B)).

Les chaînes de conjonctions comme (A ∧ B ∧ C) abrègent toute formule avec plus de parenthèses comme ((A ∧ B) ∧ C), équivalentes entre elles par associativité; de même pour les chaînes de disjonctions (A ∨ B ∨ C).

Affirmer (déclarer vraie) une conjonction de formules revient à affirmer successivement toutes ces formules.

Implication

Le connecteur binaire d'implication ⇒ se definit par (A ⇒ B) ⇔ ((¬A) ∨ B). Il peut se lire «A implique B», «A est une condition suffisante à B», ou «B est une condition nécessaire à A». Etant vrai sauf quand A est vrai et B est faux, il exprime la vérité de B quand A est vrai, mais il ne donne plus d'information sur B quand A est faux (étant alors vrai).
De plus,
(A ⇒ B) ⇎
(A ⇒ B) ⇔		 (A ∧ ¬B)
(¬B ⇒ ¬A)
La formule (¬B ⇒ ¬A) est appelée la contraposée de (A ⇒ B).
L'équivalence peut aussi se redéfinir par
(A ⇔ B) ⇔ ((A ⇒ B) ∧ (B ⇒ A)).
Ainsi dans une théorie donnée, une preuve de A ⇔ B peut se former d'une preuve de la première implication (A ⇒ B), puis une preuve de la deuxième (B ⇒ A) appelée la réciproque de (A ⇒ B).

La formule (A ∧ (A ⇒ B)) sera abrégée en A ∴ B, qui se lit «A donc B». Elle est équivalente à (A ∧ B), mais sert à indiquer qu'elle est déduite des vérités de A et de (A ⇒ B).

Les négations transforment les formules d'associativité et de distributivité des conjonctions et disjonctions en diverses tautologies avec des implications:

(A ⇒ (B ⇒ C)) ⇔ ((A ∧ B) ⇒ C)
(A ⇒ (B ∨ C)) ⇔ ((A ⇒ B) ∨ C)

(A ⇒ (B ∧ C)) ⇔ ((A ⇒ B) ∧ (A ⇒ C))
((A ∨ B) ⇒ C) ⇔ ((A ⇒ C) ∧ (B ⇒ C))
((A ⇒ B) ⇒ C) ⇔ ((A ∨ C) ∧ (B ⇒ C))
(A ∧ (B ⇒ C)) ⇔ ((A ⇒ B) ⇒ (A ∧ C))
Enfin on a
(A ⇒ B) ⇒ ((A∧C) ⇒ (B∧C))
(A ⇒ B) ⇒ ((A∨C) ⇒ (B∨C)).

Chaînes d'implications et d'équivalences

Par une autre sorte d'abréviation, toute chaîne de formules reliées par des ⇔ et/ou ⇒, abrégera la conjonction de toutes ces implications ou équivalences entre formules voisines:

(A ⇒ B ⇒ C) ⇔ ((A ⇒ B) ∧ (B ⇒ C)) ⇒ (A ⇒ C)
(A ⇔ B ⇔ C) ⇔ ((A ⇔ B) ∧ (B ⇔ C)) ⇒ (A ⇔ C)
0 ⇒ A ⇒ A ⇒ 1
(¬A) ⇔ (A ⇒ 0) ⇔ (A ⇔ 0)
(A ∧ 1) ⇔ A ⇔ (A ∨ 0) ⇔ (1 ⇒ A) ⇔ (A ⇔ 1)
(A ∧ B) ⇒ A ⇒ (A ∨ B)



Théorie des ensembles et fondements des mathématiques
1. Premiers fondements des mathématiques
1.1. Introduction au fondement des mathématiques
1.2. Variables, ensembles, fonctions et opérations
1.3. Forme des théories: notions, objets, méta-objets
1.4. Structures mathématiques
1.5. Expressions et structures définissables ⇦
1.6. Connecteurs logiques
⇨1.7. Classes en théorie des ensembles
1.8. Symboles liants
 1.9. Axiomes et preuves
1.10. Quantificateurs
1.11. Quantificateurs du 2e ordre
Aspects philosophiques
1.A. Temps en théorie des modèles
1.B. Indéfinissabilité de la vérité
1.C. Théorèmes d'incomplétude
1.D. Le cadre ensembliste unifié
2. Théorie des ensembles - 3. Algèbre

Other languages:
EN : 1. First foundations of mathematics : 1.6. Connectives