Mathématiques pour l’Informatique
2013–14
http://www.lri.fr/~paulin/MathInfo
Table des matières
1 Quelques éléments de logique
1.1 Formules
1.2 Formule vraie
1.3 Formule avec variable
1.4 Formule démontrable
1.4.1 Calcul des séquents
1.4.2 Règles dérivées
1.4.3 Théories
1.4.4 Proprietés de correction et complétude
1.5 Assistant de preuve
2 Théorie naive des ensembles
2.1 Constructions de base
2.2 Relations
2.2.1 Relations binaires
2.2.2 Fonctions
2.3 Ensemble fini
2.4 Cardinal d’un exemble fini
2.5 Ensemble dénombrable
3 Systèmes d’inférence, induction, récursion
3.1 Récurrence sur les entiers
3.2 Définition de relation par cloture
3.2.1 Système d’inférence
3.3 Preuve par induction
3.4 Définition récursive de fonction
4 Le paysage syntaxique
4.1 Ensemble des mots
4.1.1 Définitions
4.1.2 Propriétés
4.1.3 Ensemble de mots
4.1.4 Définitions de fonctions récursives sur les mots
4.2 Termes
4.2.1 Définitions
4.2.2 Egalité sur les termes
4.3 Induction, récursion sur les termes
4.3.1 Définition récursive sur les termes
4.3.2 Induction sur les termes
4.4 Généralisations
4.4.1 Termes vus comme des arbres
4.4.2 Termes avec sortes
4.5 Arbres binaires
5 Équivalence et Ordres
5.1 Définitions
5.2 Equivalence
5.2.1 Partition
5.2.2 Espace quotient
5.3 Construction d’ordres
5.3.1 Définitions générales sur les ordres
5.3.2 Diagramme de Hasse
5.3.3 Majorants et minorants
5.3.4 Ordre sur un ensemble produit
5.4 Ordres bien fondés
5.5 Treillis et théorèmes de point fixe
5.5.1 Cas particuliers de treillis
5.5.2 Théorèmes de point fixe
6 Algèbre de Boole
6.1 Définitions et propriétés
6.1.1 Exemples
6.1.2 Anneau de Boole
6.2 Fonctions booléennes
6.3 Fonctions caractéristiques
7 Combinatoire
7.1 Rappels sur les cardinaux
7.2 Arrangements
7.3 Permutations
7.4 Combinaisons
7.4.1 Propriétés des combinaisons