Logique formelle

Ce matériel couvre les fondements du calcul des propositions en logique formelle, destiné aux étudiants en informatique, mathématiques ou disciplines connexes. Il présente la syntaxe et la sémantique du langage propositionnel, les notions de validité, satisfiabilité, équivalence, ainsi que les formes normales et les systèmes complets de connecteurs.

Le calcul des propositions : syntaxe

Un langage logique est défini par une syntaxe, c’est-à-dire un alphabet de symboles et des règles pour former des mots appelés formules. La syntaxe décrit la structure grammaticale des formules, tandis que la sémantique leur donne un sens.

Alphabet du calcul propositionnel

• Variables propositionnelles (atomes) : R0 = {p, q, …} éventuellement indexées (p1, q1, p2, q2, …)
• Connecteurs logiques :
  • négation (⎤) : unaire
  • disjonction (∨), conjonction (∧), implication (⇒), équivalence (⇔) : binaires
• Constantes : V (vrai), F (faux)
• Symboles auxiliaires : (, ), ,

Définition des formules propositionnelles (L0)

L’ensemble L0 des formules propositionnelles est le plus petit ensemble de mots sur l’alphabet A0 qui vérifie :

• Contient toutes les variables propositionnelles R0 et les constantes V, F
• Si A est une formule, alors (⎤ A) est une formule
• Si A et B sont des formules, alors (A ∨ B), (A ∧ B), (A ⇒ B), (A ⇔ B) sont des formules
• Rien d’autre n’est une formule

Exemples de formules

• Formules valides : (p ⇒ ((⎤ (q ∧ r)) ∨ p)), (p ⇔ q), (F ⇔ V), ((p ∨ q) ∨ q), (⎤ p), ((⎤ p) ∨ (⎤ q)), F, q
• Non formules : (p q ∨), ((⎤ p) ⇒ ⇔ (⎤ q))

Priorités des opérateurs

Pour éviter l’ambiguïté, on fixe un ordre de priorité des connecteurs (du plus fort au plus faible) :

⎤ > ∧ > ∨ > ⇒ > ⇔

Parenthésage d’une formule

Exemple :

p ∧ q ⇒ r ∧ s ⇒ ⎤ p ⇔ u ∨ v

est parenthésée :

(( ( (p ∧ q) ⇒ (r ∧ s) ) ⇒ (⎤ p) ) ⇔ (u ∨ v))

Arbre de décomposition d’une formule

Une formule peut être représentée par un arbre dont les nœuds sont les connecteurs et les feuilles les atomes ou constantes. Par exemple pour :

A = ((p ∧ (⎤ q ⇒ ⎤ p)) ∧ (⎤ q ∨ ⎤ r)) ⇒ (q ⇒ ⎤ p)

Chaque sous-formule correspond à un nœud unique, ce qui garantit l’unicité de l’arbre de décomposition (théorème de lecture unique).

Substitution dans une formule

Soient A et B deux formules, et p une variable propositionnelle de A. La substitution A [p ← B] consiste à remplacer toutes les occurrences de p dans A par la formule B.

Exemple :

A : p ⇒ (q ∨ p)
B : q ⇒ r

A [p ← B] = (q ⇒ r) ⇒ (q ∨ (q ⇒ r))

La substitution simultanée sur plusieurs variables est notée :

A [p1 ← B1, p2 ← B2, …, pn ← Bn]

Attention : la substitution simultanée diffère de la substitution séquentielle (ordre important dans cette dernière).

Le calcul des propositions : sémantique

Interprétation et valeurs de vérité

Une interprétation I est une application qui associe à chaque variable propositionnelle une valeur de vérité dans B = {VB (vrai), FB (faux)}.

L’interprétation s’étend aux formules par morphisme sur l’algèbre de Boole :

• [V]I = VB, [F]I = FB
• [⎤ A]I = ⎤B [A]I
• [A ∨ B]I = [A]I ∨B [B]I
• [A ∧ B]I = [A]I ∧B [B]I
• [A ⇒ B]I = [A]I ⇒B [B]I
• [A ⇔ B]I = [A]I ⇔B [B]I

Tables de vérité

Le résultat de l’interprétation d’une formule selon toutes les interprétations possibles se présente sous forme d’une table de vérité, avec 2^n lignes pour n variables.

