Skip to main content Informatique en prépa - Lycée Malherbe 

5- Logique propositionnelle

I. Syntaxe

Définition : formule propositionnelle

On se donne un ensemble de variables. On définit inductivement les formules propositionnelles comme :

  • (cas de base) , pour ;
  • (induction) si et sont des formules :
    • , la négation de ;
    • , la conjonction ;
    • , la disjonction.

, et sont des connecteurs logiques d'arité 1, 2 et 2 respectivement.

Définition : connecteurs supplémentaires

On utilise parfois des connecteurs logiques supplémentaires :

  • ou pour l'équivalence ;
  • ou pour l'implication ;
  • , ou , pour le "faux" ;
  • , ou , pour le "vrai".

Ces symboles pourront être exprimés à partir des symboles de base.

Par exemple, est une formule propositionnelle. Les formules peuvent être représentées sous forme d'arbre :

et ∧ ou1 ∨ et--ou1 ou2 ∨ et--ou2 a1 a ou1--a1 b b ou1--b non ¬ ou2--non c c ou2--c a2 a non--a2
Définition : hauteur et taille

On définit :

  • la taille d'une formule comme le nombre de symboles nécessaires pour l'écrire ;
  • la hauteur d'une formule comme la hauteur de l'arbre correspondant.

Par exemple, est de taille 8 et de hauteur 3.

II. Sémantique

On va maintenant donner un sens à nos formules.

Définition : valuation

On appelle valuation une application . On note .

Définition : valeur de vérité

Pour une valuation, on définit par induction la valeur de vérité d'une formule :

  • pour , ;
  • si , sont des formules avec une valeur de vérité et , alors : avec le "non", le "et" et le "ou" usuels.

Si , on dit que est un modèle de .

Définition : satisfiabilité

On dit qu'une formule est :

  • satisfiable si elle a un modèle ;
  • une tautologie si pour toute valuation , est un modèle de .
Définition : équivalence de deux formules

Deux formules et sont équivalentes si On note alors .

L'outil ci-dessous calcule la table de vérité d'une formule (et son arbre, avec sa taille et sa hauteur). Avec une deuxième formule, il vérifie si elles sont équivalentes :

(ou au clavier : ~ & | -> <->)
abc(a ∨ b) ∧ (¬a ∨ c)
0000
0010
0101
0111
1000
1011
1100
1111

Taille : 8, hauteur : 3

f est satisfiable (4 modèles sur 8 valuations), mais pas une tautologie.

III. Simplification de formules

Grâce à la notion d'équivalence, on peut simplifier ou reformuler les formules, à l'aide d'opérations.

Propriétés : opérations sur les formules
  1. Distributivité : et sont distributives l'une sur l'autre :
  2. Tiers exclu : (c'est une tautologie).
  3. Lois de De Morgan :
Propriétés : réécriture de l'implication et de l'équivalence

On peut réécrire l'implication et l'équivalence avec les autres opérateurs :

Simplifiez au maximum la formule suivante :

é

Vérification avec les tables de vérité :

(ou au clavier : ~ & | -> <->)
ab¬(¬a ∨ ¬b) ∨ (b ∧ ¬a)b
0000
0111
1000
1111

Taille : 11, hauteur : 4

f est satisfiable (2 modèles sur 4 valuations), mais pas une tautologie.

f et g sont équivalentes : f ≡ g.

IV. Conséquence logique

Définition : modèle d'un ensemble de formules

Soit un ensemble de formules. On dit qu'une valuation est un modèle de si elle est un modèle de chacune de ses formules.

Définition : conséquence logique d'un ensemble de formules

Soit un ensemble de formules. Une formule est une conséquence logique de si tout modèle de est un modèle de .

On note alors . Quand est vide, signifie que est une tautologie.

Par exemple, : dans la table de vérité, la seule valuation qui rend vraies et est , et elle rend vraie.

001
011
100
111

si et seulement si la formule est une tautologie.

V. Formes normales

Définition : littéral

Un littéral est soit une variable, soit la négation d'une variable.

Définition : clause

Une clause conjonctive (resp. disjonctive) est une conjonction (resp. disjonction) de littéraux.

Conjonction = "et", disjonction = "ou".

Définition : formes normales

Une formule est :

  1. en forme normale conjonctive si c'est une conjonction de clauses disjonctives, c'est-à-dire qu'elle est de la forme :
  2. en forme normale disjonctive si c'est une disjonction de clauses conjonctives, c'est-à-dire qu'elle est de la forme :

La forme la plus courante est la forme normale conjonctive, et donc on dit parfois simplement "clause" au lieu de "clause disjonctive".

Propriété : lien avec la table de vérité

Une formule est en forme normale disjonctive complète si chaque clause contient toutes les variables.

Dans ce cas, pour remplir la table de vérité, il suffit de mettre un "1" sur la ligne correspondant à chaque clause, et un "0" sur les autres.

Par exemple, est en forme normale disjonctive complète, et sa table de vérité est :

001
010
100
111

VI. Le problème SAT

On a plusieurs problèmes très célèbres en informatique : la famille des problèmes SAT.

Définition : problèmes SAT
  • SAT : étant donné une formule, est-elle satisfiable ?
  • CNF-SAT : étant donné une formule en forme normale conjonctive, est-elle satisfiable ?
  • k-SAT : étant donné une formule en forme normale conjonctive avec au plus littéraux par clause, est-elle satisfiable ?

Exemples d'instances de ces problèmes :

Théorème (hors programme)

3-SAT est NP-complet. Il en découle que SAT, CNF-SAT, et k-SAT pour le sont aussi.

Globalement, un problème NP-complet est un problème qui ne peut a priori pas être résolu en temps polynomial : c'est donc un problème (très) difficile. Cela vaut si , ce qui n'a pas été démontré.

Le problème SAT est important car il est assez facile d'"encoder" plein d'autres problèmes avec, et de montrer que ceux-ci sont également NP-complets.

Exercices

Exercice 1

Montrer que (la contraposée), par un calcul, puis en vérifiant avec l'outil de table de vérité.

.

Exercice 2

Mettre la formule sous forme normale conjonctive, puis sous forme normale disjonctive.

FNC : . FND (d'après la table de vérité, vraie quand et ont la même valeur) : .

Exercice 3

A-t-on ? Et ?

  • Oui : si est vraie, est fausse, et comme est vraie, est vraie.
  • Non : la valuation , rend vraies et , mais pas .
(ou au clavier : ~ & | -> <->)
ab(a → b) ∧ (b → a)(a ∧ b) ∨ (¬a ∧ ¬b)
0011
0100
1000
1111

Taille : 7, hauteur : 2

f est satisfiable (2 modèles sur 4 valuations), mais pas une tautologie.

f et g sont équivalentes : f ≡ g.