Interprétation booléenne

Satisfiabilité et tautologie
Complétude fonctionnelle
Équivalence de formules
Conséquence sémantique
Formes normales

Logique propositionnelle
Sémantique

Igor Stéphan

UFR Sciences Angers

2020-2021

1/ 120
Igor Stéphan L0 .Sem
 Interprétation booléenne
Satisfiabilité et tautologie
Complétude fonctionnelle
Équivalence de formules
Conséquence sémantique
Formes normales

Plan

1 Interprétation booléenne

2 Satisfiabilité et tautologie

3 Complétude fonctionnelle

4 Équivalence de formules

5 Conséquence sémantique

6 Formes normales
2/ 120
Igor Stéphan L0 .Sem
 Interprétation booléenne
Satisfiabilité et tautologie
Complétude fonctionnelle
Équivalence de formules
Conséquence sémantique
Formes normales

L’ensemble des valeurs de vérité et la valuation

Définition 4 (ensemble des valeurs de vérité)

L’ensemble des valeurs de vérité est BOOL = {vrai, faux}.

Définition 5 (valuation)
Une valuation v est une fonction qui assigne à chaque symbole
propositionnel une valeur de vérité.

L’ensemble des symboles propositionnels est infini (et

dénombrable)
À chaque symbole est assigné une valeur de vérité

3/ 120
Igor Stéphan L0 .Sem
 Interprétation booléenne
Satisfiabilité et tautologie
Complétude fonctionnelle
Équivalence de formules
Conséquence sémantique
Formes normales

Bivalence et vérifonctionnalité

La définition de la sémantique de la logique propositionnelle

repose sur deux postulats
La bivalence : toute formule propositionnelle, selon une
valuation donnée, a une et une seule valeur de vérité qui est
soit vrai soit faux
La vérifonctionnalité : la valeur de vérité d’une formule
propositionnelle dépend uniquement de la valeur de vérité des
symboles propositionnels et fonctionnellement des
sous-formules qui la composent

4/ 120
Igor Stéphan L0 .Sem
 Interprétation booléenne
Satisfiabilité et tautologie
Complétude fonctionnelle
Équivalence de formules
Conséquence sémantique
Formes normales

Sémantique des constantes et connecteurs

À chaque connecteur logique est associée une fonction à
valeur dans BOOL qui en définit sa sémantique
Définition 6 (sémantique des constantes et connecteurs)
i⊥ :→ BOOL i� :→ BOOL i¬ : BOOL → BOOL
x i¬ (x)
i⊥ = faux i� = vrai vrai faux
faux vrai
i∧ , i∨ , i→ , i↔ : BOOL × BOOL → BOOL
x y i∧ (x, y ) i∨ (x, y ) i→ (x, y ) i↔ (x, y )
vrai vrai vrai vrai vrai vrai
vrai faux faux vrai faux faux
faux vrai faux vrai vrai faux
faux faux faux faux vrai vrai
5/ 120
Igor Stéphan L0 .Sem
 Interprétation booléenne
Satisfiabilité et tautologie
Complétude fonctionnelle
Équivalence de formules
Conséquence sémantique
Formes normales

Interprétation booléenne

Définition 7 (interprétation booléenne)

Une interprétation booléenne selon une valuation v est une
fonction notée v ∗ : PROP → BOOL définie inductivement par :

v ∗ (⊥) = i⊥
v ∗ (�) = i�
v ∗ (p) = v (p) pour tout p ∈ SP
v ∗ (¬F ) = i¬ (v ∗ (F )) pour tout F ∈ PROP
v ∗ ((F ∗ G )) = i∗ (v ∗ (F ), v ∗ (G )) pour tout F , G ∈ PROP
et ∗ ∈ {∧, ∨, →, ↔}.

6/ 120
Igor Stéphan L0 .Sem
 Interprétation booléenne
Satisfiabilité et tautologie
Complétude fonctionnelle
Équivalence de formules
Conséquence sémantique
Formes normales

Unicité du résultat du calcul de l’interprétation

Théorème 3
L’interprétation booléenne d’une formule propositionnelle selon une
valuation est unique.

7/ 120
Igor Stéphan L0 .Sem
 Interprétation booléenne
