title |
---|
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 $$p$$ alors $$q$$”. 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”.
Une proposition est une phrase dont on peut affirmer qu’elle est vraie ou fausse. Ainsi “il pleut”, “$$n$$ est pair”, “$$n>0$$” sont des propositions, mais “le nombre de doigts de la main”, “4”, “$$f(n)$$” 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
$$n > 0$$ ou$$n < 0$$ , alors$$n\ne0$$
sont représentées par la même formule
Si
$$p$$ ou$$q$$ , alors$$r$$
où les variables
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 |
|
équivalence |
|
|
conjonction |
|
|
disjonction |
|
|
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
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 | |
----------- | ----------- | ------------------------------------------------------- |
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).
La syntaxe du calcul propositionnel est composée des éléments suivants:
- Une liste infinie (mais dénombrable) de
propositions atomiques (ou formules atomiques), en général
représentées par les lettres de l'alphabet
$$p, q, \ldots$$ , - Des opérateurs logiques, en général
$$\wedge, \vee, \to, \neg$$ .
Une proposition (ou formule, ou formule bien formée) est
- soit une proposition atomique,
- soit le résultat de la combinaison d'un opérateur logique avec deux
(ou une dans le cas de
$$\neg$$ ) propositions (non nécessairement atomiques).
Ainsi
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
doit être lue comme
Puisque on peut démontrer que
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 à
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.
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
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é).
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.
Considérons
0 | 1 |
1 | 0 |
Le connecteur
Le sens donné au connecteur
0 | 0 | 0 |
0 | 1 | 0 |
1 | 0 | 0 |
1 | 1 | 1 |
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
L'implication
Afin de mettre les choses en clair commençons par un exemple. Soit
0 | 0 | 1 |
0 | 1 | 1 |
1 | 0 | 0 |
1 | 1 | 1 |
Remarque. Comme on vient de le voir si
Si un modèle
- satisfaisable s’il existe un modèle qui la rend vraie;
- une tautologie si elle est vraie dans tout modèle (on dit aussi que la formule est valide);
- falsifiable s’il existe un modèle qui la rend fausse;
- une antilogie s’il n’existe aucun modèle qui la rend vraie.
Par example
Donc, on appelle tautologie une formule
signifie que
Si
intuitivement, ceci signifie que
Lorsque on a
Pour donner un exemple, il suffit de regarder les tables de vérité pour
se rendre compte que
Attention: aucun des symboles
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
Supposons que nous avons une formule de la forme
Le même constat tient si on remplace
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 :
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:
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 :
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
|Propriété | Formules équivalentes |-|:-:|:-: |Double négation |$$p$$ |$$\neg\neg p$$ |Commutativité |$$p\wedge q$$ |$$q\wedge p$$ | |$$p\vee q$$ |$$q\vee p$$ |Associativité |$$(p\wedge q)\wedge r$$ |$$p\wedge(q\wedge r)$$ | |$$(p\vee q)\vee r$$ |$$p\vee(q\vee r)$$ |Distributivité |$$p\wedge(q\vee r)$$ |$$(p\wedge q)\vee(q\wedge r)$$ | |$$p\vee(q\wedge r)$$ |$$(p\vee q)\wedge(q\vee r)$$ |Lois de de Morgan |$$\neg(p\wedge q)$$ |$$\neg p\vee\neg q$$ | |$$\neg(p\vee q)$$ |$$\neg p\wedge\neg q$$ |Implication |$$p\to q$$ |$$\neg p \vee q$$ |Transposition |$$p\to q$$ |$$\neg q \to \neg p$$ |Exportation |$$(p \wedge q) \to r$$ |$$p \to (q \to r)$$
Considérons la proposition
De façon générale, la réciproque d’une implication
La phrase
Si par exemple
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
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.