Techniques de base
2. Notions de logique
2.1 Généralités
Une propriété est une affirmation dont la valeur de vérité – vrai (V) ou
faux (F) – peut dépendre de un ou plusieurs arguments, numériques ou
autres. On notera P (x) si la valeur de vérité de la proposition P dépend
de la valeur de l’argument (ou variable) x. On dit alors que x est une
variable libre pour la propriété P.
x étant un nombre entier, la propriété P (x) : « x est un nombre premier » est vraie si x = 2, fausse si x = 4.
2.2 Quantificateurs
Définitions
Soit P (x) une propriété, avec x appartenant à un ensemble de référence E.
• Quantificateur existentiel. La propriété
∃x ∈ E, P (x)
est vraie si, et seulement si, il existe x appartenant à E tel que la propriété
P (x) soit vraie. On lit « il existe x appartenant à E tel que P (x) », ou
« pour quelque x appartenant à E, P (x) ».
• Quantificateur universel. La propriété
∀x ∈ E, P (x)
est vraie si, et seulement si, pour tout x appartenant à E, la propriété
P (x) est vraie. Lire « quel que soit x appartenant à E, P (x). »
Exemples
L’ensemble de référence est N. Soit les propriétés
P 1 : ∀x ∈ N, x 0
; P 2 (y) : ∀x ∈ N, x y ;
P 3 : ∀x ∈ N, ∃y ∈ N, x < y ; P 4 : ∃y ∈ N, ∀x ∈ N, x < y.
P 1 est vraie (tout entier naturel est supérieur ou égal à 0).
P 2 (y) est vraie si y = 0, fausse dans tous les autres cas.
P 3 est vraie : tout entier naturel admet un entier qui lui est supérieur.
P 4 est fausse : il n’existe pas d’entier naturel supérieur à tous les autres. À
noter que l’ordre des quantificateurs a de l’importance.
Dans P 3 , ni x ni y ne sont des variables libres. P 3 est une propriété de N,
pas de x, ni de y, qui sont ici des variables muettes. On pourrait écrire
P 3 sous la forme : ∀a ∈ N, ∃b ∈ N, a < b.
5
2. Notions de logique
2.1 Généralités
Une propriété est une affirmation dont la valeur de vérité – vrai (V) ou
faux (F) – peut dépendre de un ou plusieurs arguments, numériques ou
autres. On notera P (x) si la valeur de vérité de la proposition P dépend
de la valeur de l’argument (ou variable) x. On dit alors que x est une
variable libre pour la propriété P.
x étant un nombre entier, la propriété P (x) : « x est un nombre premier » est vraie si x = 2, fausse si x = 4.
2.2 Quantificateurs
Définitions
Soit P (x) une propriété, avec x appartenant à un ensemble de référence E.
• Quantificateur existentiel. La propriété
∃x ∈ E, P (x)
est vraie si, et seulement si, il existe x appartenant à E tel que la propriété
P (x) soit vraie. On lit « il existe x appartenant à E tel que P (x) », ou
« pour quelque x appartenant à E, P (x) ».
• Quantificateur universel. La propriété
∀x ∈ E, P (x)
est vraie si, et seulement si, pour tout x appartenant à E, la propriété
P (x) est vraie. Lire « quel que soit x appartenant à E, P (x). »
Exemples
L’ensemble de référence est N. Soit les propriétés
P 1 : ∀x ∈ N, x 0
; P 2 (y) : ∀x ∈ N, x y ;
P 3 : ∀x ∈ N, ∃y ∈ N, x < y ; P 4 : ∃y ∈ N, ∀x ∈ N, x < y.
P 1 est vraie (tout entier naturel est supérieur ou égal à 0).
P 2 (y) est vraie si y = 0, fausse dans tous les autres cas.
P 3 est vraie : tout entier naturel admet un entier qui lui est supérieur.
P 4 est fausse : il n’existe pas d’entier naturel supérieur à tous les autres. À
noter que l’ordre des quantificateurs a de l’importance.
Dans P 3 , ni x ni y ne sont des variables libres. P 3 est une propriété de N,
pas de x, ni de y, qui sont ici des variables muettes. On pourrait écrire
P 3 sous la forme : ∀a ∈ N, ∃b ∈ N, a < b.
5