Formule logique

Un article de Wikipédia, l'encyclopédie libre.
Aller à : navigation, rechercher

En logique on dit d’une suite finie de lettres qu’elle est une formule, ou parfois formule bien formée, d'un langage logique donné. Lorsqu’elle peut être construite en appliquant une combinaison des règles de la grammaire formelle associée, on parle de la syntaxe du langage. Informellement les formules sont les assemblages de lettres auxquels il est possible de donner une signification en termes de valeur de vérité (Vrai, ou Faux). Les formules logiques sont l'équivalent des phrases du langage naturel.

Les formules du langage sont interprétées, suivant la sémantique de la logique considérée, en leur attribuant une valeur de vérité. La syntaxe du calcul des prédicats nécessite d'introduire une autre notion, celle de terme, la syntaxe des termes du langage étant liée à une signature. Les termes sont eux interprétés par des objets (nombres, points, etc.).

Il est possible d'assembler les formules pour construire des démonstrations, suivant des règles formelles associées à un système de déduction.

L'appellation « formule bien formée » (traduction de (en)well-formed formula) pour formule, est une trace d'un usage ancien où on appelait formules les suites finies de caractères quelconques.

Introduction[modifier | modifier le code]

L'utilisation clé de formules est en logique propositionnelle, telle que la logique du premier ordre. Dans ce contexte, une formule est une chaîne de symboles φ pour lesquels il faut se demander «est ce que φ vrai?», une fois que toutes les variables libres dans φ ont été instancié. En logique formelle, les démonstrations peuvent être représentées par des suites de formules munis de certaines propriétés, et la formule finale est ce qui est prouvé.

Les formules sont des objets syntaxiques. Elles sont donnés par des interprétations. Par exemple, dans une formule propositionnelle, chaque variable propositionnelle peut être interprétée comme une proposition concrète, de sorte que la formule globale exprime une relation entre ces propositions.

Calcul des propositions[modifier | modifier le code]

Les formules issues du calcul des propositions, aussi appelées formules propositionnelles,[1] sont des expressions de la forme . Leur définition commence par le choix arbitraire d'un ensemble V de variables propositionnelles. L'alphabet se compose des lettres de V avec les symboles correspondants aux conjonctions et aux parenthèses propositionnelles « ( » et « ) », qui sont tous supposés ne pas être en V. Les formules seront certaines expressions (c'est-à-dire, des chaînes de symboles) sur cet alphabet. Les formules sont inductivement définies comme suit:

  • Chauqe variable propositionnelle est, en soi, une formule.
  • Si φ est une formule, alors φ est une formule.
  • Si φ et ψ sont des formules, et • est n'importe quelle connecteur binaire, alors ( φ • ψ) est une formule. Ici • pourrait être (mais sans y être limité) un des opérateurs usuels ∨, ∧, →, ou ↔.Cette définition peut aussi être écrite en grammaire formelle sous la forme de Backus-Naur, à condition que l'ensemble des variables est finie:

    <alpha set> ::= p | q | r | s | t | u | ... (ensemble fini arbitraire de variables propositionnelles)

    <form> ::= <alpha set> | <form> | (<form><form>) | (<form><form>) | (<form><form>) | (<form><form>)

En utilisant cette grammaire, la suite de symboles

(((p q) (r s)) (q s))est une formule, car elle est grammaticalement correct. La suite de symboles
((p q)(qq))p))

n'est pas une formule, car elle ne se conforme pas à la grammaire.

Une formule complexe peut être difficile à lire, en raison, par exemple, la prolifération des parenthèses. Pour remédier à ce problème, les règles de priorité (semblable à l'ordre mathématique standard des opérations) sont imposées entre les opérateurs, ce qui rend certains opérateurs plus contraignant que d'autres. Par exemple, en supposant que la priorité (du plus contraignant au moins contraignante) 1.   2.   3.   4. . Ainsi, la formule

(((p q) (r s)) (q s))peut être abrégé
p q r s q sCeci est, cependant, seule une convention utilisée pour simplifier la représentation d'une formule écrite.

Logique des prédicats[modifier | modifier le code]

La définition d'une formule dans la logique du premier ordre est relative à sa signature de la théorie en question. Cette signature spécifie les symboles constants, de relation, et les symboles de fonction de la théorie, ainsi que les arités des symboles de fonction et de relation.

La définition d'une formule vient en plusieurs parties. Tout d'abord, l'ensemble des termes est défini de manière récursive. Les termes, de façon informelle, sont des expressions qui représentent des objets du domaine du discours.

  1. N'importe quelle variable est un terme.
  2. Tout symbole constant de la signature est un terme
  3. une expression de la forme f(t1,...,tn), où f est une symbole de fonction n-aire, et t1,...,tn sont des termes, est encore un terme.L'étape suivante consiste à définir les formules atomiques.
  4. Si t1 et t2 sont des termes, alors t1=t2 est une formule atomique.
  5. Si R est un symbole de relation n-aire, et t1,...,tn sont des termes, alors R(t1,...,tn) est une formule atomiqueEnfin, l'ensemble des formules est défini comme étant le plus petit ensemble contenant l'ensemble des formules atomiques tel que:
  6. est une formule quand est une formule
  7. et sont des formules quand et sont des formules;
  8. est une formule quand est une variable et est une formule;
  9. est une formule quand est une variable et est une formule (alternativement, peut être défini comme étant une abréviation de ).

Si une formule a aucune occurrence de ou , pour toute variable , il est alors appelé sans-quantificateur. Une formule existentielle est une formule à partir d'une suite de quantification existentielle suivie par une formule sans-quantificateur.

Formules ouvertes et atomiques[modifier | modifier le code]

Article détaillé : formule atomique.

Une formule atomique est une formule qui ne contient pas de connecteurs logiques ni de quantificateurs. La forme précise de formules atomiques dépend du système formel en question; pour la logique propositionnelle, par exemple, les formules atomiques sont des variables propositionnelles. Pour le calcul des prédicats, les formules atomiques sont des symboles de prédicat avec leurs arguments, chaque argument étant un terme.

Selon sa terminologie, une formule ouverte est formée en combinant des formules atomiques en utilisant uniquement des connecteurs logiques, excluant les quantificateurs.[2] Elle ne doit pas être confondue avec une formule qui n'est pas fermée.

Propriétés applicables aux formules[modifier | modifier le code]

  • Une formule A dans un langage est valide si elle est vraie pour toute interprétation de .
  • Une formule A dans un langage est satisfaisable si elle est vraie pour quelques interprétations de .
  • Une formule A du langage de l'arithmétique est décidable si elle représente un ensemble décidable, à savoir s'il existe une méthode efficace qui, étant donné une substitution des variables libres de A, dit si A est prouvable ou si sa négation l'est.

Références[modifier | modifier le code]

  1. First-order logic and automated theorem proving, Melvin Fitting, Springer, 1996 [1]
  2. Handbook of the history of logic, (Vol 5, Logic from Russell to Church), Tarski's logic by Keith Simmons, D. Gabbay and J. Woods Eds, p568 [2].

Voir aussi[modifier | modifier le code]

Bibliographie[modifier | modifier le code]

  • René Cori, Daniel Lascar, Logique mathématique, tome 1 : Calcul propositionnel, algèbre de Boole, calcul des prédicats [détail des éditions]

Liens externes[modifier | modifier le code]