Logique formelle

Logique formelle

23

Calcul des propositions Syntaxe

Exemples

A : p ∧ q

B : p ∨ q

C : p ⇒ q

• A [ p ← B, q ← C] =

( p ∨ q ) ∧ ( p ⇒ q )

•

(A [ p ← B ] ) [ q ← C] =

( ( p ∨ q ) ∧ q ) [ q ← C]

= ( p ∨ ( p ⇒ q ) ) ∧ ( p ⇒ q )

• A [ q ← C, p ← B] =

( p ∨ q ) ∧ ( p ⇒ q )

•

(A [ q ← C] ) [ p ← B ] =

( p ∨ ( p ⇒ q ) ) [ p ← B ]

= ( p ∨ q ) ∧ ( ( p ∨ q ) ⇒ q )

ENSI

Logique formelle

24

Calcul des propositions Syntaxe

Remarque

• Pour la substitution simultanée l’ordre n’est pas important

A [ p ← B , q ← C] = A [ q ← C , p ← B ]

• Pour la substitution séquentielle l’ordre est important

(A [ p ← B]) [q ← C] ≠ (A [ q ← C] ) [ p ← B ]

ENSI

Logique formelle

25

Calcul des propositions

I – Syntaxe

II – Sémantique

1. Interprétation 2. Satisfiabilité - Validité 3. Equivalence et conséquence sémantiques 4. Système complet de connecteurs 5. Satisfiabilité d’un ensemble de formules 6. Application 7. Formes normales

ENSI

Logique formelle

26

Calcul des propositions Sémantique

Sémantique : relatif au sens (du grec sêmantikos : «qui signifie»)

Donner un sens à une description textuelle (fournir un modèle de

certains aspects de ce que représente cette description)

• Syntaxe = définition des formules (la forme)

• Sémantique = effets de l’évaluation des formules (le sens)

ENSI

Logique formelle

27

Calcul des propositions Sémantique

1- Interprétation

A chaque proposition A, on va lui associer une valeur de

vérité dans l’ensemble { VB , FB } au moyen d’une application appelée interprétation (notée I)

(cid:190) Notation [A]I

Pour cela nous allons utiliser un morphisme sur l’algèbre de Boole

ENSI

Logique formelle

28

Calcul des propositions Sémantique

Définition Algèbre de Boole

L’algèbre de Boole est formée par :

• un ensemble de valeurs de vérité

B = { VB , FB }

• un ensemble d’opérateurs booléens

{ ∨B , ∧B , ⎤B , ⇒B , ⇔B }

définis comme suit :

ENSI

Logique formelle

suite

29

Calcul des propositions Sémantique

b b’

VB

VB

FB

FB

VB

FB

VB

FB

⎤B b b ∧B b’ b ∨B b’ b ⇒B b’ b ⇔B b’ FB

VB

VB

VB

VB

FB

VB

VB

FB

FB

FB

VB

VB

FB

FB

VB

VB

FB

FB

VB

ENSI

Logique formelle

30

Calcul des propositions Sémantique

George BOOLE (1815 - 1864) Mathématicien et logicien anglais. Autodidacte, créateur de la logique moderne qui porte son nom (logique booléenne, aussi appelée algèbre de Boole ou algèbre booléenne). Il a aussi travaillé dans d'autres domaines mathématiques, des équations différentielles aux probabilités en passant par l'analyse.

Il publia : - « Mathematical Analysis of Logic » (1847) - « An investigation into the laws of thought, on which are founded the mathematical theories of logic and probabilities » (1854) Où il développe une nouvelle forme de logique, à la fois symbolique et mathématique. Le but : traduire des idées et des concepts en équations, leur appliquer certaines lois et retraduire le résultat en termes logiques.

ENSI

Logique formelle

31

Calcul des propositions Sémantique

Définition Interprétation

(cid:131) Une interprétation (ou distribution de valeurs de vérité),

notée I, est une application de R 0 dans l’ensemble B

ENSI

Logique formelle

suite

32

Calcul des propositions Sémantique

Définition (suite)

(cid:131) Une interprétation peut être étendue à l’ensemble de formules L0 (appelée aussi interprétation) par le morphisme suivant :

•

•

•

•

•

•

