Dossier complet — Logique mathématique

L2 · S4 · Données et logique

Dossier pédagogique original Matrice MI. Contenu d’entraînement non officiel; il ne remplace pas le support ou la maquette d’un établissement.

Objectifs d’apprentissage

• Évaluer, transformer et comparer des formules de logique propositionnelle à l’aide de tables de vérité et d’équivalences.

• Formaliser des énoncés en prédicats en explicitant domaines, variables libres et ordre des quantificateurs.

• Choisir et rédiger une preuve directe, par contraposée, contradiction ou récurrence avec des justifications complètes.

• Construire des formes normales et identifier validité, satisfaisabilité, contre-exemple et conséquence logique.

• Spécifier un programme par précondition, postcondition et invariant, puis argumenter sa correction partielle.

Prérequis

• Maîtriser les ensembles, les fonctions élémentaires et les opérations sur les entiers.

• Savoir lire une notation mathématique avec variables, égalités, inégalités et sommes finies.

• Avoir une première expérience de lecture de pseudo-code, de boucles et de tests simples.

Cours

1. Logique propositionnelle

Définitions et méthode

Une proposition est un énoncé auquel on peut attribuer exactement une valeur de vérité : vrai ou faux. Les connecteurs ¬, ∧, ∨, ⇒ et ⇔ construisent des propositions composées. Une formule est valide si elle est vraie pour toute valuation, et satisfaisable si elle est vraie pour au moins une valuation. La table de vérité est sûre, mais devient vite longue ; on peut donc utiliser les équivalences usuelles, notamment $P\implies Q\equiv\neg P\lor Q$ et les lois de De Morgan.

Exemple guidé

Simplifions $\neg(P\lor\neg Q)\lor P$. De Morgan donne $(\neg P\land Q)\lor P$. La distributivité donne $(P\lor\neg P)\land(P\lor Q)$, donc $P\lor Q$. Une valuation avec $P=F,Q=F$ montre que la formule n’est pas une tautologie. Erreur fréquente : confondre implication et réciproque ; $P\implies Q$ n’autorise pas $Q\implies P$.

Point de contrôle : vérifier par quatre lignes que $P\lor Q$ et la formule initiale ont les mêmes valeurs.

Points-clés

• Distinguer proposition, validité et satisfaisabilité.
• Transformer une implication en disjonction.
• Contrôler une équivalence par table de vérité.

2. Prédicats et quantificateurs

Du langage aux prédicats

Un prédicat $P(x)$ devient une proposition quand $x$ reçoit une valeur. Il faut toujours préciser le domaine : entiers, réels ou objets d’un programme. Les quantificateurs s’écrivent $\forall x\in E$ (« pour tout ») et $\exists x\in E$ (« il existe »). La négation se pousse jusqu’au prédicat : $\neg\forall x\,P(x)\equiv\exists x\,\neg P(x)$ et $\neg\exists x\,P(x)\equiv\forall x\,\neg P(x)$.

Exemple guidé

Nions : « pour tout entier $n$, il existe un entier $m$ tel que $m>n$ ». On obtient « il existe un entier $n$ tel que, pour tout entier $m$, $m\le n$ ». Cette négation est fausse dans $\mathbb Z$, car pour tout $n$, $n+1>n$. L’ordre est décisif : $\forall x\exists y\,P(x,y)$ ne signifie pas qu’un même $y$ convient à tous les $x$. Une erreur fréquente consiste à oublier la restriction de domaine.

Point de contrôle : donner un témoin explicite pour réfuter une proposition existentielle négative et indiquer son domaine.

Points-clés

• Préciser le domaine de chaque variable.
• Nier en inversant les quantificateurs.
• Respecter l’ordre de dépendance des témoins.

3. Preuves et invariants

Normaliser une formule

Une forme normale conjonctive (FNC) est une conjonction de disjonctions de littéraux ; une forme normale disjonctive (FND) est une disjonction de conjonctions. On élimine d’abord $⇒$ et $⇔$, puis on pousse les négations avec De Morgan. La distributivité permet ensuite d’obtenir la forme demandée. Pour une formule propositionnelle, une table de vérité fournit une FND en prenant les lignes vraies, ou une FNC en prenant les lignes fausses.

Exemple guidé

