3. CALCUL PROPOSITIONNEL



THÉORIE DE LA DÉMONSTRATION

1. Crise des fondements

1.1.Paradoxes

2. Raisonnement hypothético-déductif

3. Calcul propositionnel

3.1. Propositions

3.2. Connecteurs

3.3. Procédures de décision

3.3.1. Procédures de décision non axiomatisées

3.3.2. Procédures de décision axiomatisées

3.4. Quantificateurs

4. Calcul des prédicats

4.1. Grammaire

4.2. Langages

4.2.1. Symboles

4.2.2. Termes

4.2.3. Formules

5. Démonstrations

5.1. Règles de démonstration

Le "calcul propositionnel" (ou "logique propositionnelle") est un préliminaire absolument indispensable pour aborder une formation en sciences, philosophie, droit, politique, économie, etc. Ce type de calcul autorise des procédures de décisions ou tests. Ceux-ci permettent de déterminer dans quel cas une expression (proposition) logique est vraie et en particulier si elle est toujours vraie.

Définitions:

D1. Une expression toujours vraie quel que soit le contenu linguistique des variables qui la composent est appelée une "expression valide", une "tautologie", ou encore une "loi de la logique propositionnelle".

D2. Un expression toujours fausse est appelée une "contradiction" ou "antologie"

D3. Une expression qui est parfois vraie, parfois fausse est appelée une "expression contingente"

D4. Nous appelons "assertion" une expression dont nous pouvons dire sans ambiguïté s'il elle est vraie ou fausse.

D5. Le "langage objet" est le langage utilisé pour écrire les expressions logiques.

D6. Le "métalangage" est le langage utilisé pour parler du langage objet dans la langue courante

Remarques:

R1. Il existe des expressions qui ne sont effectivement pas des assertions. Par exemple, l'énoncé : "cet énoncé est faux", est un paradoxe qui ne peut être ni vrai, ni faux.

R2. Soit un expression logique A. Si celle-ci est une tautologie, nous la notons fréquemment equation et s'il l'expression est une contradiction, nous la notons equation.


3.1. PROPOSITIONS

Définition: En logique, une "proposition" est une affirmation qui a un sens. Cela veut dire que nous pouvons dire sans ambiguïté si cette affirmation est vraie (V) ou fausse (F). C'est ce que nous appelons le "principe du tiers exclu".

exemple Exemple:

"Je mens" n'est pas une proposition. Si nous supposons que cette affirmation est vraie, elle est une affirmation de sa propre invalidité, donc nous devrions conclure qu'elle est fausse. Mais si nous supposons qu'elle est fausse, alors l'auteur de cette affirmation ne ment pas, donc il dit la vérité, aussi la proposition serait vraie.

Définition: Une proposition en logique binaire (où les propositions sont soit vraies, soit fausses) n'est donc jamais vraie et fausse à la fois. C'est que nous appelons le "principe de non-contradiction".

Ainsi, une propriété sur l'ensemble E des propositions est une application P de E dans l'ensemble des "valeurs de vérité" :

equation   (1.2)

Nous parlons de "sous-ensemble associé", lorsque la proposition engendre uniquement une partie E' de E et inversement.

exemple Exemple:

Dans equation, si P(x) s'énonce "x est pair" , alors equation ce qui est bien seulement un sous-ensemble associé de E mais de même cardinal (cf. chapitre Théorie Des Ensembles).

Définition: Soit P une propriété sur l'ensemble E. Une propriété Q sur E est une "négation" de P si et seulement si, pour tout equation :

- equation est F si P(x) est V

- equation est V si P(x) est F

Nous pouvons rassembler ces conditions dans une table dite "table de vérité" :

P

Q

V

F

F

V

Tableau: 1.1  - Table de vérité des valeurs

En d'autres termes, P et Q ont toujours des valeurs de vérité contraires. Nous noterons ce genre d'énoncé "Q est une négation de P" :

equation   (1.3)

où le symbole equation est le "connecteur de négation".

Remarque: Les expressions doivent être des expressions bien formées (souvent abrégé "ebf"). Par définition, toute variable est une expression bien formée, alors equation est une expression bien formée. Si P,Q sont des expressions bien formées, alors equation est une expression bien formée (l'expression "je mens" n'est pas bien formée car elle se contredit elle-même).