[ 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

ENSI

Logique formelle

33

Calcul des propositions Sémantique

Remarque

L’extension de l’application I de R 0 à L0 est unique vu l’unicité de l’arbre de décomposition

ENSI

Logique formelle

34

Calcul des propositions Sémantique

Exemple

Soit A : p ∧ (q ⇒ p)

[ A ]I = [ p ∧ (q ⇒ p) ]I = [ p ]I ∧B [(q ⇒ p) ]I

= [ p ]I ∧B ([q ]I ⇒B [p ]I)

L’interprétation de A par I va dépendre de l’interprétation de p

et de q par I

Si I est définie comme suit : [ p ]I = VB , [q ]I = FB

alors

[ A ]I = VB ∧B ( FB ⇒B VB) = VB

ENSI

Logique formelle

35

Calcul des propositions Sémantique

(cid:137)Le résultat de l’interprétation d’une formule - selon les

différentes distributions de valeurs de vérité possibles - peut être représenté par une table appelée

« table des valeurs de vérité » ou « table de vérité »

(cid:137)La table aura 2n lignes différentes qui correspondent aux

différentes distributions de valeurs de vérité possibles (avec n le nombre de variables distinctes de la formule)

ENSI

Logique formelle

36

Calcul des propositions Sémantique

Table de vérité de

A : p ∧ (q ⇒ p)

[p]I VB VB FB FB

[q]I VB FB VB FB

[q ⇒ p]I VB VB FB VB

[ A ]I VB VB FB FB

(cid:190) Désormais nous confondons

les constantes booléens avec les opérateurs et les constantes logiques

les opérateurs et

ENSI

Logique formelle

37

Calcul des propositions Sémantique

Table de vérité de ⎤ p , p ∧ q , p ∨ q , p ⇒ q , p ⇔ q

p q

⎤ p

p ∧ q p ∨ q

p ⇒ q p ⇔ q

V

V

F

F

V

F

V

F

F

F

V

V

V

F

F

F

V

V V

V

V

F

F

F

V F

V V

ENSI

Logique formelle

38

Calcul des propositions Sémantique

Exemples

• Table de vérité de

B : ( ( (p ⇒ q) ∧ p) ⇒ p )

p q

p ⇒ q (p ⇒ q) ∧ p B

V

V

F

F

V

F

V

F

V

F

V

F

V

V

V F V

V F

V

ENSI

Logique formelle

suite

39

Calcul des propositions Sémantique

• Table de vérité de

C : ( (p ⇒ q) ∧ (p ∧ ⎤ q) )

p q

p ⇒ q p ∧ ⎤ q

V

V

F

F

V

F

V

F

C

F

F

V

F

F

V

V F F

V F

F

ENSI

Logique formelle

40

Calcul des propositions Sémantique

2- Satisfiabilité - Validité

Définition

Soient I une interprétation et A une formule

Si [ A ]I = V, alors on dit que :

(cid:131) A est vraie dans l’interprétation I

(cid:131) A est satisfaite par I

(cid:131) I satisfait A

(cid:131) I est modèle de A

(cid:190) notation I ╞ A

ENSI

Logique formelle

41

Calcul des propositions Sémantique

Définitions

(cid:131) Une formule vraie dans toute interprétation est dite valide

appelée aussi une tautologie

Pour tout interprétation I, on a [ A ]I = V (cid:190) notation ╞ A

(cid:131) Elle est dite invalide dans le cas contraire

(au moins fausse pour une interprétation )

(cid:131) Une formule fausse pour toute interprétation est dite

insatisfiable ou inconsistante ou contradictoire

appelée aussi une contradiction (ou une antilogie)

(cid:131) Elle est dite satisfiable ou consistante dans le cas contraire

(au moins vraie pour une interprétation)

ENSI

Logique formelle

42

Calcul des propositions Sémantique

Exemples

(cid:131) La formule ((p ⇒ q) ∧ p ) ⇒ p est une tautologie

(cid:131) La formule (p ⇒ q) ∧ ( p ∧ ⎤ q ) est une contradiction

(cid:131) La formule p ∧ (q ⇒ p) est satisfiable et invalide

ENSI

Logique formelle

43

Calcul des propositions Sémantique

Remarques

(cid:131) Si une formule est valide (tautologie) alors elle est

satisfiable. L’inverse n’est pas vrai

(cid:131) Si une formule est insatisfiable (contradiction) alors elle est

invalide. L’inverse n’est pas vrai

(cid:131) Une formule peut être à la fois satisfiable et invalide

(cid:131) Une formule ne peut jamais être à la fois valide et

insatisfiable (en même temps une tautologie et une

contradiction)

ENSI

Logique formelle

44

Calcul des propositions Sémantique

Remarque

Pour n’importe quelle formule propositionnelle, il est possible

de savoir si la formule est valide, invalide, satisfiable ou

insatisfiable

► Il suffit de dresser la table de vérité

Donc le calcul des propositions est décidable : il existe un

algorithme qui, pour toute formule propositionnelle, nous dit

si «oui» ou «non» la formule est une tautologie (notion à

étudier ultérieurement)

C’est une propriété fondamentale du calcul des propositions

ENSI

Logique formelle

45

Calcul des propositions Sémantique

Propositions

(cid:131) A est une tautologie ssi

⎤ A est une contradiction

(cid:131) A est une contradiction ssi

⎤ A est une tautologie

ENSI

Logique formelle

46

Calcul des propositions Sémantique

Preuve (cid:131) A est une tautologie ssi pour tout I on a [ A ]I = V comme [⎤ A ]I = ⎤ [ A ]I

alors pour tout I on a [⎤ A ]I = ⎤ [ A ]I = ⎤ V = F

donc ⎤ A est une contradiction

(cid:131)

⎤ A est contradiction ssi pour tout I on a [⎤ A ]I = F

alors pour tout I on a [⎤ A ]I = ⎤ [ A ]I = F donc pour tout I on a [ A ]I = V

donc A est une tautologie

Conclusion :

A est une tautologie ssi ⎤ A est une contradiction

ENSI

Logique formelle

47

Calcul des propositions Sémantique

Propriétés

(cid:131) (p ∨ ⎤ p) est une tautologie

(cid:131) (p ∨ q1 ∨ … ∨ qn ∨ ⎤ p ∨ qn+1 ∨ … ∨ qn+m) est une tautologie

(cid:131) (p ∨ A ∨ ⎤ p ∨ B) est une tautologie

(cid:131) (p ∧ ⎤ p) est une contradiction

(cid:131) (p ∧ q1 ∧ … ∧ qn ∧ ⎤ p ∧ qn+1 ∧ … ∧ qn+m) est une

contradiction

(cid:131) (p ∧ B ∧ ⎤ p ∧ C) est une contradiction

ENSI

Logique formelle

48

Calcul des propositions Sémantique

Preuve (cid:131) Pour tout I on a :

1er cas : [ p ]I = V

[ p ∨ ⎤ p]I = [ p ]I ∨ ⎤ [ p ]I = V ∨ F = V

2eme cas : [ p ]I = F alors

⎤ [ p ]I = V

[ p ∨ ⎤ p]I = [ p ]I ∨ ⎤ [ p ]I = F ∨ V = V

donc (p ∨ ⎤ p) est une tautologie

(cid:131) Pour tout I on a :

1er cas : [ p ]I = V

[ p ∧ ⎤ p]I = [ p ]I ∧ ⎤ [ p ]I = V ∧ F = F

2eme cas : [ p ]I = F alors

⎤ [ p ]I = V

[ p ∧ ⎤ p]I = [ p ]I ∧ ⎤ [ p ]I = F ∧ V = F

ENSI

Logique formelle

49

donc (p ∧ ⎤ p) est une contradiction

Calcul des propositions Sémantique

Proposition

Soient

• A , B1, B2, …, Bn des formules propositionnelles • p1, p2, …, pn des variables propositionnelles

Si A est une tautologie alors

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

est également une tautologie

ENSI

Logique formelle

50

Calcul des propositions Sémantique

3- Equivalence et conséquence sémantiques

Définitions

(cid:131) Une

formule A est conséquence sémantique

(ou

conséquence logique) d’une formule B ssi

tout modèle de B est un modèle de A

c-à-d pour toute interprétation I , si [B]I = V alors [A]I = V

(cid:190) notation B╞ A

(cid:131) Une formule A est équivalente sémantiquement à une

formule B ssi B est conséquence sémantique de A et A

est conséquence sémantique de B ( B ╞ A et A ╞ B )

(cid:190) notation A ≡ B

ENSI

Logique formelle

51

Calcul des propositions Sémantique

Propriétés

1. B ╞ A ssi

B ⇒ A est une tautologie (╞ (B ⇒ A) )

2. B ≡ A ssi

B ⇔ A est une tautologie (╞ (B ⇔ A) )

3. Si B ≡ A et ╞ B alors ╞ A

Remarque

• La propriété 1 est très importante, elle relie le ‘⇒ logique’, le

‘⇒ mathématique’ et la conséquence sémantique (╞)

• De même

la propriété 2 pour mathématique’ et l’équivalence sémantique ( ≡ )

le

‘⇔ logique’,

le

‘⇔

ENSI

Logique formelle

52

Calcul des propositions Sémantique

Preuve

1.

(seulement si) B ╞ A

Soit I une interprétation :

si [ B ]I = V , alors [ A ]I = V, donc [ B ⇒ A ]I = V si [ B ]I = F , alors [ B ⇒ A ]I = V

donc ╞ (B ⇒ A)

(si) ╞ (B ⇒ A)

alors pour tout I, [ B ⇒ A ]I = V, donc [ B ]I ⇒ [ A ]I =V en particulier si [ B ]I = V alors forcement [ A ]I = V

donc B ╞ A

2. 3. Exo.

ENSI

Logique formelle

53

Calcul des propositions Sémantique

Propriétés

1. Si A ≡ B alors ⎤ A ≡ ⎤ B

2. Si A ≡ B et C ≡ D alors

•

•

•

•

(A ∨ C) ≡ (B ∨ D)

(A ∧ C) ≡ (B ∧ D)

(A ⇒ C) ≡ (B ⇒ D)

(A ⇔ C) ≡ (B ⇔ D)

ENSI

Logique formelle

54

Calcul des propositions Sémantique

Preuve

1. A ≡ B alors pour tout I

[ A ]I = [ B ]I donc pour tout I ⎤ [A ]I = ⎤ [B ]I et donc [⎤ A ]I = [⎤ B ]I

d’où ⎤ A ≡ ⎤ B

2. Exo.

Remarque

Si A ≡ B alors A et B ont forcément le même modèle

ENSI

Logique formelle

55

Calcul des propositions Sémantique

Théorème

Le calcul propositionnel est muni d’une structure d’algèbre de Boole

(cid:131) Associativité

A ∨ (B ∨ C) ≡ (A ∨ B ) ∨ C

A ∧ (B ∧ C) ≡ (A ∧ B ) ∧ C

(cid:131) Commutativité

(A ∨ B) ≡ (B ∨ A)

(A ∧ B) ≡ (B ∧ A)

(cid:131) Distributivité

A ∧ ( B ∨ C) ≡ (A ∧ B ) ∨ (A ∧ C )

A ∨ ( B ∧ C) ≡ (A ∨ B ) ∧ (A ∨ C )

ENSI

Logique formelle

suite

56

Calcul des propositions Sémantique

Théorème (suite)

(cid:131) Lois de De Morgan

⎤ (A ∨ B ) ≡ ⎤ A ∧ ⎤ B

⎤ (A ∧ B ) ≡ ⎤ A ∨ ⎤ B

(cid:131) Idempotence

(A ∨ A) ≡ A

(A ∧ A) ≡ A

(cid:131) Absorption

A ∧ ( A ∨ B) ≡ A

A ∨ ( A ∧ B) ≡ A

ENSI

Logique formelle

suite

57

Calcul des propositions Sémantique

Théorème (suite)

(cid:131) Eléments neutres

(A ∧ V ) ≡ A

(A ∨ F) ≡ A

(cid:131) Eléments absorbants

(A ∧ F) ≡ F (A ∨ V ) ≡ V

(cid:131) Tiers exclu

(A ∧ ⎤ A) ≡ F

(A ∨ ⎤ A) ≡ V

ENSI

Logique formelle

suite

58

Calcul des propositions Sémantique

Théorème (suite)

(cid:131) Inverse

⎤ V ≡ F ⎤ F ≡ V

(cid:131) Involution

⎤ ⎤ A ≡ A

Preuve

Par table de vérité (exo)

ENSI

Logique formelle

59

Calcul des propositions Sémantique

Augustus De MORGAN (juin 1806 – mars 1871)

Mathématicien et logicien anglais (né en Inde).

Fondateur avec Boole de la logique moderne et auteur des lois de calcul des propositions.

De Morgan contribua beaucoup aux mathématiques : la première notion

d'induction mathématique, loi de De Morgan sur la convergence d'une suite

mathématique... Il développa un théorème sur les probabilités

d'évènements vie utilisé par les sociétés d'assurance aujourd'hui.

Notons que l'on doit à De Morgan l'usage (en 1845) de la notation a/b

(slash) pour désigner le quotient de a par b qui fut très rapidement adoptée.

Il imposa l'usage du point décimal (utilisé par Neper) : 23/10 = 2.3 (soit 2,3

pour les francophones)

