Cours suivi · logique mathématiqueD. van Dalen, Logic and Structure, 4e éd.
Un cours en français, une leçon à la fois, exercices corrigés dans la conversation

Logique avec Van Dalen

Trente leçons pour lire Logic and Structure de Dirk van Dalen (Springer), de la syntaxe des propositions au théorème d’incomplétude de Gödel. Chaque leçon explique une partie du livre, définit chaque terme, replace les idées dans leur histoire et se termine par des exercices.

En ligneLeçon 1 · Le langage des propositions
EnsuiteLeçon 2 · Vérité et valuations
Mis à jour2 octobre 2026
Méthode

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.

  1. 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.
  2. 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.
  3. 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.
  4. É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.
Plan

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

  1. 01Le langage des propositionsen lignePréface, introduction, § 1.1 · pp. 1–15
  2. 02Vérité et valuationsà venir§ 1.2 · pp. 15–21
  3. 03Équivalences, formes normales, connecteursà venir§ 1.3 · pp. 21–30
  4. 04La déduction naturelleà venir§ 1.4 · pp. 30–40
  5. 05Le théorème de complétudeà venir§ 1.5 · pp. 40–49
  6. 06Les connecteurs manquantsà venir§ 1.6 · pp. 49–56

Partie II · chapitre 2Logique des prédicats

  1. 07Quantificateurs et structuresà venir§ 2.1–2.2 · pp. 57–60
  2. 08Le langage d’un type de similaritéà venir§ 2.3 · pp. 60–68
  3. 09La sémantique de Tarskià venir§ 2.4 · pp. 68–73
  4. 10Propriétés simples de la logique des prédicatsà venir§ 2.5 · pp. 73–81
  5. 11L’identité ; exemples de théoriesà venir§ 2.6–2.7 · pp. 81–91
  6. 12Déduction naturelle : ∀ et ∃à venir§ 2.8–2.9 · pp. 91–99
  7. 13Déduction naturelle et identitéà venir§ 2.10 · pp. 99–102

Partie III · chapitre 3Complétude et applications

  1. 14Le théorème de complétudeà venir§ 3.1 · pp. 103–111
  2. 15Compacité et Skolem-Löwenheimà venir§ 3.2 · pp. 111–118
  3. 16Théorie des modèles : sous-structures, modèles non standardà venir§ 3.3 · pp. 118–124
  4. 17Théorie des modèles : catégoricité, décidabilité, élimination des quantificateursà venir§ 3.3 · pp. 124–135
  5. 18Fonctions de Skolemà venir§ 3.4 · pp. 135–142

Partie IV · chapitre 4Logique du second ordre

  1. 19Le second ordreà venirch. 4 · pp. 143–152

Partie V · chapitre 5Logique intuitionniste

  1. 20Le raisonnement constructifà venir§ 5.1 · pp. 153–156
  2. 21Logique intuitionniste des propositions et des prédicatsà venir§ 5.2 · pp. 156–162
  3. 22La sémantique de Kripkeà venir§ 5.3 · pp. 162–173
  4. 23Théorie des modèles intuitionnisteà venir§ 5.4 · pp. 173–186

Partie VI · chapitre 6Normalisation

  1. 24Les coupuresà venir§ 6.1 · pp. 187–192
  2. 25Normalisation classique et intuitionnisteà venir§ 6.2–6.3 · pp. 192–208

Partie VII · chapitre 7Le théorème de Gödel

  1. 26Fonctions récursives primitivesà venir§ 7.1 · pp. 209–218
  2. 27Fonctions récursives partiellesà venir§ 7.2 · pp. 218–230
  3. 28Ensembles récursivement énumérablesà venir§ 7.3 · pp. 230–236
  4. 29Arithmétique et représentabilitéà venir§ 7.4–7.5 · pp. 236–246
  5. 30Dérivabilité et incomplétudeà venir§ 7.6–7.7 · pp. 246–256
Leçon 1 · Partie I, logique propositionnelle

Le langage des propositions

Livre : préface (pp. V–VII), introduction (pp. 1–3), § 1.1 (pp. 5–15) · PDF : pp. 5–23
Lecture de la leçon : 40 min · exercices : 1 h à 1 h 30

À 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.
Préface et introduction · pp. V–VII, 1–3

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.

Syntaxe · § 1.1LangagePROP

Les suites de symboles bien formées.

Sémantique · § 1.2Vérité⊨ φ

φ est vraie dans toutes les situations.

Démonstration · § 1.4Preuve⊢ φ

φ se dérive par des règles.

Complétude · § 1.5, § 3.1Le théorème de complétude relie les deux dernières colonnes : ⊢ φ ⇔ ⊨ φ.

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.

