Introduction au calcul des propositions

Introduction

Nous allons maintenant introduire une classe de langages particuliers, que l'on va appeler langages propositionnels. Les mots de ces langages seront appelés des énoncés, parce que nous voulons pouvoir dire que ces «mots» sont vrais ou faux. Les mots des langages propositionnels seront aussi appelés formules. Nous verrons plus tard d'autres langages où l'on fera une distinction entre mots du langages, formules et énoncés.

Nous pouvons commencer par introduire un type particulier d'énoncés: les proposition. Ces propositions sont aussi appelées formules atomiques (atomique au sens de «insécable»), c'est à dire que ce sont des formules qui ne sont pas construits à partir d'autres formules.

Dans les langages propositionnels, on note les propositions par un simple symbole, généralement avec une lettre minuscule. De combien de symboles avons-nous besoin? Il n'y a pas de réponse à cette question dans le sens que l'on définit ici une classe de langages et non un langage en particulier, aussi on peut autoriser un nombre de symboles différents suivant les langages. Il en faut toutefois au moins un (sans quoi il n'y aurait aucun mot dans le langage, à part le mot vide qui ne contient aucun symbole), mais on peut en avoir autant que l'on veut, même une infinité. On conviendra d'utiliser les lettres: $p, q, r, s, . . .$ comme symboles propositionnels, éventuellement, on peut rajouter un indice si on manque de lettres et utiliser $p_{1}, q_{1}, . . . p_{2}, q_{2}, . . .$ (notez qu'une écriture comme $p_{1}$ est considéré comme un seul symbole).

Si on s'arrête ici, on aura des langages parfaitement inutiles. L'idée est de construire des formules à partir des symboles propositionnels et d'autres symboles, qu'il reste à définir, que l'on appellera des connecteurs logiques. Comme leur nom l'indique, il vont «connecter» les formules atomiques de façon à construire des formules composées, qui seront donc des formules avec plus d'un symbole. On peut s'attendre à ce que l'on puisse les utiliser de la même façon pour «connecter» des formules atomiques et des formules composées. Ainsi, on pourra définir, étant donné un certain connecteur logique et un certain nombre d'énoncés (de formules), comment on peut construire une formule qui les combine, sans se préoccuper de savoir si les formules que l'on combine sont atomiques ou non.

Pour représenter symboliquement cette construction, un problème se pose. On voudrait disposer de symboles qui puissent représenter n'importe quel énoncé, pour définir proprement la syntaxe des langages propositionnels. On conviendra alors de noter les énoncés par des lettres majuscules $A, B, C, . . .$ , mais ici il faut bien comprendre que ces symboles ne font pas partie des langages propositionnels !! Il servent à définir plus facilement la syntaxe de tels langages, on peut dire que ces symboles font partie d'un méta-langage.

Il faudra aussi définir proprement la sémantique de ces langages, c'est à dire se poser la question de la signification des énoncés. On peut déjà dire qu'à chaque proposition correspond une valeur de vérité: soit vrai soit faux. Anticipant un peu sur la suite, on peut déjà donner des principes qui seront valable pour n'importe quel énoncé:

principe de bivalence: les deux seules valeurs de vérité possible sont le vrai et le faux,
principe du tiers-exclu: à tout énoncé on associe soit le vrai, soit le faux, aucun énoncé est dépourvu de valeur de vérité,
principe de non-contradiction: aucun énoncé ne avoir plus d'une valeur de vérité, un énoncé ne peut donc être à la fois vrai et faux.

On a alors la définition suivante:

Définition 4.

Soit $L$ un langage propositionnel. Une $L$ -assignation est une relation qui à chaque formule atomique de $L$ associe une et une seule valeur de vérité, soit $V$ (vrai), soit $F$ (faux).

Connecteurs logiques

