Logique mathématique

S'intéresser à la syntaxe de la logique propositionnelle, c'est considérer les formules qui sont “bien écrites”. Pour cela, on se donne un alphabet (langage que l'on notera L), i.e. un ensemble de symboles, avec :

• Un ensemble V = {p,q,r,...} dénombrable de lettres appelées variables propositionnelles. Il s'agit des propositions atomiques telles que par exemple « 6 est divisible par 2 » ;

• Atomes : Nous appellerons atomes ou variables propositionnelles ou propositions élémentaires des énoncés dont nous ne connaissons pas la structure interne, et qui gardent leur identité tout au long du calcul propositionnel qui nous occupe. L'ensemble des variables propositionnelles est noté v(L). Elles sont écrites en minuscules (p, q...);

• Un ensemble (fini) de connecteurs logiques : ∧, ∨, ¬, →, ≡ ;

• Formules : Nous dénoterons les formules par des lettres majuscules de l'alphabet latin ou grec (A, B, . . . ou φ...). L'ensemble des formules, noté F(L), est défini par : les atomes sont des formules (v(L) ⊆ F(L)) .

Si A et B sont des formules, alors (A ↔B), (A→ B), (A ∧ B), (A ∨B) et (￢ B) sont des formules.

Les parenthèses sont un moyen de lever l'ambiguïté. Il en existe un autre qui consiste à donner à chaque opérateur un ordre de priorité. Les connecteurs sont traditionnellement classés de la façon suivante (par priorité décroissante des connecteurs) : ￢, ∧, ∨, →, ↔. Dans le cas où deux connecteurs ont même priorité, et en l'absence de parenthèses, l'associativité se fait de gauche à droite. On peut ainsi se permettre d'omettre les parenthèses. Par exemple, la formule doit se lire ((p → q) ↔ (￢r)). A l'avenir, lorsque nous parlerons de formules bien formées, nous inclurons également les formules dont le parenthèsage est partiellement ou complètement implicite. L'ensemble des formules bien formées ainsi défini forme le langage de la logique propositionnelle.

Parmi les mots que l'on peut écrire avec cet alphabet, on va regarder ceux qui correspondent à des expressions logiques bien formées que l'on définit (inductivement) ainsi :

1. Toutes les propositions atomiques p,q,r,... sont des expressions bien formées ;

2. Si A est une expression bien formée, alors ¬A est une expression bien formée ;

3. Si A et B sont deux expressions bien formées, alors (A ∧ B), (A ∨ B), (A → B) et (A ≡ B) sont des expressions bien formées ;

4. Il n'y a pas d'autres expressions bien formées que celles des règles précédentes. Par exemple (((¬p ≡ q) ∨ ¬(r ∧ s)) → q) est une expression bien formée, tandis que p¬qr → t(≡ ne l'est pas. Dans la suite, on ne considère que des expressions bien formées.

   • Littéral : Un littéral est un atome (littéral positif) ou la négation d'un atome (littéral négatif).

   • Clause : Une clause est une disjonction de littéraux (p1∨p2∨. . .∨ pn), les littéraux pouvant être positifs ou négatifs.