Exercices Corrigés

Logique

Théorie de la preuve (du calcul des propositions)

Rappel: Un système de preuve pour le calcul propositionnel est constitué par un ensemble (éventuellement infini) de formules dites axiomes et par un ensemble fini de règles d’inférence qui établissent le façons admissibles de dériver des formules vraies à partir d’autres formules vraie.

Pour toutes formules on note si est démontrable uniquement à partir des axiomes en utilisant les règles d’inférence. On note si est démontrable en ajoutant et aux axiomes et en utilisant les règles d’inférence.

Dans la suite nous allons prendre la liste (infinie) d’axiomes suivante:

  1. ,
  2. ,
  3. ,
  4. ,
  5. .
  6. ,

sont des formules quelconques (par exemple , ou , etc.). La seule règle d’inférence de notre système est le modus ponens:

qui veut dire qu’à chaque fois qu’on a les formules et , on peut déduire .

Les axiomes 1-3 sont dus à Łukasiewicz, les autres sont redondants (dans le sens qu’ils pourraient être dérivés des trois premiers), mais nous les ajoutons pour simplifier les preuves.

Question 1 Prouver que .

Question 2 Prouver que .

Question 3 Prouver le raisonnement par contrapposée: .

Question 4 On va montrer de d’une proposition fausse on peut déduire n’importe quoi. Nous choisissons comme proposition fausse.

  1. Calculez sa table de vérité et vérifiez qu’elle est bien une antilogie.
  2. Dans notre logique nous avons fait le choix d’utiliser seulement les symboles et . En utilisant les équivalences bien connues, transformez en une formule équivalente qui n’utilise que et . Vérifiez que les deux formules sont bien équivalentes à l’aide des tables de vérité.
  3. Montrez que .

Question 5 Très difficile: montrez que l’axiome 6 peut être déduit des axiomes 1 et 3.

Solution

Dans les séquents qui suivent, on prend la convention de marquer une barre au dessus des hypothèses pour les distinguer des axiomes.

Question 1 Du premier axiome: . En utilisant l’hypothèse et le modus ponens:

Question 2 En appliquant les axiomes 1 et 2 et deux fois le modus ponens:

Question 3 En appliquant l’axiome 6 et deux fois le modus ponens:

Question 4 On vérifie aisement que est une antilogie, ensuite on voit rapidement qu’une formule équivalente possible est:

Pour faire la preuve formelle, l’astuce consiste à instancier l’Axiome 1 en prenant et , cela donne

Le reste suit aisement en invoquant les axiomes 2 et 5 et trois fois le modus ponens:

Question 5 On va prouver que découle des axiomes 1 et 3. L’énoncé général suit immédiatement en remplaçant par une formule quelconque.

Il faut un bon coup d’intuition pour résoudre ce problème: l’astuce consiste à instancier l’axiome 3 de la façon suivante (en prenant )

Le reste de la preuve nécessite seulement de deux utilisations (presque évidentes) de l’axiome 1

Partiel 2010

Métro

Considérons le plan de métro de Paris. Soit l’ensemble des stations de métro.

  1. Soit la relation sur suivante: Soit et deux stations de métro, on a si et seulement si et sont sur la même ligne. Quelles sont les propriétés de ?
  2. Sot la relation sur suivante: Soit et deux stations de métro, on a si et seulement si un passager peut aller de vers en métro. Quelles sont les propriétés de ?

Solution

  1. La relation est réflexive et symétrique. En effet est sur la même ligne que lui même, si est sur la même ligne que alors est sur la même ligne que . La relation n’est pas transitive: en effet Cité et Raspail sont sur la ligne 4, Raspail et Picpus sont sur la ligne 6, mais Cité et Picpus ne sont pas sur la même ligne.
  2. Il s’agit d’une équivalence. En effet la réflexivité et la transitivité sont claires. La symétrie est moins claire (pensez à la ligne 10 qui fait une boucle vers la fin), mais on constate tout de même que si on ne peut pas prendre le métro en sens inverse, on peut au pire faire une boucle pour revenir à la station de départ.