Prérequis

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.

NotationSe litExemple dans la leçon
a ∈ Xa appartient à Xp0 ∈ PROP
a ∉ Xa n’appartient pas à X¬¬⊥ ∉ PROP
X ⊆ YX est inclus dans Y : tout élément de X est dans YPROP ⊆ X
X ∪ Yréunion : les éléments de X ou de YSub(φ) ∪ Sub(ψ)
X − Ydifférence : les éléments de X qui ne sont pas dans YX − {¬¬⊥}
{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 → BF est une fonction qui associe à chaque élément de A un élément de Br : PROP → ℕ
A²l’ensemble des couples (a, b) d’éléments de AH_□ : A² → A
⇒, iff« entraîne », « si et seulement si », dans le raisonnement, jamais dans les formulesφ ∈ X ⇒ (¬φ) ∈ X
§ 1.1 · pp. 5–7

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.

Déf. 1.1.1 et 1.1.2 · pp. 7–8

L’alphabet et l’ensemble PROP

On commence par l’alphabet, la liste des symboles permis.

Définition 1.1.1 · l’alphabet

L’alphabet de la logique propositionnelle comprend :

  1. des symboles propositionnels p0, p1, p2, … (une infinité) ;
  2. des connecteurs ∧, ∨, →, ¬, ↔, ⊥ ;
  3. des symboles auxiliaires : les parenthèses ( et ).
SymboleSe litNom
∧etconjonction
∨oudisjonction
→si…, alors…implication
¬nonnégation
↔si et seulement siéquivalence, bi-implication
⊥le fauxfalsum, 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.

Définition 1.1.2 · les propositions

PROP est le plus petit ensemble X tel que :

  1. p_i ∈ X pour tout i ∈ ℕ, et ⊥ ∈ X ;
  2. si φ, ψ ∈ X, alors (φ ∧ ψ), (φ ∨ ψ), (φ → ψ), (φ ↔ ψ) ∈ X ;
  3. 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 ».

Exemple · p. 8

¬¬⊥ ∉ 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 ¬⊥.

p. 8

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-objetMé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.

Th. 1.1.3 · p. 9

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.

Théorème 1.1.3 · principe d’induction

Soit A une propriété. A(φ) est vraie pour toute φ ∈ PROP si :

  1. A(p_i) pour tout i, et A(⊥) ;
  2. A(φ) et A(ψ) entraînent A((φ □ ψ)) ;
  3. 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

  1. Atomes. Vérifier A pour chaque p_i et pour ⊥.
  2. 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.
  3. 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.

Déf. 1.1.4, th. 1.1.5 · pp. 9–10

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.

Définition 1.1.4 · suite de formation

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.

Théorème 1.1.5

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.

Th. 1.1.6 · pp. 10–12 · exercices 10 et 11

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(φ) :

b(φ) = 0si φ est atomique b((φ □ ψ)) = b(φ) + b(ψ) + 2 b((¬φ)) = b(φ) + 2
Théorème 1.1.6 · définition par récursion

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 :

F(φ) = H_at(φ)si φ est atomique F((φ □ ψ)) = H_□(F(φ), F(ψ)) F((¬φ)) = H_¬(F(φ))

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.

Le compteur de parenthèses de ((p0 ∧ p1) → (¬p2)). Le connecteur principal, →, est le seul connecteur binaire au niveau 1. L’atelier affiche ce compteur pour n’importe quelle formule.

Trois définitions par récursion

Le rang r(φ) mesure la profondeur d’imbrication :

r(φ) = 0si φ est atomique r((φ □ ψ)) = max(r(φ), r(ψ)) + 1 r((¬φ)) = r(φ) + 1

L’ensemble des sous-formules Sub(φ) (déf. 1.1.7, p. 12) :

Sub(φ) = {φ}si φ est atomique Sub((φ □ ψ)) = Sub(φ) ∪ Sub(ψ) ∪ {(φ □ ψ)} Sub((¬φ)) = Sub(φ) ∪ {(¬φ)}

ψ 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.

pp. 11–13

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.

Étiqueté par les sous-formules
Étiqueté par les connecteurs
L’arbre de (p1 → (⊥ ∨ (¬p3))), de deux façons. La seconde, plus légère, place les atomes en bas et les connecteurs aux nœuds. Comme chez Van Dalen, les arêtes de négation sont tracées en gras.

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éviationFormule 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.

Th. 1.1.8 · pp. 13–14

Induction sur le rang

Théorème 1.1.8 · 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.

Outil · pour vérifier C1–C3 et les exercices 1, 6c et 7a du livre

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.

Lecture
Exemples

Au clavier : ~ ou ! pour ¬ · & pour ∧ · | pour ∨ · -> pour → · <-> pour ↔ · _|_ pour ⊥ · atomes p0, p1, p2…

Toucher un nœud pour voir son adresse et sa sous-formule.
Exercices · corrigés dépliables pour C1–C7 · livre pp. 14–15

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.

  1. C1

    Forme officielle. Rétablir toutes les parenthèses :

    1. ¬p0 ∨ p1 → p2 ∧ ¬⊥
    2. ¬(p1 ∧ ¬p2) ↔ p3
    3. p0 → (p1 → p2)
    Corrigé
    1. (((¬p0) ∨ p1) → (p2 ∧ (¬⊥))) : ¬ s’applique d’abord, puis ∨ et ∧, enfin →.
    2. ((¬(p1 ∧ (¬p2))) ↔ p3)
    3. (p0 → (p1 → p2)) : ici les parenthèses intérieures étaient déjà obligatoires, puisqu’aucune convention ne groupe → avec →.
  2. C2

    Dans PROP ou non ? Au sens strict de la définition 1.1.2, lesquelles de ces suites sont des formules ?

    1. (p1 ∧ p2)
    2. p1 ∧ p2
    3. ((¬p1) → ⊥)
    4. (p1)
    5. (p1 ∨ p2 ∨ p3)
    6. ⊥
    7. (¬¬p1)
    8. ((p0 ↔ p0) ∧ (¬⊥))
    Corrigé
    1. Oui.
    2. Non : c’est l’abréviation de (a) ; il manque les parenthèses extérieures.
    3. Oui.
    4. Non : aucune clause ne met un atome entre parenthèses.
    5. Non : chaque connecteur binaire apporte sa propre paire de parenthèses. Il faudrait ((p1 ∨ p2) ∨ p3) ou (p1 ∨ (p2 ∨ p3)).
    6. Oui : c’est un atome.
    7. Non : la négation intérieure doit avoir ses parenthèses, (¬(¬p1)).
    8. Oui.
  3. 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)).

  4. 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.

  5. 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.

  6. 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.

  7. 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(φ) + 1
    At(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.

  8. C8

    Défi : la lecture unique. Cet exercice prépare l’exercice 10 du livre.

    1. Montrer par induction que toute formule contient autant de « ( » que de « ) ».
    2. Montrer par induction que tout segment initial propre et non vide d’une formule contient strictement plus de « ( » que de « ) ».
    3. 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)