3.2. CONNECTEURS

Il y a d'autres types de connecteurs en logique :

Soit P et Q deux propriétés définies sur le même ensemble Eequation (lire "P ou Q") est une propriété sur E définie par :

- equation est vraie si au moins l'une des propriétés P, Q  est vraie

- equation est fausse sinon

Nous pouvons créer la table de vérité du "connecteur OU" ou "connecteur de disjonction" equation :

P

Q

equation

V

V

V

V

F

V

F

V

V

F

F

F

Tableau: 1.2  - Table de vérité de OU

Il est facile de se convaincre que, si les parties P, Q de E sont respectivement associées aux propriétés P, Q que equation (cf. chapitre Théorie Des Ensembles) est associé à equation.

equation   (1.4)

Le connecteur equation est associatif. Pour s'en convaincre, il suffit de faire une table vérité où nous vérifions que :

equation   (1.5)

Il existe également le "connecteur ET" ou "connecteur de conjonction" equation pour quel que soient PQ  deux propriétés définies sur E, equation  est une propriété sur E définie par :

- equation est vraie si toutes les deux propriétés P, Q sont vraies

- equation est fausse sinon

Nous pouvons créer la table de vérité du connecteur equation:

P

Q

equation

V

V

V

V

F

F

F

V

F

F

F

F

Tableau: 1.3  - Table de vérité de ET

Il est également facile de se convaincre que, si les parties P, Q de E sont respectivement associées aux propriétés P, Q que equation (cf. chapitre Théorie Des Ensembles) est associé à equation :

equation   (1.6)

Le connecteur equation est associatif. Pour s'en convaincre, il suffit aussi de faire une table vérité où nous vérifions que:

equation   (1.7)

Les connecteurs equation sont distributifs l'un sur l'autre. A l'aide d'une simple table de vérité, nous prouvons que:

equation   (1.8)

ainsi que:

equation   (1.9)

Une négation de equation est equation une négation de equation est  equation tel que pour résumer:

equation   (1.10)

A nouveau, ces propriétés peuvent se démontrer par une simple table de vérité.

Remarque: Pour voir les détails de tous les opératures logiques, le lecteur devra se rendre dans le chapitre d'Algèbre De Boole (cf. section d'Informatique Théorique) où l'identité, la double négation, l'idempotence, l'associativité, la distributivité, les relations de De Morgan sont présentées plus formellement.

Revenons maintenant sur le "connecteur d'implication logique" appelé aussi parfois le "conditionnel" noté "equation"

Remarque: Dans certains ouvrages sur le calcul propositionnel, ce connecteur est noté "equation" et dans le cadre de la théorie de la démonstration nous lui préférons souvent le symbole "equation".

Soient P, Q deux propriétés sur E. equation est une propriété sur E définie par:

- equation est fausse si P est vraie et Q fausse

- equation est vraie sinon

En d'autres termes, P implique logiquement Q signifie que Q est vrai pour toute évaluation pour laquelle P est vraie. L'implication représente donc le "si... alors.."

Si nous écrivons la table de vérité de l'implication (attention à l'avant dernière ligne !!!) :

P

Q

equation

V

V

V

V

F

F

F

V

V

F

F

V

Tableau: 1.4  - Table de vérité de l'implication

