Logique -- L3 mathématiques-Informatique - semestre 2

Année 2014-2015

• semaine 1 : 19/01/2015
  • Introduction : prédicat / ensemble ; préliminaires ensemblistes (non formels) : extensionnalité, définition en compréhension, paradoxe de Russell et Berry mentionnés.
  • Intersection, réunion, passage au complémentaire ; Algèbre de Boole des parties d'un ensemble E, axiomatisation (redondante) : propriétés caratéristiques du complément, involutivité ; associativité, commutativité et idempotence de ∩ et ∪ ; E et ∅ éléments neutres ou absorbants pour ∩ et ∪ ; distributivité de l'une sur l'autre ; lois de De Morgan.
  • Algèbre de Boole (les identités précédentes prises comme axiomes). Démonstration des lois d'absorption par les précédentes (distributivité, élément neutre et absorbant).
  • Rappel des axiomes d'ordre, ordre partiel ordre total ; un sous-ensemble d'un ensemble ordonné est ordonné par la restriction de l'ordre à celui-ci; plus grand/petit élément d'un ensemble ordonné, d'une partie de celui-ci ; minorant/majorant, borne inférieure/supérieure.
  • L'ensemble des parties de E ordonné par inclusion, l'intersection et la réunion de deux éléments sont la borne inférieure et la borne supérieure, ppe et pge.
  • Soit une structure (A,∧,1) où la loi binaire ∧ est associative, commutative et idempotente, alors x ≤ y définie par x ∧ y = x est une relation d'ordre et deux éléments on toujours une borne inférieure définie par ∧ ; l'élément neutre correspond au plus grand élément, l'élément absorbant au plus petit. On a la même propriété par dualité pour x ∨ y = x. On appelle treillis un ensemble ordonné dont deux éléments ont toujours une borne supérieure et une borne inférieure ; si les deux lois ainsi définies sont distributives l'une sur l'autre c'est un treillis distributif.
  • Un treillis distributif avec plus grand et plus petit élément peut être défini algébriquement comme une structure (A,∧,∨,0,1) par deux lois avec les lois binaires ∧,∨ associatives, commutatives et idempotentes, distributives l'une sur l'autre, 1 neutre pour ∧ absorbant pour ∨ et 0 neutre pour ∨ absorbant pour ∧. Dans ce cas les lois d'absorption sont satisfaites, les deux relations d'ordre définies par x ∧ y = x et x ∨ y = x sont identiques et munissent A d'une structure de treillis (pour la définituion algébrique des treillis voir la feuille d'exercices).
  • Une algèbre de Boole est un treillis distributif (défini comme ensemble ordonné) avec plus grand et plus petit élément, et avec complément, c'est-à-dire que pour tout x de A il existe x' tel que x ∧ x' = 0, x ∨ x' = 1 (on déduit l'unicité du complément, l'involutivité du passage au complément, les lois de De Morgan).
  • Feuille d'exercices 1.

• semaine 2 : 26/01/2015
  • Intersection réunion infinies, algèbre de Boole complètes.
  • Les définitions inductives ; exemple, intersection d'ensembles ayant une certaine propriété.
  • Les entiers naturels : vus comme structure définie inductivement ; axiomatisation de l'arithmétique (Dedekind-Peano) ; démonstration par récurrence ; principe de définition par récurrence, avec paramètres, avec paramètre dépendant de l'argument ; définitions des opérations usuelles et de l'ordre.
  • Polycopié Axiomatisation de l'arithmétique (Axiomes de Peano).
• semaine 3 : 02/02/2015
  • Ordre sur les entiers : propriétés, ordre total, bon ordre.
  • Deux structures (N,0,s) et (N',0,s') qui vérifient les axiomes de Peano sont isomorphes (par le théorème de définition par récurrence) et limites de ce résultat (qui dépend en réalité du contexte ensembliste).
  • Axiomatisation des entiers comme ensemble bien ordonné, tel que tout élément a un successeur, et tout élément non nul est un successeur.
