Formule (logique mathematique)

En logique et en mathématiques, une formule est une suite finie d'objets, dotée de propriétés particulières qui rendent possible la syntaxe dans tous ces domaines.

Sommaire 1 Définition 2 Propriétés 3 Voir aussi 4 Notes et références

Définition

Étant donnés un ensemble E et une fonction poids p: E →N, une formule est un mot extrait de E obtenu par les deux règles de construction suivantes : ^[1]

1. un seul élément de E de poids 0 est une formule ;
2. si t est un élément de poids n, pour toute suite de n formules F1, F2, ...., Fn, le mot concaténé tF1F2....Fn est une formule.

On reconnaît les « mots significatifs » qui forment un sous-ensemble du monoïde libre Lo(E) construit sur E.^{[2] [3]}

La notation théorique introduite ici est celle dite de Łukasiewicz ou « notation polonaise » ; mais la notation communément utilisée en algèbre et en analyse est celle à parenthèses t(F2, ...., Fn) ; si t est de poids 2, on écrit (F1)t(F2) au lieu de tF1F2, et

[r(F1, ...., Fm)] t [s(G1, ...., Gn)] au lieu de trF1 ....FmsG1....Gn.

Étant donnée une formule F, tout intervalle de F qui est une formule en est une sous-formule. Ainsi, F1, rF1....Fm, sG1....Gn sont des sous-formules de trF1 ....FmsG1....Gn.

Si F = tF1F2....Fn, les Fi 1≤i≤n sont les sous-formules immédiates de F.

Il est facile de voir que dans tout ensemble de formules la relation binaire « F est une sous-formule de G » est une relation d'ordre : réflexive, antisymétrique et transitive.

Propriétés

• Si F est une formule et M un mot non vide, alors FM n’est pas une formule.
• Corollaire - Si F1, F2, …., Fm, G1, G2, …., Gn sont des formules et si F1F2…Fm = G1G2…Gn, alors m=n et pour tout i≤n, Fi= Gi.

En effet, d’après le théorème précédent , on ne peut avoir Fi = GiM ou Gi = FiM à moins que M ne soit vide.

• Soient F une formule et t un signe de poids p ; alors les signes qui suivent t dans F se répartissent de façon unique en un nombre m≥p d’occurrences de sous-formules consécutives et disjointes.
• Étant données deux occurrences de sous – formules de F, ou bien elles sont disjointes, ou bien l’une est incluse dans l’autre.

De tout cela il résulte que l’on peut dire :

• La relation d’inclusion sur les occurrences de sous-formules d’une formule, est un ordre ramifié, ou arbre syntaxique, dans lequel , pour tout élément, les éléments antérieurs sont tous comparables.

Les formules sont définies relativement à un langage formel, qui est une collection de symboles constants, de symboles de fonction et de symboles de relation, où chacun des symboles de fonctions et de relation vient avec une arité qui indique le nombre d'arguments qu'elle prend.

Ensuite on définit récursivement un terme comme

1. Une variable,
2. Un symbole constant, ou
3. f(t₁,...,t_n), où f est un symbole n-aire de fonction, et t₁,...,t_n sont des termes.

Finalement, une formule revêt l'une des formes suivantes :^[4]

1. t₁=t₂, où t₁ et t₂ sont des termes, ou
2. R(t₁,...,t_n), où R est un symbole de relation n-aire, et t₁,...,t_n sont des termes, ou
3. (¬φ), où φ est une formule, ou
4. (φ∧ψ), où φ et ψ sont des formules, ou
5. (∃x)(φ), où x est une variable et φ est formule.

On appelle les deux premiers cas des formules atomiques.

Voir aussi

• Formule bien formée
• Mot (mathématiques)
• Monoïde
• Arbre syntaxique

Notes et références