CM de structures discrètes (DUT Informatique 1^ère année)

Voici les thèmes abordés, séance par séance :

• CM 1, 11 septembre 2012 : notions de base sur les ensembles ; théorème de la double inclusion ; diagrammes de Venn ; notations ensemblistes.


• CM 2, 18 septembre 2012 : opérations sur les ensembles : ensemble des parties, produit cartésien, union, intersection, différence ensembliste, différence symétrique, complémentaire ; opérations commutatives, opérations associatives ; notion de contre-exemple pour infirmer une proposition ; démonstration par double inclusion.


• CM 3, 24 septembre 2012 : distributivité de l'intersection et de l'union ensembliste ; théorème de De Morgan ; partition d'ensembles ; notions de base sur les relations binaires ; représentation des relations binaires (sagittale, matricielle, par graphe orienté) ; classification des relations binaires (réflexivité, transitivité, etc.).


• CM 4, 1^er octobre 2012 : lecture des propriétés des relations binaires sur leur graphe orienté ; relations d'équivalence ; démontrer qu'une relation binaire est une relation d'équivalence ; classes d'équivalence.


• CM 5, 8 octobre 2012 : interprétation des relations d'équivalence en termes de graphes orientés ; théorème des relations d'équivalence et des partitions d'ensemble ; relations d'ordre ; démontrer qu'une relation binaire est une relation d'ordre ; exemples de démonstrations par l'absurde ; opérations sur les relations binaires (inverse, complémentaire, réunion, intersection).


• CM 6, 15 octobre 2012 : altération des propriétés des relations binaires lors d'opérations ; définitions de base à propos des fonctions ; domaine de définition et image d'une fonction ; ensemble des images et des antécédents d'un ensemble.


• CM 7, 22 octobre 2012 : les applications ; la notion d'injectivité, de surjectivité et de bijectivité pour les applications ; exemples d'applications injectives/surjectives/bijectives ; techniques pour démontrer/infirmer qu'une application est injective/surjective/bijective.


• CM 8, 5 novembre 2012 : composition et inversion d'applications ; syntaxe de la logique propositionnelle ; notion de définition récursive ; taille, hauteur et ensemble des sous-formules d'une formule de la logique propositionnelle.


• CM 9, 19 novembre 2012 : priorité et associativité des connecteurs logiques ; arbres syntaxiques de formules ; lecture de propriétés des formules sur leurs arbres syntaxiques ; contexte et évaluation de formules ; tables de vérité.


• CM 10, 26 novembre 2012 : formules satisfiables, falsifiables, valides, contradictoires ; formules à deux variables ; équivalence de formules et démonstration du fait que l'équivalence de formules est une relation d'équivalence ; bi-implication et validité ; tautologies remarquables.


• CM 11, 3 décembre 2012 : littéraux, clauses et formes normales conjonctives (FNC) ; algorithme de mise en FNC ; interprétation de l'algorithme de mise en FNC en termes d'arbres syntaxiques ; notation ensembliste des formules en FNC ; notion de résolvant ; conséquences logiques.


• CM 12, 10 décembre 2012 : démonstration par réfutation ; langage du 1^er ordre ; termes ; syntaxe de la logique du 1^er ordre ; arbres syntaxiques ; occurrences d'une variable dans une formule.


• CM 13, 17 décembre 2012 : occurrences de variables libres/liées ; formules closes ; interprétation d'un langage ; affectations ; valeur d'un terme ; évaluation d'une formule ; exemples d'évaluations de formules ; formules satisfiables, falsifiables, valides, contradictoires ; équivalence de formules ; négation des quantificateurs.