Calcul des prédicats : quantificateurs ∀ et ∃

Un prédicat est une phrase qui contient une ou plusieurs variables, comme « x est pair » : elle n'est ni vraie ni fausse tant que x n'est pas fixé. Les quantificateurs ∀ (« pour tout ») et ∃ (« il existe ») transforment un prédicat en proposition, en disant pour combien d'éléments il doit être vrai. Ce chapitre montre comment lire, écrire et nier un énoncé quantifié, et pourquoi l'ordre de deux quantificateurs change le sens.

Variable, constante et prédicat

Dans un énoncé mathématique, on distingue :

• une constante : un objet précis, qui ne change pas (le nombre 5, le serveur srv-web01, le port 443) ;
• une variable : une lettre qui représente un objet quelconque d'un ensemble donné, appelé domaine (x dans ℕ, l'ensemble des entiers naturels ; u dans l'ensemble des utilisateurs d'un annuaire).

Un prédicat est un énoncé qui dépend d'une ou plusieurs variables et qui devient une proposition quand on remplace chaque variable par une constante. On le note avec une lettre minuscule suivie de ses variables entre parenthèses : p(x), q(x, y).

Au BTS, les prédicats portent sur une, deux ou trois variables, comme le précise le programme.

Il y a deux façons de transformer un prédicat en proposition : remplacer chaque variable par une constante (p(4)), ou quantifier la variable, c'est-à-dire dire pour combien d'éléments du domaine le prédicat est vrai.

Le quantificateur universel ∀

Le symbole ∀ (un A renversé, pour All) se lit « pour tout » ou « quel que soit ».

∀x ∈ E, p(x) se lit « pour tout x de E, p(x) » et signifie : p(x) est vraie pour chaque élément x de E, sans exception.

• ∀x ∈ ℕ, x² ≥ 0 : vraie, le carré d'un entier n'est jamais négatif.
• ∀x ∈ ℕ, x est pair : fausse, puisque 3 est impair.

Pour montrer qu'un énoncé « pour tout » est faux, un seul contre-exemple suffit : un élément du domaine pour lequel le prédicat est faux. Pour montrer qu'il est vrai, il faut au contraire un raisonnement valable pour tous les éléments (ou, sur un domaine fini, vérifier chaque élément).

Le quantificateur existentiel ∃

Le symbole ∃ (un E retourné, pour Exists) se lit « il existe ».

∃x ∈ E, p(x) se lit « il existe x dans E tel que p(x) » et signifie : p(x) est vraie pour au moins un élément de E. Il peut y en avoir un seul, plusieurs, ou même tous.

• ∃x ∈ ℕ, x² = 49 : vraie, x = 7 convient.
• ∃x ∈ ℕ, x + 3 = 1 : fausse, aucun entier naturel ne convient.

Pour montrer qu'un énoncé « il existe » est vrai, il suffit d'exhiber un élément qui convient (un exemple). Pour montrer qu'il est faux, il faut prouver qu'aucun élément ne convient.

On rencontre aussi ∃!, « il existe un unique » : ∃!x ∈ ℕ, x + 3 = 5 est vraie (seul x = 2 convient).

Sur un ensemble fini : ∀ est un grand ET, ∃ un grand OU

Quand le domaine est fini, les quantificateurs se ramènent aux connecteurs du chapitre 1. Prenons E = {srv1, srv2, srv3}, les trois serveurs d'une PME, et s(x) : « le serveur x est sauvegardé cette nuit ».

• ∀x ∈ E, s(x) ≡ s(srv1) ∧ s(srv2) ∧ s(srv3) : tous les serveurs sont sauvegardés.
• ∃x ∈ E, s(x) ≡ s(srv1) ∨ s(srv2) ∨ s(srv3) : au moins un serveur est sauvegardé.

Avec ce journal, ∀x ∈ E, s(x) est fausse (srv2 est un contre-exemple) et ∃x ∈ E, s(x) est vraie (srv1 convient).

Cette correspondance est exactement ce que font les fonctions all() et any() de Python :

sauvegarde = {"srv1": True, "srv2": False, "srv3": True}

tous = all(sauvegarde.values())   # ∀x, s(x) : False
un_au_moins = any(sauvegarde.values())   # ∃x, s(x) : True
print(tous, un_au_moins)   # False True

Nier un énoncé quantifié

Les règles se déduisent des lois de De Morgan, puisque ∀ est un grand « et » et ∃ un grand « ou ».

Exemples :

