Calcul des propositions

Le calcul propositionnel (sporadiquement appelé logique d’ordre zéro) est une théorie formelle (au sens où il s’agit de manipuler des formules) qui modélise des raisonnements mathématiques simples du type “si alors . On s’intéresse notamment à la façon de créer de nouvelles propositions à partir des propositions élémentaires, dits atomiques, et à la manière de déduire si la proposition construite est vraie ou fausse à partir de la vérité ou la fausseté des propositions élémentaires.

Le Calcul des prédicats constitue une généralisation du calcul des propositions à des formules plus complexes du type “pour tout n, si n a la propriété X alors n a la propriété Y”.

Concepts de base

Une proposition est une phrase dont on peut affirmer qu’elle est vraie ou fausse. Ainsi “il pleut”, “ est pair”, “” sont des propositions, mais “le nombre de doigts de la main”, “4”, “” ne le sont pas.

Le calcul des propositions modélise la façon dont le mathématicien raisonne sur la vérité et la fausseté en faisant abstraction des propositions spécifiques qui forment le raisonnement concret. Ce qui compte est exclusivement la forme du raisonnement, ainsi l’affirmation

S’il pleut ou il neige, alors il y a des nuages

et l’affirmation

Si ou , alors

sont représentées par la même formule

Si ou , alors

où les variables représentent à la fois les propositions “il pleut”, “il neige”, “”, etc.

De plus, les connecteurs logiques si, alors, ou, etc. sont exprimés par des symboles plutôt que par des mots. Par convention, on utilise les symboles suivants:

Appellation Formule Interprétation
implication si alors ,
équivalence si et seulement si ,
conjonction et ,
disjonction ou ,
négation il n’est pas vrai que .

De tous les opérateurs, seul le “ou” mérite quelques mots d’explication en plus. Par ou l’on entend le ou inclusif du français c’est à dire qu’au moins l’une des propositions ou doit être vraie, mais possiblement les deux sont vraies. On appelle ou exclusif ce qui est souvent exprimé en français par “soit… soit…” et qui signifie ou , mais pas les deux en même temps. Ce type d’opérateur est parfois ajouté à la logique propositionnelle avec la notation . Voici des exemples

Type de ou Notation Exemple
ou inclusif une résidence accueille des personnes malades ou agées
ou exclusif demain, j’irai travailler en train ou en voiture

Définitions

En calcul des propositions, comme dans tout autre système formel, on fait une distinction minutieuse entre syntaxe, sémantique et métalogique. Ainsi, la syntaxe décrit la façon correcte de former les formules, la sémantique donne l’interprétation des formules, et la métalogique est le processus de raisonner sur le système formel avec des outils externes (la pensée mathématique, en général, ou plus formellement une autre logique formelle plus puissante que le calcul des propositions).

Syntaxe

La syntaxe du calcul propositionnel est composée des éléments suivants:

Une proposition (ou formule, ou formule bien formée) est

Ainsi , , sont des propositions, mais , ne le sont pas.

Remarque: les parenthèses ne font pas partie du calcul des propositions, elles sont simplement là pour décrire la structure syntaxique des formules, i.e. pour indiquer dans quel ordre les opérateurs ont été appliqués pour obtenir la formule. Voir du bon usage des parenthèses.

Pour réduire le nombre de parenthèses, on assigne une précédence par défaut aux opérateurs. Ainsi a la précédence la plus haute, ensuite viennent et avec la même précédence, et enfin . Par conséquent la formule

doit être lue comme

Puisque on peut démontrer que et sont associatifs, un autre usage courant consiste à ne pas écrire les parenthèses d’une chaîne de ces opérateurs, à moins que l’on ne s’intéresse à l’arbre de formation d’une formule. Ainsi

peut être aussi bien interprété comme

que comme

ce qui ne change rien dans un contexte où l’on s’intéresse à la vérité de la formule puisque ces deux formules sont sémantiquement équivalentes. Cependant, nous allons essayer d’utiliser cette convention le moins possible.

Attention: Par contre, il est toujours incorrect d’écrire

puisque les deux parenthésages possibles de la formule n’ont pas la même sémantique (remarquez que certains auteurs préfèrent assigner une priorité plus haute à , en levant donc cette ambiguïté). De façon similaire, la formule

est ambiguë puisque les deux parenthésages ne sont pas équivalents. Beaucoup de textes adoptent la convention de l’associativité à droite, ainsi la seule lecture possible de la formule ci-dessus serait

mais remarquez que ceci est purement une convention, que nous allons éviter d’utiliser dans ce texte.

Sémantique

La sémantique consiste à attacher des interprétations aux formules du calcul propositionnel. Le système qui est obtenu en considérant toutes les interprétations possibles est aussi appelée logique Booléenne ou algèbre de Boole.

