Mémo logique et ensembles

Logique

Soit A et B deux formules, c’est-à-dire des phrases mathématiques comme « 2 + 2 = 4 », « la fonction f est croissante », « xy » et même « 0 = 1 ». Une formule peut être fausse ! Elle peut aussi contenir des variables.

Connecteurs logiques
Notation (et lecture) Résultat Signification
A et B conjonction A et B sont vrais simultanément
A ou B disjonction au moins l’une des deux formules est vraie
AB (« A implique B ») implication si A est vrai alors B aussi
AB (« A est équivalent à B ») équivalence A est vrai si et seulement si B est vrai
¯(A) (« non A ») négation A est faux

L’implication est le seul de ces 4 connecteurs logiques qui ne soit pas symétrique.

prémisse (condition suffisante) ⇒ conclusion (condition nécessaire)

L’implication est vraie quand la prémisse est fausse.

Transformation d’une implication
Dénomination Notation Exemple
implication AB Si vous avez connu l’an 2000, alors vous avez plus de 18 ans.
réciproque BA Si vous avez plus de 18 ans, alors vous avez connu l’an 2000.
contraposée ¯(B)¯(A) Si vous avez 18 ans ou moins, alors vous n’avez pas connu l’an 2000.

Une implication a même valeur de vérité que sa contraposée, mais pas forcément celle de sa réciproque.

Quantificateurs
Dénomination Notation Exemple
universel x, Px Tous les élèves sont majeurs.
existentiel x : Px Il y a un élève majeur.
Lois de De Morgan en logique
Soient A et B deux formules.
¯(A et B)¯(A) ou ¯(B) ;
¯(A ou B)¯(A) et ¯(B)
Négation de l’implication
Soient A et B deux formules.
¯(AB)A et ¯(B)
Négation des quantificateurs
Soit Px une formule dépendant d’une variable x.
¯(x, Px) ⇔ ∃ x : ¯(Px)
Modus ponens
Si A et (AB) sont vrais alors B aussi

Ensembles

Relations
DénominationNotationLectureReprésentationExemple
appartenance xE « x appartient à E » ou « x est élément de E » E x Un élève appartient à sa classe.
inclusion AE « A est inclus dans E » E A Le groupe des latinistes est inclus dans la classe.

Contrairement à une liste, un ensemble n’est pas ordonné et ne peut contenir de répétition. L’ensemble vide ne contient aucun élément.

Si E est un ensemble, 𝒫(E) est l’ensemble des parties de E.

Exemple
𝒫({1, 2, 3}) = {∅, {1}, {2}, {3}, {1, 2}, {1, 3}, {2, 3}, {1, 2, 3}}}
Opérations ensemblistes
DénominationNotationLectureReprésentation
intersection AB « A inter B » A B
réunion AB « A union B » A B
complémentation AB « A privé de B » A B

S’il n’y a pas d’ambiguïté sur l’ensemble E, on peut noter EA = ¯(A).

Le produit cartésien de deux ensembles E et F est l’ensemble E × F contenant les couples (x, y) tels que xE et yF.

Exemple
{1, 2, 3} × {1, 2} = {(1, 1), (1, 2), (2, 1), (2, 2), (3, 1), (3, 2)}

Un couple est une liste et peut donc contenir des répétitions. L’ordre des termes est important : (1, 2) ≠ (2, 1).

En particulier, E2 = E × E. Plus généralement, si p est un entier strictement positif, Ep est l’ensemble des listes de p éléments de E.

Liens entre opérations ensemblistes et connecteurs logiques
Soient A et B deux parties d’un ensemble E. xE, xABxA et xB ; xABxA ou xB ; x¯(A)xA
Lois de De Morgan ensemblistes
Soient A et B deux ensembles.
¯(AB) = ¯(A)¯(B) ; ¯(AB) = ¯(A)¯(B)
Propriétés des opérations ensemblistes
Soit A, B et C trois ensembles.
Associativité :
A ∩ (BC) = (AB) ∩ C ; A ∪ (BC) = (AB) ∪ C
Commutativité :
AB = BA ; AB = BA
Distributivité :
A ∩ (BC) = (AB) ∪ (AC) ; A ∪ (BC) = (AB) ∩ (AC)