Le nombre d'alternances entre quantificateurs existentiels et universels dans la plus longue séquence alternée d'une formule ; en d'autres termes, le nombre de changements de type de quantificateur (∃→∀ ou ∀→∃) le long d'un chemin maximal à travers les occurrences de quantificateurs.

Principe

La profondeur d'alternance organise la structure quantifiée d'une formule en mesurant combien de fois le type de quantificateur change ; elle sert à classer la complexité logique et à relier les formules aux couches de hiérarchies descriptives ou computationnelles.

Démonstration

Dans la forme pré­nexe ∃x ∀y ∃z P(x,y,z), le motif de quantificateurs ∃→∀→∃ contient deux alternances (∃ vers ∀ puis ∀ vers ∃), donc la profondeur d'alternance vaut 2 ; une formule ∀∀∃∃ comporte une seule alternance.

Mauvaise application

Confondre la profondeur d'alternance avec la profondeur d'imbrication des quantificateurs ou compter des quantificateurs identiques adjacents comme des alternances (par exemple traiter ∃∃ comme une alternance) est une mauvaise application qui surestime la structure réelle d'alternance.

Conséquence

Une profondeur d'alternance correctement identifiée prédit la force d'expression et corrèle souvent avec une augmentation de la complexité décisionnelle ou computationnelle : davantage d'alternances peut placer une spécification dans une couche supérieure d'une hiérarchie et modifier les méthodes de preuve ou d'algorithme applicables.

Inversion

Le concept inverse est un préfixe de quantificateurs sans alternance (tous les quantificateurs du même type), qui n'a aucune alternance et correspond aux fragments purement existentiels ou purement universels dont le comportement et la complexité diffèrent nettement des préfixes alternés.

Limite

S'applique aux séquences de quantificateurs (généralement considérées en forme pré­nexe) et aux séquences alternées le long de chemins syntaxiques ; exclut le comptage de blocs de quantificateurs séparés et non interagissant dans des sous-formules distinctes et dépend de la convention pour mettre les formules en forme pré­nexe.

Tension sémantique

La profondeur d'alternance est en tension avec des mesures apparentées comme le rang de quantificateur (profondeur d'imbrication), la longueur de la formule et le nombre de blocs de quantificateurs ; deux formules peuvent avoir la même profondeur d'alternance tout en différant fortement en rang ou en longueur, rendant délicat le choix de la mesure la plus pertinente.

Synthèse

La profondeur d'alternance compte les changements de polarité entre ∃ et ∀ le long du chemin quantifié le plus long d'une formule ; elle résume la façon dont les quantificateurs alternent et sert d'indicateur syntaxique ciblé de la complexité expressive et computationnelle.