ENSI

Logique formelle

60

Calcul des propositions Sémantique

4- Système complet de connecteurs

Définition

(cid:131) On appelle système (ou ensemble) complet de connecteurs

tout ensemble de connecteurs propositionnels permettant

d’engendrer tous les autres connecteurs propositionnels

(cid:131) Il est dit minimal

lorsque aucun de ses sous-ensembles

strictes n’est un système complet de connecteurs

ENSI

Logique formelle

61

Calcul des propositions Sémantique

Exemples

(cid:131) { ∨ , ∧ , ⎤ , ⇒ } est un système complet de connecteurs

car (p ⇔ q) ≡ ( p ⇒ q ) ∧ ( q ⇒ p )

(cid:131) { ∨ , ∧ , ⎤ } est un système complet de connecteurs

car (p ⇒ q) ≡ ( ⎤ p ∨ q )

ENSI

Logique formelle

suite

62

Calcul des propositions Sémantique

(cid:131) { ∧ , ⎤ } est un système complet de connecteurs

car (p ∨ q) ≡ ⎤ (⎤ p ∧ ⎤ q)

(cid:131) { ∨ , ⎤ } est un système complet connecteurs

car (p ∧ q) ≡ ⎤ (⎤ p ∨ ⎤ q)

(cid:131) { ⎤ } n’est pas un système complet

