Aller au contenu
Topos Uranos
Français

Lois généralisées de De Morgan et de distributivité

Résumé

Les lois de De Morgan et de distributivité ont été énoncées jusqu’ici pour deux termes ; les formes normales, en revanche, réunissent des conjonctions et des disjonctions d’un nombre quelconque de termes, et les exigent dans cette généralité. Cette leçon définit par récurrence la conjonction et la disjonction d’une liste de formules (φ1,…,φn)(\varphi_1, \ldots, \varphi_n), qui s’écrivent ⋀i=1nφi\bigwedge_{i=1}^{n} \varphi_i et ⋁i=1nφi\bigvee_{i=1}^{n} \varphi_i, en associant à gauche, et démontre par récurrence sur le nombre de termes le lemme de la valeur (une conjonction est vraie si et seulement si tous ses termes le sont ; une disjonction, si et seulement si l’un d’eux l’est), l’associativité généralisée, qui autorise à regrouper, l’indépendance de l’ordre et des répétitions, les lois de De Morgan généralisées et la distributivité généralisée sous la forme qu’utilisera la leçon sur les formes normales : la conjonction de deux disjonctions, de nn et de mm termes, équivaut à la disjonction des nmnm conjonctions d’un terme de chacune, et dualement. Les problèmes comptent des valuations, localisent l’erreur d’une démonstration qui fait passer un regroupement pour une définition, mesurent la croissance d’une distribution et en tirent une tautologie de 2n2^n termes.

Objectifs d’apprentissage

  1. Écrire des conjonctions et des disjonctions de nn termes avec la notation ⋀\bigwedge et ⋁\bigvee, les déplier en chaînes associées à gauche et calculer leur valeur de vérité avec le lemme de la valeur.
  2. Démontrer par récurrence sur le nombre de termes l’associativité généralisée, l’indépendance de l’ordre et des répétitions et les lois de De Morgan généralisées, en distinguant à chaque pas l’identité de chaînes de l’équivalence sémantique.
  3. Démontrer la distributivité généralisée et sa duale en organisant la récurrence sur deux indices, et compter les termes que produit une distribution.
  4. Localiser l’erreur d’une démonstration par récurrence dont l’initialisation est mal écrite ou dont l’hérédité cache un regroupement, et la réparer.

Des lois pour un nombre quelconque de termes

La leçon sur la conséquence et l’équivalence sémantiques a établi les lois d’équivalence pour deux termes : parmi elles, la commutativité et l’associativité de ∧\wedge et de ∨\vee, les lois de De Morgan et les deux distributivités. Or une formule en forme normale disjonctive est une disjonction de conjonctions, chacune avec autant de termes qu’il le faut, et transformer une formule en cette forme exige de nier, de regrouper et de distribuer des conjonctions et des disjonctions de longueur quelconque. S’il en est ainsi, les lois binaires ne suffisent pas telles quelles : il faut les étendre à nn termes, et le faire une fois pour toutes pour tous les nn.

Pour chaque nn fixé, la loi de De Morgan à nn termes pourrait se vérifier par une table de vérité de 2n2^n lignes, écrite avec nn variables, et la substitution uniforme de la leçon précédente, appliquée à la double implication entre les deux membres, l’étendrait à des formules quelconques. Mais il y a une infinité de valeurs de nn, et aucune quantité de tables ne les épuise. Il s’ensuit que l’affirmation « pour tout nn » n’est pas une équivalence entre deux formules, mais un énoncé sur une infinité d’équivalences, formulé dans le métalangage ; sa démonstration est, comme celles de la leçon sur la récurrence sur les entiers et l’induction sur les formules, une démonstration externe, et son instrument est la récurrence sur le nombre de termes. La notation ⋀i=1nφi\bigwedge_{i=1}^{n} \varphi_i appartient elle aussi au métalangage : ce n’est pas un nouveau symbole de la langue, mais un nom pour une chaîne de cercles et de disques, de même que (φ∧ψ)(\varphi \wedge \psi) en est un.

Il convient de fixer dès maintenant trois relations qu’il ne faut pas confondre. L’égalité α=β\alpha = \beta dit que α\alpha et β\beta sont la même chaîne ; les définitions, qui s’écrivent avec :=:=, introduisent des noms pour des chaînes, et ce que l’on obtient en dépliant une définition est égal, et non simplement équivalent. L’équivalence sémantique α≡β\alpha \eqsem \beta dit que v(α)=v(β)v(\alpha) = v(\beta) pour toute valuation vv. L’équivalence prouvable α⊣⊢β\alpha \dashv\vdash \beta de l’unité de déduction dit que chacune se déduit de l’autre. Cette leçon travaille avec les deux premières ; la troisième n’apparaît que dans un commentaire.

Ce qui est utilisé