Formellement, un modèle (parfois on dit une interprétation) d’une proposition est l’affectation d’une valeur ou (appelée valeur de vérité) à chacune de ses propositions atomiques. En général, affecter à est interprété comme l’affirmation “il est vrai que ”, affecter à comme “il n’est pas vrai que ”.

On parle aussi de modèle du calcul propositionnel lorsque on assigne une valeur de vérité à chacune de ses propositions atomiques (souvenez-vous qu’il y en a une infinité).

Connecteurs logiques et tables de vérité

Dans les langages naturelles on peut composer des propositions complexes à l’aide des propositions plus simples. Nous venons de voir que dans le calcul propositionnel on peut de la même façon composer des propositions complexes à partir des propositions atomiques en utilisant les connecteurs logiques. La valeur de vérité des propositions composées ne dépend que de celles des propositions atomiques. On peut décrire des telles constructions à l’aide des tables de vérité, qui sont des tables qui donnent, en fonction des valeurs de vérité des propositions atomiques, la valeur de vérité de la proposition composée.

Négation

Considérons la proposition Il fait beau aujourd’hui. La langue française possède plusieurs formes grammaticales pour exprimer la négation de cette proposition, la plus courante étant sans doute l’expression il ne fait pas beau aujourd’hui. En l’occurence, ne … pas signifie que s’il est vrai que Il fait beau aujourd’hui, alors il est faux qu’il ne fait pas beau aujourd’hui, et que s’il est faux que ”Il fait beau aujourd’hui”, alors il est vrai qu’il ne fait pas beau aujourd’hui. On peut illustrer la signification de la négation à l’aide d’une table de vérité :

0 1
1 0

Le connecteur est appelé connecteur monadique car il s’applique à une seule proposition. Tous les autres connecteurs sont des connecteurs dyadiques s’appliquant à deux propositions.

Conjonction

Le sens donné au connecteur et celle du et. Par conséquent, la proposition est vraie si et sont tous les deux vrais, et sera fausse dans tous les autres cas. Ceci peut se résumer par la table de vérité suivante :

0 0 0
0 1 0
1 0 0
1 1 1
Disjonction

La disjonction est un connecteur dyadique défini par la table de vérité :

0 0 0
0 1 1
1 0 1
1 1 1

La proposition est vraie si au moins une des propositions et est vraie. (Rappel : Le symbole définit le ou inclusif).

Implication

L’implication est sans doute la plus compliquée à comprendre. On lit comme si , alors , implique ou encore , à condition que .

Afin de mettre les choses en clair commençons par un exemple. Soit la proposition j’obtiens ma licence et la proposition je vais organiser une fête. Dans ce cas se lit si j’obtiens ma licence alors je vais organiser une fête. Clairement, si j’obtiens ma licence, donc si est vraie et si j’organise une fête, donc si est vraie, la promesse est tenue donc est vraie. Par contre, si j’obtiens ma licence mais je n’organise pas de fête ( est vraie tandis que est fausse) alors la promesse n’est pas tenue, donc est fausse. Regardons cependant ce qu’il se passe si malheureusement je n’obtiens pas ma licence. Dans ce cas, si j’organise une fête malgré ça ou si je ne fait rien, ne fait pas démentir ma promesse car je ne me suis engagé à rien dans ce cas-ci. Personne ne pourrait dire que je suis un menteur. Donc, si la proposition est fausse, l’implication est vraie, peut importe la valuer de . Nous pouvons alors conclure que la table de vérité de l’implication est la suivante:

0 0 1
0 1 1
1 0 0
1 1 1

Remarque. Comme on vient de le voir si est fausse, alors l’implication est vraie, quelle que soit la valeur de vérité de . Ainsi, si , alors est une implication vraie, de même que si , alors . Cela conduit à la constatation suivante : du faux, on peut déduire n’importe quoi !

Théorie des modèles

Si un modèle associe la valeur à une formule donnée, on dit que la formule est vraie dans le modèle . On dit qu’une formule est

Par example est satisfaisable et falsifiable car et la rendent vraie, mais et la rendent fausse. est non seulement satisfaisable, mais aussi une tautologie. est une antilogie.

Donc, on appelle tautologie une formule dont l’interprétation est 1, quelle que soit la valeur des variables propositionnelles. La notation

signifie que est une tautologie. On a par exemple , puisque quelque soit la valeur associée à , la valeur de sera toujours 1.

Si et sont deux formules, on dit que est une conséquence logique de (ou conséquence sémantique ou, plus informellement, que implique ) si tout modèle qui satisfait satisfait aussi . Si est une conséquence logique de on écrit

intuitivement, ceci signifie que est vraie sous l’hypothèse . Plus généralement, si est un ensemble de formules on dit que est une conséquence logique de , et on note , si tout modèle qui satisfait toutes les formules de satisfait aussi .

Lorsque on a et , on dit que et sont (sémantiquement) équivalentes, ce qui, selon les textes, est noté