Quand le prédicat est lui-même une formule, on lui applique les règles du chapitre 2. La forme la plus fréquente est « tous les éléments qui vérifient p vérifient aussi q » :

• énoncé : ∀x ∈ E, p(x) ⇒ q(x) ;
• négation : ∃x ∈ E, p(x) ∧ ¬q(x).

Exemple : « tout ordinateur portable de l'entreprise a un disque chiffré » se nie en « il existe un ordinateur portable de l'entreprise dont le disque n'est pas chiffré ». La négation n'est pas « aucun portable n'a de disque chiffré », ni « si un ordinateur n'est pas portable, son disque est chiffré ».

Prédicats à deux variables et ordre des quantificateurs

Avec un prédicat à deux variables, il faut deux quantificateurs pour obtenir une proposition, et leur ordre compte quand ils sont de types différents.

Prenons U l'ensemble des utilisateurs d'une entreprise, M l'ensemble des mots de passe possibles, et c(u, m) : « l'utilisateur u a pour mot de passe m ».

• ∀u ∈ U, ∃m ∈ M, c(u, m) : « chaque utilisateur a un mot de passe ». Le mot de passe peut être différent d'un utilisateur à l'autre : m dépend de u.
• ∃m ∈ M, ∀u ∈ U, c(u, m) : « il existe un mot de passe que tous les utilisateurs ont ». Un seul et même mot de passe pour tout le monde : une faille de sécurité.

Un exemple mathématique classique :

• ∀n ∈ ℕ, ∃m ∈ ℕ, m > n : « pour tout entier, il existe un entier plus grand ». Vraie : m = n + 1 convient.
• ∃m ∈ ℕ, ∀n ∈ ℕ, m > n : « il existe un entier plus grand que tous les entiers ». Fausse : m devrait être plus grand que lui-même.

Avec trois variables, la lecture est la même. Soit P l'ensemble des postes, A l'ensemble des adresses IP et V l'ensemble des VLAN, et r(p, a, v) : « le poste p a l'adresse a dans le VLAN v ». L'énoncé ∀p ∈ P, ∃a ∈ A, ∃v ∈ V, r(p, a, v) dit : « chaque poste a une adresse dans un VLAN ».

Nier un énoncé à plusieurs quantificateurs

On applique la règle de négation quantificateur par quantificateur, de gauche à droite : chaque ∀ devient ∃, chaque ∃ devient ∀, et le prédicat final est nié.

• ¬(∀x, ∃y, p(x, y)) ≡ ∃x, ¬(∃y, p(x, y)) ≡ ∃x, ∀y, ¬p(x, y)
• ¬(∃x, ∀y, p(x, y)) ≡ ∀x, ∃y, ¬p(x, y)

Exemple : « chaque utilisateur appartient à au moins un groupe » s'écrit ∀u ∈ U, ∃g ∈ G, m(u, g). Sa négation : ∃u ∈ U, ∀g ∈ G, ¬m(u, g), « il existe un utilisateur qui n'appartient à aucun groupe ».

Quantificateurs et requêtes

Les quantificateurs sont partout dans les requêtes et les programmes.

• ∃ en SQL : EXISTS (sous-requête) teste s'il existe au moins une ligne. « Les employés qui ont ouvert au moins un ticket » est un ∃.
• ∀ en SQL : il n'y a pas de mot-clé « pour tout ». On utilise la négation : « tous les tickets de l'employé sont clos » ≡ « il n'existe aucun ticket de l'employé qui ne soit pas clos », d'où NOT EXISTS (… WHERE statut <> 'clos'). C'est exactement la règle ¬∃x, ¬p(x) ≡ ∀x, p(x). Le cours SQL détaille cette technique dans le chapitre sous-requêtes, IN et EXISTS.
• En Python : all(...) pour ∀ et any(...) pour ∃, ou une boucle qui s'arrête au premier contre-exemple (pour ∀) ou au premier exemple (pour ∃).

def tous_pairs(liste):
    """∀x ∈ liste, x est pair : faux dès le premier contre-exemple."""
    for x in liste:
        if x % 2 != 0:
            return False   # contre-exemple trouvé
    return True

print(tous_pairs([2, 8, 14]), tous_pairs([2, 7, 14]))   # True False

Exercices

tailles = [14, 12, 9, 16, 12]
print(all(t >= 12 for t in tailles))   # False : 9 est un contre-exemple
print(any(t < 12 for t in tailles))    # True : la négation est vraie