De la leçon sur la sémantique de la logique propositionnelle, on reprend les valuations, fonctions des variables v1,v2,…v_1, v_2, \ldots dans {0,1}\{0, 1\}, et leur prolongement à toutes les formules, qui s’écrit avec la même lettre vv ; la valeur des connecteurs dérivés, calculée à partir des abréviations officielles : v(¬φ)=1−v(φ)v(\neg\varphi) = 1 - v(\varphi), v((φ∧ψ))=v(φ) v(ψ)v((\varphi \wedge \psi)) = v(\varphi)\,v(\psi), de sorte que la conjonction vaut 11 si et seulement si ses deux composantes valent 11, et v((φ∨ψ))=1v((\varphi \vee \psi)) = 1 si et seulement si v(φ)=1v(\varphi) = 1 ou v(ψ)=1v(\psi) = 1 ; le lemme de coïncidence (si deux valuations coïncident sur les variables d’une formule, elles coïncident sur la formule) ; et les formules ⊤\top et ⊥\bot, une tautologie et une antilogie fixées. De la leçon sur la conséquence et l’équivalence sémantiques, on reprend que ≡\eqsem est réflexive, symétrique et transitive, le théorème de remplacement sémantique et le catalogue des lois avec leurs noms : commutativité, (φ∧ψ)≡(ψ∧φ)(\varphi \wedge \psi) \eqsem (\psi \wedge \varphi) et (φ∨ψ)≡(ψ∨φ)(\varphi \vee \psi) \eqsem (\psi \vee \varphi) ; associativité, (φ∧(ψ∧χ))≡((φ∧ψ)∧χ)(\varphi \wedge (\psi \wedge \chi)) \eqsem ((\varphi \wedge \psi) \wedge \chi) et son analogue pour ∨\vee ; De Morgan, ¬(φ∧ψ)≡(¬φ∨¬ψ)\neg(\varphi \wedge \psi) \eqsem (\neg\varphi \vee \neg\psi) et ¬(φ∨ψ)≡(¬φ∧¬ψ)\neg(\varphi \vee \psi) \eqsem (\neg\varphi \wedge \neg\psi) ; distributivité, (φ∧(ψ∨χ))≡((φ∧ψ)∨(φ∧χ))(\varphi \wedge (\psi \vee \chi)) \eqsem ((\varphi \wedge \psi) \vee (\varphi \wedge \chi)) et (φ∨(ψ∧χ))≡((φ∨ψ)∧(φ∨χ))(\varphi \vee (\psi \wedge \chi)) \eqsem ((\varphi \vee \psi) \wedge (\varphi \vee \chi)) ; double négation, ¬¬φ≡φ\neg\neg\varphi \eqsem \varphi ; idempotence, (φ∨φ)≡φ(\varphi \vee \varphi) \eqsem \varphi ; identité, (φ∧⊤)≡φ(\varphi \wedge \top) \eqsem \varphi ; et tiers exclu, ⊨(φ∨¬φ)\models (\varphi \vee \neg\varphi). Les lois valent pour des formules quelconques φ\varphi, ψ\psi, χ\chi, qui sont des métavariables.

À chaque pas des démonstrations qui suivent, on remplace une partie d’une formule par une autre, équivalente. Le théorème de remplacement sémantique l’autorise pour une occurrence à la fois ; le lemme suivant, qui en est un cas particulier, le donne d’un coup pour les parties d’une négation, d’une conjonction ou d’une disjonction. Il faut remarquer que ce n’est pas une trivialité syntaxique : ¬α\neg\alpha est la chaîne (α↓α)(\alpha \downarrow \alpha), où α\alpha apparaît deux fois, et (α∧β)(\alpha \wedge \beta) contient donc huit occurrences de α\alpha et huit de β\beta.

LemmeCompatibilité des connecteurs avec l’équivalence

Si α≡α′\alpha \eqsem \alpha' et β≡β′\beta \eqsem \beta', alors ¬α≡¬α′\neg\alpha \eqsem \neg\alpha', (α∧β)≡(α′∧β′)(\alpha \wedge \beta) \eqsem (\alpha' \wedge \beta') et (α∨β)≡(α′∨β′)(\alpha \vee \beta) \eqsem (\alpha' \vee \beta').

Démonstration

  1. v(α)=v(α′),v(β)=v(β′)\dato{h}{v(\alpha) = v(\alpha'), \qquad v(\beta) = v(\beta')}

    Soit vv une valuation quelconque. Par hypothèse, α\alpha et α′\alpha' ont la même valeur, ainsi que β\beta et β′\beta'.

  2. v(¬α)=1−v(α)=1−v(α′)=v(¬α′),v((α∧β))=v(α) v(β)=v(α′) v(β′)=v((α′∧β′))v(\neg\alpha) = 1 - \resaltar{v(\alpha)} = 1 - \resaltar{v(\alpha')} = v(\neg\alpha'), \qquad v((\alpha \wedge \beta)) = \resaltar{v(\alpha)\,v(\beta)} = \resaltar{v(\alpha')\,v(\beta')} = v((\alpha' \wedge \beta'))

    La valeur d’une négation et celle d’une conjonction ne dépendent que des valeurs de leurs composantes.

  3. v((α∨β))=1  ⇔  v(α)+v(β)≥1  ⇔  v(α′)+v(β′)≥1  ⇔  v((α′∨β′))=1v((\alpha \vee \beta)) = 1 \;\Leftrightarrow\; v(\alpha) + v(\beta) \geq 1 \;\Leftrightarrow\; v(\alpha') + v(\beta') \geq 1 \;\Leftrightarrow\; v((\alpha' \vee \beta')) = 1

    Il en va de même pour la disjonction : elle vaut 11 si et seulement si une composante vaut 11, et les composantes ont les mêmes valeurs des deux côtés.

  4. ¬α≡¬α′,(α∧β)≡(α′∧β′),(α∨β)≡(α′∨β′)\neg\alpha \eqsem \neg\alpha', \qquad (\alpha \wedge \beta) \eqsem (\alpha' \wedge \beta'), \qquad (\alpha \vee \beta) \eqsem (\alpha' \vee \beta')

    Comme vv était quelconque, les trois équivalences sont vraies.