Examen corrigé d'éléments de logique pour l'informatique - Info 315

Introduction à l'examen de logique pour l'informatique

Ce document est le sujet d'examen d'Éléments de logique pour l'informatique, référencé sous le code Info 315, proposé dans le cadre de la Licence Informatique (semestre 5). Daté du 19 décembre 2013 (avec une mention au 25 mai 2014), cet examen de trois heures est accompagné de corrections détaillées pour chaque exercice, ce qui en fait un outil de révision particulièrement formateur pour les étudiants en informatique.

Présentation générale du sujet

L'épreuve est conçue pour évaluer la maîtrise des concepts fondamentaux de la logique mathématique appliquée à l'informatique. Le document comprend l'énoncé complet des exercices ainsi que des corrigés rédigés pas à pas. Les étudiants y trouveront également un rappel utile des règles logiques du système G en fin de document.

Principaux thèmes et exercices abordés

Le sujet est divisé en plusieurs exercices indépendants couvrant divers aspects de la logique formelle :

Questions de cours : Analyse de la décidabilité et des relations entre la validité des formules et leur satisfiabilité, notamment dans le calcul des prédicats.
Logique propositionnelle : Étude approfondie du connecteur de Sheffer (barre de Sheffer), de ses tables de vérité, de sa commutativité, de son associativité, ainsi que de l'expression des connecteurs usuels à l'aide de cette seule barre. Cet exercice aborde également des règles du système G pour ce connecteur.
Modélisation : Formalisation d'un plan de table à l'aide de prédicats logiques (voisinage, amitié, genre, égalité) et manipulation de structures de domaines finis.
Modèles et Résolution : Manipulation de formules du calcul des prédicats, mise en forme clausale, application de la méthode de résolution et vérification de la validité de formules.
Résolution et interprétations : Étude d'un langage avec un prédicat binaire, une constante et des symboles de fonctions unaires, incluant l'unification, le système G, la mise en forme clausale et la recherche de clauses vides.

Ce que l'étudiant peut apprendre avec ce document

Ce sujet corrigé permet d'aborder des notions clés telles que la skolemisation, la mise en forme normale, la méthode de résolution par unification, et la construction de preuves dans le système G. Les corrections fournies ne se limitent pas à donner les résultats : elles explicitent les raisonnements par tables de vérité, les étapes de transformation en forme clausale et l'utilisation de l'algorithme d'unification.

Conseils d'utilisation pour les révisions

Pour tirer le meilleur parti de ce document, il est conseillé de traiter chaque exercice de manière autonome avant de consulter la correction détaillée. Les étudiants peuvent s'entraîner à refaire les démonstrations du système G et à manipuler les clauses pour acquérir les automatismes indispensables en logique informatique.

Questions fréquentes

Quel est le niveau académique de cet examen ?

Cet examen s'adresse à des étudiants en Licence Informatique, plus précisément au semestre 5, dans le cadre de l'UE d'Éléments de logique pour l'informatique.

Quels types de correction trouve-t-on dans le document ?

Le document fournit des corrections complètes et rédigées pour l'ensemble des exercices, incluant des tables de vérité, des étapes de résolution formelle, des arbres de dérivation pour le système G et des explications sur les interprétations des modèles.

Le connecteur de Sheffer est-il au programme ?

Oui, l'exercice 2 est entièrement consacré à l'étude détaillée de la barre de Sheffer, de ses propriétés algébriques et de son utilisation pour exprimer les autres connecteurs logiques.

Testez vos connaissances

Question 1

Quelle est la propriété de la satisfiabilité dans le calcul des prédicats mise en avant dans les questions de cours ?

Elle est décidable par un algorithme simple.
Elle n'est pas décidable.
Elle équivaut toujours à la validité.
Elle ne s'applique qu'aux formules sans quantificateur.

Réponse correcte : Elle n'est pas décidable.

Explication : La correction du cours rappelle explicitement que la satisfiabilité dans le calcul des prédicats n'est pas décidable.

Question 2

Le connecteur de Sheffer (barre de Sheffer, noté |) est-il associatif ?

Oui, il est à la fois commutatif et associatif.
Non, il est commutatif mais pas associatif.
Oui, il possède la même associativité que l'implication.
Non, il n'est ni commutatif ni associatif.

Réponse correcte : Non, il est commutatif mais pas associatif.

Explication : Le document montre que la table de vérité de x | y est symétrique (donc commutatif), mais un contre-exemple avec des valeurs de vérité montre que l'associativité n'est pas vérifiée.

Question 3

Quelle méthode est utilisée dans l'exercice 5 pour montrer qu'une formule est une conséquence logique ?

La méthode des tables de vérité uniquement.
La méthode de résolution après mise en forme clausale.
La récurrence structurelle sur les entiers naturels.
L'utilisation exclusive des diagrammes de Venn.

Réponse correcte : La méthode de résolution après mise en forme clausale.

Explication : L'exercice 5 demande de mettre les formules en forme clausale puis d'utiliser la méthode de résolution pour dériver la clause vide.

Télécharger Examen corrigé d'éléments de logique pour l'informatique - Info 315 pdf