Formule (logique mathematique)

Formule (logique mathematique)

Formule (mathématiques)

Page d'aide sur l'homonymie Pour les articles homonymes, voir formule.

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

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(t1,...,tn), où f est un symbole n-aire de fonction, et t1,...,tn sont des termes.

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

  1. t1=t2, où t1 et t2 sont des termes, ou
  2. R(t1,...,tn), où R est un symbole de relation n-aire, et t1,...,tn 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

Notes et références

  1. Roland Fraïssé, Cours de logique mathématique, Gauthier-Villars Paris 1971-1975, Vol. 1, Relation et formule logique, 1.2 p. 3
  2. Bourbaki Algèbre, Diffusion CCLS Paris 1977, I, §7, n°2
  3. Bourbaki Eléments de mathématiques, Diffusion CCLS Paris 1977, (ISBN 2903684057), E p. I.42
  4. J.F. Pabion Logique mathématique - Hermann Paris 1976 (ISBN 2-7056 5830-0) II 2.2 p.48
Ce document provient de « Formule (math%C3%A9matiques) ».

Wikimedia Foundation. 2010.

Contenu soumis à la licence CC-BY-SA. Source : Article Formule (logique mathematique) de Wikipédia en français (auteurs)

Игры ⚽ Поможем сделать НИР

Regardez d'autres dictionnaires:

  • Formule (Logique Mathématique) — Formule (mathématiques) Pour les articles homonymes, voir formule. 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… …   Wikipédia en Français

  • Formule (logique mathématique) — Formule (mathématiques) Pour les articles homonymes, voir formule. 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… …   Wikipédia en Français

  • LOGIQUE MATHÉMATIQUE — La logique au sens étroit du terme, c’est à dire la logique formelle par opposition à l’épistémologie ou à la théorie de la connaissance, se propose de donner une théorie de l’inférence formellement valide. Elle considère comme valide toute… …   Encyclopédie Universelle

  • Logique Mathématique — La logique mathématique est née à la fin du XIXe siècle de la logique au sens philosophique du terme. Ses débuts furent marqués par la rencontre entre deux idées nouvelles : la volonté chez Frege, Russell, Peano et Hilbert de donner une …   Wikipédia en Français

  • Logique mathematique — Logique mathématique La logique mathématique est née à la fin du XIXe siècle de la logique au sens philosophique du terme. Ses débuts furent marqués par la rencontre entre deux idées nouvelles : la volonté chez Frege, Russell, Peano et… …   Wikipédia en Français

  • Logique mathématique — La logique mathématique, ou logique formelle, est une discipline des mathématiques introduite à la fin du XIXe siècle et qui s est donnée comme objet l étude des mathématiques en tant que langage. Les objets fondamentaux de la logique… …   Wikipédia en Français

  • Proposition (logique mathématique) — Calcul des propositions Pour les articles homonymes, voir Déduction. Le calcul des propositions ou calcul propositionnel est une théorie logique qui définit les lois formelles du raisonnement. C est la version moderne de la logique stoïcienne. C… …   Wikipédia en Français

  • Prédicat (logique mathématique) — Pour les articles homonymes, voir prédicat. Sur les autres projets Wikimedia : « Prédicat (logique mathématique) », sur le Wiktionnaire (dictionnaire universel) Cet article court présente un sujet plus développé dans : Calcul… …   Wikipédia en Français

  • Formule Bien Formée — En logique mathématique, le sigle anglais WFF (prononcé wiff ) est une abréviation pour well formed formula, c.à.d en Français formule bien formée. Soit une grammaire formelle, un WFF est toute chaîne qui est générée par cette grammaire. Par… …   Wikipédia en Français

  • Formule bien fondée — Formule bien formée En logique mathématique, le sigle anglais WFF (prononcé wiff ) est une abréviation pour well formed formula, c.à.d en Français formule bien formée. Soit une grammaire formelle, un WFF est toute chaîne qui est générée par cette …   Wikipédia en Français

Share the article and excerpts

Direct link
Do a right-click on the link above
and select “Copy Link”