L1SF
- Math discrètes - 2014-15
Raisonnement mathématique
12 semaines de cours le vendredi 8h-9h30 dans l'amphi Phys2 ; 1er cours le 23 janvier
12 semaines de TD (1h30) ; début des TD lundi 26 janvier
Présentation.
Progression du cours :
1. (23jan) Introduction au cours, qq textes mathématiques. Document projeté.
Objets mathématiques désignés par des mots (la fonction sinus) ou des symboles (2.5) ou des constructions (-2/3, ∫12 ln(x)
dx ), variable liée par une construction, variable libre, constante ; énoncé informel
("l'intégrale de 1 à 2 de la fonction Log est positive") ou formalisé
(alphabet restreint), valeur de vérité d'un énoncé (un énoncé est vrai
dans un contexte s'il a une preuve dans ce contexte), preuve = suite
d'applications de règles de raisonnement ; texte mathématique = récit :
articulation entre les phrases. Construction sur les énoncés : table de
vérité de et, de ⇒, quantificateur ∀, variable liée par un quantificateur.
2. (30jan) Enoncé
formalisé (écrit avec un dictionnaire spécifique ∀, ∃, =, ∈, R, x, ou,
...), résumé d'énoncé ex. "f est continue en 0", "π est irrationnel".
Composition d'énoncés avec les opérateurs logiques non, et, ou, ⇒, ⇔,
table de vérité, calcul de la valeur de vérité d'un énoncé composé en
fonction des valeurs de vérité des morceaux.
3. (6fev)
Quantification des énoncés : ∀x, P(x) , ∃x, P(x) où P(x) est un énoncé
avec x comme variable libre. En pratique on restreint x à un ensemble
de valeurs ∀x∈E, P(x) qu'on peut réécrire comme ∀x, x∈E ⇒ P(x). Valeur
de vérité d'un énoncé quantifié : intuition donnée par la traduction
informelle de ∀ "quel que soit" et de ∃ "il existe", on sera plus
précis avec la partie de cours sur les preuves. Si E=E1∪E2 alors ∀x∈E, P(x) ≡ (∀x∈E1, P(x)) et (∀x∈E2, P(x)) où ≡ signifie "a même valeur de vérité que". Si E a un seul élément x0 alors ∀x∈E, P(x) ≡ P(x0). Exposé analogue pour ∃.
Construction : nouvel objet obtenu par assemblage de sympobes ou de
mots désignant des objets, ex. f(x) pour f une fonction et x un
argument, 0<1 est une construction dont le résultat est un énoncé,
etc.
Type d'un objet, d'une variable, d'une constante : fait référence à
l'"ensemble" des objets de même type et aux constructions
disponibles pour cet objet (cf la Programmation Orientée Objet en
informatique)
4. (13fev) Expression dans (F2,+,x) d'un énoncé, expression de P ou Q, P et Q, P ⇒ Q, P ⇔ Q, calcul et simplification, cf ex.6 de la feuille 2 de TD.
Type d'un objet, déclaration x:T, usage ∀x:T, ∃x:T, exemples de types et constructions associées : nombres, Ens, fonctions, etc.
5. (20fev) Le type
Ensemble, théorie pure des ensembles (tous les objets sont des
ensembles), théorie typée, constructions {a,b}, {x:T, P(x)},
paradoxe de Russel, axiomes d'existence
Lectures : paradoxe de Russel, théorie des ensembles sur Wikipedia
6. (6mar)
Constructions et réécritures : rappel : objets mathématiques écrit avec
le dictionnaire des énoncés formalisés ou avec le dictionnaire de la
langue courrante pour les énoncés informels, avec éventuellement des
symboles désignant des constantes ou des variables ; deux types d'objet
: les énoncés et les objets dont parlent les énoncés.
Une construction suit une règle syntaxique précise d'une part (la
notation), elle peut être vue comme une fonction T → T' où T et T'
désignent des types (T peut être un produit T1xT2...) d'autre part, ex. ∫abf
(l'intégrale), ∃x:T, P(x) (l'existence). Une construction C:T → T' est
définie la réécriture de l'énoncé t'=C(t), ex. la paire {a,b} est
définie par la réécriture E={a,b} ≡ (∀x, x∈E ⇔ (x=a ou x=b)).
Réécriture de I=∫abf, de l=limn→∞un. Rq un texte mathématique est une suite de réécritures suivant des règles précises, qu'on peut appeler calcul.
7. (13mar) Deux
réécritures de l'enoncé P(C(t)) où C:T→T' est une construction et P(t')
un énoncé avec t':T' variable libre (une propriété sur les objets de
type T'), ex réécriture de √2>1 avec une définiton de √, réécriture
de ∀a,b:R, [a,b]≠∅ avec une définition du segment [a,b].
Contextes, séquents, preuves d'un séquent partant d'une liste de séquents admis et suivant un ensemble de règles de déductions.
8. (20mar) (8h30) Partiel.
9. (27mar) Règles "gratuites" ou réversibles du calcul des séquents.
10. (3avr) Preuve
en calcul des séquents de l'énoncé "√2 n'est pas un nombre rationnel" :
réécriture de √2, de "x est un nombre rationnel", raisonnement par
l'absurde, utilisation du théorème acquis "tout entier non nul s'écrit
de façon unique comme le produit d'une puissance de 2 et d'un nombre
impair".
11. (10avr)
"Macro"-Règles correspondant à un schéma de raisonnement : Modus Ponens :
observer A pour montrer B, Distinguer suivant une hypothèse H,
Particulariser un théorème (remplacer la variable libre t par une
formule C(x)), ∀t:T,P(t) dans le contexte (choisir un tel t), ∃t:T,
P(t) comme objectif (exhiber un tel t), Eliminer une formule C(t) par
réécriture de l'énoncé t'=C(t). Illustrations avec la preuve de √2∉Q
(réécriture, Observer un lemme, distinguer suivant H) et avec la preuve
de l'existence d'une racine réelle du polynôme x^5+x^2+1 (limite d'une
suite construite par dichotomie).
12. (17avr)
Axiomes des théories mathématiques : du raisonnement, égalité, théorie
des ensembles (axiome d'existence d'ensembles décrits par une propriété
de leurs éléments), entiers (principe de récurrence, construction de
suites), nombres réels (nbre réel décrit comme limite d'une suite
croissante majorée ou comme borne supérieure d'une partie non vide
majorée).
|
Documents du cours :
Feuilles de TD 1-2 (26 jan 15)
Feuille de TD 3 (9 fev 15)
Feuille de TD 4 (2 mar 15)
Feuille de TD 5 (16 mar 15)
Feuille 7 de 2013-14 (8 avr 15), corrigé sur la page du cours de 2013-14.
Document sur le calcul des séquents (mai14)
Feuille de référence pour l'examen (mai 15)
Partiel (mar15)
Test QCM corrigé (avr15)
examen (mai15), session 2 (juin15)
La page du cours en 2013-14 avec quelques corrigés des exercices de TD et le sujet d'examen.
Lectures :
Le cours de 2011-12 par A. Hirschowitz, les exercices
WIMS, un corrigé de l'examen (sur
feuille) de juin 2013
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.
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
|