Satisfiabilité et tautologie
Complétude fonctionnelle
Équivalence de formules
Conséquence sémantique
Formes normales

Exemple de calcul de l’interpration booléenne

Exemple 4
Calculons la valeur de vérité pour la formule propositionnelle
((¬r ∨ q) → (q ∧ r )) pour la valuation v (r ) = vrai et v (q) = faux.

v ∗ (((¬r ∨ q) → (q ∧ r )))
= i→ (v ∗ ((¬r ∨ q)), v ∗ ((q ∧ r ))) [Définition 7]
= i→ (i∨ (v ∗ (¬r ), v ∗ (q)), i∧ (v ∗ (q), v ∗ (r ))) [Définition 7]
= i→ (i∨ (i¬ (v ∗ (r )), v ∗ (q)), i∧ (v ∗ (q), v ∗ (r ))) [Définition 7]
= i→ (i∨ (i¬ (v (r )), v (q)), i∧ (v (q), v (r ))) [Définition 7]
= i→ (i∨ (i¬ (vrai), faux), i∧ (faux, vrai)) [Définition de v ]
= i→ (i∨ (faux, faux), faux) [Définition 6]
= i→ (faux, faux) [Définition 6]
= vrai [Définition 6]

8/ 120
Igor Stéphan L0 .Sem
 Interprétation booléenne
Satisfiabilité et tautologie
Complétude fonctionnelle
Équivalence de formules
Conséquence sémantique
Formes normales

Exercice 4
Soient les symboles propositionnels pl, mo, na, ti et la valuation v
telle que v (pl) = vrai, v (mo) = faux, v (na) = faux et
v (ti) = vrai.
Calculer l’interprétation booléenne de la formule propositionnelle

((pl → mo) → (((na → mo) ∧ ((¬pl ∧ ti) → na)) → (ti → mo)))

pour la valuation v .

9/ 120
Igor Stéphan L0 .Sem
 Interprétation booléenne
Satisfiabilité et tautologie
Complétude fonctionnelle
Équivalence de formules
Conséquence sémantique
Formes normales

Seul les symboles propositionnels de la formule compte

Théorème 4
Soient v et v � deux valuations quelconques identiques sur les
symboles propositionnels présents dans une proposition F alors
v ∗ (F ) = v �∗ (F ).

10/ 120
Igor Stéphan L0 .Sem
 Interprétation booléenne
Satisfiabilité et tautologie
Complétude fonctionnelle
Équivalence de formules
Conséquence sémantique
Formes normales

Table de vérité

Définition 8 (table de vérité)

Une table de vérité pour une formule propositionnelle contenant n
symboles propositionnels distincts est constituée sur les n
premières colonnes de l’ensemble des 2n combinaisons possibles sur
les valeurs de vérité pour les symboles propositionnels et d’une
dernière colonne contenant l’interprétation booléenne
correspondante de la formule propositionnelle.

11/ 120
Igor Stéphan L0 .Sem
 Interprétation booléenne
Satisfiabilité et tautologie
Complétude fonctionnelle
Équivalence de formules
Conséquence sémantique
Formes normales

Table de vérite

Une table de vérité peut contenir aussi les calculs

intermédiaires sur les sous-formules

Exemple 5

F = ((¬r ∨ q) → (q ∧ r ))

v (r ) v (q) v ∗ (¬r ) v ∗ ((¬r ∨ q)) v ∗ ((q ∧ r )) v ∗ (F )

vrai vrai faux vrai vrai vrai
vrai faux faux faux faux vrai
faux vrai vrai vrai faux faux
faux faux vrai vrai faux faux
12/ 120
Igor Stéphan L0 .Sem
 Interprétation booléenne
Satisfiabilité et tautologie
Complétude fonctionnelle
Équivalence de formules
Conséquence sémantique
Formes normales

Remplacement et valuation

Théorème 5
Soient F , G1 , . . . , Gn des formules propositionnelles, p1 , . . ., pn des
symboles propositionnels et une valuation v . La valuation v ’ est
définie par :

v � (p) = v (p) si p �∈ {p1 , . . . , pn }