Monnaie

Nous considérons des pièces de monnaie de 1, 2, 5 centimes. Notons le nombre minimum de pièces pour obtenir centimes.

  1. Quelle est la valeur de ?
  2. Trouver la relation sous forme mathématique de en fonction des valeurs avec .
  3. Prouver cette formule par induction/récurrence sur .

Solution

  1. , , .
  2. J’affirme que pour tout .
  3. Soient . Très clairement en ajoutant respectivement 1, 2, ou 5 centimes on obtient une façon de composer centimes en utilisant , et pièces respectivement. Donc . Supposons maintenant que . Nécessairement , puisque . Supposons, sans perte de généralité, que dans les pièces pour obtenir il y en ait au moins une de centime, alors en ôtant cette pièce on a une façon d’obtenir centimes en utilisant seulement pièces, ce qui contredit l’hypothèse que . On conclut que .

Récurrence

Considérons la suite telle que et . Montrer que

en fixant les variables et .

Solution

On commence par calculer quelques termes de la récurrence.

On dirait que la valeur de grandit à peu près comme le double de . Si on regarde bien, on s’aperçoit que . Une possibilité consiste à faire le pari que cette égalité est bonne et à essayer de la prouver par récurrence.

Nous allons procéder d’une façon différente en faisant une induction à reculons. Nous allons laisser les valeurs de et indeterminées et nous allons quand même faire la preuve, en commençant par le cas inductif. Ceci va nous permettre de trouver des contraintes sur et sur . Ensuite nous allons travailler le cas de base pour résoudre les indeterminées qui restent.

Supposons , alors

Donc pour que on a nécessairement . Choisissons la valeur limite et recommençons la preuve. Supposons , alors

Tout va bien, donc, il ne nous reste qu’à trouver un qui fait marcher le cas de base. On a

d’où on déduit , donc on peut prendre . On vérifie que l’inégalité est en fait une égalité.

Fonctions

Soit deux ensembles finis. Soit une application. Montrer que

  1. Si est surjective et si est un sous ensemble de , alors
  2. Si est injective et si est un sous ensemble de , alors

Supposons que sont deux ensembles finis de même cardinalité. Montrer que

  1. Si est injective alors est surjective.
  2. Si est surjective alors est injective.

Solution

Pour l’instant nous n’avons pas besoin de l’hypothèse que et sont finis.

  1. Soit . Puisque est surjective il existe tel que . Mais alors et donc . Inversement soit , alors par définition il existe tel que . Mais alors par définition de il existe tel que , donc puisque ne peut prendre deux valeurs en . On conclut que .
  2. Soit et soit , alors , du coup . Soit , par définition il existe tel que . Mais implique qu’il existe tel que . Comme est injective et .

Maintenant il devient important d’utiliser la finitude de et .

  1. Soit la cardinalité de . Puisque est injective, à chaque élément de correspond un unique élément de . Donc l’image de a cardinalité et correspond à tout entier.
  2. Supposons que ne soit pas injective, alors il existe tels que . On considère l’ensemble de cardinalité , son image par a cardinalité au plus . Donc l’image de tout entier par a cardinalité au plus ( de , plus de ), ce qui contredit la surjectivité.

Encore des fonctions

Existe-t-il

  1. Une application non-surjective et non-injective.
  2. Une application non-surjective et injective.
  3. Une application surjective et non-injective.

Solution

Oui, elles existent toutes. Une façon simple d’en montrer des exemples c’est de dessiner des diagrammes de Venn finis (des ensembles avec un ou deux éléments suffisent). Nous allons donner des exemples un peu plus intéressants de fonctions de dans lui même:

  1. Le sinus et le cosinus.
  2. L’arc tangente.
  3. La fonction .

Équivalence binaire

Soit un entier. l’ensemble des entiers compris entre et . Soit une relation d’équivalence définie de la façon suivante: on a si et seulement si le nombre de bits de la représentation binaire de est égal au nombre de bits de la représentation binaire de .

