Formule logique

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

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

Les formules issues du calcul des propositions, aussi appelées formules propositionnelles^[1], sont des expressions de la forme $A\land (B\land C)$ . 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:

Chaque variable propositionnelle est, en soi, une formule.
Si φ est une formule, alors $\lnot$ φ 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> | $\neg$ <form> | (<form> $\wedge$ <form>) | (<form> $\vee$ <form>) | (<form> $\rightarrow$ <form>) | (<form> $\leftrightarrow$ <form>)

En utilisant cette grammaire, la suite de symboles

(((p

\rightarrow

q)

\wedge

(r

\rightarrow

s))

\vee

(

\neg

q

\wedge

\neg

s)) est une formule, car elle est grammaticalement correcte. La suite de symboles

((p

\rightarrow

q)

\rightarrow

(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, de 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 contraignants que d'autres. Par exemple, en supposant que la priorité (du plus contraignant au moins contraignant) 1. $\neg$ 2. $\rightarrow$ 3. $\wedge$ 4. $\vee$ . Ainsi, la formule

(((p

\rightarrow

q)

\wedge

(r

\rightarrow

s))

\vee

(

\neg

q

\wedge

\neg

s))peut être abrégé

p

\rightarrow

q

\wedge

r

\rightarrow

s

\vee

\neg

q

\wedge

\neg

s

Ceci est, cependant, seule une convention utilisée pour simplifier la représentation d'une formule écrite.

Logique des prédicats

La définition d'une formule dans la logique du premier ordre ${\mathcal {QS}}$ 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.

N'importe quelle variable est un terme.
Tout symbole constant de la signature est un terme
une expression de la forme f(t₁,...,t_n), où f est un symbole de fonction n-aire, et t₁,...,t_n sont des termes, est encore un terme.

L'étape suivante consiste à définir les formules atomiques.

Si t₁ et t₂ sont des termes, alors t₁=t₂ est une formule atomique.
Si R est un symbole de relation n-aire, et t₁,...,t_n sont des termes, alors R(t₁,...,t_n) est une formule atomique.

Enfin, l'ensemble des formules est défini comme étant le plus petit ensemble contenant l'ensemble des formules atomiques tel que :

$\neg \phi$ est une formule quand $\ \phi$ est une formule
$(\phi \land \psi )$ et $(\phi \lor \psi )$ sont des formules quand $\ \phi$ et $\ \psi$ sont des formules;
$\exists x\,\phi$ est une formule quand $\ x$ est une variable et $\ \phi$ est une formule;
$\forall x\,\phi$ est une formule quand $\ x$ est une variable et $\ \phi$ est une formule (alternativement, $\forall x\,\phi$ peut être défini comme étant une abréviation de $\neg \exists x\,\neg \phi$ ).

Si une formule n'a aucune occurrence de $\exists x$ ou $\forall x$ , pour toute variable $\ x$ , elle est alors appelée sans-quantificateur. Une formule existentielle est constituée d'une suite de quantifications existentielles suivie par une formule sans-quantificateur.

Formules ouvertes et atomiques

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

Une formule A dans un langage ${\mathcal {Q}}$ est valide si elle est vraie pour toute interprétation de ${\mathcal {Q}}$ .
Une formule A dans un langage ${\mathcal {Q}}$ est satisfaisable si elle est vraie pour quelques interprétations de ${\mathcal {Q}}$ .
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

(en) Cet article est partiellement ou en totalité issu de l’article de Wikipédia en anglais intitulé « Well-formed forumla » (voir la liste des auteurs).

↑ First-order logic and automated theorem proving, Melvin Fitting, Springer, 1996 [1]
↑ 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

Bibliographie

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

Terminologie et ontologie - Cairn.info
La sémantique propositionnelle
La nature des théories scientifiques
(en) Well-Formed Formula for First Order Predicate Logic - inclut un court test en Java.
(en) Well-Formed Formula at ProvenMath

[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].

[1]

[2]