1.6. Connecteurs logiques

Nous avons déjà vu les connecteurs nullaires : les constantes booléennes 0 (faux) et 1 (vrai).
Le connecteur binaire d'égalité entre booléens est noté ⇔ et appelé équivalence : AB se lit «A équivaut à B».

Présentons les autres connecteurs les plus utiles, avec leurs propriétés vraies pour toutes valeurs des variables booléennes (A, B, C, remplaçables par des formules)

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:
xy
xE
(AB)
(AB)
⇔ ¬(x=y)
⇔ ¬(xE)
⇔ ¬(AB)
⇔ (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
(AA) ⇔ A
(AA) ⇔ A
Commutatif
(BA) ⇔ (AB)
(BA) ⇔ (AB)
Associatif
((AB) ∧ C) ⇔ (A ∧ (BC))
((AB) ∨ C) ⇔ (A ∨ (BC))
Distributif sur l'autre
(A ∧ (BC)) ⇔ ((AB) ∨ (AC))
(A ∨ (BC)) ⇔ ((AB) ∧ (AC))

La symétrie entre eux vient du fait qu'ils sont échangés par la négation:

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

Les chaines de conjonctions comme (ABC) abrègent toute formule avec plus de parenthèses comme ((AB) ∧ C), équivalentes entre elles grâce à l'associativité; de même pour les chaines de disjonctions comme (ABC).
Affirmer une conjonction de formules revient à affirmer successivement toutes ces formules.
L'inéquivalence ⇎ est aussi appelée «ou exclusif» car (AB) peut aussi s'écrire ((AB) ∧ ¬(AB)).

Implication

Le connecteur binaire d'implication ⇒ se definit par (AB) ⇔ ((¬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,
(AB) ⇎
(AB) ⇔
(A ∧ ¬B)
B ⇒ ¬A)
La formule (¬B ⇒ ¬A) est appelée la contraposée de (AB).
L'équivalence peut aussi se redéfinir par
(AB) ⇔ ((AB) ∧ (BA)).
Ainsi, une preuve de AB peut se former d'une preuve de la première implication (AB), puis une preuve de la deuxième (BA) appelée la réciproque de (AB).

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

Les négations transforment les formules d'associativité et de distributivité des conjonctions et disjonctions en diverses formules avec des implications:
(A ⇒ (BC)) ⇔ ((AB) ⇒ C)
(A ⇒ (BC)) ⇔ ((AB) ∨ C)
(A ⇒ (BC)) ⇔ ((AB) ∧ (AC))
((AB) ⇒ C) ⇔ ((AC) ∧ (BC))
((AB) ⇒ C) ⇔ ((AC) ∧ (BC))
(A ∧ (BC)) ⇔ ((AB) ⇒ (AC))
Enfin on a
((AB) ∧ (AC)) ⇒ (BC)
((AB) ∧ (AC)) ⇒ (BC)

Chaines d'implications et d'équivalences

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

(ABC) ⇔ ((AB) ∧ (BC)) ⇒ (AC)
(ABC) ⇔ ((AB) ∧ (BC)) ⇒ (AC)
0 ⇒ AA ⇒ 1
A) ⇔ (A ⇒ 0) ⇔ (A ⇔ 0)
(A ∧ 1) ⇔ A ⇔ (A ∨ 0) ⇔ (1 ⇒ A) ⇔ (A ⇔ 1)
(AB) ⇒ A ⇒ (AB)

Axiomes de l'égalité

Pour tous objets x,y (pouvant abréger des termes), tout foncteur T et tout prédicat unaire A,
x = y
x = y
x = x
T(x) = T(y)
(A(x) ⇔ A(y))
Cette dernière formule peut aussi s'écrire (A(x) ∧ x = y) ⇒ A(y), puisque la réciproque A(y) ⇒ A(x) peut se déduire soit par sa contraposée (replaçant A par ¬A) ou par la symétrie de l'égalité (x = yy = x) obtenue en prenant pour A(z) la formule (z = x).
Cela donne aussi pour tous x, y, z, (x = yy = z) ⇒ x = z. La formule (x = yy = z) sera abrégée en x = y = z.

Prouvabilité

Une preuve d'une formule A dans une théorie générique T, est un modèle fini de la théorie de la démonstration, reliant A à des axiomes de T.
On dit que A est prouvable (ou démontrable) dans T et on note TA s'il existe une preuve de A dans T.
Encore dans T, une réfutation d'une formule A, est une preuve de ¬A. S'il en existe (T⊢ ¬A), on dit que A est réfutable (dans T).
Une formule est indécidable (dans T) si elle n'est ni prouvable ni réfutable.

Si une formule est à la fois prouvable et réfutable alors toutes le sont, ce qui signifie que la théorie est contradictoire:

(A ∧ ¬A) ⇔ 0
((TA)∧(T⊢ ¬A))⇔(T⊢ 0).

La théorie T is est dite contradictoire ou inconsistante si T⊢ 0, sinon est est dite cohérente. Dans une théorie contradictoire, toute formule est démontrable. Une telle théorie n'a aucun modèle.

Sans chercher à formaliser ce qu'est une preuve, on se contentera d'écrire les preuves naturellement, souvent comme succession de formules, chacune clairement vraie à l'aide des précédentes et des propriétés ci-dessus des connecteurs et de l'égalité. Des articulations en langage courant peut aussi être employées, en particulier pour manipuler les quantificateurs (1.9) et introduire des symboles définis par des expressions.
Ainsi une égalité entre termes x=y permet de remplacer toute occurrence de x par y dans toute expression sans en affecter le résultat; lorsqu'un symbole est défini par un terme, les deux sont égaux, et donc interchangeables dans toute expression. Les axiomes et autres lois exprimés à l'aide de symboles de variables (sous quantificateurs universels, voir 1.9) s'utilisent en remplaçant ces variables par des termes.
Les formules démontrables dont on connait une preuve (humainement ou par ordinateur) peuvent se qualifier différemment en langage courant suivant leur importance: un théorème est plus important qu'une proposition. L'un ou l'autre peuvent se déduire d'un lemme autrement moins important, et un corolaire peut s'en déduire facilement.

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 en théorie des ensembles
1.9. Quantificateurs
1.10. Formalisation de la théorie des ensembles
1.11. Principe de génération des ensembles
Aspects philosophiques
Temps en théorie des modèles
Temps en théorie des ensembles
Interprétation des classes
Concepts de vérité en mathématiques
2. Théorie des ensembles (suite)
3. Théorie des modèles

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