Pour donner un exemple, il suffit de regarder les tables de vérité pour se rendre compte que , mais que la réciproque n’est pas vraie ( n’est pas une conséquence logique de ).

Attention: aucun des symboles ne fait partie de la logique. Ce sont tous des symboles métalogiques qui permettent d’exprimer des propriétés qu’on a démontrées en dehors de la syntaxe du calcul des propositions (par exemple en lisant les tables de vérité). On fera surtout attention à ne pas confondre et , qui sont des propositions du calcul des propositions, avec et .

Équivalences remarquables

Commutativité

Les phrases il est beau et intelligent et il est intelligent et beau sont sémantiquement équivalentes. De la même façon les phrases il est beau ou intelligent et il est intelligent ou beau sont sémantiquement équivalentes. De manière générale, pour toutes propositions et ,

Associativité

Supposons que nous avons une formule de la forme . Nous pouvons interpréter cette formule de deux façons différentes. Ou bien on calcule d’abord et ensuite , c’est qui est équivalent à , ou bien on calcule d’abord et ensuite , ce qui revient à faire .

Le même constat tient si on remplace par . En effet, les connecteurs et sont associatives et donc l’ordre dans lequel on effectue les opérations n’est pas important. On peut alors conclure que

Distributivité

Imaginez que votre professeur vous dit: Pour valider le cours il faut d’abord réussir l’examen écrit et ensuite réussir l’examen sur machine ou avoir une note supérieure à 12 à tous les devoirs maison. Vous avez alors deux manières de valider le cours: Réussir l’examen écrit et l’examen sur machine, ou bien réussir l’examen écrit et avoir une note supérieure à 12 à tous les devoirs maison.

Ceci est dû aux tautologies suivantes :

Lois de De Morgan

Pour que la phrase “La maison est grande et belle” soit fausse, il suffit que la maison soit petite ou qu’elle soit moche, mais il n’est pas nécessaire que ces deux caractéristiques soient réunis en même temps. La négation de cette phrase est alors “La maison est petite ou moche” et non pas “La maison est petite et moche”.

Les tautologies suivantes, connues comme les lois de De Morgan, formalisent cela:

Implication

Transposition

La phrase si l’eau bout, alors sa température est à 100 degrés est équivalente à si la temperature de l’eau n’est pas à 100 degrés, alors l’eau ne bout pas. Ceci provient de la tautologie suivante :

Exportation

On résume maintenant la liste de formules qui peuvent être prouvées sémantiquement équivalentes en comparant leur tables de vérité (remarquez qu’à la place de et on peut substituer n’importe quelles formules et non nécessairement atomiques).

Propriété Formules équivalentes  
Double négation
Commutativité
 
Associativité
 
Distributivité
 
Lois de de Morgan
 
Implication
Transposition
Exportation

Réciproque et contraposée d’une implication

Réciproque

Considérons la proposition est un nombre entier et la position est un nombre réel. L’implication est vraie, puisque tout nombre entier est aussi un nombre réel. On peut maintenant se demander si la réciproque est vraie, c’est-à-dire si implique , qui donne si est un nombre réel, alors est un nombre entier. Cette implication est évidemment fausse. En effet, est un nombre réel, mais pas un nombre entier.

De façon générale, la réciproque d’une implication est l’implication

Contraposée

La phrase est la contraposée de la phrase .

Si par exemple est la phrase est un rectangle et la phrase a quatre angles droits. L’implication se lit alors si c’est un rectangle alors il quatre angles trois. L’implication contraposée est donc la phrase s’il n’a pas quatre angles droits, alors ce n’est pas un rectangle. Puisque et sont sémantiquement équivalentes, pour démontrer une implication, nous pouvons à la place démontrer sa contraposée.

Bibliographie

Pour les définitions de base et les algèbres de Boole, on pourra consulter un quelconque des ouvrages conseillés dans la Bibliographie.

Pour une exposition claire et complète sur la distinction entre syntaxe et sémantique et sur la théorie de la preuve, je conseille les chapitres 4 et 5 du livre Mathématiques pour l’Informatique de Arnold et Guessarian, en particulier la section 5.2: à quelques choix de nomenclature et de notation près (par exemple le symbole est remplacé par ), les arguments y sont traités de la même façon que dans cette page. Malheureusement ce livre contient assez peu d’exercices sur cette partie.

Introduction à la logique de David, Nour et Raffali est un autre très bon texte. Le chapitre 1 couvre toute la théorie de la preuve faite dans ce cours, plus la théorie de la preuve du Calcul des Prédicats. Il propose aussi beaucoup d’exercices pour vous entraîner avec les séquents. Le chapitre 2 couvre la sémantique et les théorèmes de complétude. L’étudiant intéressé pourra les lire rapidement.

Allez voir aussi les pages des Exercices et des Exercices Corrigés.

Fork me on GitHub