Exemple : table de vérité de A = p ∧ (q ⇒ p)

[p]I	[q]I	[q ⇒ p]I	[A]I
VB	VB	VB	VB
VB	FB	VB	VB
FB	VB	FB	FB
FB	FB	VB	FB

Définitions importantes

• Formule vraie dans une interprétation I : [A]I = V (on dit que I satisfait A, notation I ╞ A)
• Formule valide (tautologie) : vraie dans toute interprétation (╞ A)
• Formule insatisfiable (contradiction) : fausse dans toute interprétation
• Formule satisfiable : vraie dans au moins une interprétation

Exemples

• ((p ⇒ q) ∧ p) ⇒ p est une tautologie
• (p ⇒ q) ∧ (p ∧ ⎤ q) est une contradiction
• p ∧ (q ⇒ p) est satisfiable mais pas valide

Relations entre validité et satisfiabilité

• Une tautologie est toujours satisfiable, mais l’inverse est faux
• Une contradiction est toujours insatisfiable, mais l’inverse est faux
• Une formule ne peut jamais être à la fois valide et insatisfiable

Propriétés classiques

• (p ∨ ⎤ p) est une tautologie (tiers exclu)
• (p ∧ ⎤ p) est une contradiction
• Plus généralement, (p ∨ A ∨ ⎤ p ∨ B) est une tautologie
• Et (p ∧ B ∧ ⎤ p ∧ C) est une contradiction

Conséquence et équivalence sémantiques

• A est conséquence sémantique de B (notation B ╞ A) si tout modèle de B est un modèle de A
• A est équivalente sémantiquement à B (notation A ≡ B) si B ╞ A et A ╞ B

Propriétés importantes :

• B ╞ A ssi B ⇒ A est une tautologie
• B ≡ A ssi B ⇔ A est une tautologie
• Si B ≡ A et ╞ B alors ╞ A

Algèbre de Boole et lois classiques

• Associativité : A ∨ (B ∨ C) ≡ (A ∨ B) ∨ C, A ∧ (B ∧ C) ≡ (A ∧ B) ∧ C
• Commutativité : A ∨ B ≡ B ∨ A, A ∧ B ≡ B ∧ A
• Distributivité : A ∧ (B ∨ C) ≡ (A ∧ B) ∨ (A ∧ C), A ∨ (B ∧ C) ≡ (A ∨ B) ∧ (A ∨ C)
• Lois de De Morgan : ⎤ (A ∨ B) ≡ ⎤ A ∧ ⎤ B, ⎤ (A ∧ B) ≡ ⎤ A ∨ ⎤ B
• Idempotence : A ∨ A ≡ A, A ∧ A ≡ A
• Absorption : A ∧ (A ∨ B) ≡ A, A ∨ (A ∧ B) ≡ A
• Éléments neutres : A ∧ V ≡ A, A ∨ F ≡ A
• Éléments absorbants : A ∧ F ≡ F, A ∨ V ≡ V
• Inverse et involution : ⎤ V ≡ F, ⎤ F ≡ V, ⎤ ⎤ A ≡ A

Systèmes complets de connecteurs

Un système complet de connecteurs est un ensemble de connecteurs permettant de définir tous les autres connecteurs propositionnels.

• {∨, ∧, ⎤, ⇒} est complet (car p ⇔ q ≡ (p ⇒ q) ∧ (q ⇒ p))
• {∨, ∧, ⎤} est complet (car p ⇒ q ≡ ⎤ p ∨ q)
• {∧, ⎤} est complet (car p ∨ q ≡ ⎤ (⎤ p ∧ ⎤ q))
• {∨, ⎤} est complet (car p ∧ q ≡ ⎤ (⎤ p ∨ ⎤ q))
• {⎤} seul n’est pas complet (un connecteur binaire est nécessaire)

Satisfiabilité d’un ensemble de formules

Soient ℰ et ℱ des ensembles de formules, et I une interprétation :

• ℰ est satisfait par I si I satisfait toutes les formules de ℰ
• ℰ est satisfiable s’il existe au moins une interprétation qui satisfait ℰ
• ℰ est finiment satisfiable si tout sous-ensemble fini de ℰ est satisfiable
• ℰ est contradictoire (insatisfiable) si ℰ n’a aucun modèle
• Une formule B est conséquence logique de ℰ (notation ℰ ╞ B) si tout modèle de ℰ est modèle de B
• ℰ et ℱ sont équivalents (ℰ ≡ ℱ) si elles ont les mêmes modèles