Prenons un exemple. Considérons deux énoncés $A$ et $B$ . On peut imaginer que de $A$ on peut déduire $B$ , c'est à dire que si $A$ est vrai, alors $B$ est vrai lui aussi. On écrit alors: «si $A$ alors $B$ ». Mais on a alors que la phrase «si $A$ alors $B$ » peut être vrai ou fausse.

On peut faire un raisonnement intuitif en associant à $A$ et $B$ des énoncés du langage naturel. Si $A$ veut dire «ceci est un est cobra» et $B$ veut dire «ceci est un serpent», alors «si $A$ alors $B$ » veut dire «si ceci est un cobra alors ceci est un serpent» ce qui est vrai. Mais on peut imaginer que $A$ veuille dire «ceci est un tigre» et alors «si $A$ alors $B$ » devient faux.

On comprend alors que lorsque l'on combine des énoncés de cette manière, on obtient des énoncés qui ont aussi une valeur de vérité, et que cette valeur de vérité dépend des valeurs de vérités des énoncés $A$ et $B$ .

Les mots «si» et «alors» sont des connecteurs logiques (en fait il n'en forment qu'un puisqu'on les utilisent ensembles). Nous allons maintenant en voir d'autres et représenter chaque connecteur par un symbole différent.

Le connecteur «non» (négation)

C'est le connecteur le plus simple de tous. Considérons une proposition $A$ . La proposition «non $A$ » est vrai si $A$ est faux, et fausse si $A$ est vrai. Ce connecteur s'écrit symboliquement $\neg$ .

On peut illustrer cela dans un tableau que l'on appelle «table de vérité»:

$A$	$\neg A$
V	F
F	V

Ce type de tableau est simple et nous l'utiliserons encore beaucoup.

Le connecteur «ou» (disjonction)

Ce connecteur permet de former des énoncés comme « $A$ ou $B$ » mais il faut faire attention que si $A$ et $B$ sont tout les deux vrais alors « $A$ ou $B$ » est vrai aussi (c'est juste une convention, ne vous casser pas la tête à savoir pourquoi!). C'est pourquoi on précise parfois «ou inclusif» (par opposition au «ou exclusif» souvent utilisé en langage courant). Ce connecteur s'écrit $\lor$ .

On peut tout comme avec le connecteur «non», résumer tout cela par une table de vérité:

$A$	$B$	$A \lor B$
V	V	V
V	F	V
F	V	V
F	F	F

Se souvenir de cette table est très facile: On a simplement que $A \lor B$ est faux si $A$ et $B$ sont tout les deux faux, vrai dans tout les autres cas.

Le connecteur «et» (conjonction)

Ce connecteur permet de former des énoncés comme « $A$ et $B$ ». Sa signification est exactement la même que celle du mot «et» français: « $A$ et $B$ » n'est vrai que si $A$ et $B$ sont tout les deux vrais. Il est représenté par le symbole $\land$ .

Sa table de vérité est la suivante:

$A$	$B$	$A \land B$
V	V	V
V	F	F
F	V	F
F	F	F

Le connecteur «si... alors» (conditionnel matériel ou implication)

Il est représenté par le symbole: $\Rightarrow$ .

$A$	$B$	$A \Rightarrow B$
V	V	V
V	F	F
F	V	V
F	F	V

«si $A$ alors $B$ » veut dire tout simplement que si $A$ est vrai, $B$ l'est nécessairement aussi.

Mais la table de vérité peut surprendre. Pourquoi les deux «V» au bas de la colonne de droite? Ici pour comprendre, considérons chaque cas un à un.

Premier cas: le vrai implique le vrai. C'est assez logique: par définition de l'implication, si $A$ est vrai, $B$ est vrai aussi. Deuxième cas: le vrai n'implique pas le faux!! Logique encore une fois: à partir d'une proposition vraie, on ne pourra jamais en déduire une proposition fausse.

Donnez une valeur de vérité à $A \Rightarrow B$ quand $A$ est faux est plus délicat. Commençons par le cas où $B$ est vrai. On voit dans la table de vérité que $A \Rightarrow B$ est vrai. Cela veut dire qu'à partir d'une proposition fausse, on peut très bien aboutir à une conclusion vraie. Cela peut paraître étrange mais nous allons donner un exemple.

Supposons donc que $A$ veuille dire: « $2 + 2 = 5$ » (proposition fausse donc). On peut en déduire facilement une proposition vraie: il suffit de multiplier chaque cotés de l'égalité par zéro. On a donc $0 \cdot (2 + 2) = 0 \cdot 5$ ce qui donne $0 = 0$ c'est à dire une proposition vraie! Le faux implique donc le vrai.

Enfin, montrer que le faux implique le faux est très facile. en effet de « $2 + 2 = 5$ » on peut déduire directment que... « $2 + 2 = 5$ »!!

Le connecteur «est équivalent à»

Le connecteur «équivalence» s'écrit symboliquement: $\Leftrightarrow$ et veut dire: «à la la même valeur de vérité que».

$A$	$B$	$A \Leftrightarrow B$
V	V	V
V	F	F
F	V	F
F	F	V

D'autres connecteurs

Ces connecteurs ne sont pas ou peu utilisés en mathématique, mais plutôt en électronique et en informatique. Comme on les utilise surtout en informatique, on utilise le «1» à la place du «V» et le «0» à la place du «F».

Ces connecteurs sont aussi appelés des «portes logiques». La porte NOT est le «non»logique, la porte AND est le «et» et la porte OR est le «ou». On trouve aussi la porte NOR (NOT OR):

A	B	A NOR B
1	1	0
1	0	0
0	1	0
0	0	1

La porte XOR (ou exclusif):

A	B	A XOR B
1	1	0
1	0	1
0	1	1
0	0	0

La porte NAND (NOT AND):

A	B	A NAND B
1	1	0
1	0	1
0	1	1
0	0	1

Langages propositionnelles

Il est maintenant facile de donner l'alphabet et la syntaxe des langages propositionnels:

L'alphabet d'un langage de logique propositionnelle est constitué:

d'un ensemble éventuellement infini de symboles propositionnels: $p, q, r, s, . . .$ ,
des symboles: $\neg, \lor, \land, \Rightarrow, \Leftrightarrow$ ,
des séparateurs (parenthèses): «(» et «)».

Les parenthèses sont utiles dans les énoncés logiques car il faut se rendre compte par exemple qu'un énoncé de la forme $\neg A \lor B$ n'est pas équivalent à un énoncé de la forme $\neg (A \lor B)$ .

On peut ensuite définir la syntaxe:

Syntaxe: l'ensemble des formules d'un langage propositionnel est le plus petit ensemble tel que:

si $A$ est un symbole propositionnel alors $A$ est une formule,
si $A$ est une formule, alors $\neg A$ est une formule,
si $A$ et $B$ sont des formules, alors $(A \lor B)$ est une formule,
si $A$ et $B$ sont des formules, alors $(A \land B)$ est une formule,
si $A$ et $B$ sont des formules, alors $(A \Rightarrow B)$ est une formule,
si $A$ et $B$ sont des formules, alors $(A \Leftrightarrow B)$ est une formule.

Petite remarque: pourquoi dit-on dans la définition: «le plus petit ensemble»? L'explication est simple. Si on avait la même définition mais sans préciser cela, on ne saurait pas par exemple, si la formule $A \lor \land B$ est valide ou pas. En effet, la définition n'implique pas que cette formule existe, mais ne l'interdit pas non plus. C'est pour cela que l'on précise «le plus petit ensemble», sinon la définition ne serait pas correcte.

Valuation

Étant donné un langage propositionnel $L$ et une $L$ -assignation, on peut attribuer une valeur de vérité à chaque formule atomique. Mais alors, on peut assigner une valeur de vérité aux formules composées grâces aux tables de vérité, à la $L$ -assignation correspond donc une $L$ -valuation qui fait fait à tout les énoncés une valeur de vérité. On va maintenant énoncer un théorème qui dit simplement qu'étant donnée une $L$ -assignation, il existe une et une seule $L$ -valuation associée. On verra alors que les tables de vérités ne sont que des conséquences de ce théorème, qui définit comment on associe une valeur de vérité à toute formule.

Théorème 1.

Soit $L$ un langage propositionnel, à chaque $L$ -assignation possible $M$ correspond une et une seule relation appelée $L$ -valuation et notée $V_{M}$ , qui à chaque énoncé $A$ fait correspondre une et une seule valeur de vérité qui ne peut être que $V$ ou $F$ , tel que, en notant $M (A)$ la valeur de vérité associée à la proposition $A$ par $M$ , et $v_{M} (A)$ la valeur de vérité associée à la proposition $A$ par $V_{M}$ :

Si $A$ est une proposition, $v_{M} (A) = M (A)$ .
Si $A$ est une formule, $v_{M} (\neg A) = V$ si et seulement si $v_{M} (A) = F$ .
Si $A$ et $B$ sont des formules, $v_{M} (A \lor B) = V$ si et seulement si $v_{M} (A) = V$ et/ou $v_{M} (B) = V$ .
Si $A$ et $B$ sont des formules, $v_{M} (A \land B) = V$ si et seulement si $v_{M} (A) = V$ et $v_{M} (B) = V$ .
Si $A$ et $B$ sont des formules, $v_{M} (A \Rightarrow B) = V$ si et seulement si $v_{M} (A) = F$ et/ou $v_{M} (B) = V$ .
Si $A$ et $B$ sont des formules, $v_{M} (A \Leftrightarrow B) = V$ si et seulement si $v_{M} (A) = v_{M} (B)$ .

Démonstration. Montrons d'abord que pour toute formule $X$ , on a au moins une valuation. Si $X$ est une proposition, on a tout simplement $v_{M} (X) = M (X)$ . Sinon, par la syntaxe du langage, on sait que $X$ peut s'écrire sous au moins l'une des forme suivantes: $\neg A$ , $(A \lor B)$ , $(A \land B)$ , $(A \Rightarrow B)$ et $(A \Leftrightarrow B)$ , où $A$ et $B$ sont des formules. Les règles données dans le théorème nous donne alors une valeur de vérité, connaissant la valeur de vérité de $A$ et $B$ . Mais eux-mêmes peuvent se mettre sous au moins l'une des formes $\neg A'$ , $(A' \lor B')$ , $(A' \land B')$ , $(A' \Rightarrow B')$ et $(A' \Leftrightarrow B')$ , donc on peut obtenir leur valeur de vérité en fonction d'autre énoncés et ainsi de suite jusqu'à arriver à la valuation de propositions.

Montrons maintenant qu'il n'y a qu'une valuation pour chaque formule. Pour les propositions, c'est trivialement vrai. Sinon, supposons deux valuations $v_{M}$ et $v_{M}'$ différentes sur certaines formules. Si pour deux formules $A$ et $B$ on a $v_{M} (A) = v_{M}' (A)$ et $v_{M} (B) = v_{M}' (B)$ (et il est toujours possible d'en trouver puisque l'on peut choisir des propositions), alors on a $v_{M} (\neg A) = v_{M}' (\neg A)$ , $v_{M} (A \lor B) = v_{M}' (A \lor B)$ , ..., et on peut refaire le même raisonnement avec ces formules composées, et ainsi de suite. De proche en proche, on a $v_{M} (X) = v_{M}' (X)$ pour toute formule $X$ .

Notons que les tables de vérités sont une conséquence de ce théorème, une façon schématique simple de représenter les règles qui définissent les $L$ -valuations.

Page Précédente Sommaire Page Suivante