Logique formelle/Calcul des propositions

Un système de calcul propositionnel est un système formel logique $ℒ=ℒ(\mathrm{A},\mathrm{\Omega },\mathrm{Z},\mathrm{I})$ constitué de :

• Un alphabet Α qui est un ensemble fini dont les éléments sont appelés variables propositionnelles. On les notera en général p, q, r, s,...
• Un ensemble fini de connecteurs logiques Ω qui peut être partitionné en $\mathrm{\Omega }=\bigsqcup _{i=0}^n{\mathrm{\Omega }}_i$ où ${\mathrm{\Omega }}_i$ désigne l’ensemble des symboles d'arité j.

L'arité correspond au nombre de variables du connecteur logique. Par exemple, en logique mathématique, on a en général $\mathrm{\Omega }={\mathrm{\Omega }}_0\cup {\mathrm{\Omega }}_1\cup {\mathrm{\Omega }}_2$ où ${\mathrm{\Omega }}_0=\{\mathrm{\top },\mathrm{\perp }\}$, ${\mathrm{\Omega }}_1=\{\mathrm{\neg }\}$ et ${\mathrm{\Omega }}_2=\{\wedge ,\vee ,⟹,⟺\}$

Le langage est alors défini récursivement de la façon suivante :

• Tout élément de $\mathrm{A}\cup {\mathrm{\Omega }}_0$ est une formule.
• Si $f\in {\mathrm{\Omega }}_i$ et que $p_1,p_2,...,p_i$ sont des formules, alors $f(p_1,p_2,...,p_i)$ également.
• Aucune autre formule qu'une obtenue à l'aide de ces règles n'est une formule.

Remarque : la notation $f(p_1,p_2,...,p_i)$ est juste une question de convention ; suivant le système formel étudié, n’importe quelle notation (préfixée, infixée, postfixée, ...) pourra être utilisée.

On peut également remarquer que pour, une suite finie de symboles, le fait d’être ou non une formule est décidable : il est possible d'expliciter un algorithme qui décidera en un temps fini si la suite de symboles est ou non une formule.