Théorème de compacité

• ℰ est satisfiable ssi ℰ est finiment satisfiable
• ℰ est contradictoire ssi ℰ admet un sous-ensemble fini contradictoire
• Pour toute formule B, B est conséquence de ℰ ssi B est conséquence d’une partie finie de ℰ

Propriétés supplémentaires

• ℰ ╞ A ssi ℰ ∪ {⎤ A} est contradictoire
• Si ℰ est satisfiable et ℱ ⊆ ℰ alors ℱ est satisfiable
• Si ℰ est contradictoire et ℰ ⊆ ℱ alors ℱ est contradictoire
• ℰ ∪ {A} ╞ B ssi ℰ ╞ (A ⇒ B)
• {A1, …, An} ╞ B ssi ╞ ((A1 ∧ … ∧ An) ⇒ B)
• Une tautologie est conséquence logique de l’ensemble vide
• ℰ est contradictoire ssi ℰ ╞ (A ∧ ⎤ A) pour une formule A
• Un ensemble fini de formules est équivalent à la conjonction de ses formules

Exemple d’application

Énoncé :

« Si je travaille bien alors je vais réussir. Si je suis malade, je ne peux pas bien travailler. Or je suis malade mais je travaille bien. Donc je vais réussir. »

Variables propositionnelles :

• t : « bien travailler »
• m : « être malade »
• r : « réussir »

Modélisation :

• H1 : t ⇒ r
• H2 : m ⇒ ⎤ t
• H3 : m ∧ t
• C : r

Vérification :

{H1, H2, H3} ╞ C ssi ((t ⇒ r) ∧ (m ⇒ ⎤ t) ∧ (m ∧ t)) ╞ r

soit :

╞ (((t ⇒ r) ∧ (m ⇒ ⎤ t) ∧ (m ∧ t)) ⇒ r)

Remarque : cet ensemble est contradictoire, donc toute conclusion est logiquement conséquence de cet ensemble.

Glossaire des termes clés

• Atome : variable propositionnelle élémentaire (ex. p, q)
• Formule propositionnelle : mot construit selon les règles syntaxiques du calcul propositionnel
• Connecteurs logiques : symboles unaires ou binaires (⎤, ∨, ∧, ⇒, ⇔) permettant de construire des formules
• Interprétation : application associant à chaque variable une valeur de vérité (VB ou FB)
• Table de vérité : tableau listant les valeurs de vérité d’une formule selon toutes les interprétations possibles
• Tautologie : formule vraie dans toutes les interprétations
• Contradiction : formule fausse dans toutes les interprétations
• Satisfiabilité : existence d’une interprétation qui rend la formule vraie
• Conséquence sémantique (B ╞ A) : tout modèle de B est aussi un modèle de A
• Équivalence sémantique (A ≡ B) : A et B ont les mêmes modèles
• Forme normale disjonctive (FND) : disjonction de conjonctions de littéraux
• Forme normale conjonctive (FNC) : conjonction de disjonctions de littéraux
• Littéral : atome ou négation d’atome
• Système complet de connecteurs : ensemble minimal de connecteurs permettant d’exprimer tous les autres

Points clés à retenir

• Le langage propositionnel est défini par un alphabet et des règles syntaxiques précises.
• Chaque formule a une unique décomposition en arbre, garantissant l’absence d’ambiguïté.
• L’interprétation attribue une valeur de vérité à chaque formule selon les règles de l’algèbre de Boole.
• Une formule peut être tautologie, contradiction, satisfiable ou insatisfiable selon ses valeurs sous toutes les interprétations.
• Le calcul propositionnel est décidable grâce aux tables de vérité.
• Les connecteurs logiques obéissent à des lois algébriques classiques (associativité, distributivité, lois de De Morgan, etc.).
• Les formes normales (FNC et FND) permettent de standardiser les formules pour faciliter leur traitement.
• Le théorème de compacité relie satisfiabilité d’ensembles infinis à celle de leurs sous-ensembles finis.
• La substitution permet de remplacer des variables par des formules, avec des règles précises sur l’ordre d’application.
• Les systèmes complets de connecteurs minimaux permettent de construire tous les connecteurs logiques.