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
|