Pour $P⇒(Q∧R)$, on remplace l’implication : $\neg P\lor(Q\land R)$. La distributivité donne $(\neg P\lor Q)\land(\neg P\lor R)$ : c’est une FNC. Une formule en FNC n’est pas nécessairement minimale ; supprimer un littéral sans preuve peut changer sa valeur. En informatique, cette distinction compte pour la satisfaisabilité et la génération de tests.

Point de contrôle : vérifier chaque clause sur la valuation $P=V,Q=F,R=V$, puis comparer avec la formule de départ.

Points-clés

• Éliminer implication et biconditionnelle.
• Appliquer De Morgan et distributivité.
• Distinguer forme normale et forme minimale.

4. Techniques de preuve

Choisir une stratégie

Une preuve directe part des hypothèses et enchaîne des implications valides. La contraposée remplace $P\implies Q$ par $\neg Q\implies\neg P$. La contradiction suppose la conclusion fausse puis obtient une impossibilité. Pour une propriété indexée par $n$, la récurrence comporte une initialisation, une hypothèse au rang $n$ et une hérédité vers $n+1$.

Exemple guidé

Prouvons par contraposée : si $n^2$ est pair, alors $n$ est pair. La contraposée est « si $n$ est impair, alors $n^2$ est impair ». Écrivons $n=2k+1$ ; alors $n^2=4k^2+4k+1=2(2k^2+2k)+1$, donc il est impair. La preuve est complète. Ne pas invoquer « l’évidence » d’une implication, ni utiliser une hypothèse plus forte que celle annoncée.

Point de contrôle : dans une preuve par récurrence, identifier séparément la propriété initiale et la propriété héréditaire avant tout calcul.

Points-clés

• Choisir une stratégie de preuve adaptée.
• Rédiger base et hérédité en récurrence.
• Éviter les arguments intuitifs non justifiés.

5. Invariants et spécification de programmes

Relier logique et programme

Une spécification décrit les états autorisés avant et après une commande. La notation de Hoare $\{P\}\ C\ \{Q\}$ signifie que si $P$ est vraie avant C et si C termine, alors $Q$ est vraie après ; c’est une correction partielle. Un invariant de boucle reste vrai après chaque itération. Pour prouver un résultat, il faut montrer initialisation, conservation et suffisance de l’invariant à la sortie.

Exemple guidé

Pour somme = 0; i = 0; while i < n: somme += a[i]; i += 1, avec $n\ge0$, prenons $I:0\le i\le n\land somme=\sum_{k=0}^{i-1}a[k]$. Initialement, la somme vide vaut $0$. Si $i<n$, l’ajout de $a[i]$ et l’incrément conservent $I$. À la sortie, $i=n$, donc somme est la somme voulue. Oublier la terminaison ou l’indexation des tableaux est une erreur fréquente.

Point de contrôle : proposer une variante de boucle et vérifier que son invariant implique bien la postcondition.

Points-clés

• Définir un invariant sur un préfixe.
• Prouver initialisation et conservation.
• Relier sortie de boucle et postcondition.

Exercices corrigés

Exercice 1 · Fondamental

Construire la table de vérité de $F=(P\implies Q)\land P$ et déterminer si $F$ est équivalente à $P\land Q$.

Correction détaillée

On examine les quatre valuations. Pour $(P,Q)=(F,F)$, l’implication est vraie mais $F$ vaut faux. Pour $(F,V)$, l’implication est vraie et $F$ vaut faux. Pour $(V,F)$, l’implication est fausse et $F$ vaut faux. Pour $(V,V)$, l’implication est vraie et $F$ vaut vrai. La colonne de $P\land Q$ vaut respectivement faux, faux, faux, vrai. Les colonnes coïncident : $((P\implies Q)\land P)\equiv(P\land Q)$.

Exercice 2 · Fondamental

Nier correctement l’énoncé : « Pour tout réel $x$, il existe un réel $y$ tel que $y^2>x$ », puis décider si l’énoncé initial est vrai.

Correction détaillée

La négation est $\exists x\in\mathbb R,\forall y\in\mathbb R,\ y^2\le x$. Pour tester l’énoncé initial, fixons un réel $x$. Choisissons $y=|x|+1$. Alors $y^2=(|x|+1)^2>|x|\ge x$. Un témoin existe pour chaque $x$ ; l’énoncé initial est donc vrai. Attention : le témoin $y$ dépend de $x$, ce qui est autorisé par $\forall x\exists y$.

Exercice 3 · Intermédiaire

