02:

Logique propositionnelle
- Sémantique -

1
 Plan
1-Introduction
2- Valuation (assignation, système de valeurs)
3- Interprétation
4- Analyse sémantique (analyse de Vérité) d'une formule
5- Formules propositionnelles synonymes/équivalentes
6- Formes normales d'une formule propositionnelle
7- Satisfaisabilité et validité d'une formule
8- Modèle
9- Compatibilité
10- Conséquence logique (conséquence tautologique)

2
 1. Introduction
 Le rôle de la sémantique est de préciser le sens.
 Pour la logique propositionnelle, le seul sens d'une
formule est sa valeur de vérité (i.e la propriété d'être
vraie ou fausse)
 L'ensemble des valeurs de vérité est {0,1} où :
1 représente le Vrai et 0 représente le faux
 Pour la logique propositionnelle, la sémantique des
formules obéit au deux principes suivants :
• Bivalence : une formule est soit vraie, soit fausse
• Vérifonctionnalité : la valeur de vérité d'une formule
non-atomique est déterminée par les valeurs de ses
constituants.
3
 Il existe des logiques non bivalentes, par exemple
on peut définir :

• 3 valeurs de vérité {0,1/2,1} ⟶ logique

trivalente

• infinité de valeurs [0,1] ⟶ logique multivaluée

(floue, probabiliste)

 Il existe des logiques qui n’obéissent pas au principe

de vérifonctionnalité, par exemple: la logique modale

4
 Plan
1-Introduction
2- Valuation (assignation, système de valeurs)
3- Interprétation
4- Analyse sémantique (analyse de Vérité) d'une formule
5- Formules propositionnelles synonymes/équivalentes
6- Formes normales d'une formule propositionnelle
7- Satisfaisabilité et validité d'une formule
8- Modèle
9- Compatibilité
10- Conséquence logique (conséquence tautologique)

5
2. Valuation (assignation, système de valeurs)

Définition:
 Une valuation est une fonction V de l'ensemble
des variables propositionnelles VAR vers
l'ensemble des valeurs de vérités {0,1}

V : Var ⟶ {0,1}

 Une valuation affecte à chaque variable

propositionnelle de Var une valeur de vérité

6
Exemple

V1 V2
A A
0 0
B B
1 1
C C

V1(A)=0 V1(B)=1 V1(C )=1 V2(A)=0 V2(B)=0 V2(C )=1

7
 Si var contient n variables on a 2ⁿ valuations
possibles
Exemple :
n=3 n=2
A B C A B
V1 ⟶ 0 0 0 V1 ⟶ 0 0
V2 ⟶ 0 0 1 V2 ⟶ 0 1
V3 ⟶ 0 1 0 V3 ⟶ 1 0
V4 ⟶ 0 1 1 V4 ⟶ 1 1
V5 ⟶ 1 0 0
V6 ⟶ 1 0 1
V7 ⟶ 1 1 0
V8 ⟶ 1 1 1

8
 Plan
1-Introduction
2- Valuation (assignation, système de valeurs)
3- Interprétation
4- Analyse sémantique (analyse de Vérité) d'une formule
5- Formules propositionnelles synonymes/équivalentes
6- Formes normales d'une formule propositionnelle
7- Satisfaisabilité et validité d'une formule
8- Modèle
9- Compatibilité
10- Conséquence logique (conséquence tautologique)

9
 3. interprétation
 Pour chaque valuation V, il existe une
application unique qui prolonge V et qui est
définie de l'ensemble des formules
propositionnelles dans {0,1}.
FP
[ ]v
A
B
C 0
Av B
B A 1

ACA
….

10
 Cette application est appelée:
interprétation des FP dans V
et elle est notée par : [ ]V

 La signification d'une formule j dépend des

valeurs de vérité des variables qu'elle contient et
de la sémantique des connecteurs
(vérifonctionnalité).

11
 La sémantique des connecteurs logiques est
donnée par les tables suivantes :

A B A B AVB A B A B
A A
0 1 0 0 0 0 1 1

1 0 0 1 0 1 1 0
1 0 0 1 0 0
1 1 1 1 1 1

12
 L'interprétation (ou sémantique) d'une formule j
dans la valuation V est notée [j]v et est définie par :

 Si j est une variable propositionnelle alors