Si equation, nous pouvons dire que pour que Q soit vraie, il suffit que P soit vraie (effectivement l'implication sera vraie si P est vraie ou fausse selon la table de vérité). Donc P est une condition suffisante de Q (mais non nécessaire!). D'un autre côté, equation est équivalent à equation. Donc, si Q est fausse, il est impossible que P soit vraie (pour que l'implication reste vraie bien sûr!). Donc finalement Q est une condition nécessaire de P.

exemple Exemples:

E1. Soit la proposition : "Si tu obtiens ton diplôme, je t'achète un ordinateur"

Parmi tous les cas, un seul correspond à une promesse non tenue: celui où l'enfant à son diplôme, et n'a toujours pas d'ordinateur (deuxième ligne dans le tableau).

Et le cas où il n'a pas le diplôme, mais reçoit quand même un ordinateur? Il est possible qu'il ait été longtemps malade et a raté un semestre, et le père a le droit d'être bon.

Que signifie cette promesse, que nous écrirons aussi : "Tu as ton diplôme equation je t'achète un ordinateur" ? Exactement ceci:

- Si tu as ton diplôme, c'est sûr, je t'achète un ordinateur (je ne peux pas ne pas l'acheter)

- Si tu n'as pas ton diplôme, je n'ai rien dit

E2. De toute proposition fausse nous pouvons déduire toute proposition (deux dernières lignes)

C'est un exemple plutôt anecdotique : dans un cours de Russell portant sur le fait que d'une proposition fausse, toute proposition peut être déduite, un étudiant lui posa la question suivante :

- "Prétendez-vous que de 2 + 2 = 5, il s'ensuit que vous êtes le pape ? "

- "Oui", fit Russell

- "Et pourriez-vous le prouver !", demanda l'étudiant sceptique

- "Certainement", réplique Russell, qui proposa sur le champ la démonstration suivante.

(1) Supposons que 2 + 2 = 5

(2) Soustrayons 2 de chaque membre de l'égalité, nous obtenons 2 = 3

(3) Par symétrie, 3 = 2

(4) Soustrayant 1 de chaque côté, il vient 2 =1

Maintenant le pape et moi sommes deux. Puisque 2 = 1, le pape et moi sommes un. Par suite, je suis le pape.

Sur ce ...

Le connecteur d'implication est essentiel en mathématiques, philosophie, etc. C'est un des fondements de toute démonstration, preuve ou déduction.

Le connecteur d'implication a comme propriétés (vérifiables à l'aide de la table de vérité ci-dessous) :

equation   (1.11)

conséquence de la dernière propriété (à nouveau vérifiable par une table de vérité) :

equation   (1.12)

Le "connecteur d'équivalence logique" ou "bi-conditionnel" noté "equation" ou "equation" signifiant par définition que :

equation   (1.13)

en d'autres termes, la première expression a la même valeur pour toute évaluation de la deuxième.

Ce que nous pouvons vérifier à l'aide d'une table de vérité:

P

Q

equation

equation

equation

V

V

V

V

V

V

F

F

V

F

F

V

V

F

F

F

F

V

V

V

Tableau: 1.5  - Table de vérité de l'équivalence logique

equation signifie bien (lorsqu'il est vrai!) que "P et  Q ont toujours la même valeur de vérité" ou encore  "P et  Q sont équivalents". C'est vrai si P et Q ont même valeur, faux dans tout cas contraire.

Bien évidemment (c'est une tautologie) :

equation   (1.14)

La relation equation équivaut donc à ce que P soit une condition nécessaire et suffisante de Q et à ce que Q soit une condition nécessaire et suffisante de P.

La conclusion, est que les conditions de type "nécessaire, suffisant, nécessaire et suffisant" peuvent être reformulés avec les termes "seulement si", "si", "si et seulement si".

Ainsi :

1. equation traduit le fait que Q est une condition nécessaire pour P ou dit autrement, P est vraie seulement si Q est vraie (dans le table de vérité, lorsque equation prend la valeur 1 on constate bien que P vaut 1 seulement si Q vaut 1 aussi). On dit aussi, si P est vraie alors Q est vraie.

2. equation ou ce qui reviens au même equation traduit le fait que Q est une condition suffisante pour P ou dit autrement, P est vraie si Q est vraie (dans le table de vérité, lorsque equation prend la valeur 1 on constate bien que P vaut 1 si Q vaut 1 aussi).

3. equation traduit le fait que Q est une condition nécessaire et suffisante pour P ou dit autrement, P est vraie si et seulement si Q est vraie (dans le table de vérité, lorsque equation prend la valeur 1 on constate bien que P vaut 1 si Q vaut 1 et seulement si Q vaut 1).

Remarque: L'expression "si et seulement si" correspond donc à une équivalence logique et ne peut être utilisée pour décrire un implication!!

La première étape du calcul propositionnel est donc la formalisation des énoncés du langage naturel. Pour réaliser ce travail, le calcul propositionnel fournit finalement trois types d'outils :

1. Les "variables propositionnelles" (P, Q, R,...) symbolisent des propositions simples quelconques. Si la même variable apparaît plusieurs fois, elle symbolise chaque fois la même proposition.

2. Les cinq opérateurs logiques : equation

3. Les signes de ponctuation se réduisent aux seules parenthèses ouvrante et fermante qui organisent la lecture de manière à éviter toute ambiguïté.

Voici un tableau récapitulatif :

Description

Symbole

Utilisation

La "négation" est un opérateur qui ne porte que sur une proposition, il est unaire ou monadique. "Il ne pleut pas" s'écrit equation. Cet énoncé est vrai si et seulement si P est faux (dans ce cas s'il est faux qu'il pleut). L'usage classique de la négation est caractérisé par la loi de double négation : equation est équivalent à P.

equation

equation

La "conjonction" ou "produit logique" est un opérateur binaire, elle met en relation deux propositions. "Tout homme est mortel ET Ma voiture perd de l'huile" s'écrit equation. Cette dernière expression est vraie si et seulement si P est vrai et Q est vrai.

equation

equation

La "disjonction" ou "somme logique" est, elle aussi, un opérateur binaire. equation est vrai si et seulement si P est vrai ou Q est vrai. Nous pouvons comprendre ce OU de deux façons : soit de manière inclusive, soit de manière exclusive. Dans le premier cas equation est vrai si P est vrai, si Q est vrai ou si P et Q sont tous deux vrais. Dans le second cas, equation est vrai si P est vrai ou si Q est vrai mais pas si les deux le sont. La disjonction du calcul propositionnel est le OU inclusif et on donne au OU exclusif le nom "d'alternative".

equation

equation

"L'implication" est également un opérateur binaire. Elle correspond, en gros, au schéma linguistique "Si...alors...". "Si j'ai le temps, j'irai au cinéma" s'écrit equation. equation est faux si P est vrai et Q est faux. Si le conséquent (ici Q) est vrai, l'implication equation est vraie. Lorsque l'antécédent (ici P) est faux, l'implication est toujours vraie. Cette dernière remarque peut être comprise si l'on se réfère à des énoncés de type : "Si on pouvait mettre Paris en bouteille, on utiliserait la tour Eiffel comme bouchon." En résumé, une implication est fausse si et seulement si son antécédent est vrai et son conséquent est faux.

equation

equation

La "bi-implication" est, elle aussi, binaire : elle symbolise les expressions "... si et seulement si..." et "... est équivalent à..." L'équivalence entre deux propositions est vraie si celles-ci ont la même valeur de vérité. La bi-implication exprime donc aussi une forme d'identité et c'est pourquoi elle est souvent utilisée dans les définitions.

equation

equation

Tableau: 1.6  - Récapitulatif des opérateurs

Il est possible d'établir des équivalences entre ces opérateurs. Nous avons déjà vu comment le bi-conditionnel pouvait se définir comme un produit de conditionnels réciproques, voyons maintenant d'autres équivalences :

equation   (1.15)

Remarque: Les opérateurs classiques equation peuvent donc être définis à l'aide de equation grâce aux lois d'équivalence entre opérateurs.

Sont à noter également les deux relations de De Morgan (cf. chapitre d'Algèbre de Boole) :

equation   (1.16)

Elles permettent de transformer la disjonction en conjonction et vice-versa :

equation   (1.17)


3.3. PROCÉDURES DE DÉCISION

Nous avons introduit précédemment les éléments de base nous permettant d'opérer sur des expressions à partir de propriétés (variables propositionnelles) sans toutefois dire grand chose quant à la manipulation de ces expressions. Alors, il convient maintenant de savoir qu'en calcul propositionel qu'il existe deux manières d'établir qu'une proposition est un loi de la logique propositionnelle. Nous pouvons soit :

1. Employer des procédures non axiomatisées

2. Recourir à des procédures axiomatiques et démonstratives

Remarque: Dans de nombreux ouvrages ces procédures sont présentées avant même la structure du langage propositionnel. Nous avons choisi de faire le contraire pensent que l'approche serait plus aisée.

3.3.1. PROCÉDURES DE DÉCISIONS NON AXIOMATISÉES

Plusieurs de ces méthodes existent mais nous nous limiterons ici à la plus simple et à la plus parlante d'entre elles, celle du calcul matriciel, souvent appelée aussi "méthodes des tables de vérité".

La procédure de construction est comme nous l'avons vu précédemment assez simple. Effectivement, la valeur de vérité d'une expression complexe est fonction de la valeur vérité des énoncés plus simples qui la composent, et finalement fonction de la valeur de vérité des variables propositionelles qui la composent. En envisageant toutes les combinaisons possibles des valeurs de vérité des variables de propositionnelles, nous pouvons déterminer les valeurs de vérité de l'expression complexe.

Les tables de vérité, comme nous l'avons vu, permettent donc de décider, à propos de toute proposition, si celle-ci est une tautologie (toujours vraie), une contradiction (toujours fausse) ou une expression contingente (parfois vraie, parfois fausse).

Nous pouvons ainsi distinguer quatre façons de combiner les variables propositionnelles, les paranthèses et les connecteurs :

  Nom Description Exemple
1

Enoncé mal formé

Non-sens. Ni vrai, ni faux

equation

2

Tautologie

Enoncé toujours vrai

equation

3

Contradiction

Enoncé toujours faux

equation

4

Enoncé contingent

Enoncé parfois vrai, parfois faux

equation

Tableau: 1.7  - Combinaison de variables propositionnelles

La méthode des tables de vérité permet de déterminer le type d'expression bien formée face auquel nous nous trouvons. Elle n'exige en principe aucune invention, c'est une procédure mécanique. Les procédures axiomatisées, en revanche, ne sont pas entièrement mécaniques. Inventer une démonstration dans le cadre d'un système axiomatisé demande parfois de l'habilité, de l'habitude ou de la chance. Pour ce qui est des tables de vérité, voici la marche à suivre :

Lorsqu'on se trouve face à un expression bien formée, ou fonction de vérité, nous commencons par déterminer à combien de variables propositionnelles distinctes nous avons affaire. Ensuite, nous examinons les différents arguments qui constituent cette expression. Nous construisons alors un tableau comprenant equationrangées (n étant le nombre de variables) et un nombre de colonnes égal au nombre d'arguments plus des colonnes pour l'expression elle-même et ses autres composantes. Nous attribuons alors aux variables les différentes combinaisons de vérité et de fausseté qui peuvent leur être conférées (la vérité est exprimée dans la table par un 1 et la fausseté par un 0). Chacune des rangées correspond à un monde possible et la totalité des rangées constitue l'ensemble des mondes possibles. Il existe, par exemple, un monde possible dans lequel P est une proposition vraie tandis que Q est fausse.

3.3.2. PROCÉDURES DE DÉCISIONS AXIOMATISÉES

L'axiomatisation d'une théorie implique, outre la formalisation de celle-ci, que nous partions d'un nombre fini d'axiomes et que, grâce à la transformation réglée de ces derniers, que nous puissions obtenir tous les théorèmes de cette théorie. Nous pardons donc de quelques axiomes dont la vérité est posée (et non démontrée). Nous déterminons des règles de déduction permettant de manipuler les axiomes ou toute expression obtenue à partir de ceux-ci. L'enchaînement de ces déductions est une démonstration qui conduit à un théorème, à une loi.

Nous allons sommairement présenter deux systèmes axiomatiques, chacun étant constitué d'axiomes utilisant deux règles dites "règles d'inférence" (règles intuitives) particulières :

1. Le "modus ponens" : si nous avons prouvé A et equation, alors nous pouvons déduire B. A est appelé la "prémisse mineure" et equation la prémisse majeure de la règle du modus ponens.

exemple Exemple:

De equation et equation nous pouvons déduire equation

2. La "substitution" : nous pouvons dans un schéma d'axiome remplacer une lettre par une formule quelconque, pourvue que toutes les lettres identiques soient remplacées par des formules identiques.

Donnons à titre d'exemple, deux systèmes axiomatiques : le système axiomatique de Whithead et Rusell, le système axiomatique de Lukasiewicz.

1. Le système axiomatique de Whitehead et Russel adopte comme symboles primitifs equation et définit equation à partir de ces derniers de la manière suivante (relations facilement vérifiables à l'aide de tables de vérité) :

equation   (1.18)

nous avions déjà présenté plus haut quelque uns de ces éléments.

Ce système comprend cinq axiomes, assez évidents en soi plus les deux règles d'inférence. Les axiomes sont donnés ici en utilisant des symboles non primitifs, comme le faisaient Whitehead et Russel :

A1. equation

A2. equation

A3. equation

A4. equation

A5. equation

Remarque: Ces cinq axiomes ne sont pas indépendants les uns des autres. Le quatrième peut être obtenu à partir des quatre autres.

exemple Exemple:

Pour prouver equation, nous pouvons procéder ainsi :

equation
  (1.19)

 

2. Le système axiomatique Lukasiewicz comprend les trois axiomes suivants, plus les deux règles d'inférences (modus ponens et substitution):

A1. equation

A2. equation

A3. equation

Voici des preuves des deux premiers axiomes, dans le système de Whitehead et Russel. Ce sont les formules (6) et (16) de la dérivation suivante :

equation
  (1.20)

Ces axiomatisations permettent de retrouver comme théorème toutes les tautologies ou lois de la logique propositionnelle. De par tout ce qui a été dit jusqu'à maintenant, nous pouvons tenter de définir ce qu'est une preuve.

Définition: Une suite finie de formules equation est appelée "preuve" à partir des hypothèses equation si pour chaque i :

- equation est l'une des hypothèses equation
- ou equation est une variante d'un axiome
- ou equation est inférée (par application de la règle du modus ponens) à partir de la prémisse majeure equation et de la prémisse mineure equationequation
- ou equation est inférée (par application de la règle de substitution) à partir d'une prémisse antérieure equation, la variable remplacée n'apparaissant pas dans equation

Une telle suite de formules, equation étant la formule finale de la suite, est appelée plus explicitement "preuve de equation" à partir des hypothèses equation, ce que nous notons par :

equation   (1.21)

Remarque: Il faut noter que lorsque nous essayons de prouver un résultat à partir d'un certain nombre d'hypothèses, nous essayons pas de prouver les hypothèses elles-mêmes.

3.4. QUANTIFICATEURS

Nous devons compléter l'utilisation des connecteurs du calcul propositionnel par ce que nous appelons des "quantificateurs" si nous souhaitons pouvoir résoudre certains problèmes. Effectivement, le calcul propositionnel ne nous permet pas d'affirmer des choses générales sur les éléments d'un ensemble par exemple. Dans ce sens, la logique propositionnelle ne reflète qu'une partie du raisonnement. Le "calcul des prédicats" au contraire permet de manipuler formellement des affirmations telles que "il existe un x tel que [x a une voiture américaine]" ou "pour tous les x [si x est une teckel, alors x est petit]"; en somme, nous étendons les formules composées afin de pouvoir affirmer des quantifications existentielles ("il existe...") et des quantifications universelles ("pour tout...."). Les exemples que nous venons de donner font intervenir des propositions un peu particulières comme "x a une voiture américaine". Il s'agit ici de propositions comportant une variable. Ces propositions sont en fait l'application d'une fonction à x. Cette fonction, c'est celle qui associe "x a une voiture américaine" à x. Nous dénoterons cette fonction par "... a une voiture américaine" et nous dirons que c'est une fonction propositionnelle, car c'est une fonction dont la valeur est une proposition. Ou encore un "prédicat".

Les quantificateurs existentiels et universels vont donc de pair avec l'emploi de fonctions propositionnelles. Le calcul des prédicats est cependant limité dans les formules existentielles et universelles. Ainsi, nous nous interdisons des formules comme "il existe une affirmation de x telle que...". En fait, nous ne nous autorisons à quantifier que des "individus". C'est pour cela que la logique des prédicats est dite une "logique de premier ordre".

Avant de passer à l'étude du calcul des prédicats nous devons définir :

D1. Le "quantificateur universel" : equation (pour tout)

D2. Le "quantificateur existentiel" : equation (il existe)

Remarque: Nous utilisons parfois le symbole equation pour dire brièvement : "il existe un et un seul":

equation   (1.22)

Nous allons voir que la théorie de la démonstration et des ensembles est l'exacte transcription des principes et résultats de la Logique (celle avec un "L" majuscule).


page suivante : 4. Calcul des prédicats