• semaine 4 : 09/02/2015
  • Introduction au calcul propositionnel
  • Syntaxe des formules propositionnelle : approche inductive. Définition de hauteur, sous-formule. Existence d'un arbre de décomposition unique
  • Sémantique : valuations (i.e. modèles), tables de vérité. Satisfaisabilité et validité. Une formule est satisfaisable ssi sa négation n'est pas valide. Equivalence de formules. Définition des fonctions Booléennes. Formule propositionnelle comme représentation d'une fonction Booléenne.
  • Exemples de modélisation en calcul propositionnel
  • Quelques équivalences logiques et tautologies usuelles.
  • Formes normales conjonctives et disjonctives : définitions.
  • Feuille d'exercices 2.
• semaine 5 : 16/02/2015
  • Systèmes de connecteurs fonctionnellement complet
  • Impliquants premiers d'une formule. FND complète : toute formule peut être mise sous FND dont les conjonctions sont ses impliquants premiers. FND première
  • Forrmules propositionnelles positives : définition sémantique, forme de ses impliquants premiers. La FND complète d'une formule propositionnelle positive est "syntaxiquement" positive et non redondante. Unicité de la FND première.
  • Application aux bornes inférieures sur la longueur des FND de certaines formules
  • Feuille d'exercices 3.
• semaine : 23/02/2015
  • Pause ufr de math.
• semaine 6 : 02/03/2015
  • Equisatisfaisabilité. Mise sous forme FNC équisatisfiable
  • Méthode de résolution : présentation. Preuve de réfutation par résolution
  • Cohérence et complétude pour la réfutation par résolution : si une formule peut être réfutée, elle n'est pas satisfaisable; Si une formule n'est pas satisfaisable, elle peut être réfutée par résolution. Test de satisfaisabilité par résolution.
  • Longueur d'une preuve. Limite de la résolution. Théorème d'Haken (énoncé seulement) : Toute réfutation du principe des tiroirs (pour n tiroirs) par résolution est de longueur au moins 2^{n/32}
  • Application à certains type de formules : définition des formules de Horn
• semaine 7 : 09/03/2015
  • Méthode de résolution unitaire et application à la décision de la satisfaisabilité des formules de Horn
  • Valuation partielle. Propagation unitaire. Algorithme de décision pour SAT basé sur l'affectation progressive de valeurs de vérité aux variables : DP (Davis, Putnam) puis DPLL (Davis, Putnam, Logemann et Loveland). Exemples.
  • Principe de l'apprentissage de clauses et stratégie de backtrack. Graphe de conflits. Principe des algorithmes CDCL (Conflict-Driven Clause Learning).
  • Feuille d'exercices 4.
• semaine 8 : 16/03/2015
  • Calcul des prédicats du premier ordre -- introduction : objets, énoncés, preuves ; théorie et structure ; premier et second ordre. Syntaxe : signature, langage du premier ordre : termes et formules. Sémantique : structure, interprétation des termes, satisfaction d'une formule dans une structure.
  • Feuille d'exercices 5.
• semaine 9 : 23/03/2015
  • Clôture universelles, formules universellement valides, formules satisfaisables ; théorie ; axiomatisation d'une classe de structure par une ensemble fini de formules, par un ensemble infini de formules ; exemples de la classe des ensembles de cardinalité au plus ou au moins ''n'' (''n'' entier fixé), dela classe des ensembles infinis.
  • Relation de conséquence, relation d'équivalence, relativement à une théorie (définitions sémantiques).
  • Formules universellement valides obtenues par substitution à partir des tautologies du calcul des prédicats ; règles de maniement des quantificateurs, en particulier celles permettant la mise sous forme prénexe.
  • Corrigé du test numéro 1 (arithmétique, bon ordre).
  • Partiel le 25/03/2015, 10h30-13h30, salle 2017.
