Calcul des propositions - Définition

Introduction

Le calcul des propositions ou calcul propositionnel est une théorie logique qui définit les lois formelles du raisonnement. C'est la version moderne de la logique stoïcienne. C'est aussi la première étape dans la construction des outils de la logique mathématique.

Introduction générale

Assez complexe à définir en général, la notion de proposition a fait l'objet de nombreux débats au cours de l'histoire de la logique ; l'idée consensuelle est qu'une proposition est une construction syntaxique pour laquelle il fait sens de parler de vérité.

En logique mathématique, le calcul des propositions est la première étape dans la définition de la logique et du raisonnement. Il définit les règles de déduction qui relient les propositions entre elles, sans en examiner le contenu ; il est ainsi une première étape dans la construction du calcul des prédicats, qui lui s'intéresse au contenu des propositions et qui est une formalisation achevée du raisonnement mathématique.

Définition d'une proposition

Quoique le calcul des propositions ne se préoccupe pas du contenu des propositions, mais seulement de leurs relations, il peut être intéressant de discuter ce que pourrait être ce contenu.

Une proposition donne une information sur un état de chose. Ainsi « 2 + 2 = 4 » ou « le livre est ouvert » sont deux propositions. En logique classique, une proposition peut prendre uniquement les valeurs vrai ou faux.

Une phrase optative (qui exprime un souhait comme par exemple « Que Dieu nous protège !», une phrase impérative (« viens !», « tais-toi !») ou une interrogation n'est pas une proposition. « Que Dieu nous protège !» ne pouvant être ni vraie ni fausse: elle exprime uniquement un souhait du locuteur. En revanche, une phrase comme « Dans ce calcul, toutes les variables informatiques sont strictement positives » est une proposition dont le contenu a été modifié par le quantificateur toutes et qui est supposée s'avérer dans la durée. Ce type de proposition est étudié dans la logique modale, plus précisément dans la logique temporelle dans ce cas, à cause l'affirmation de sa pérennité.

Définition d'un système déductif

Un calcul ou un système déductif est, en logique, un ensemble de règles permettant en un nombre fini d'étapes et selon des règles explicites de déterminer si une proposition est vraie. Un tel procédé s'appelle une démonstration.

On associe aussi aux propositions une structure mathématique qui permet de garantir que ces raisonnements ou démonstrations ont du sens, on dit qu'on lui a donné une sémantique. En calcul des propositions classique, cette sémantique n'utilise que deux valeurs, vrai et faux (souvent notés 1 et 0). Une proposition entièrement déterminée (c'est-à-dire dont les valeurs des constituants élémentaires sont déterminées) ne prend qu'une seule de ces deux valeurs.

Structure

Dans les théories de la logique mathématique, on considère donc deux points de vue dits syntaxique et sémantique, c'est le cas en calcul des propositions.

• Aspect syntaxique : il s’agit de définir le langage du calcul des propositions par les règles d’écriture des propositions.

• Aspect sémantique : il s’agit ici de donner un sens aux symboles représentant les connecteurs logiques en fonction de la valeur de vérité des propositions de base (ainsi signifie non). Ce sens est donné, par exemple, par des tables de vérité ou par des modèles de Kripke. Puis de décrire les règles d’inférence permettant la déduction de propositions à partir d'autres. Ces règles de déduction permettent d'engendrer des propositions spécifiques que l'on appelle des théorèmes.

Le fait que la déduction corresponde parfaitement à la sémantique s'appelle la complétude.

Le système exposé ci-dessous se situe dans le cadre de la logique classique, qui est la branche de la logique mathématique la plus utilisée en mathématiques. On trouvera une présentation de logiques non classiques. L'adjectif « classique » ne doit pas être pris dans un sens de « normalité », mais comme un attribut que lui a donné l'histoire de la logique, elle aurait tout aussi bien pu s'appeler « booléenne ».