Introduction à la Théorie des graphes

Objectifs et prérequis du TP sur le calcul des propositions

Objectifs

Ce TP sur le calcul des propositions vise à enseigner aux étudiants les concepts fondamentaux de la logique formelle, notamment la syntaxe et la sémantique des propositions. À la fin de ce TP, les étudiants devraient être capables de :

• Définir un langage logique et ses composants.
• Construire et analyser des formules propositionnelles.
• Utiliser des arbres de décomposition pour représenter des formules.
• Établir des tables de vérité pour évaluer des formules.
• Comprendre les notions de satisfiabilité et de validité.

Prérequis

Pour réaliser ce TP, les étudiants doivent avoir des connaissances de base en logique et en mathématiques. Aucun logiciel spécifique n'est requis, mais il est recommandé d'avoir accès à un environnement de travail pour effectuer des calculs et des représentations graphiques.

Créer des formules propositionnelles pas à pas

Définition du langage

Un langage logique est défini par une syntaxe, qui est un ensemble de symboles (alphabet) et de règles permettant de combiner ces symboles sous forme de formules. Les symboles incluent :

• Des variables propositionnelles (atomes) : R0 = {p, q, ...}
• Des symboles logiques (connecteurs) : non (¬), disjonction (∨), conjonction (∧), implication (⇒), équivalence (⇔).
• Des constantes : V (vrai), F (faux).

Une formule propositionnelle est un mot construit sur l'alphabet A0 = R0 ∪ {∨, ∧, ¬, ⇒, ⇔} ∪ {F, V} ∪ {(, )}.

Arbre de décomposition d’une formule

Pour représenter une formule, on peut utiliser un arbre de décomposition. Par exemple, pour la formule :

A : ((p ∧ (¬q ⇒ ¬p)) ∧ (¬q ∨ ¬r)) ⇒ (q ⇒ ¬p)

On décompose cette formule en un arbre où chaque nœud représente un connecteur logique et chaque feuille représente une variable propositionnelle ou une constante.

Substitution dans une formule

La substitution s'applique à toutes les occurrences d'une variable propositionnelle dans une formule. Par exemple, pour A : p ⇒ (q ∨ p) et B : q ⇒ r, la substitution A [p ← B] donne :

(q ⇒ r) ⇒ (q ∨ (q ⇒ r))

Résultats attendus

Les étudiants devraient observer que les formules qu'ils construisent respectent les règles de syntaxe et peuvent être évaluées à l'aide de tables de vérité. Par exemple, pour la formule A : p ∧ (q ⇒ p), la table de vérité serait :

Erreurs fréquentes avec le calcul des propositions

Les erreurs les plus courantes lors de la manipulation des formules propositionnelles incluent :

• Confusion entre les connecteurs logiques, par exemple, utiliser ∧ au lieu de ∨.
• Oublier de parenthésiser correctement les formules, ce qui peut mener à des interprétations incorrectes.
• Ne pas respecter l'ordre de priorité des connecteurs, ce qui peut fausser les résultats.

Il est essentiel de vérifier chaque étape lors de la construction et de l'évaluation des formules pour éviter ces erreurs.

Questions fréquentes

Qu'est-ce qu'une formule propositionnelle ?

Une formule propositionnelle est un mot construit sur un alphabet logique qui respecte des règles de syntaxe spécifiques. Elle peut contenir des variables propositionnelles, des connecteurs logiques et des constantes.

Comment construire une table de vérité ?

Pour construire une table de vérité, il faut énumérer toutes les combinaisons possibles des valeurs de vérité des variables dans la formule. Ensuite, on évalue la formule pour chaque combinaison.

Qu'est-ce que la satisfiabilité ?

Une formule est satisfiable si elle peut être vraie pour au moins une interprétation des variables. Si elle est vraie pour toutes les interprétations, elle est valide.

Quelle est la différence entre validité et satisfiabilité ?

La validité signifie qu'une formule est vraie dans toutes les interprétations, tandis que la satisfiabilité signifie qu'il existe au moins une interprétation où la formule est vraie.

Comment utiliser les arbres de décomposition ?

Les arbres de décomposition permettent de visualiser la structure d'une formule en décomposant les connecteurs logiques et en représentant les variables et constantes sous forme de nœuds et de feuilles.