car on a au moins besoin d’un connecteur binaire

(cid:131) { ∧ , ⎤ } et { ∨ , ⎤ } sont donc des systèmes de connecteurs

complets et minimaux

ENSI

Logique formelle

63

Calcul des propositions Sémantique

5- Satisfiabilité d’un ensemble de formules

On peut étendre les résultats de satisfiabilité à un ensemble de formules

Soient

• ℰ et ℱ deux ensembles de formules (évent. infinie) • I une interprétation

(cid:131) ℰ est satisfait par I (ou I est un modèle de ℰ )

si I est modèle de toute formule de ℰ

(cid:131) ℰ est satisfiable (ou cohérent ou consistant )

s’il existe au moins une interprétation I qui est modèle de ℰ

ENSI

Logique formelle

suite

64

Calcul des propositions Sémantique

(cid:131) ℰ est finiment satisfiable si

tout sous-ensemble fini de ℰ est satisfiable

(cid:131) ℰ est contradictoire (ou insatisfiable ou une contradiction) ssi

ℰ est non satisfiable

(cid:131) Une formule B est conséquence logique de ℰ (ℰ ╞ B ) ssi

tout modèle de ℰ est modèle de B

(cid:131) ℰ et ℱ sont équivalents ( ℰ ≡ ℱ ) ssi

