Un niveau minimal de capacité d'expression qu'un fragment logique ou une logique doit posséder pour capter une classe donnée de phénomènes ou de propriétés ; l'ensemble le plus restreint de constructions syntaxiques et de garanties sémantiques nécessaires pour être adéquat vis-à-vis d'une spécification cible.

Principe

Les planchers sont déterminés par les propriétés de fermeture minimales et les opérateurs indispensables pour exprimer des distinctions essentielles (par exemple la possibilité d'énoncer des faits atomiques, d'utiliser des combinaisons booléennes ou de quantifier existentiellement), et dépendent de la classe de modèles et des propriétés visées.

Démonstration

Si l'on souhaite qu'une logique caractérise l'atteignabilité dans des graphes orientés arbitraires, la logique doit au minimum fournir un mécanisme pour la clôture transitive ou un opérateur à point fixe équivalent ; sans un tel opérateur aucun fragment de la logique du premier ordre ne peut servir de plancher requis — cette capacité requise est le plancher d'expressivité pour l'atteignabilité.

Mauvaise application

Traiter le plancher comme un seuil numérique ou comme impliquant que toute logique satisfaisant le plancher sera efficace ; un plancher n'affirme qu'une adéquation minimale d'expressivité, pas la concision, la décidabilité ou le faible coût computationnel.

Conséquence

Identifier un plancher clarifie les choix de conception : toute logique candidate qui échoue au plancher ne peut représenter les phénomènes cibles et doit être étendue, tandis que satisfaire le plancher permet d'engager une analyse des compromis entre expressivité, concision et complexité.

Inversion

Retirer des constructions situées au-dessous du plancher (par exemple interdire les combinaisons booléennes ou la quantification existentielle) produit une logique incapable d'exprimer la classe cible ; inversement, enrichir une logique au-delà du plancher augmente les capacités mais peut entraîner des coûts en complexité.

Limite

Un plancher est relatif à une spécification cible et à une classe de modèles choisies ; il n'implique pas d'universalité pour toutes les tâches et exclut des considérations telles que l'efficacité algorithmique ou la praticabilité de l'inférence dans la logique qui satisfait le plancher.

Tension sémantique

Il existe une tension entre fixer un plancher bas (qui préserve simplicité et traçabilité) et relever le plancher (qui garantit une expressivité plus riche mais risque une explosion de complexité) ; les planchers interagissent avec les plafonds, un plancher proche du plafond laissant peu de place à des logiques intermédiaires.

Synthèse

Un plancher d'expressivité spécifie les caractéristiques syntaxiques et sémantiques minimales qu'une logique doit posséder pour capturer de manière significative une classe de propriétés : c'est un critère de conception assurant l'adéquation pour une tâche, qui guide ensuite le choix entre garder la logique minimale ou la renforcer en connaissance des compromis.