Exercices

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 .

Solutions: allez voir la solution de cet exercice dans les Exercices Corrigés.

Relations

Ordres bien fondés

Ordres finis

Prouver que tout ordre fini est bien fondé.

Induction, Récurrence

Preuves par induction

Quelques égalités

Prouver les égalités suivantes

Quelques inégalités

Prouver les inégalités suivantes

Induction forte

On dit qu’une preuve utilise l’induction forte lorsque le pas inductif a la forme , plutôt que . Prouvez les propositions suivantes par l’induction forte:

Nombres de Fibonacci

Soit le -ième nombre de Fibonacci, prouver les identités suivantes:

Récursion

Définitions récursives

Exprimer les propriétés suivantes par une définition récursive. Pour chacune indiquer quel est l’ordre bien fondé qui garantit la cohérence de la définition.

Tour de Hanoï

Le jeu de la tour de Hanoï à été inventé par le mathématicien Édouard Lucas. Il le décrit ainsi dans le journal Récréations mathématiques en 1892:

N. Claus de Siam a vu, dans ses voyages pour la publication des écrits de l’illustre Fer-Fer-Tam-Tam, dans le grand temple de Bénarès, au-dessous du dôme qui marque le centre du monde, trois aiguilles de diamant, plantées dans une dalle d’airain, hautes d’une coudée et grosses comme le corps d’une abeille. Sur une de ces aiguilles, Dieu enfila au commencement des siècles, 64 disques d’or pur, le plus large reposant sur l’airain, et les autres, de plus en plus étroits, superposés jusqu’au sommet. C’est la tour sacrée du Brahmâ. Nuit et jour, les prêtres se succèdent sur les marches de l’autel, occupés à transporter la tour de la première aiguille sur la troisième, sans s’écarter des règles fixes que nous venons d’indiquer, et qui ont été imposées par Brahma. Quand tout sera fini, la tour et les brahmes tomberont, et ce sera la fin des mondes!

Voici l’image d’une tour de Hanoï miniature

Une tour de Hanoï en bois Photo prise par Ævar Arnfjörd Bjarmason. Téléchargée de Wikimedia Commons.

Question. Les brahmes ont droit de déplacer un seul disque à la fois d’une aiguille à une autre, à condition de ne pas poser un disque plus gros sur un plus petit. Combien de temps nous reste-t-il avant la fin du monde?

Suggestions. Commencez par résoudre le problème pour une tour constituée d’un seul disque, puis 2, puis 3… Maintenant, vous vous en doutiez, utilisez l’induction!

Éléments de combinatoire énumérative

Combinaisons

Triangle de Pascal

Le triangle de Pascal est un tableau de nombres triangulaire et infini. Voici les premières 6 lignes.

Triangle de Pascal Auteur: Conrad.Irwin. Source: Wikimedia Commons.

Par convention on énumère les lignes et les colonnes à partir de , ainsi le triangle de Pascal définit une fonction dont les premières valeurs sont:

On dit que est la fonction binomiale. Une case quelconque du triangle de Pascal est définie ainsi:

L’animation suivante montre la procédure pour obtenir une case du triangle de Pascal.

Triangle de Pascal, animation Auteur: Hersfold. Source: Wikimedia Commons.

Question 1. Donner une définition récursive de la fonction binomiale .

Question 2. La fonction est elle totale, partielle, injective, surjective, bijective?

Question 3. Quel ordre bien fondé sur garantit la cohérence de la définition de ?

Question 4. Démontrer par induction les égalités suivantes:

Définition: La valeur de la fonction binomiale est aussi appelée le -ième coefficient binomial et est aussi notée ou .

Question 5. Soit un ensemble de éléments, on considère son ensemble des parties .

Note: Une partie de contenant éléments est appelée une -combinaison de .

Combinaisons, formule binomiale

Soit un ensemble de éléments.

  1. Quelle est la cardinalité de son ensemble des parties ?
  2. Soit , combien y a-t-il de sous-ensembles de contenant exactement éléments?
  3. Démontrer l’égalité par récurrence.
  4. On rappelle la formule binomiale: démontrer l’égalité précédente à l’aide de la formule binomiale.

Permutations

Anagrammes

Question 1 Quel est le nombre d’anagrammes du mot “mot”? Et du mot “cour”? Quel est le nombre d’anagrammes d’un mot de lettres différentes?

Question 2 Quel est le nombre d’anagrammes du mot “papa”? Trouver une règle générale pour compter le nombre d’anagrammes d’un mot avec lettres répétées.

Permutations, décomposition en cycles

On rappelle qu’une permutation de est une bijection de l’ensemble vers lui même. La notation la plus simple pour les permutations est la notation à deux lignes: par exemple si on note

la permutation telle que , , , etc.

Question 1 Combien y a-t-il de permutations dans ?

Soient

Question 2

  1. Combien valent et ? La composition de permutations est-elle commutative?
  2. Combien valent et ?
  3. Décomposer et en cycles. Lesquels de ces cycles sont des transpositions?

Question 3 Écrire en notation à deux lignes les produits de cycles suivants:

  1. ,
  2. ,
  3. .

L’ordre des facteurs est-il important? Considérez maintenant les cycles suivants (non-disjoints):

  1. ,
  2. .

L’ordre des facteurs est-il important? Écrire les produits de cycles inverses.

Question 4 Écrire en produit de cycles disjoints, puis en notation à deux lignes, les produits de transpositions suivants:

  1. ,
  2. ,
  3. .

L’ordre des facteurs est-il important? Écrire les produits de transpositions inverses.

Fork me on GitHub