[j]v =V(j)

 Si j=  j' alors [j]v =  [j' ]v

 Si j = j' K j" alors [j]v = [j' ]v K [j" ]v

K  {,, ,}
Exemple: Soient V1 la valuation définie par: V1(A)=0,
V1(B)=1, V1(C)=1 et la formule: j= (AB)C
[j]v1 = 1
13
Exemple
 Soient V1 la valuation définie par :
V1(A)=0, V1(B)=1, V1(C)=1
et la formule : j= (AB)C

14
 Plan
1-Introduction
2- Valuation (assignation, système de valeurs)
3- Interprétation
4- Analyse sémantique (analyse de Vérité) d'une formule
5- Formules propositionnelles synonymes/équivalentes
6- Formes normales d'une formule propositionnelle
7- Satisfaisabilité et validité d'une formule
8- Modèle
9- Compatibilité
10- Conséquence logique (conséquence tautologique)

15
 4. Analyse sémantique (analyse de Vérité)
d'une formule
L'analyse de vérité d'une formule propositionnelle j consiste
à étudier sa valeur pour toutes les valuations possibles des
variables propositionnelles qu'elle contient.

Ceci revient à trouver une fonction Fj qui associe à chaque

valuation V des VP de j l'interprétation de j dans V.

Fj : {V1,V2,…Vn}  {0,1}
Fj(V)= [j]v

Fj
V1 [j]v1
V2 [j]v2
… …..

Vn [j]vn
16
 L'analyse de vérité peut être faite de deux
manières:

4-1 Table de Vérité

4-2 Diagramme de Quine

17
 4-1 Table de Vérité

Description de la méthode

 Soient A1,A2,….An des VP de la formule j

 On énumère toutes les valuations possibles

sur l'ensemble {A1,..An} (soit 2n valuations)

 Pour chaque valuation V on calcule [j]v

18
Exemple:
j = (AB)C
Fj
A B C AB (AB)C
0 0 0 0 1
0 0 1 0 1
0 1 0 0 1
0 1 1 0 1
1 0 0 0 1
1 0 1 0 1
1 1 0 1 0
1 1 1 1 1

19
 Quand le nombre de variables augmente :
 nombre total de valuations possibles augmente

 nombre de lignes de la table de vérité augmente

 Quand la formule j est longue :

 nécessité de calculs intermédiaires sur les sous
formules de j
 nombre de colonnes de la table de vérité
augmente

20
 4-2 Diagramme de Quine
 Description de la méthode

 Soient A1,A2,..An les VP de la FP j

 Choisir une variable Ai

 On remplace à gauche Ai par 0 , et à droite par 1

 On effectue les calculs possibles (pour

simplifier sémantiquement j)

 On répète la procédure pour les

formules obtenues jusqu'à ce qu'il n'ait plus de
VP
21
Exemple: j = (AB)C

(AB)C
0 A 1

(0  B) C (1  B) C
BC
0 C
0 B 1
1
0C 1C

1 0 C 1
A B C j
0 ∀ ∀ 1 10 11
1 0 ∀ 1 0 1
1 1 0 0
1 1 1 1

22
 j = (AB)C

Analyse de j par
la table de vérité
Analyse de j par A B C AB (AB)C
la méthode de Quine
0 0 0 0 1
A B C j 0 0 1 0 1
0 ∀ ∀ 1 0 1 0 0 1
1 0 ∀ 1 0 1 1 0 1
1 1 0 0 1 0 0 0 1
1 1 1 1 1 0 1 0 1
1 1 0 1 0
1 1 1 1 1

23
 Plan
1-Introduction
2- Valuation (assignation, système de valeurs)
3- Interprétation
4- Analyse sémantique (analyse de Vérité) d'une formule
5- Formules propositionnelles synonymes/équivalentes
6- Formes normales d'une formule propositionnelle
7- Satisfaisabilité et validité d'une formule
8- Modèle
9- Compatibilité
10- Conséquence logique (conséquence tautologique)

24
 5. Formules propositionnelles
synonymes/équivalentes
Formules synonymes

Définition :
Deux formules j1 et j2 sont synonymes ssi pour toute
valuation V, j1 et j2 ont même interprétation.

j1 synonyme de j2   V [j1]V=[j2]V

Exemple :
AvB AvB
(AB) AvB
AvB v(C C) AvB
25
 Formules équivalentes

Définition :

j1 synonyme de j2
j1 et j2 équivalentes et
j1 et j2 ont les mêmes variables

Exemple :

AB , AvB sont équivalentes

AvB v(C C ) AvB synonymes mais non équivalentes

26
 Lemme-1:

j1 synonyme de j2  j1[/A] est synonyme j2[/A]

 Lemme-2:
j1 synonyme de j2  j1[1/A1, .. n/An]
est synonyme de
j2[1/A1, .. n/An]

 Lemme-3:
1 est synonyme de 2  j[1/A] est synonyme j[2/A]

27
 Plan
1-Introduction
2- Valuation (assignation, système de valeurs)
3- Interprétation
4- Analyse sémantique (analyse de Vérité) d'une formule
5- Formules propositionnelles synonymes/équivalentes
6- Formes normales d'une formule propositionnelle
7- Satisfaisabilité et validité d'une formule
8- Modèle
9- Compatibilité
10- Conséquence logique (conséquence tautologique)

28
6. Formes normales d'une formule
En Informatique, et en particulier dans certaines
méthodes de preuve, on exige que la Formule à
traiter soit sous une forme bien particulière.

Par exemple:
 j ne doit contenir que les connecteurs  et 
 j ne doit contenir que les connecteurs  et  et
v
…etc.

Nous allons définir les formes les plus connues.

Nous montrons comment on peut mettre une
Formule sous une forme normale donnée.
29
Quelques définitions :

Atome: On appelle atome une Variable Propositionnelle

Littéral: Un littéral est un atome ou la négation d'un atome

Conjonction élémentaire: est un littéral

ou
une conjonction de littéraux
Exemples :
ABCAD , (AB)C ,  B, B des [Link].
AB , (AB), (AvB)(BC) non conj. élémentaires

Disjonction élémentaire: est un littéral

ou
une disjonction de littéraux
30
 4-1 Forme Normale Négative (FNN)

Définition :
Une formule j est sous forme normale négative (sous
FNN) ssi :
 j est construite avec les connecteurs  v  seulement
et
 le connecteur  n'apparaît que devant les VP
(  ne gouverne pas une  , une v ou une autre  )

Exemples :
AB v C , (AB)v (AC) A , A(BvC) sont sous FNN
AB, A B vC , A (AvB) ne sont pas sous FNN

31
 Lemme:

Toute forme propositionnelle j est synonyme d'une FP

sous FNN
 Méthode de mise sous FNN

1. Eliminer les  et les  en remplaçant

j1j2 par j1vj2
j1j2 par (j1vj2)  (j1 vj2)

2. Utiliser la lois de Morgan pour pousser les

négations vers l'intérieur
(j1j2)=j1vj2 (j1vj2)=j1j2
3. Remplacer les sous formules j par j 35
32
Exemple

33
 4-1 Forme Normale Conjonctive (FNC)

Définition :

Une formule j est sous forme normale conjonctive

(sous FNC) ssi :
j est une disjonction élémentaire
ou
j est une conjonction de disjonctions élémentaires

Exemples:
(AvB)(AvBvC) (AvCvD) (AvD) AvB A
sont sous FNC

34
 Lemme:

Toute forme propositionnelle j est synonyme d'une FP

sous FNC
 Méthode de mise sous FNC (1)

1. Mettre j sous FNN

2. Remplacer toutes les sous-formules :

j1v(j2j3) par (j1vj2)(j1vj3)

distributivité à gauche de v par 

(j2j3)vj1 par (j2vj1) (j3vj1)

distributivité à droite de v par 
35
Exemple

36
 Méthode de mise sous FNC (2)

(Utilisation de la table de vérité)

j=A( BC )
A B C j
0 0 0 1
0 0 1 1
0 1 0 1
0 1 1 1
1 0 0 0
1 0 1 0
1 1 0 0
1 1 1 1
FNC= (AvBvC)  (AvBvC)  (AvBvC)
37
 4-1 Forme Normale Disjonctive (FND)

Définition :

Une formule j est sous forme normale disjonctive

(sous FND) ssi :
j est une conjonction élémentaire
ou
j est une disjonction de conjonctions élémentaires

Exemples:
(AB)v(A  B  C) (ACD) v (A D) AB A
sont sous FND

38
 Lemme:

Toute forme propositionnelle j est synonyme d'une FP

sous FND
 Méthode de mise sous FND (1)

1. Mettre j sous FNN

2. Remplacer toutes les sous-formules :

j1 (j2vj3) par (j1j2) v(j1j3)

distributivité à gauche de  par v

(j2vj3) j1 par (j2j1) v(j3j1)

distributivité à droite de  par v
39
Exemple

40
 Méthode de mise sous FND (2)

(Utilisation de la table de vérité)

j = A( BC )
A B C j
0 0 0 1
0 0 1 1
0 1 0 1
0 1 1 1
1 0 0 0
1 0 1 0
1 1 0 0
1 1 1 1
FND= (A B C) v (A BC) v (ABC) v
(ABC) v (ABC)
41
 Plan
1-Introduction
2- Valuation (assignation, système de valeurs)
3- Interprétation
4- Analyse sémantique (analyse de Vérité) d'une formule
5- Formules propositionnelles synonymes/équivalentes
6- Formes normales d'une formule propositionnelle
7- Satisfaisabilité et validité d'une formule
8- Modèle
9- Compatibilité
10- Conséquence logique (conséquence tautologique)

42
 7. Satisfaisabilité et validité d'une formule
Formule satisfaite
Une formule j est satisfaite ssi j est vraie pour au
moins une valuation V des variables de j on a [j]V=1
j satisfaisable  V [j]V=1
Une formule satisfaite ssi elle est vraie au moins une fois

Une formule n'est pas satisfaite ssi elle est fausse

pour toute valuation V des variables de j
j non satisfaite  V [j]V=0
Une formule non satisfaite ssi elle est toujours fausse

Exemple:
AVB est satisfaite
AA non satisfaite 43
 Formule valide

Une formule j est valide ssi pour toute valuation

V des variables de j on a [j]V=1

j valide  V [j]V=1
Une formule j est valide ssi elle est toujours vraie

Une formule n'est pas valide ssi elle est fausse pour
au moins une valuation

j non valide  V [j]V=0

Une formule j est non valide ssi elle est fausse au moins une fois

Exemple:
AvA est valide
AvB n'est pas valide 44
 Tautologie
Une tautologie est une formule qui est toujours vraie
Une tautologie est une formule valide

j est une tautologie  V [j]V=1

Antilogie
Une antilogie est une formule qui est toujours fausse
Une antilogie est une formule non satisfaite

j est une antilogie  V [j]V=0

Toute substitution d’une tautologie est une tautologie

Toute substitution d’une antilogie est une antilogie 45
On a donc 3 catégories de formules:

 Les formules valides (toujours vraie)

i.e les tautologies

 Les formule satisfiables et non valides

 Les formules non satisfiables (toujours

fausses)
i.e les antilogies.

46
 Exemples :

Formules valides Formules Formules non

satisfiables et satisfaites
non valides
A v A A A  A
A v A v B A v B (AvA)(AA)
AA A B A A  B
(AB)(BA) B  (B  A) (A v B)  (A  B)
(AB) A (A v B)  A (A B) (AB)
(A A)B (A  C)  B
BBVA (A v B )  C
(AA)A (A  B)  (B  A)
(AAA)A (A  B)  (A  B)
47
 Plan
1-Introduction
2- Valuation (assignation, système de valeurs)
3- Interprétation
4- Analyse sémantique (analyse de Vérité) d'une formule
5- Formules propositionnelles synonymes/équivalentes
6- Formes normales d'une formule propositionnelle
7- Satisfaisabilité et validité d'une formule
8- Modèle
9- Compatibilité
10- Conséquence logique (conséquence tautologique)

48
8. Modèle
8-1 Modèle d'une formule propositionnelle
Définition :
Un modèle d'une formule propositionnelle j est une
valuation V telle que [j]V=1
V est un modèle de j  [j]V =1
On note V j
V j  [j]V =1
 (V j )  [j]V =0

Exemple: AvB  AB a deux modèles :

V1 / V1(A)=0 V1(B)=0
V2/ V2(A)=1 V2(B)=1 49
8-2 Modèle d'un ensemble de formules propositionnelles

Définition :
Un modèle d'un ensemble de formules propositionnelles 
est une valuation V qui satisfait toutes les formules de 
V modèle de   j   V j
V modèle de   j   [j]V=1
V non modèle de    j    ( V j)
V non modèle de    j   [j]V=0

On note V 

Exemple:  = {AvB, ABvC, C }

 a un modèle :
V1 / V1(A)=1, V1(B)=0, V1(C)=1 50
 Plan
1-Introduction
2- Valuation (assignation, système de valeurs)
3- Interprétation
4- Analyse sémantique (analyse de Vérité) d'une formule
5- Formules propositionnelles synonymes/équivalentes
6- Formes normales d'une formule propositionnelle
7- Satisfaisabilité et validité d'une formule
8- Modèle
9- Compatibilité
10- Conséquence logique (conséquence tautologique)

51
9. Compatibilité
9-1 Compatibilité d'une formule

Définition :
Une FP j est compatible ssi j a au moins un
modèle

j est compatible   V [j]V =1

j est incompatible   V [j]V =0  j antilogie

Exemple:
AvB est compatible
AA est incompatible

52
9. Compatibilité
9-2 Compatibilité d'un ensemble de formules
Définition :
Un ensemble de formules  est compatible ssi il a
au moins un modèle

 est compatible  V j  [j]V =1

 est incompatible   V j  [j]V =0

Exemple:
 L'ensemble {AB, AC, CvB} est compatible
V(A)=1, V(B)=1 , V(C)=0
 {AC, AC, CvB} est incompatible
53
Exemple :
Pour l'inscription à une université, on a énoncé le règlement
suivant:

1. Tout inscrit non algérien a une chambre dans la cité

universitaire
2. Tout inscrit a une carte d'identité ou n'a pas une chambre
dans la cité universitaire
3. Tout inscrit marié n'a pas de bourse
4. Un inscrit a une bourse ssi il est algérien
5. Tout inscrit qui a une carte d'identité est algérien et marié.
6. Tout inscrit algérien a une carte d'identité.

Peut-on accepter quelqu'un dans cette université?

54
Le problème posé :
Peut-on accepter quelqu'un dans cette université?

revient à vérifier si :
l'ensemble des FP est compatible ?

Méthodes :
1. Utilisation de la Table de vérité
2. utilisation de diagramme de Quine
3. Quand l'ensemble des FP est grand et le nombre
des VP est important, on essaye de procéder
progressivement à satisfaire les différentes FP : on
fixe une VP à 0 (puis 1) et on déduit les valeurs de
vérité des autres VP jusqu'à avoir un modèle.
55
 Plan
1-Introduction
2- Valuation (assignation, système de valeurs)
3- Interprétation
4- Analyse sémantique (analyse de Vérité) d'une formule
5- Formules propositionnelles synonymes/équivalentes
6- Formes normales d'une formule propositionnelle
7- Satisfaisabilité et validité d'une formule
8- Modèle
9- Compatibilité
10- Conséquence logique (conséquence tautologique)

56
10- Conséquence logique (conséquence
tautologique)
10-1 Conséquence d’une formule

Définition :
Une formule j est une conséquence logique (ou
conséquence tautologique) d'une formule  ssi tout
modèle de  est un modèle de j.

( j conséquence de )  (V ([]V =1 [j]V =1))

( j conséquence de )  (V [ j]V =1)
( j conséquence de )  ( j est une tautologie)

Notation:  j

57
Définition :
Une formule j n'est pas une conséquence logique
(ou conséquence tautologique) d'une formule  ssi
il existe un modèle de  qui n'est pas une modèle
de j.
 ( | j)  V ([]V =1  [j]V =0)

Exemple :

 = Av (AB) j= AB
 ( | j)

V(A)=0 V(B)=0,
(V )   (V j)
58
10- Conséquence logique (conséquence
tautologique)
10-2 Conséquence d’un ensemble de formules

Définition :

Une formule j est une conséquence logique (ou

conséquence tautologique) d'un ensemble de
formules propositionnelles ={j1,j2,….,jn}
(noté j1, ... ,jn | j) ssi tout modèle de  est un
modèle de j

( j)  (V (V  V j))
( j)  V ( (ji  [ji]V =1)  [j]V =1)

59
Exemple :

{AB, AC , CvB} AB

A B C AB AC CvB AB

0 0 0 1 0 0 0
0 0 1 1 0 1 0
0 1 0 1 0 1 0
0 1 1 1 0 1 0
1 0 0 0 1 0 0
1 0 1 0 0 1 0
1 1 0 1 1 1 1
1 1 1 1 0 1 1

60
Remarques :

On écrit souvent :

j1,...,jn | j à la place de {j1,...,jn} | j

 | j à la place de {} | j.

,  | j à la place de  U {} | j

| j à la place de  | j

61
Définition :
Une formule j n'est pas une conséquence logique
(ou conséquence tautologique) d'un ensemble de
formes propositionnelles ={j1,j2,….,jn} ssi il
existe au moins un modèle de  qui n'est pas un
modèle de j

 ( | j)  V (V    (V j))

 ( | j)  (V ((ji  [ji]V =1)  [j]V =0))

62
Exemple :

 ( {AB, CvB } AB )

A B C AB CvB AB

0 0 0 1 0 0
0 0 1 1 1 0
0 1 0 1 1 0
0 1 1 1 1 0
1 0 0 0 0 0
1 0 1 0 1 0
1 1 0 1 1 1
1 1 1 1 1 1

63
Exemple :

A | A 

A , B | A 

j1,j2,..,jn | ji 

j1, j2 | j1j2 

j1, j2 | j1vj2 

j1v j2 | j1 

j1 , j1  j2 | j2 

j1 v j2 | j1j2 

j2, j1j2 | j1 

64