Logique et structure discrètes [ LINGI1101 ]

 > http://www.icampus.ucl.ac.be/claroline/course/index.php?cid=INGI1101

• Mathématiques discrètes élémentaires (fonctions, ensembles, ...)
• Exposition à différentes techniques de démonstration mathématique

tels que visés par les cours FSAB1101, MAT1111 et SINF1250.

• Introduction à la logique mathématique: logique des propositions, logique des prédicats; théories du premier ordre.
• Mécanismes de raisonnement: résolution, réécriture, induction sur un ensemble bien fondé.
• Structures discrètes vue comme théories du premier ordre: égalité, ordres partiels, treillis; naturels, chaînes, arbres, listes, ensembles, multi-ensembles, tuples, etc.

Les étudiants ayant suivi avec fruit ce cours seront capables de

• utiliser à bon escient la terminologie de base relatives aux fonctions, relations et ensemble et effectuer des opérations associées à ces concepts dans différents cas concrets,
• appliquer le formalisme de la logique des propositions et des prédicats pour modéliser et raisonner sur diverses situations de la vie réelle,
• décrire les limitations et avantages de la logique des propositions et de la logique des prédicats, et choisir la plus adéquate dans une situation donnée,
• maîtriser différentes techniques de démonstration(preuve directe, contre-exemple, preuve par l'absurde, induction mathématique) afin d'identifier et appliquer la plus appropriée dans une situation particulière,
• exploiter le lien entre, d'une part, induction mathématique et, d'autre part, programmes récursifs et structures récursives en informatique, afin de décrire et raisonner sur ces programmes et structures.

Les étudiants auront développé des compétences méthodologiques et opérationnelles.  En particulier, ils auront développé leur capacité à

• définir et interpréter avec rigueur et précision les concepts 
• éviter les mauvaises interprétations et détecter des erreurs de raisonnement.

• brefs tests durant le quadrimestre (auto-évaluation)
• examen écrit en session

• 2h de cours magistral/semaine, insistant sur les points délicats et difficiles
• 2h de séances d'exercices / semaine

• Préliminaires: ensembles, relations et fonctions, systèmes formels.
• Logique mathématique:
  • Calcul des propositions - syntaxe, sémantique, règles d'inférence; calcul des prédicats du premier ordre - syntaxe, sémantique, règles d'inférence, réfutation;
  • Notion de théorie, modèles, consistance, inclusion et extension de théories.
• Théories équationnelles: théorie de l'égalité, théorie des ordres partiels, théorie des treillis, théorie des groupes.
• Théories inductives: relation biens fondées; induction générale sur un ensemble bien fondé; étude de quelques théories inductives de base - entiers, chaînes, arbres, listes, ensembles, multi-ensembles, tuples. Notion de générateur de structure, construction systématique d'axiomatisations, et démonstrations inductives de propriétés selon différents principes d'induction (récurrence, induction complète, etc.).

Illustrations élémentaires dans différents champs d'application: preuves de programmes, spécification de types abstraits, automatisation du raisonnement déductif, systèmes experts, robotique, bases de données, analyse syntaxique, etc.

• syllabus disponible au service d'impression des étudiants
• transparents en ligne sur icampus