Comment travailler
Le cours ne remplace pas le livre : il le prépare et l’accompagne. Il est écrit pour quelqu’un qui n’a jamais fait de logique formelle et qui lit le livre en anglais.
- Lire la leçonElle explique en français ce que le livre fait, dans quel ordre et pourquoi, avec des exemples et le contexte historique.
- Lire les pages du livreLes démonstrations complètes y sont. La leçon indique les pages, et celles qu’on peut sauter en première lecture.
- Faire les exercicesCeux du cours (C1, C2…) ont un corrigé dépliable. Ceux du livre n’en ont pas : ils se corrigent dans la conversation.
- Écrire dans la conversationEnvoyer les réponses en les nommant (« L1, livre 3 : … »), poser les questions, puis demander la leçon suivante. Les corrections règlent le rythme de la suite.
Trente leçons, sept parties
Le plan suit l’ordre du livre. Le tronc commun va jusqu’à la leçon 15 (chapitres 1 à 3, jusqu’à la compacité). Ensuite, on peut suivre le livre ou son intérêt : théorie des modèles (16–18), second ordre (19), intuitionnisme (20–23) puis normalisation (24–25), Gödel (26–30).
Partie I · chapitre 1Logique propositionnelle
- 01Le langage des propositionsen lignePréface, introduction, § 1.1 · pp. 1–15
- 02Vérité et valuationsà venir§ 1.2 · pp. 15–21
- 03Équivalences, formes normales, connecteursà venir§ 1.3 · pp. 21–30
- 04La déduction naturelleà venir§ 1.4 · pp. 30–40
- 05Le théorème de complétudeà venir§ 1.5 · pp. 40–49
- 06Les connecteurs manquantsà venir§ 1.6 · pp. 49–56
Partie II · chapitre 2Logique des prédicats
- 07Quantificateurs et structuresà venir§ 2.1–2.2 · pp. 57–60
- 08Le langage d’un type de similaritéà venir§ 2.3 · pp. 60–68
- 09La sémantique de Tarskià venir§ 2.4 · pp. 68–73
- 10Propriétés simples de la logique des prédicatsà venir§ 2.5 · pp. 73–81
- 11L’identité ; exemples de théoriesà venir§ 2.6–2.7 · pp. 81–91
- 12Déduction naturelle : ∀ et ∃à venir§ 2.8–2.9 · pp. 91–99
- 13Déduction naturelle et identitéà venir§ 2.10 · pp. 99–102
Partie III · chapitre 3Complétude et applications
- 14Le théorème de complétudeà venir§ 3.1 · pp. 103–111
- 15Compacité et Skolem-Löwenheimà venir§ 3.2 · pp. 111–118
- 16Théorie des modèles : sous-structures, modèles non standardà venir§ 3.3 · pp. 118–124
- 17Théorie des modèles : catégoricité, décidabilité, élimination des quantificateursà venir§ 3.3 · pp. 124–135
- 18Fonctions de Skolemà venir§ 3.4 · pp. 135–142
Partie IV · chapitre 4Logique du second ordre
- 19Le second ordreà venirch. 4 · pp. 143–152
Partie V · chapitre 5Logique intuitionniste
- 20Le raisonnement constructifà venir§ 5.1 · pp. 153–156
- 21Logique intuitionniste des propositions et des prédicatsà venir§ 5.2 · pp. 156–162
- 22La sémantique de Kripkeà venir§ 5.3 · pp. 162–173
- 23Théorie des modèles intuitionnisteà venir§ 5.4 · pp. 173–186
Partie VI · chapitre 6Normalisation
- 24Les coupuresà venir§ 6.1 · pp. 187–192
- 25Normalisation classique et intuitionnisteà venir§ 6.2–6.3 · pp. 192–208
Partie VII · chapitre 7Le théorème de Gödel
- 26Fonctions récursives primitivesà venir§ 7.1 · pp. 209–218
- 27Fonctions récursives partiellesà venir§ 7.2 · pp. 218–230
- 28Ensembles récursivement énumérablesà venir§ 7.3 · pp. 230–236
- 29Arithmétique et représentabilitéà venir§ 7.4–7.5 · pp. 236–246
- 30Dérivabilité et incomplétudeà venir§ 7.6–7.7 · pp. 246–256
Le langage des propositions
À la fin de la leçon, on sait :
- distinguer le langage qu’on étudie et la langue dans laquelle on l’étudie ;
- dire si une suite de symboles est une formule, et le démontrer quand elle n’en est pas une ;
- démontrer une propriété de toutes les formules par induction ;
- définir une fonction sur les formules par récursion : rang, sous-formules, arbre.
Ce que fait le livre
Logic and Structure est né des cours que Dirk van Dalen donnait aux étudiants en mathématiques de l’université d’Utrecht ; la première édition date de 1980. Van Dalen a fait sa thèse sous la direction d’Arend Heyting, et il est le biographe de L. E. J. Brouwer, le fondateur de l’intuitionnisme. Cette filiation explique deux traits du livre : la place centrale de la déduction naturelle, et les chapitres consacrés à la logique intuitionniste (ch. 5) et à la normalisation des preuves (ch. 6).
La préface s’ouvre sur une distinction : « Logic appears in a ‘sacred’ and in a ‘profane’ form ». La forme sacrée, dominante en théorie de la démonstration, traite la logique avec la méfiance qu’ont laissée les paradoxes du début du XXe siècle (Cantor, Russell). La forme profane, celle de la théorie des modèles, la traite comme une branche ordinaire des mathématiques, au même titre que l’algèbre linéaire. Van Dalen, formé dans la tradition sacrée, choisit de commencer en profane : acquérir d’abord une pratique, garder les subtilités pour la fin du livre.
Le livre travaille avec trois notions, introduites pour les propositions au chapitre 1, puis étendues aux formules avec quantificateurs au chapitre 2.
Les suites de symboles bien formées.
φ est vraie dans toutes les situations.
φ se dérive par des règles.
Démontrabilité et vérité sont des notions de nature très différente. La première est combinatoire : on manipule des symboles selon des règles. La seconde est ensembliste : on parcourt toutes les situations possibles. Le théorème de complétude, démontré par Gödel en 1929, dit pourtant qu’elles délimitent exactement les mêmes formules. C’est le premier sommet du livre.
Le titre annonce un second fil : le rapport entre une description syntaxique et les structures mathématiques qu’elle décrit. L’introduction en donne un exemple. Un sous-ensemble d’un groupe, clos par produit et par inverse, est encore un groupe ; un sous-ensemble d’un corps algébriquement clos, clos par les opérations du corps, n’est en général pas algébriquement clos. La différence tient à la forme des axiomes : ceux des groupes sont universels (« pour tous x, y, z… »), alors que « tout polynôme a une racine » demande un « il existe ». Un théorème de Łoś et Tarski montre que ce n’est pas un hasard de formulation : une classe de structures axiomatisable est close par sous-structures si et seulement si on peut l’axiomatiser par des énoncés universels. On lit ainsi une propriété des structures sur la forme de leurs axiomes.
Pourquoi commencer par les propositions, alors que les mathématiques ont besoin de quantificateurs ? Parce que la logique propositionnelle présente en miniature les problèmes de la logique des prédicats, sans leurs complications techniques. La preuve de complétude du § 1.5 utilise déjà les ensembles cohérents maximaux, mais sans les « axiomes de Henkin » du chapitre 3.
L’introduction donne aussi un conseil de lecture. Quand une démonstration semble prouver une évidence, se figurer en machine : très habile à manipuler des symboles, dépourvue de toute intuition. La machine ne voit que des suites de symboles, et c’est pour elle que l’évidence doit être démontrée. Passé le chapitre 2, le même lecteur doit apprendre l’inverse : reconnaître les détails triviaux et les traiter comme tels.
Les notations du livre
Van Dalen suppose connues quelques notations ensemblistes. Voici celles du § 1.1 ; aucune autre théorie des ensembles n’est nécessaire pour l’instant.
| Notation | Se lit | Exemple dans la leçon |
|---|---|---|
| a ∈ X | a appartient à X | p0 ∈ PROP |
| a ∉ X | a n’appartient pas à X | ¬¬⊥ ∉ PROP |
| X ⊆ Y | X est inclus dans Y : tout élément de X est dans Y | PROP ⊆ X |
| X ∪ Y | réunion : les éléments de X ou de Y | Sub(φ) ∪ Sub(ψ) |
| X − Y | différence : les éléments de X qui ne sont pas dans Y | X − {¬¬⊥} |
| {x ∈ X ∣ A(x)} | les éléments de X qui ont la propriété A | {φ ∈ PROP ∣ A(φ)} |
| ℕ | les entiers naturels 0, 1, 2… | p_i pour i ∈ ℕ |
| F : A → B | F est une fonction qui associe à chaque élément de A un élément de B | r : PROP → ℕ |
| A² | l’ensemble des couples (a, b) d’éléments de A | H_□ : A² → A |
| ⇒, iff | « entraîne », « si et seulement si », dans le raisonnement, jamais dans les formules | φ ∈ X ⇒ (¬φ) ∈ X |
Phrases et connecteurs
La logique propositionnelle traite de phrases déclaratives : des phrases qui affirment qu’une chose est le cas, et qui peuvent donc être vraies ou fausses. Les questions et les ordres sont laissés de côté ; les mathématiques s’en passent. Van Dalen signale une exception, les instructions des programmes (« goto », « if… then… else »), qu’il écarte aussi.
On ne demande pas de savoir si une phrase est vraie, seulement qu’elle ait une valeur de vérité en principe. La conjecture de Goldbach (tout entier pair supérieur à 2 est la somme de deux nombres premiers) est vraie ou fausse, même si personne ne sait laquelle des deux. Ce principe de bivalence fonde les tables de vérité de la leçon 2.
Une phrase est atomique quand aucune de ses parties propres n’est une phrase, comme 2 + 2 = 5. Les autres se construisent à partir de phrases plus petites au moyen de connecteurs : et, ou, non, si… alors, mais, puisque, bien que, ni… ni… La logique n’en garde qu’un petit nombre et leur donne un sens fixe. Les exemples du livre (pp. 6–7) montrent ce qu’on perd en route.
- Les nuances. « π est irrationnel mais n’est pas algébrique » dit la même chose que « π est irrationnel et n’est pas algébrique ». « Mais » ajoute l’idée d’un contraste, qui ne change rien à la vérité de la phrase. On écrit ∧.
- Le temps. « Il a démarré et renversé un piéton » ne raconte pas la même histoire que « il a renversé un piéton et démarré ». En mathématiques le temps ne joue aucun rôle : φ ∧ ψ dit seulement que les deux sont le cas.
- Le lien de sens. « Si j’ouvre la fenêtre, nous aurons de l’air frais » suppose un rapport entre les deux parties. L’implication des mathématiques, dite matérielle, n’en exige aucun : « si 1 + 2 = 4, alors nous aurons de l’air frais » est acceptée. Van Dalen justifie ce choix : si le sens entrait dans la syntaxe, elle deviendrait une collection de cas particuliers.
- L’exclusion. Dans la langue, « ou » est souvent exclusif, et on ne dit pas « ou » quand on sait laquelle des deux parties est vraie. Le « ou » mathématique est inclusif et accepte ces disjonctions superflues : 2 ≥ 2 abrège « 2 > 2 ou 2 = 2 ».
La formalisation se fait en deux temps : se donner un langage formel, puis dire quelles propositions sont valides, par la sémantique (leçon 2) et par la preuve (leçon 4). La suite de cette leçon est le premier temps.
L’alphabet et l’ensemble PROP
On commence par l’alphabet, la liste des symboles permis.
L’alphabet de la logique propositionnelle comprend :
- des symboles propositionnels p0, p1, p2, … (une infinité) ;
- des connecteurs ∧, ∨, →, ¬, ↔, ⊥ ;
- des symboles auxiliaires : les parenthèses ( et ).
| Symbole | Se lit | Nom |
|---|---|---|
| ∧ | et | conjonction |
| ∨ | ou | disjonction |
| → | si…, alors… | implication |
| ¬ | non | négation |
| ↔ | si et seulement si | équivalence, bi-implication |
| ⊥ | le faux | falsum, absurde |
Les symboles propositionnels et ⊥ sont les atomes, ou propositions atomiques : les propositions qu’on ne décompose pas. Chaque p_i compte pour un seul symbole, même s’il s’écrit avec un indice.
Vient ensuite la définition des propositions. Van Dalen dit « propositions » ; on dit aussi « formules », et ce cours emploie les deux mots.
PROP est le plus petit ensemble X tel que :
- p_i ∈ X pour tout i ∈ ℕ, et ⊥ ∈ X ;
- si φ, ψ ∈ X, alors (φ ∧ ψ), (φ ∨ ψ), (φ → ψ), (φ ↔ ψ) ∈ X ;
- si φ ∈ X, alors (¬φ) ∈ X.
Pour abréger la clause (ii), on écrit (φ □ ψ), où □ désigne l’un quelconque des quatre connecteurs binaires.
Chaque construction ajoute sa paire de parenthèses : la négation de p0 s’écrit (¬p0), et la conjonction de p0 et de (¬p1) s’écrit (p0 ∧ (¬p1)). Ces parenthèses alourdissent l’écriture ; on verra plus bas qu’elles garantissent qu’une formule se lit d’une seule façon.
Pourquoi « le plus petit » ensemble ?
Beaucoup d’ensembles satisfont (i), (ii) et (iii). Par exemple, l’ensemble de toutes les suites finies de symboles de l’alphabet : il contient les atomes et il est clos par les constructions, mais il contient aussi des suites absurdes comme ((→∧. PROP est le plus petit de ces ensembles : il est inclus dans chacun d’eux.
Un tel plus petit ensemble existe : c’est l’intersection de tous les ensembles qui satisfont (i)–(iii). Cette intersection satisfait encore (i)–(iii). Chaque atome est dans tous ces ensembles, donc dans l’intersection ; si φ et ψ sont dans l’intersection, ils sont dans chacun des ensembles, donc (φ □ ψ) aussi, donc (φ □ ψ) est dans l’intersection ; de même pour (¬φ). Enfin l’intersection est incluse dans chacun des ensembles.
Concrètement, « le plus petit » signifie : PROP contient ce que les règles permettent de construire, et rien d’autre. Montrer qu’une suite est une formule est facile : on exhibe sa construction. Ainsi (p7 → p0) ∈ PROP, car p7 et p0 sont dans PROP par (i), puis (p7 → p0) par (ii). Montrer qu’une suite n’est pas une formule demande d’utiliser le « rien d’autre ».
¬¬⊥ ∉ PROP. Sous sa forme officielle, la double négation de ⊥ s’écrit (¬(¬⊥)). Pour montrer que la suite ¬¬⊥, sans parenthèses, n’est pas une formule, prenons un ensemble X qui satisfait (i)–(iii) et contient ¬¬⊥, et posons Y = X − {¬¬⊥}.
Y satisfait encore (i)–(iii). Les atomes sont dans Y, car aucun n’est la suite ¬¬⊥. Si φ, ψ ∈ Y, alors (φ □ ψ) ∈ X ; cette suite commence par une parenthèse, ce n’est donc pas ¬¬⊥, et elle est dans Y. De même pour (¬φ). Ainsi un ensemble qui satisfait (i)–(iii) et contient ¬¬⊥ n’est jamais le plus petit : le plus petit, PROP, ne contient pas ¬¬⊥.
La méthode est générale : pour exclure une suite, on exhibe un ensemble qui satisfait les clauses et ne la contient pas. L’exercice C5 en donne une autre, plus maniable, fondée sur l’induction.
Le connecteur ⊥
⊥ ne relie rien : c’est une constante logique, la proposition toujours fausse. Van Dalen le range parmi les connecteurs par commodité. On pourrait s’en passer, mais il simplifie la suite : en déduction naturelle (leçon 4), ⊥ est ce qu’on conclut d’une contradiction, et ¬φ y sert d’abréviation pour φ → ⊥. Le vrai, ⊤, n’est pas dans l’alphabet : c’est une abréviation de ¬⊥.
Langage-objet et métalangage
La définition 1.1.2 contient des lettres grecques, φ et ψ. Elles ne font pas partie de l’alphabet : aucune formule ne contient de φ. Ce sont des métavariables : des lettres qui désignent des formules quelconques, dans la langue que l’on parle à propos des formules.
Il y a donc deux langues. Le langage-objet, PROP, est celui qu’on étudie. Le métalangage est celui dans lequel on l’étudie : le français de ce cours, l’anglais du livre, complétés de notations mathématiques. Plusieurs symboles ont un double dans l’autre langue.
| Langage-objet | Métalangage |
|---|---|
| p0, p1, ⊥ : des symboles de l’alphabet | φ, ψ, χ : des noms pour des formules quelconques |
| → : un symbole qui figure dans les formules | ⇒ : « entraîne », dans un raisonnement sur les formules |
| ↔ : un symbole qui figure dans les formules | ⇔, « si et seulement si », « ssi » (iff) |
| (p0 ∧ p1) : une formule | « (p0 ∧ p1) ∈ PROP » : une phrase vraie à propos d’une formule |
Une expression comme (φ ∧ ψ) est un schéma : elle désigne une formule dès qu’on remplace φ et ψ par des formules. Avec φ = p0 et ψ = (¬p1), elle désigne (p0 ∧ (¬p1)). Sans métavariables, la clause (ii) se dirait : si deux formules sont dans X, la suite formée d’une parenthèse ouvrante, de la première formule, du symbole ∧, de la seconde formule et d’une parenthèse fermante est aussi dans X. Van Dalen fait remarquer que cette version verbale suffit à faire apprécier la notation.
Démontrer par induction
La définition inductive de PROP fournit une méthode de démonstration. Pour établir qu’une propriété vaut pour toutes les formules, on suit la construction : on la vérifie pour les atomes, puis on montre que chaque connecteur la préserve.
Soit A une propriété. A(φ) est vraie pour toute φ ∈ PROP si :
- A(p_i) pour tout i, et A(⊥) ;
- A(φ) et A(ψ) entraînent A((φ □ ψ)) ;
- A(φ) entraîne A((¬φ)).
Preuve. L’ensemble X = {φ ∈ PROP ∣ A(φ)} satisfait les clauses (i), (ii) et (iii) de la définition 1.1.2. Or PROP est le plus petit ensemble qui les satisfait ; donc PROP ⊆ X : toute formule a la propriété A. □
C’est le mécanisme de la récurrence sur les entiers. ℕ est le plus petit ensemble qui contient 0 et qui contient n + 1 dès qu’il contient n ; d’où le principe de récurrence. PROP a plusieurs points de départ, les atomes, et plusieurs façons de passer à l’étape suivante, une par connecteur. En français, on parle aussi de récurrence structurelle ou d’induction structurelle.
Le patron d’une démonstration par induction
- Atomes. Vérifier A pour chaque p_i et pour ⊥.
- Connecteurs binaires. Supposer A(φ) et A(ψ) (c’est l’hypothèse d’induction), en déduire A((φ □ ψ)). Un seul raisonnement couvre souvent les quatre connecteurs.
- Négation. Supposer A(φ), en déduire A((¬φ)).
Exemple du livre : toute formule contient un nombre pair de parenthèses.
(i) Un atome en contient 0, qui est pair. (ii) Si φ en contient 2n et ψ en contient 2m, alors (φ □ ψ) en contient 2n + 2m + 2 = 2(n + m + 1). (iii) Si φ en contient 2n, alors (¬φ) en contient 2(n + 1). □
En pratique, on écrit seulement les trois cas ; la conclusion, « donc toute formule a la propriété », va sans dire.
Suites de formation
La définition 1.1.2 décrit PROP d’en haut, comme le plus petit ensemble clos. On peut aussi la décrire d’en bas, comme le résultat d’une construction pas à pas où chaque étape n’utilise que des étapes antérieures.
Une suite φ_0, …, φ_n est une suite de formation de φ si φ_n = φ et si, pour tout i ≤ n, φ_i est un atome, ou φ_i = (φ_j □ φ_k) pour certains j, k < i, ou φ_i = (¬φ_j) pour un certain j < i.
Pour ((¬p0) → ⊥), par exemple : p0, ⊥, (¬p0), ((¬p0) → ⊥). Une suite de formation peut contenir des déchets, des étapes qui ne servent à rien : p0, p5, ⊥, (p5 ∧ p5), (¬p0), ((¬p0) → ⊥) en est une aussi.
PROP est l’ensemble des suites de symboles qui ont une suite de formation.
Idée de la preuve. Toute formule a une suite de formation : par induction sur φ ; pour (φ □ ψ), on met bout à bout une suite de formation de φ et une de ψ, et on ajoute (φ □ ψ). Réciproquement, une suite de symboles qui a une suite de formation est une formule : par récurrence sur la longueur de la suite de formation. □
Le théorème justifie la notion de suite de formation, et permet de démontrer des propriétés des formules par récurrence ordinaire sur la longueur de ces suites.
Définir par récursion
En arithmétique, on définit des fonctions par récurrence : x^0 = 1 et x^{y+1} = x^y · x ; 0! = 1 et (n + 1)! = n! · (n + 1). Chaque valeur se calcule à partir des précédentes. La définition inductive de PROP permet de définir de la même façon des fonctions sur les formules : on donne la valeur sur les atomes et, pour chaque connecteur, une règle qui calcule la valeur d’un composé à partir des valeurs de ses parties. Par exemple, le nombre de parenthèses b(φ) :
Soient H_at une fonction de l’ensemble des atomes dans un ensemble A, H_□ : A² → A (une pour chaque connecteur binaire) et H_¬ : A → A. Il existe une et une seule fonction F : PROP → A telle que :
Pour b : A = ℕ, H_at(φ) = 0, H_□(m, n) = m + n + 2 et H_¬(n) = n + 2. Van Dalen laisse la preuve du théorème en exercice (exercice 11) : elle n’a rien d’évident.
Ce que suppose le théorème : la lecture unique
Pour calculer F(σ), on décompose σ en ses parties immédiates, puis on applique la clause qui convient. Cela suppose que la décomposition soit unique. Si une même suite de symboles pouvait se lire à la fois comme (φ ∧ ψ) et comme (φ′ → ψ′), les deux clauses pourraient donner deux valeurs différentes, et F ne serait pas une fonction.
Supprimons les parenthèses pour voir le problème : p0 ∧ p1 ∨ p2 se lit (p0 ∧ p1) ∨ p2 ou p0 ∧ (p1 ∨ p2). Si p0 est faux et p2 vrai, la première lecture est vraie et la seconde fausse. Or la vérité d’une formule (leçon 2) sera elle-même définie par récursion : sans lecture unique, une formule n’aurait pas de valeur de vérité déterminée.
Les parenthèses garantissent l’unicité ; c’est le théorème de lecture unique, que Van Dalen donne en exercice (exercice 10, p. 15). L’idée tient en un compteur. Sous chaque symbole d’une formule, notons le nombre de parenthèses ouvertes, et pas encore refermées, qui le précèdent. Dans (φ □ ψ), le connecteur □ est le seul connecteur binaire au niveau 1 ; ceux de φ et de ψ sont plus profonds. On repère ainsi sans ambiguïté le connecteur principal, la dernière étape de la construction.
Trois définitions par récursion
Le rang r(φ) mesure la profondeur d’imbrication :
L’ensemble des sous-formules Sub(φ) (déf. 1.1.7, p. 12) :
ψ est une sous-formule de φ si ψ ∈ Sub(φ). Par exemple, Sub((p0 ∧ (¬p1))) = {p0, p1, (¬p1), (p0 ∧ (¬p1))}. L’arbre d’analyse, enfin, se définit lui aussi par récursion : c’est l’objet de la section suivante.
Arbres, rang, sous-formules
L’arbre d’analyse T(φ) d’un atome est un nœud unique, étiqueté φ. Celui de (φ □ ψ) a une racine étiquetée (φ □ ψ), sous laquelle on place T(φ) à gauche et T(ψ) à droite. Celui de (¬φ) a une racine étiquetée (¬φ) avec T(φ) au-dessous. La racine est en haut, les atomes en bas.
L’arbre rend visibles plusieurs notions à la fois :
- le connecteur principal est l’étiquette de la racine, la dernière étape de la construction (ici →) ;
- les sous-formules sont les formules attachées aux nœuds ;
- le rang est la hauteur de l’arbre, la longueur de sa plus longue branche (exercice 8c) : ici 3.
Formules et occurrences
Dans (p1 → p1), il n’y a qu’une sous-formule atomique, p1, mais elle figure à deux endroits. Pour distinguer les occurrences, Van Dalen repère chaque nœud de l’arbre par une adresse, une suite de 0 et de 1. La racine a l’adresse vide ⟨ ⟩. Si un nœud a l’adresse ⟨s_0, …, s_{n−1}⟩, son premier descendant immédiat a l’adresse ⟨s_0, …, s_{n−1}, 0⟩ et le second, s’il existe, ⟨s_0, …, s_{n−1}, 1⟩. Dans (p1 → p1), les deux occurrences de p1 ont les adresses ⟨0⟩ et ⟨1⟩. Une occurrence est un couple formé d’une formule et d’une adresse. L’atelier affiche l’adresse du nœud qu’on touche.
Conventions d’écriture
Les parenthèses officielles rendent les formules pénibles à lire. On convient donc (p. 12) :
- de supprimer les parenthèses extérieures ;
- de supprimer celles des négations : ¬φ pour (¬φ) ;
- que ∧ et ∨ lient plus fort que → et ↔, comme · lie plus fort que + en arithmétique ;
- que ¬ lie plus fort que tous les autres connecteurs.
| Abréviation | Formule officielle |
|---|---|
| ¬p0 ∨ p1 | ((¬p0) ∨ p1) |
| p0 ∧ p1 → p2 | ((p0 ∧ p1) → p2) |
| ¬(p0 → ¬p1) | (¬(p0 → (¬p1))) |
| p0 → p1 ∨ (p2 ↔ ⊥) | (p0 → (p1 ∨ (p2 ↔ ⊥))) |
Deux remarques. Les abréviations ne sont pas des formules : ce sont des noms commodes pour des formules. Et les conventions ne règlent pas tout : ∧ et ∨ lient avec la même force, et rien ne fixe le groupement de → avec →. Dans p0 ∧ p1 ∨ p2 ou p0 → p1 → p2, les parenthèses restent obligatoires.
Induction sur le rang
Si, pour toute formule φ, la propriété A vaut pour φ dès qu’elle vaut pour toutes les formules de rang strictement inférieur à r(φ), alors A vaut pour toute formule.
Le rang ramène l’arbre à la droite des entiers : on raisonne par récurrence forte sur le nombre r(φ). Ce principe est équivalent au principe d’induction 1.1.3. La démonstration de l’équivalence (pp. 13–14) peut être sautée en première lecture ; Van Dalen le dit lui-même en note, et conseille d’appliquer l’induction sur le rang sans scrupule. D’autres mesures feraient aussi bien l’affaire : le nombre de symboles, le nombre de connecteurs.
Son intérêt : le principe 1.1.3 ne fournit l’hypothèse que pour les parties immédiates φ et ψ ; l’induction sur le rang la fournit pour toutes les formules plus simples. Cela servira quand une démonstration a besoin de formules qui ne sont pas des sous-formules, par exemple des formules obtenues par substitution.
Atelier : l’arbre d’une formule
Saisir une formule : l’atelier dit si elle est bien formée, rétablit la forme officielle, trace l’arbre et calcule le rang, les sous-formules, une suite de formation et le compteur de parenthèses. Faire d’abord les exercices à la main, puis vérifier ici.
Au clavier : ~ ou ! pour ¬ · & pour ∧ · | pour ∨ · -> pour → · <-> pour ↔ · _|_ pour ⊥ · atomes p0, p1, p2…
Exercices
Les exercices C1 à C8 sont propres au cours. Ceux du livre se font dans le livre ; envoyer les réponses dans la conversation en les nommant (« livre 3 », « C6 ») pour qu’elles soient corrigées. Minimum pour passer à la leçon 2 : C1 à C6, et les exercices 1, 2, 3, 6 et 7 du livre.
- C1
Forme officielle. Rétablir toutes les parenthèses :
- ¬p0 ∨ p1 → p2 ∧ ¬⊥
- ¬(p1 ∧ ¬p2) ↔ p3
- p0 → (p1 → p2)
Corrigé
- (((¬p0) ∨ p1) → (p2 ∧ (¬⊥))) : ¬ s’applique d’abord, puis ∨ et ∧, enfin →.
- ((¬(p1 ∧ (¬p2))) ↔ p3)
- (p0 → (p1 → p2)) : ici les parenthèses intérieures étaient déjà obligatoires, puisqu’aucune convention ne groupe → avec →.
- C2
Dans PROP ou non ? Au sens strict de la définition 1.1.2, lesquelles de ces suites sont des formules ?
- (p1 ∧ p2)
- p1 ∧ p2
- ((¬p1) → ⊥)
- (p1)
- (p1 ∨ p2 ∨ p3)
- ⊥
- (¬¬p1)
- ((p0 ↔ p0) ∧ (¬⊥))
Corrigé
- Oui.
- Non : c’est l’abréviation de (a) ; il manque les parenthèses extérieures.
- Oui.
- Non : aucune clause ne met un atome entre parenthèses.
- Non : chaque connecteur binaire apporte sa propre paire de parenthèses. Il faudrait ((p1 ∨ p2) ∨ p3) ou (p1 ∨ (p2 ∨ p3)).
- Oui : c’est un atome.
- Non : la négation intérieure doit avoir ses parenthèses, (¬(¬p1)).
- Oui.
- C3
Lire une formule. Pour φ = (p0 → p1) ∧ ¬p0, donner : le connecteur principal ; le rang ; Sub(φ) ; une suite de formation sans déchets, puis une avec déchets.
Corrigé
Connecteur principal : ∧. Rang : r(p0 → p1) = 1 et r(¬p0) = 1, donc r(φ) = max(1, 1) + 1 = 2.
Sub(φ) = {p0, p1, (p0 → p1), (¬p0), φ} : cinq sous-formules. p0 est une seule sous-formule, avec deux occurrences.
Sans déchets : p0, p1, (p0 → p1), (¬p0), ((p0 → p1) ∧ (¬p0)). Avec déchets : p0, p1, p7, (p0 → p1), (p7 ∨ p7), (¬p0), ((p0 → p1) ∧ (¬p0)).
- C4
Ambiguïtés. Pourquoi φ ∧ ψ ∨ χ et φ → ψ → χ ne sont-elles pas des abréviations admises ?
Corrigé
Les conventions de la p. 12 ne disent rien du groupement de ∧ avec ∨, qui lient avec la même force, ni de celui de → avec →. Chaque écriture a deux lectures : (φ ∧ ψ) ∨ χ ou φ ∧ (ψ ∨ χ) ; (φ → ψ) → χ ou φ → (ψ → χ).
Ces lectures ne disent pas la même chose. Avec φ faux et χ vrai, (φ ∧ ψ) ∨ χ est vraie et φ ∧ (ψ ∨ χ) fausse. Avec φ, ψ, χ tous faux, (φ → ψ) → χ est fausse et φ → (ψ → χ) vraie. La leçon 2 justifie ces calculs.
- C5
Exclure par induction. Montrer par induction que toute formule est un atome, ou bien commence par « ( » et finit par « ) ». En déduire que ¬¬⊥ ∉ PROP.
Corrigé
Soit A(φ) : « φ est un atome, ou φ commence par ( et finit par ) ». (i) Les atomes ont la propriété. (ii) (φ □ ψ) commence par ( et finit par ), sans même qu’on ait besoin de l’hypothèse sur φ et ψ. (iii) De même pour (¬φ). Par le théorème 1.1.3, toute formule a la propriété A.
Or ¬¬⊥ n’est pas un atome et commence par ¬ : ce n’est pas une formule. L’induction sert ici moins à construire qu’à exclure tout ce que les règles ne produisent pas.
- C6
Compter. Soit a(φ) le nombre d’occurrences d’atomes dans φ, et c(φ) le nombre d’occurrences de connecteurs binaires. Montrer que a(φ) = c(φ) + 1 pour toute formule φ.
Corrigé
(i) Pour un atome : a = 1 et c = 0. (ii) Avec l’hypothèse d’induction pour φ et ψ : a((φ □ ψ)) = a(φ) + a(ψ) = (c(φ) + 1) + (c(ψ) + 1) = (c(φ) + c(ψ) + 1) + 1 = c((φ □ ψ)) + 1. (iii) La négation ne change ni a ni c : a((¬φ)) = a(φ) = c(φ) + 1 = c((¬φ)) + 1. □
⊥ compte comme un atome. Dans l’arbre, la propriété dit qu’un arbre où chaque nœud a zéro, un ou deux descendants possède une feuille de plus que de nœuds à deux descendants.
- C7
Définir par récursion. Définir par récursion : la fonction n(φ), nombre d’occurrences de ¬ dans φ ; la fonction At(φ), ensemble des symboles propositionnels qui figurent dans φ. Calculer les deux pour ¬(p1 ∧ ¬p2) ↔ p1. Préciser, pour n, les fonctions H_at, H_□, H_¬ du théorème 1.1.6.
Corrigé
n(φ) = 0si φ est atomique n((φ □ ψ)) = n(φ) + n(ψ) n((¬φ)) = n(φ) + 1At(p_i) = {p_i}et At(⊥) = ∅ At((φ □ ψ)) = At(φ) ∪ At(ψ) At((¬φ)) = At(φ)Pour ¬(p1 ∧ ¬p2) ↔ p1 : n = 2 et At = {p1, p2}. Pour n : A = ℕ, H_at(φ) = 0, H_□(k, l) = k + l, H_¬(k) = k + 1.
- C8
Défi : la lecture unique. Cet exercice prépare l’exercice 10 du livre.
- Montrer par induction que toute formule contient autant de « ( » que de « ) ».
- Montrer par induction que tout segment initial propre et non vide d’une formule contient strictement plus de « ( » que de « ) ».
- En déduire que dans une formule (φ □ ψ), le connecteur □ est le seul connecteur binaire précédé d’exactement une parenthèse ouverte non refermée. Pourquoi cela entraîne-t-il la lecture unique ?
Indications
(b) Un atome est un seul symbole : il n’a pas de segment initial propre non vide. Un segment initial propre non vide de (φ □ ψ) s’écrit « ( » suivi d’un segment initial de φ □ ψ ; utiliser (a) pour les morceaux complets et l’hypothèse d’induction pour le morceau entamé.
(c) Un connecteur binaire situé à l’intérieur de φ est précédé de « ( » et d’un segment initial propre non vide de φ : combien de parenthèses ouvertes, au moins ? Même question à l’intérieur de ψ.
Pour conclure, comparer deux décompositions (φ □ ψ) = (φ′ □′ ψ′), et utiliser C5 pour séparer le cas (¬φ). Envoyer la démonstration dans la conversation.
Exercices du livre (pp. 14–15)
| Exercice | Ce qu’il travaille | Priorité |
|---|---|---|
| 1 | suites de formation | essentiel |
| 2 | montrer qu’une suite n’est pas une formule | essentiel |
| 3 | la relation « est une sous-formule de » est transitive (induction) | essentiel |
| 4, 5 | sous-formules et suites de formation | approfondir |
| 6 | le rang : inégalités, calculs, sous-formules propres | essentiel |
| 7 | arbres, dans les deux sens | essentiel |
| 8, 9 | compter nœuds, sous-formules, branches | approfondir |
| 10 | lecture unique (voir C8) | défi · utile pour la suite |
| 11 | justifier la définition par récursion | défi |
À retenir
- PROP est défini par induction : des atomes et des règles de construction. « Le plus petit ensemble » exclut tout le reste.
- φ, ψ, χ sont des métavariables du métalangage ; → est un symbole du langage-objet, ⇒ un mot du raisonnement.
- Démontrer par induction : les atomes, puis chaque connecteur, en supposant la propriété pour les parties.
- Définir par récursion : une valeur pour les atomes, une règle de calcul par connecteur. C’est légitime parce que chaque formule se lit d’une seule façon.
- La structure d’une formule est un arbre : le connecteur principal en est la racine, les sous-formules en sont les nœuds, le rang en est la hauteur.
Leçon 2 · Vérité et valuations (§ 1.2, pp. 15–21) : valuations, tables de vérité, conséquence sémantique Γ ⊨ φ, tautologies, substitution. Pour la préparer : lire les pp. 15–21.
Les mots du cours
Le livre est en anglais, le cours en français : chaque terme est donné dans les deux langues, avec la leçon où il apparaît.
| Français | Anglais (livre) | Sens | Leçon |
|---|---|---|---|
| proposition, formule | proposition | élément de PROP | 1 |
| symbole propositionnel | proposition symbol | p0, p1, p2, … | 1 |
| atome | atom, atomic proposition | symbole propositionnel ou ⊥ | 1 |
| connecteur | connective | ∧, ∨, →, ¬, ↔ ; ⊥ par extension | 1 |
| falsum, absurde | falsum, absurdum | ⊥, la proposition toujours fausse | 1 |
| implication matérielle | material implication | l’implication sans lien de sens exigé entre ses parties | 1 |
| langage-objet | object language | le langage étudié, ici PROP | 1 |
| métalangage | meta-language | la langue dans laquelle on parle du langage-objet | 1 |
| métavariable | meta-variable | φ, ψ, χ : lettres pour des formules quelconques | 1 |
| définition inductive | inductive definition | des éléments de départ et des règles ; on prend le plus petit ensemble clos | 1 |
| démonstration par induction | proof by induction on φ | vérifier les atomes, puis chaque connecteur | 1 |
| suite de formation | formation sequence | construction pas à pas d’une formule | 1 |
| définition par récursion | definition by recursion | une valeur sur les atomes, une règle de calcul par connecteur | 1 |
| lecture unique | unique decomposition, unique readability | chaque formule se décompose d’une seule façon | 1 |
| connecteur principal | main connective | la dernière étape de la construction, la racine de l’arbre | 1 |
| arbre d’analyse | (parsing) tree | T(φ) | 1 |
| rang | rank | r(φ), la hauteur de l’arbre | 1 |
| sous-formule | subformula | élément de Sub(φ) | 1 |
| occurrence | occurrence | une sous-formule à un endroit précis de l’arbre | 1 |
| imprédicatif | impredicative | défini au moyen d’une totalité dont il fait partie | 1 |