Fondements de l'informatique 2

L’UE se compose d'une matière enseignée sur 2 périodes  : Fondements de l'informatique 2 P6 (CM et TD) et Fondements de l'informatique 2 P7 (CM et TD).

Logique propositionnelle : morphologie ; sémantique (interprétation, satisfiabilité, insatisfiabilité, tautologie, table de vérité), relation d’équivalence et formes normales, complétude fonctionnelle, conséquence sémantique (modélisation de problèmes) et méthodes sémantiques (arbre sémantique et propagation) ; méthodes syntaxiques (analytique : la méthode des tableaux, axiomatique : système de Hilbert, synthétique : le calcul des séquents), propriétés de correction et complétude (vis-à-vis de la sémantique) et terminaison d’une méthode syntaxique.
Logique du premier ordre : morphologie ; sémantique (interprétation dans une structure, vérité versus validité), relation d’équivalence et formes normales, conséquence sémantique (modélisation de problèmes), forme normale de Skolem, théorème de Skolem-Herbrand-Gödel ; méthodes syntaxiques : l’unification et la Résolution de Robinson.