L1SF  -  Math discrètes  -  2016-17

Emploi du temps en L1Math
12 semaines de cours le vendredi 8h-9h30 dans l'amphi Phys2 ; 1er cours le 20 janvier
12 semaines de TD (1h30) ; début des TD lundi 23 janvier

Objectif du cours : analyser syntaxiquement les formules et énoncés mathématiques, deviner les types d'objets apparaissant dans les formules ou énoncés, expliciter très précisément les définitions ou axiomes et les règles de calcul (règles de réécriture) pour les premiers types d'objets : énoncés (calculs=preuves), ensembles, applications entre ensembles, entiers (constructions et raisonnements par récurrence), cardinalité des ensembles, nombres (représentations et calculs algébriques), permutations.

Présentation du cours de 2013-15 (le programme et la présentation changent cette année).
La page du cours en 2015-16

Progression du cours :
1. (20jan) Discussion sur l'expressison "Mathématiques discrètes", langage naturel, langage formel

Sur le web : notice wikipedia pour "Mathématiques discrètes" (en).

Premier langage et règles de calcul : représentation décimales des entiers (et nbres décimaux, nbres rationnels), règles pour l'addition, la soustraction, la multiplication.

...
Formules : constantes, variables libres, variables liées, opérateurs, arbre d'une formule
...

6 (10mar) Les preuves du calcul propositionnel : règles de raisonnement, exemples
Lectures : le style de Fitch pour la déduction naturelle,  (difficile) logique intuitioniste (versus logique classique) sur Wikipedia.

7-8 (24mar) (3h) Logique du 1er ordre : un seul type d'objets, règles pour ∀, ∃, =, exemple : preuve de la transitivité de l'égalité.
Les entiers : constante 0, opération S, règle (spécifique) de raisonnement par récurrence, autres axiomes (0 n'est pas un successeur, S est injectif), première preuve (tout entier non nul est un successeur), règles pour +, ×,
≤ (pas de définition en logique du 1er ordre : ce ne sont pas des objets), théorèmes (commutativité, associativité de + et ×, distributivité de × sur +).
Rq modèles ensemblistes pour les entiers, idée de preuve qu'un axiome n'est pas un théorème
Lecture : les suites de Goodstein sur Wikipedia

9 (31mar) Partiel 1h20

Cours (1h15) : introduction des nom de propriété des relations et des constantes, explicites et implicites ; règles de réécriture associées ; exemple avec ≤ dans la théorie des entiers, avec π en analyse.
Théorie des ensembles non typée : langage et axiomes spécifiques, déf. de A⊂E

10 (6avr) Les ensembles : formule {x,P(x)}, l'existence de {x, non x∈x} aboutit à une contradiction, formule et axiome d'existence pour {a,b}, P(x), ∪x, {x,x∈E et P(x)} ; déf. de E∪F, E∩F.
Relation (énoncé + désignation dans l'ordre de deux variables libres), relation fonctionnelle, application du point de vue syntaxique, formules xRy, f(x). Modèle pour le couple (a,b) en théorie des ensembles, graphe d'une relation, relation associée à une partie de E×F

11 (14avr) Application, correspondance, pté caractéristique de la formule f(x), pb d'existence, ex. ln(-1). Formules associées à la notion d'application : f, f(x), f:E→F, f:x↦f(x), f-1(y), f-1({y}), f-1(B), f∘g, Γf (graphe), xRfy (relation), f est injective, surjective, bijective

12 (14 avr) Rappel sur ℕ, suite définie par une relation de récurrence. Ensemble {1,...,n}, cardinal d'un ensemble fini, ensemble Σn des permutations de {1,...,n}, #Σn=n!, représentation d'une permutation, décomposition en cycles, calcul de puissances, ex.18 de la feuille de TD 4.

Lecture : le problème des 100 prisonniers sur Wikipedia


Documents du cours :
Feuilles de TD 1 (fev 17) : variables libres, va liées, constantes, expressions, type, formalisation
QCM 1 réponses (fev) explications
Feuille de TD 2 (fev) : calcul propositionnel
Feuille de TD 3 (version du 27 mars) : preuves du calcul propositionnel et de la logique du 1er ordre
QCM 2A réponses (mar)
Partiel (31mar) et un corrigé
Feuille de TD 4 (version du 8 avril) : définition d'une formule, raisonnements et calculs avec les entiers, les ensembles, les bijections
Tableaux de la séance de TD du 12 avr 1g, 1d, 2g, 2d
Quelques corrigés sur la page de 2016
Examen (16mai) et un corrigé.


Lectures :
La page d'un cours de logique propositionnelle et du premier ordre à Grenoble (calcul propositionnel, preuves formelles)
La page d'un cours de math discrète à Marseille-Luminy (ensembles, dénombrement)

J-Y. Girard, La théorie de la démonstration, Leçons de mathématiques d'aujourd'hui Vol 2, Cf cette page.

Liens :
  La page du cours de Méthodologie en 2001-04.
  Le cours de 2011-12 par A. Hirschowitz, les exercices WIMS, un corrigé de l'examen (sur feuille) de juin 2013
  Un cours classique de maths discrètes (en anglais), d'autres recencés sur cette page.
  page de la Licence 1ère année - parcours Mathématiques, page du Département de mathématiques