Mettre en FNC la formule $G=(P\lor Q)\implies(\neg P\land R)$, puis donner une valuation qui la rend fausse.

Correction détaillée

On élimine l’implication : $G=\neg(P\lor Q)\lor(\neg P\land R)$. De Morgan donne $(\neg P\land\neg Q)\lor(\neg P\land R)$. On factorise $\neg P$ : $\neg P\land(\neg Q\lor R)$. C’est déjà une FNC, car elle se lit comme la clause unitaire $(\neg P)$ et la clause $(\neg Q\lor R)$. Pour la rendre fausse, prendre $P=V$ ; la première clause est alors fausse, par exemple avec $Q=F,R=V$.

Exercice 4 · Intermédiaire

Prouver par récurrence que, pour tout entier $n\ge1$, $1+3+5+\cdots+(2n-1)=n^2$.

Correction détaillée

Initialisation : pour $n=1$, le membre gauche vaut $1=1^2$. Hérédité : supposons la formule vraie au rang $n$, donc la somme vaut $n^2$. Au rang $n+1$, on ajoute le terme $2(n+1)-1=2n+1$ : la somme vaut $n^2+2n+1=(n+1)^2$. La propriété est donc héréditaire. Par le principe de récurrence, elle est vraie pour tout $n\ge1$. Il faut bien ajouter le prochain terme impair, et non $2n+2$.

Exercice 5 · Avancé

Spécifier et prouver la correction de la boucle suivante pour un tableau a de longueur $n\ge0$ : i=0; m=0; while i<n: if a[i]>m: m=a[i]; i=i+1. La postcondition visée est « $m$ est le maximum de a ».

Correction détaillée

L’énoncé est faux tel quel si le tableau contient seulement des valeurs négatives, car l’initialisation $m=0$ n’est pas un élément du tableau. Un invariant adapté après $i$ itérations serait $0\le i\le n$ et $m=\max(0,a[0],\ldots,a[i-1])$ ; il prouve seulement un maximum tronqué par zéro. Contre-exemple : $n=1,a[0]=-4$ donne $m=0$, pas $-4$. Correction : pour $n>0$, initialiser m=a[0]; i=1. L’invariant devient $1\le i\le n$ et $m=\max(a[0],\ldots,a[i-1])$. Il est vrai à l’initialisation, conservé par la comparaison, et à la sortie $i=n$ il implique la postcondition. Séparer le cas $n=0$ (erreur ou résultat optionnel) rend la spécification complète.

Quiz d’autoévaluation

Question 1

Quelle formule est une tautologie ?

• $P\land\neg P$ ✓ $P\lor\neg P$ • $P\implies\neg P$ • $P\land Q$

Explication : Pour toute valuation, soit $P$ est vraie, soit $P$ est fausse ; $P\lor\neg P$ vaut donc toujours vrai.

Question 2

Quelle est la négation de $\forall x\,P(x)$ ?

• $\forall x\,\neg P(x)$ • $\exists x\,P(x)$ ✓ $\exists x\,\neg P(x)$ • $\neg\exists x\,\neg P(x)$

Explication : Nier « tous » revient à trouver au moins un contre-exemple : $\neg\forall x P(x)\equiv\exists x\neg P(x)$.

Question 3

Laquelle est équivalente à $P\implies Q$ ?

• $P\land Q$ ✓ $\neg P\lor Q$ • $P\lor\neg Q$ • $\neg P\land Q$

Explication : Une implication est fausse uniquement quand $P$ est vraie et $Q$ fausse, exactement comme $\neg P\lor Q$.

Question 4

Que faut-il pour une preuve par récurrence ?

• Une seule vérification numérique ✓ Une base et une hérédité • Une table de vérité • Un contre-exemple

Explication : Il faut établir la propriété au premier rang puis montrer que sa vérité au rang $n$ entraîne celle au rang suivant.

Question 5

Une FNC est…

• Une disjonction de conjonctions ✓ Une conjonction de disjonctions • Une négation de quantificateurs • Une liste de témoins

Explication : La forme normale conjonctive est un ET de clauses, chaque clause étant un OU de littéraux.

Question 6

Dans $\forall x\exists y\,P(x,y)$, que peut-on dire de $y$ ?

• Il est forcément unique ✓ Il peut dépendre de $x$ • Il est choisi avant $x$ • Il n’existe jamais

Explication : Le quantificateur existentiel est à l’intérieur de celui sur $x$ : un témoin peut être choisi différemment pour chaque $x$.