toute formule de ℰ est conséquence de ℱ et toute formule de ℱ est conséquence de ℰ c-à-d ℰ et ℱ ont exactement les mêmes modèles

ENSI

Logique formelle

65

Calcul des propositions Sémantique

Théorème de compacité

Version 1

Pour tout ensemble ℰ de propositions

ℰ est satisfiable ssi ℰ est finiment satisfiable

(ℰ admet un modèle ssi toute partie finie de ℰ admet un modèle)

Version 2

Pour tout ensemble ℰ de propositions

ℰ est contradictoire ssi ℰ admet au moins un sous-ensemble fini contradictoire

ENSI

Logique formelle

suite

66

Calcul des propositions Sémantique

Théorème de compacité (suite)

Version 3

Pour tout ensemble ℰ de propositions et pour toute formule B

B est conséquence de ℰ

ssi

B est conséquence d’au moins une partie finie de ℰ

ENSI

Logique formelle

67

Calcul des propositions Sémantique

Propositions

Soient

• ℰ = { A1,…, An} et ℱ deux ensembles de propositions • A et B deux formules propositionnelles

1. ℰ ╞ A ssi ℰ U {⎤ A } est contradictoire

2. Si ℰ est satisfiable et si ℱ ⊆ ℰ, alors ℱ est satisfiable

