Le nombre de variables distinctes apparaissant dans une formule ou une théorie, où 'distinctes' signifie des symboles de variable syntaxiquement différents ; utilisé comme métrique simple de complexité syntaxique et d'exigence en ressources.

Principe

Le nombre de variables mesure combien d'emplacements séparés sont disponibles ou requis dans une expression ; il interagit avec la structure des quantificateurs, la portée et le renommage, et peut être un paramètre crucial dans des fragments de logique (par exemple le fragment à une variable ou à deux variables).

Démonstration

La formule ∀x ∃y (P(x) ∧ Q(y,z)) contient les variables distinctes x, y, z, donc son nombre de variables est 3 ; renommer y en y' conserve le nombre même si les noms changent.

Mauvaise application

Compter les occurrences de variables (mentions totales) plutôt que les symboles de variables distincts, ou confondre le nombre de variables avec le nombre de variables liées versus libres sans clarification, constitue une mauvaise application et fournit des estimations de complexité trompeuses.

Conséquence

Borner le nombre de variables distinctes dans un langage ou un fragment peut entraîner de forts résultats de décidabilité ou de complexité : de nombreux fragments logiques deviennent décidables ou plus faciles à analyser lorsque le nombre de variables est limité, et les procédures algorithmiques exploitent souvent de telles bornes.

Inversion

La situation inverse considère un approvisionnement non borné ou infini de symboles de variables ; bien que flexible pour représenter de nombreux emplacements distincts, des variables non bornées peuvent obscurcir la complexité et rendre difficiles les bornes algorithmiques uniformes.

Limite

Le nombre de variables se rapporte aux symboles de variables syntaxiquement déclarés présents dans des formules ou une théorie et ne mesure pas directement l'usage des variables (liées vs libres) sauf si le contexte précise cette distinction ; il exclut les méta-variables et les paramètres introduits uniquement au niveau méta.

Tension sémantique

Le nombre de variables est en tension avec des mesures connexes comme le rang des quantificateurs et la longueur de la formule : un petit nombre de variables peut néanmoins permettre une forte alternance de quantificateurs ou de longues formules via la réutilisation de variables, soulevant la question de la mesure la plus pertinente pour capter la complexité.

Synthèse

Le nombre de variables est le nombre de symboles de variables syntaxiquement distincts apparaissant dans une formule ou une théorie ; en tant que paramètre simple et opérationnel, il contraint les portées et l'expressivité et sert fréquemment à classifier et analyser des fragments logiques.