Question 7

Quelle étape ne fait pas partie de la preuve standard d’un invariant ?

• Initialisation • Conservation • Conclusion à la sortie ✓ Changer arbitrairement le domaine

Explication : On montre que l’invariant est vrai au départ, conservé par l’itération, puis utile lorsque la condition de boucle est fausse.

Question 8

Quel énoncé décrit une implication fausse ?

• $P=F,Q=F$ • $P=F,Q=V$ ✓ $P=V,Q=F$ • $P=V,Q=V$

Explication : La seule ligne fausse de $P\implies Q$ est celle où l’hypothèse est vraie et la conclusion fausse.

Glossaire

• Proposition — Énoncé déclaratif auquel on attribue une valeur de vérité, vraie ou fausse.
• Tautologie — Formule propositionnelle vraie pour toute valuation de ses variables.
• Prédicat — Expression dépendant de variables, qui devient une proposition après affectation de valeurs.
• Quantificateur — Symbole indiquant l’étendue d’une variable, notamment pour tout ($\forall$) ou il existe ($\exists$).
• Contraposée — Forme $\neg Q\implies\neg P$ équivalente à $P\implies Q$.
• Forme normale conjonctive — Conjonction de clauses, chaque clause étant une disjonction de littéraux.
• Invariant — Propriété vraie avant et après chaque itération d’une boucle, utile pour prouver sa correction.
• Satisfaisabilité — Propriété d’une formule qui possède au moins une valuation la rendant vraie.

TP · Spécifier et vérifier un filtre de tâches

On dispose d’une liste de tâches, chacune ayant un identifiant entier et un indicateur terminee. On veut formaliser puis tester la fonction qui renvoie les identifiants des tâches non terminées, sans doublon et dans l’ordre d’apparition.

Objectifs

• Traduire des règles métier en prédicats quantifiés.

• Écrire une précondition, une postcondition et un invariant.

• Construire un contre-exemple à une implémentation incorrecte.

• Relier preuve informelle et tests exécutables.

Étapes

1. Définir les prédicats EstTache, IdentifiantValide et NonTerminee, puis préciser le domaine.

2. Écrire la postcondition avec une équivalence : un identifiant apparaît en sortie si et seulement si une tâche correspondante non terminée apparaît en entrée.

3. Proposer l’invariant d’un parcours préfixe et justifier son initialisation et sa conservation.

4. Tester au moins les cas vide, toutes terminées, identifiants répétés et mélange terminé/non terminé.

5. Rédiger un contre-exemple pour une version qui oublie les doublons, puis corriger cette version.

Livrables attendus

• Une page de spécification avec précondition, postcondition et définitions.

• Un tableau de traces contenant quatre jeux de données et les résultats attendus.

• Une courte preuve de l’invariant et un test de non-régression.

Critères d’évaluation

• Les prédicats et domaines sont non ambigus et couvrent les cas limites.

• La postcondition distingue présence, ordre et absence de doublon.

• L’invariant est initialisé, conservé et exploité à la sortie.

• Les quatre jeux de tests donnent des résultats vérifiables et justifiés.

Piste de résolution

Parcourir la liste avec un ensemble vus et une sortie vide. L’invariant affirme que la sortie contient exactement, dans le même ordre, les identifiants distincts non terminés du préfixe déjà parcouru, et que vus est l’ensemble de ses identifiants. À chaque tâche, l’ajout conditionnel conserve l’invariant. À la fin, le préfixe est la liste entière ; la postcondition suit. Le cas vide satisfait la postcondition par vacuité.

Sujets originaux d’entraînement (non officiels)

Sujet original de préparation — logique mathématique

Sujet original d’entraînement non officiel; il ne provient pas d’une session d’examen antérieure. Ce sujet est une création pédagogique originale et non officielle. Il ne s’agit jamais d’une épreuve d’une année passée ni d’une annale.

Exercice 1

Montrer que $(P\implies Q)\land(Q\implies R)$ implique $P\implies R$, avec une preuve par cas ou par équivalences.

Correction : Supposons l’antécédent vrai et $P$ vraie. La première implication donne $Q$, puis la seconde donne $R$. Ainsi $P\implies R$. Comme l’antécédent et la valuation étaient arbitraires, l’implication composée est valide. On peut aussi remplacer chaque implication par une disjonction et vérifier les cas où $P$ est vraie.