ExerciceCe qu’il travaillePriorité
1suites de formationessentiel
2montrer qu’une suite n’est pas une formuleessentiel
3la relation « est une sous-formule de » est transitive (induction)essentiel
4, 5sous-formules et suites de formationapprofondir
6le rang : inégalités, calculs, sous-formules propresessentiel
7arbres, dans les deux sensessentiel
8, 9compter nœuds, sous-formules, branchesapprofondir
10lecture unique (voir C8)défi · utile pour la suite
11justifier la définition par récursiondéfi
Synthèse

À 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.
Lexique

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çaisAnglais (livre)SensLeçon
proposition, formulepropositionélément de PROP1
symbole propositionnelproposition symbolp0, p1, p2, …1
atomeatom, atomic propositionsymbole propositionnel ou ⊥1
connecteurconnective∧, ∨, →, ¬, ↔ ; ⊥ par extension1
falsum, absurdefalsum, absurdum⊥, la proposition toujours fausse1
implication matériellematerial implicationl’implication sans lien de sens exigé entre ses parties1
langage-objetobject languagele langage étudié, ici PROP1
métalangagemeta-languagela langue dans laquelle on parle du langage-objet1
métavariablemeta-variableφ, ψ, χ : lettres pour des formules quelconques1
définition inductiveinductive definitiondes éléments de départ et des règles ; on prend le plus petit ensemble clos1
démonstration par inductionproof by induction on φvérifier les atomes, puis chaque connecteur1
suite de formationformation sequenceconstruction pas à pas d’une formule1
définition par récursiondefinition by recursionune valeur sur les atomes, une règle de calcul par connecteur1
lecture uniqueunique decomposition, unique readabilitychaque formule se décompose d’une seule façon1
connecteur principalmain connectivela dernière étape de la construction, la racine de l’arbre1
arbre d’analyse(parsing) treeT(φ)1
rangrankr(φ), la hauteur de l’arbre1
sous-formulesubformulaélément de Sub(φ)1
occurrenceoccurrenceune sous-formule à un endroit précis de l’arbre1
imprédicatifimpredicativedéfini au moyen d’une totalité dont il fait partie1