Solution

est une relation d’équivalence par hypothèse: c’est écrit dans la définition. Blagues à part, vérifions que c’est bien le cas:

Partiel Novembre 2011

Changements de base

Effectuer les changements de base suivants

  1. en décimal, en binaire.
  2. en binaire, puis en base 8.
  3. en héxadécimal

Solution

  1. , ce qui se vérifie par un simple calcul. ; multiplier par une puissance de revient à ajouter des à droite, donc ; maintenant il est aisé de faire la somme directement en base , le résultat est .
  2. Un chiffre en base correspond à chiffres en base . On convertit chaque chiffre et on a . Donc (j’ajoute les points pour aider la lisibilité). Maintenant on regroupe les bits par paquets de 3 et on convertit vers la base . On a , donc .
  3. , donc .

Induction, pair-impair

Prouver par induction que pour tout et tout entier

Solution

Il y a plusieurs façons de poser l’induction. Nous allons choisir celle qui utilise le moins de cas de base possibles.

Cas de base: , donc la thèse est bien vérifiée car est pair.

Cas inductif: Supposons la thèse vraie pour un certain pair, alors est impair et , où la deuxième égalité découle de l’induction.

De la même façon, supposons la thèse vraie pour un certain impair, alors est pair et .

Par induction, nous concluons que la thèse est vraie pour tout .

Inductions

Prouver par induction les (in)égalités suivantes

  1. .
  2. pour tout .
  3. pour tout .

Solution du point 1

Vérifions la thèse pour .

Maintenant supposons la thèse vraie pour un certain , alors

On conclut par induction.

Solution du point 2

Vérifions la thèse pour .

Maintenant supposons la thèse vraie pour un certain , alors

où l’on fait bien attention à vérifier que pour tout .

Solution du point 3

Il y a plusieurs solutions raisonnables pour cet exercice, nous allons en choisir une qui utilise une double induction. Pour cela nous allons avoir besoin de montrer quelques cas de base en plus (la raison sera claire plus loin).

Pour on a

Maintenant supposons l’hypothèse vraie pour un , alors

où l’inégalité découle de l’hypothèse d’induction. Si l’on arrive à montrer que , alors on a fini car on déduit

Pour démontrer , on s’y prend à nouveau par induction. Ceci est faux pour et (voici pourquoi on a démontré quelques cas de base en plus), mais à partir de on a

Maintenant on suppose vrai pour un certain , alors

On conclut par induction.

Ensemble des parties et bits

On fixe un quelconque. Soit l’ensemble des chaînes de bits de longueur (par exemple est un élément de ).

Pour chaque on définit la fonction comme suit

Par exemple, .

Soit la relation sur définie par si et seulement si pour tout , .

Solution

est l’ensemble des chaînes composées d’exactement bits. Par exemple on a

Il est alors facile de voir que , en effet on a deux choix pour chaque bit et il faut faire au total choix.

L’argument ci-dessus suffit en général à convaincre un mathématicien, mais si on voulait être formels jusqu’à la moelle on pourrait montrer par induction: les cas de base sont déjà donnés en haut, pour le cas inductif on observe que le premier bit peut être fixé à soit à soit à , et que les autres bits forment une chaîne de bits, alors , où la deuxième égalité découle de l’hypothèse d’induction.

Maintenant la fonction associe à une chaîne quelconque de la valeur de son -ième bit, donc l’image inverse est l’ensemble de toutes les chaînes de ayant le -ème bit à . Fixons et étudions, par exemple, , on a

Il s’agit, en effet, de l’ensemble des chaînes de longueur auxquelles on a ajouté tout à droite un bit égal à . Il est maintenant clair que pour on a toujours la même structure: toutes les chaînes de auxquelles on a ajouté un en position ou . Donc pour .

Pour il n’existe aucune fonction (car par définition ). Pour , la fonction est la fonction définie par et , donc elle est injective et surjective (et donc, par définition, bijective). Pour les fonctions ne sont plus injectives, par exemple , par contre elles sont toutes surjectives, en effet pour chaque position il y aura toujours une chaîne qui a un ou un en cette position.