v � (p) = v ∗ (Gi ) si p = pi pour un i, 1 ≤ i ≤ n.

Alors v ∗ ([p1 ← G1 , . . . , pn ← Gn ](F )) = v �∗ (F ).

13/ 120
Igor Stéphan L0 .Sem
 Interprétation booléenne
Satisfiabilité et tautologie
Complétude fonctionnelle
Équivalence de formules
Conséquence sémantique
Formes normales

Remplacement et valuation

Exemple 6
t, q, r ∈ SP et A = (((t → q) ∧ (¬q → r )) ∧ (t ∨ r ))
Soient p1 , p2 ∈ SP, la fonction de remplacement
σ = [p1 ← (t → q), p2 ← (t ∨ r )] et
F = ((p1 ∧ (¬q → r )) ∧ p2 ) telle que σ(F ) = A
v (t) v (q) v (r ) v � (p1 ) v � (p2 ) v ∗ (A)
= v � (r ) = v ∗ ((t → q)) = v ∗ ((t ∨ r )) = v �∗ (F )
vrai vrai vrai vrai vrai vrai
vrai vrai faux vrai vrai vrai
vrai faux vrai faux vrai faux
vrai faux faux faux vrai faux
faux vrai vrai vrai vrai vrai
faux vrai faux vrai faux faux
faux faux vrai vrai vrai vrai
faux faux faux vrai faux faux

14/ 120
Igor Stéphan L0 .Sem
 Interprétation booléenne
Satisfiabilité et tautologie
Complétude fonctionnelle
Équivalence de formules
Conséquence sémantique
Formes normales

Conséquence du théorème 5

Calcul pour des formules propositionnelles sans avoir recours

aux valeurs de vérité associées aux symboles propositionnels
Dans l’exemple suivant la valeur de vérité de la formule
A = (¬B ∧ B) va être calculée sans connaı̂tre ce qu’est B

Exemple 7
Prenons q ∈ SP et F = (¬q ∧ q)
Pour toute valuation v , la valuation v � est telle que v � (q) = v ∗ (B)
Par le théorème 5, v �∗ ((¬q ∧ q)) = v ∗ ([q ← B](¬q ∧ q))
Or A = [q ← B](¬q ∧ q) donc v ∗ (A) = v �∗ ((¬q ∧ q))
Or v �∗ ((¬q ∧ q)) = i∧ (v �∗ (¬q), v �∗ (q)) = i∧ (i¬ (v �∗ (q)), v �∗ (q)) = i∧ (i¬ (v � (q)), v � (q))
Donc, que v � (q) = vrai ou v � (q) = faux, v �∗ ((¬q ∧ q)) = faux donc v ∗ (A) = faux.

15/ 120
Igor Stéphan L0 .Sem
 Interprétation booléenne
Satisfiabilité et tautologie
Complétude fonctionnelle
Équivalence de formules
Conséquence sémantique
Formes normales

Exercice 5
Soient les symboles propositionnels t et q, et la proposition

A = (((t ∧ ¬q) ∨ ¬q) → ((t ∧ ¬q) ∨ ¬q)).

Démontrer grâce au théorème 5 que pour toute valuation v ,

v ∗ (A) = vrai.

16/ 120
Igor Stéphan L0 .Sem
 Interprétation booléenne
Satisfiabilité et tautologie
Complétude fonctionnelle
Équivalence de formules
Conséquence sémantique
Formes normales

Table de vérité sur des variable de formule

Exemple 8
Calculons la table de vérité pour la formule propositionnelle
F = ((A ∧ B) ↔ (A ∨ B)) avec A, B ∈ PROP.

v ∗ (A) v ∗ (B) v ∗ ((A ∧ B)) v ∗ ((A ∨ B)) v ∗ (F )

vrai vrai vrai vrai vrai
vrai faux faux vrai faux
faux vrai faux vrai faux
faux faux faux faux vrai

Cette table de vérité a été établie en choisissant la formule

propositionnelle ((r ∧ q) ↔ (r ∨ q)) et la valuation v � définie par
v � (r ) = v ∗ (A) et v � (q) = v ∗ (B).
17/ 120
Igor Stéphan L0 .Sem