3. Si ℰ est satisfiable alors ℰ est finiment satisfiable

4. Si ℰ est contradictoire et si ℰ ⊆ ℱ

alors ℱ est contradictoire

5. Si ℰ ╞ A et si ℰ ⊆ ℱ , alors ℱ ╞ A

ENSI

Logique formelle

suite

68

Calcul des propositions Sémantique

Propositions (suite)

6. ℰ U {A} ╞ B ssi

ℰ ╞ (A ⇒ B)

7. ℰ ╞ ( A ∧ B ) ssi

ℰ ╞ A et ℰ ╞ B

8.

{ A1, …, An } ╞ B ssi ╞ (( A1 ∧ …. ∧ An ) ⇒ B)

9. A est une tautologie ssi

A est conséquence logique de l’ensemble vide

10. A est une tautologie ssi

A est conséquence de n’importe quel ensemble de formules

11. ℰ est contradictoire ssi

ℰ ╞ ( A ∧ ⎤ A )

ENSI

Logique formelle

suite

69

Calcul des propositions Sémantique

Propositions (suite)

12. ℰ est contradictoire ssi

il existe une contradiction qui soit conséquence de ℰ

13. { A1, …, An } est contradictoire ssi

(⎤ A1 ∨ …. ∨ ⎤ An ) est une tautologie

14. ℰ et ℱ sont équivalents ssi

ils sont satisfaits par les mêmes interprétations

15. L’ensemble vide est satisfiable

16. L’ensemble de toutes les formules propositionnelles

est contradictoire

17. Tout ensemble fini de formules est sémantiquement

équivalent à un ensemble constitué par seule formule

ENSI

Logique formelle

70

Calcul des propositions Sémantique

Preuve

TD 1

Remarque

Un ensemble de conjonction de formules

formules peut être vu comme une

ℰ = { A1, …, An } est sémantiquement équivalent à la formule ( A1 ∧ … ∧ An )

Plus précisément { A1, …, An } ≡ { (A1 ∧ … ∧ An ) }

(point 17 de la proposition précédente)

ENSI

Logique formelle

71

Calcul des propositions Sémantique

6- Application

Soit l’énoncé suivant :

« 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 »

1. Définition des variables propositionnelles

t : « bien travailler »

m : « être malade »

r : « réussir »

ENSI

Logique formelle

suite

72

Calcul des propositions Sémantique

2. Modélisation de l’énoncé :

H1 : «Si je travaille bien alors je vais réussir» (cid:198) t ⇒ r

H2 : «Si je suis malade , je ne peux pas bien travailler»

(cid:198) m ⇒ ⎤ t

H3 : «je suis malade mais je travaille bien» (cid:198) m ∧ t

C : «je vais réussir» (cid:198) r

3. Vérifier que {H1, H2, H3} ╞ C, c-à-d :

{ t ⇒ r , m ⇒ ⎤ t , m ∧ t } ╞ r

ssi

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

ssi

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

ENSI

Logique formelle

suite

73

Calcul des propositions Sémantique

Remarque

On peut voir l’énoncé comme suit

{H1, H2} ╞ (H3 ⇒ C)

c-à-d H3 fait partie de conclusion

Ceci ne change rien au résultat final car nous avons

{H1, H2, H3} ╞ C ssi

{H1, H2} ╞ (H3 ⇒ C)

(point 6 de la proposition précédente)

ENSI

Logique formelle

suite

74

Calcul des propositions Sémantique

Remarque