La relation est un ordre partiel (non total). En effet, elle est:

En conclusion, voici le diagramme de Hasse de :

En fait, tout l’exercice tourne autour d’un isomorphisme bien connu et souvent utilisé en informatique entre l’ensemble et l’ensemble des parties d’un ensemble quelconque à élèments. On rappelle que l’ensemble est l’ensemble de tous les sous-ensembles de . L’idée consiste à représenter un sous-ensemble par une chaîne qui contient un pour chaque élément de présent dans et un pour chaque élément de qui n’est pas dans ; ceci nécessite de choisir un ordre arbitraire sur les éléments de (ce qui est aisé puisque est fini).

Par exemple, pour , soit . On écrit les éléments de en ordre décroissant (il s’agit juste d’une convention, on aurait aussi bien pu choisir l’ordre croissant ou tout autre ordre non-standard) comme ci-dessous

alors la chaîne représente le sous-ensemble , la chaîne représente l’ensemble vide, la chaîne représente tout entier, et ainsi de suite.

Grace à cet isomorphisme, qu’on va noter , on peut reinterpréter et en termes d’opérations ensemblistes. En effet,

Pour terminer, on remarque tout de même que, comme et ont la même cardinalité (à savoir éléments), il aurait été aussi aisé de donner une bijection quelconque en donnant la liste des couples élément-image, sans besoin de comprendre la théorie qu’il y avait derrière.

Encore des bits

Soit l’ensemble de toutes les chaînes de bits de longueur arbitraire.

Pour tout , on définit la fonction qui associe à un mot la valeur de son -ème bit en partant de la droite, ou si a moins de bits. Par exemple .

On définit enfin la fonction qui associe à un mot son \textit{poids de Hamming}, c’est à dire son nombre de . Par exemple .

Les relations suivantes sont-elles réflexives? symétriques? transitives?

Justifiez vos réponses.

On note la classe d’équivalence de pour la relation donnée au point précédent. Soit l’ensemble des chaînes de longueur .

Solution

est évidemment un ensemble infini. Comme la question le suggère, il est dénombrable car il est en bijection avec les nombres naturels. On pourrait être tenté de définir la bijection tout simplement en lisant les éléments de comme des nombres en base , cependant ce choix n’est pas adapté car et sont deux éléments distingués de , mais il représentent le même nombre en base .

Une astuce possible consiste à rajouter un à gauche des éléments de et ensuite à lire le résultat comme l’écriture en base d’un nombre. Par exemple:

Or, il est facile de se convaincre que cette fonction est bien injective, mais il est aussi évident qu’elle n’est pas surjective car n’a pas d’antécédent. Heureusement il est facile de résoudre ce problème: il suffit de soustraire au résultat et on a bien une bijection.

Le poids d’Hamming d’une chaîne n’est évidemment pas une fonction injective, en effet . Elle est par contre bijective car pour tout entier on peut trouver une chaîne de caractères contenant bits égaux à (on peut prendre, par exemple, l’écriture de en base ).

L’image réciproque est constitué de tous les mots contenant exactement bits égaux à . Cet ensemble est évidemment infini, mais son intersection avec est bien évidemment vide car aucun mot peut contenir à la fois exactement et bits à . Donc .

La relation n’est ni réflexive, ni symétrique ni transitive. En effet

La relation n’est ni symétrique, ni transitive. En effet

Par contre elle est évidemment réflexive car pour tout on a en choisissant .

La relation est une relation d’équivalence. La vérification est immédiate. Donc la classe d’équivalence de par cette relation est constituée de toutes les chaînes contenant exactement le même nombre de que . Par conséquent, est l’ensemble de toutes les chaînes contenant bits à et ayant longueur . Alors

Maintenant pour compter combien de chaînes de longueur ont exactement bits à , on fixe le premier bit:

En conclusion, et . On peut maintenant prouver la formule explicite par induction: on suppose pour un certain , alors

Fork me on GitHub