Leçons de niveau 14

Logique formelle/Calcul des propositions

Une page de Wikiversité.
Sauter à la navigation Sauter à la recherche
Début de la boite de navigation du chapitre
Calcul des propositions
Icône de la faculté
Chapitre no 2
Leçon : Logique formelle
Chap. préc. :Systèmes logiques
Chap. suiv. :Calcul des prédicats
fin de la boite de navigation du chapitre
Icon falscher Titel.svg
En raison de limitations techniques, la typographie souhaitable du titre, « Logique formelle : Calcul des propositions
Logique formelle/Calcul des propositions
 », n'a pu être restituée correctement ci-dessus.

Un système de calcul propositionnel est un système formel logique 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 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 , et

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

  • Tout élément de est une formule.
  • Si et que sont des formules, alors également.
  • Aucune autre formule qu'une obtenue à l'aide de ces règles n'est une formule.

Remarque : la notation 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.