L1SF  -  Math discrètes  -  2015-16


12 semaines de cours le vendredi 8h-9h30 dans l'amphi Phys2 ; 1er cours le 22 janvier
12 semaines de TD (1h30) ; début des TD lundi 25 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 2014-15 (idem)

Progression du cours :
1. (22jan) Discussion sur l'expressison "Mathématiques discrètes", exemples d'objets, formules explicites, variables libres ou liées
Sur le web : notice wikipedia pour "Mathématiques discrètes" (en).
2. (29jan) symbole ou mot désignant une constante par opposition à une variable, dépend du contexte (ex. e=2.71.. en analyse ou dans e∈E) ; tests pour décider si une variable est libre ou liée ; type des constantes et variables, qq notations classiques pour les types
3. (5fev) Rappel : constantes, variables ; opérateurs, expressions formelles et leur type, résumé en mots du langage courant d'une expresion, définition  d'une constante, assignation d'une variable.
Calculs : suite de réécritures suivant des règles le plus souvent implicites, ex. avec le développement décimal de 58/13 tel qu'enseigné en CM2-6ème

Sur le web : syntaxes admissibles pour le calcul sur WolframAlpha : essayer int(sin(t),t,0,pi) et integrate sin(2t) for t from 0 to pi
4. (12fev) 1er thème : Calcul propositionnel : description du langage, connecteurs logiques, calcul des tables de vérité, déf. de f(P,Q,...)≡g(P,Q,...), traductions en langage naturel de P⇒Q, condition nécessaire, cond. suffisante, négation de P⇒Q, cf "infraction à la loi") ; algèbre booléenne (B,+,×) : description du langage, calculs algébriques, expression dans B d'une formule f(P,Q,...) du calcul propositionnel, application : simplification, tautologie

Un exemple de calcul algébrique avec Sagemath, version pdf
5. (26fev) Enoncés avec quantificateur, table de vérité lorsque la variable ne peut prendre qu'un nombre fini de valeurs, ex avec ∀x:{0,…,10}, n≤ n2-1, valeur de vérité par une preuve sinon. Organisation d'une preuve (suite de réécritures issues d'application des règles de raisonnement), règle de réécriture (≡), règles associées à ∀, ∃ dans une hypothèse ou une conclusion.
6. (4mar) Retour sur les preuves, exmples d'axiomes spécifiques à un type. Document de cours.
Le type ensemble : langage (∈, =, ⊂, ∅, noms de variables), expression {x, P(x)}, axiome pour l'égalité, existence et unicité de ∅, paradoxe de Russel, axiomatique de Zermelo-Fraenkel, couples, produit cartésien d'ens., relations.

Sur le web : Preuves : le style de Fitch pour la déduction naturelle ; type ensemble : paradoxe de Russel et axiomes de Zermelo-Fraenkel sur Wikipedia,
7. (11mar) Type couple d'objets, relation entre élts de E et élts de F, graphe d'une relation, application, composée de deux applications, bijection, appl. injective, surjective, préservation par composition. Type entier N (0, S:N→N, not. 1=S(0), n+1=S(n)), règle de raisonnement par récurrence. Début cardinaux.
Lecture : axiomes de Péano
8. (18mar) Construction d'une application sur N par récurrence un+1=f(n,un), définition de m+n, m×n, mn par récurrence sur n, ptés de +,×. Déf. ≤ sur N, ensemble {1,...,n}, relation "être en bijection" entre ensemble, {1,...,n}{1,...,m} ssi n=m (preuve par récurrence sur min(m,n), déf. E est fini de card. n si E{1,...,n}, ptés #(EF), si A⊂E alors #A≤#E, #FE (au passage pour e∈E fixé Φ:FE→F, Φ(f)=f(e) alors #(FE)=Σy∈F #(Φ-1(y)), déf. de Σy∈F)
9. (25mar) Partiel 1h. Au programme : tout jusqu'aux cardinaux non compris.
10. (1avr) cardinal de la réunion d'une famille d'ens. disjoints, de E×F, de FE, de Inj(E,F) (ens. des appl. injectives de E dans F), de l'ens. des permutations de {1,...,k} (notation k!), de l'ens. des parties à k éléments de {1,...,n} (notation : coefficient binomial), formule du binôme.
11. (8avr) Types de nombres : représentation (décimale, couple d'entiers, etc), opérations algébriques, synthèse pour N (def S(n), principe de réc., +, ×, ≤), Z, Q (a/b ou dvt décimal périodique, lien), R, hypothèse du continu (la représentation décimale ne dit pas tout)
12. (15avr) Permutations de {1,...,n}: orbite d'un élt sous l'action d'une permutation, décomposition en cycles, problème des cadeaux d'anniversaires, problème de la répartition des convives sur une table ronde.
Sur le web : le premier probleme et le second sur MathStackExchange
13. (22avr, 1h) Taille de l'orbite de 1 sous l'action de σi où σ est le cycle (1 2 ... n) : n/pgcd(n,i), exemple avec n=4,5,8 , lien entre le nombre de i<n tel que σi est un cycle de longueur n et les élts inversibles pour la multiplication de l'anneau Z/nZ des entiers modulo n.


Documents du cours :
Feuilles de TD 1 (25 jan 16) : variables libres, va liées, constantes, expressions, type, formalisation
QCM 1 réponses (8,10fev) explications
Feuille de TD 2 (22fev) : calcul propositionnel
QCM 2 réponses (29fev, 2,7mar) explications
Feuille de TD 3 (7mar) : preuves formelles, type ensemble
Quelques corrigés d'exercices des feuilles 1,2,3 (20mar), corrigé de l'ex. 2 de la feuille 3 (18avr)
Feuille de TD 4 (21mar), corrigé succint des ex. 2-5 (26avr).
Partiel du 25 mars et un corrigé (26avr)
Feuille de TD 5 (15avr), corrigé des ex. 1 et 2 ; corrigé succint des ex. 5 et 9 (27avr) ; ex 5: essayer dans WolframAlpha 1.3 with 6913 repeating *3.1 with 41 repeating.
Examen du 3 mai et un corrigé, corrigé de l'ex.2.
Session 2 du 17 juin  Corrigé : règles utilisées dans l'ex. 5, corrigé très succint

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