L’énoncé est correct : par table de vérité, nous avons bien

{H1, H2, H3} ╞ C

Au fait nous avons {H1, H2, H3} est contradictoire. Donc n’importe quelle conclusion donne toujours un énoncé correct.

Par exemple si nous prenons C’ : « je ne vais pas réussir »

Nous avons toujours {H1, H2, H3} ╞ C’

ENSI

Logique formelle

75

Calcul des propositions Sémantique

Commentaires sur les connecteurs logiques

(cid:131) Conjonction

A ∧ B

A et B ; A mais B ; A quoique B ; A tandis que B

(cid:131) Disjonction A ∨ B

ou inclusif (« vel » en latin)

A ou B ; A ou/et B (juridique) ; A à moins que B

A sinon B ; A sauf si B ; A ou B et peut être les deux

(cid:131) Ou exclusif

A ⊕ B ≡ (A ∧⎤ B) ∨ (⎤ A ∧ B)

A ou B mais pas les deux ; soit A, soit (exclusivement) B

(« aut » en latin)

ENSI

Logique formelle

suite

76

Calcul des propositions Sémantique

(cid:131) Implication A ⇒ B

si / lorsque A, alors / nécessairement/ c’est que B

A implique / entraîne B

A est condition suffisante de / suffit à B

A seulement si / que si B

B si /lorsque A

B est condition nécessaire de A

ENSI

Logique formelle

suite

77

Calcul des propositions Sémantique

(cid:131) Equivalence A ⇔ B

A (est) équivalent à B

A si et seulement si B

A est condition nécessaire est suffisante (CNS) de B

A si B et réciproquement

• A ssi B : A seulement si B (A ⇒ B) ; A si B (A B)

⇒

• A cns B : A condition suffisante B (A ⇒ B)

A condition nécessaire B (A B)

⇒

ENSI

Logique formelle

78

Calcul des propositions Sémantique

7- Formes normales

Définition

(cid:131) On appelle littéral un atome ou une négation d’atome

(ex. : p , ⎤ p , …)

(cid:131) Une formule est dite sous forme normale disjonctive (FND)

si elle est sous forme de disjonction de conjonctions de

littéraux

( l11 ∧ ... ∧ l1i ) ∨ ( l21 ∧ ... ∧ l2j) ∨ … ∨ ( ln1 ∧ ... ∧ lnk )

ENSI

Logique formelle

suite

79

Calcul des propositions Sémantique

Définition (suite)

(cid:131) Une formule est dite sous forme normale conjonctive (FNC)

si elle est sous forme de conjonction de disjonctions de

littéraux

( l11 ∨ ... ∨ l1i ) ∧ ( l21 ∨ ...∨ l2j) ∧ ... ∧ ( ln1 ∨ ... ∨ lnk )

Une disjonction de littéraux est appelée une clause

ENSI

Logique formelle

80

Calcul des propositions Sémantique

Exemples

(cid:131) Formule en FND : ( p ∧ ⎤ q ) ∨ p

(cid:131) Formule en FNC : ( p ∨ q ) ∧ ( r ∨ ⎤ s )

(cid:131) Formules à la fois en FNC et FND :

p p ∨ q p ∧ ⎤ q

ENSI

Logique formelle

81

Calcul des propositions Sémantique

Les FNC et le FND peuvent être obtenues en appliquant les transformations suivantes :

1. Elimination des connecteurs ⇔ et ⇒

•

•

(A ⇔ B) ≡ (A ⇒ B) ∧ (B ⇒ A)

(A ⇒ B) ≡ (⎤ A ∨ B)

2. Elimination des négations appliquées à des sous-formules

•

•

•

⎤ (⎤ A) ≡ A

⎤ (A ∧ B) ≡ (⎤ A ∨ ⎤ B)

⎤ (A ∨ B) ≡ (⎤ A ∧ ⎤ B)

ENSI

Logique formelle

suite

82

Calcul des propositions Sémantique

3. Application des lois de distributivité tant que possible

• A ∨ (B ∧ C) ≡ (A ∨ B ) ∧ (A ∨ C )

(pour obtenir une FNC)

• A ∧ ( B ∨ C) ≡ (A ∧ B ) ∨ (A ∧ C )

(pour obtenir u