2 Sémantique, théorie des modèles
| F |
¾® |
{v,f} |
| formule |
¾® |
modèle |
Définition 5
On appelle valuation ou interprétation une application I
de Vp vers {v,f}
Propriété 2
Soit I une interprétation, A,B des formules. L'application
I de F dans {v,f} existe:
|
si |
AÎ Vp |
|
ssi |
|
|
ssi |
|
|
ssi |
|
|
ssi |
|
|
ssi |
|
Définition 6
On note I(A)=v par
I |= A
pour ``A est satisfiable pour I'', `` I
satisfait A'', `` I est un modèle de A''.
Définition 7
Une formule A est satisfiable
si il existe une interprétation qui la satisfait
Les interprétations peuvent être représentées par une table de vérité :
| A |
B |
A Ù B |
A ® B |
¬ A |
... |
|
v |
v |
v |
v |
f |
... |
| f |
v |
f |
v |
v |
... |
| v |
f |
f |
f |
f |
... |
| f |
f |
f |
v |
v |
... |
Remarque : l'implication est classique (non
intuitioniste ou constructive).
Exemple : construire la table pour (a ® b) ® (b ® c)
2.1 Tautologies, équivalences, conséquence valide
Définition 8
Une tautologie est une formule vraie pour toute valuation
|= A
Propriété 3
Soit A une formule, p1...pn les variables apparaissant dans A.
Soient A1 ...An des formules et A*=def A[p1¬
A1]...[pn¬ An] une instance de A.
Si |= A alors |= A*.
Exemple : |= p ® p donc |= (p ® q) ® (p ® q).
Attention : la réciproque est fausse.
Définition 9
A est équivalent à B, Aº B, ssi pour toute valuation I,
I(A)= I(B).
Propriété 4
Aº B si et seulement si |= A « B.
Quelques équivalences de base :
| A ® B |
º |
¬ A Ú B |
|
| p Ù q |
º |
¬ (¬ p Ú ¬ q) |
loi de Morgan |
| p Ù q |
º |
q Ù p |
commutativité |
| p Ù p |
º |
p |
idempotence |
| p Ù (q Ú r) |
º |
(p Ù q) Ú (p Ù r) |
distributivité |
| p Ù (q Ù r) |
º |
(p Ù q) Ù r |
associativité |
Propriété 5
{ Ù , ¬ } est un ensemble complet de connecteurs, i.e. pour toute
formule A, il existe A*º A telle que A* ne s'écrit qu'avec ces deux connecteurs.
Exemple : transformer (p ® q) ® ((p Ù q) « p)
Définition 10
Soient A1...An, B des formules. B est conséquence de A1...An
A1... An |= B
ssi pour toute valuation I, si I(A1)=...= I(An)=v alors I(B)=v.
Remarque : A1,... An|= B ssi A1 Ù ... Ù An|= B
Propriété 6
A|= B ssi |= A ® B
Preuve : Þ :" I, si I(A)=v alors I(B)=v (car A|=
B) donc I(A ® B)=v, si I(A)=f alors I(A ® B)=v.
Ü : " I, I(A ® B)=v donc si I(A)=v alors
I(B)=v par définition de I( ® ).
Propriété 7
Réfutation : A1,...,An|= A ssi non (|=A1 Ù ... Ù An Ù ¬ A).
Preuve : Exercice.