• semaine 10 : 30/03/2015
  • Propriétés de l'égalité ; propriétés fondamentales (axiomes) : ∀x x=x, ∀x ∀y [(x=y ∧ Fxz₁...z_n) → Fyz₁...z_n] ; symétrie, transitivité ; axiomatisation par des énoncés universels : réflexivité, symétrie, transitivité, la compatibilité pour les symboles de fonction de la signature, la propriété fondamenatle restreinte aux prédicats de la signature ; modèle égalitaire et modèle non égalitaire d'une relation binaire qui satisfait les axiomes de l'égalité ; indications sur la façon de passer de l'un à l'autre.
  • Mise sous forme prénexe ; forme de Skolem (cas des formes prénexes) ; équisatisfaisabilité d'une formule et de sa forme prénexe ; démonstration sur un exemple et indications pour le cas général.
  • Méthode de Herbrand : domaine de Herbrand (les termes clos) en calcuil des prédicats non égalitaire ; structure de Herbrand ; une formule universelle est satisfaisable si et seulement si elle possède un modèle de Herbrand. Un ensemble de clauses (disjonction de littéraux) universellement quantifiées n'a pas de modèle si est seulement si il est réfutable dans un système avec règle de coupure et règle d'instanciation des formules universellement quantifiées (on pourait se restreindre aux instanciation par des termes clos). Quelques indications sur la règle de résolution (coupure + instanciation en choisissant un unificateur principal), la complétude de la résolution, la notion d'unificateur (unificateur principal non défini).
  • Version provisoire du polycopié pour le calcul des propositions et le calcul des prédicats (exercices sur la résolution à la fin du polycopié).
• semaine 11 : 6/04/2015
  • Lundi de Pâques
  • Théorie des ensembles de Zermelo (voir une liste des axiomes) : paradoxe de Berry et paradoxe de Richard -- la théorie de Zermelo vue comme une théorie du premier ordre de l'appartenance ; compréhension et paradoxe de Russell ; extensionnalité ; axiome de compréhension restreinte et autres cas particulier de la compréhension ; il existe toujours un ensemble extérieur à un ensemble donné (pas d'ensemble de tous les ensembles) ; axiome de l'infini ; définition des entiers ; ils vérifient les axiomes de Peano.
  • Feuille d'exercices 7 (définition et propriétés des couples, injectivité du successeur sur N.
  • Jean-Louis Krivine Éléments de théorie des ensembles, cours polycopié, Université de Paris 7.
• semaine 12 : 13/04/2015
  • Définition en théorie des ensembles des couples, du produit cartésien de deux ensembles, des relations, des fonctions ; ensemblne et classe propre, relation au sens ensembliste et relation définie par une formule du langage.
  • Cardinalité : cardinalité finité, ensemble fini (en bijection avec un entier), unicité du nombre d'éléments, principe des tiroirs ; cas général : la relation d'équipotence ou « avoir même cardinal », la relation de subpotence ou « avoir un cardinal plus petit ou égal à » sans définir le cardinal ; propriétés de ces relations ; théorème de Cantor-Bernstein (brève indication pour la démonstration) ; le dénombrable (en bijection avec N), propriétés ; axiome du choix (AC), une réunion dénombrable d'ensembles dénombrables est dénombrable (axiome du choix dénombrable) ; tout ensemble infini (au sens qui n'est en bijection avec aucun entier) contient un ensemble dénombrable (démonstration avec l'axiome du choix ; le lemme de Zorn (non démontré), application à la comparabilité cardinale.
  • Feuille d'exercices 8 cardinalité, lemme de Zorn.
• semaine 13 : 4/05/2015
  • Résumé des résultats sur la cardinalité ; exercice : C^{A × B} et (C^A)^B ont même cardinal, application ; démonstration du théorème de Cantor-Bernstein ; retour sur l'axiome du choix, axiome du choix dépendant.
  • Démonstration du lemme de Zorn (polycopié).
• semaine 14 : 11/05/2015
  • Séance de TD à l'horaire du cours lundi 13h30-16h30, salle à préciser, au 2nd étage a priori.
• Examen de première session le 22/05/2015, 8h30-11h30, salle 1021 (S.G.).
• Consultation des copies suivie d'une séance de correction de l'examen, et réponses aux questions le mercredi 17 juin à 10h, salle 1014 (S.G.).
• Examen de seconde session le 2/07/2015, 9h-12h, salle 2015 (S.G.).