Exercice 2

Nier puis analyser : $\forall n\in\mathbb N,\exists k\in\mathbb N, k>n\land k\text{ est pair}$.

Correction : La négation est $\exists n\in\mathbb N,\forall k\in\mathbb N,\ k\le n\lor k\text{ est impair}$. L’énoncé initial est vrai : pour un $n$ donné, choisir un entier pair strictement supérieur, par exemple le plus petit entier pair au moins égal à $n+1$. Le témoin dépend de $n$ ; c’est précisément l’effet de l’ordre des quantificateurs.

Exercice 3

Pour i=0; s=0; while i<n: s=s+a[i]; i=i+1, proposer un invariant et prouver la postcondition pour $n\ge0$.

Correction : L’invariant est $0\le i\le n$ et $s=\sum_{j=0}^{i-1}a[j]$. Il est vrai au départ car la somme vide vaut zéro. Si $i<n$, l’ajout de $a[i]$ donne la somme jusqu’à $i$, puis l’incrément établit l’invariant au rang suivant. À la sortie, $i=n$ ; la postcondition $s=\sum_{j=0}^{n-1}a[j]$ est obtenue.

Sujet original de préparation — seconde session

Sujet original d’entraînement non officiel; il ne provient pas d’une session d’examen antérieure. Ce sujet est une création pédagogique originale et non officielle. Il ne s’agit jamais d’une épreuve d’une année passée ni d’une annale.

Exercice 1

Donner une FND de $H=(P\land Q)\lor(\neg P\land R)$ et expliquer pourquoi elle est déjà sous forme normale.

Correction : Une FND est une disjonction de termes, chaque terme étant une conjonction de littéraux. Ici, $H$ est exactement la disjonction des termes $(P\land Q)$ et $(\neg P\land R)$. Aucune transformation n’est nécessaire. Elle décrit deux familles de valuations qui rendent $H$ vraie.

Exercice 2

Prouver par contradiction que $\sqrt 2$ est irrationnel.

Correction : Supposons $\sqrt2=a/b$ avec $a,b$ entiers, $b\ne0$, fraction irréductible. Alors $a^2=2b^2$, donc $a^2$ est pair et $a$ est pair ; écrire $a=2c$. On obtient $4c^2=2b^2$, donc $b^2=2c^2$ et $b$ est pair. Alors $a$ et $b$ sont tous deux pairs, contradiction avec l’irréductibilité. Donc $\sqrt2$ est irrationnel.

Exercice 3

Une boucle cherche le premier élément positif d’un tableau. Définir une postcondition et un invariant de parcours avant de traiter la terminaison.

Correction : Pour un tableau a de longueur $n$, la postcondition peut être : soit l’indice retourné est None et $\forall j<n, a[j]\le0$, soit il vaut $r<n$, $a[r]>0$ et $\forall j<r, a[j]\le0$. Avant de trouver un positif, l’invariant est $0\le i\le n$ et tous les indices strictement inférieurs à $i$ ont une valeur non positive. L’initialisation est vide ; avancer sur une valeur non positive conserve l’invariant. À l’arrêt, la condition de sortie distingue le témoin trouvé du parcours complet.

Parcours de révision sur quatre semaines

Semaine 1 · Propositions et connecteurs

Construire des tables de vérité, mémoriser les équivalences de De Morgan et résoudre les exercices 1 puis 2. Avant de terminer, reformule les notions sans tes notes, vérifie les résultats dans le cours et note une difficulté précise à reprendre la semaine suivante.

Semaine 2 · Prédicats et quantificateurs

Formaliser dix phrases, nier chacune et vérifier les témoins ou contre-exemples sur des domaines précisés. Avant de terminer, reformule les notions sans tes notes, vérifie les résultats dans le cours et note une difficulté précise à reprendre la semaine suivante.

Semaine 3 · Preuves et formes normales

Rédiger une preuve par contraposée et une par récurrence, puis normaliser trois formules en FNC ou FND. Avant de terminer, reformule les notions sans tes notes, vérifie les résultats dans le cours et note une difficulté précise à reprendre la semaine suivante.

Semaine 4 · Invariants et synthèse

Réaliser le TP, corriger l’exercice avancé, refaire le quiz sans notes et rédiger une fiche de méthodes. Avant de terminer, reformule les notions sans tes notes, vérifie les résultats dans le cours et note une difficulté précise à reprendre la semaine suivante.