Logique formelle
Partie I - Le calcul des prdicats Modlisation
CP0. Le calcul des Prdicats dordre 0 (Propositions) CP1. Le calcul des Prdicats dordre 1 (Prdicats)
Partie II - Les mthodes de calcul Dduction
ENSI Logique formelle 1
Logique formelle Chapitre 1
Le calcul des Propositions Calcul propositionnel Logique dordre 0 CP0
ENSI Logique formelle 2
Calcul des propositions
I Syntaxe
1. Dfinition du langage 2. Arbre de dcomposition dune formule 3. Substitution dans une formule
II Smantique
ENSI
Logique formelle
Calcul des propositions
Syntaxe
1- Dfinition du langage
Un langage logique est dfini par une syntaxe, qui est dfinie par un ensemble de symboles (alphabet) et un ensemble de rgles permettant de combiner ces symboles sous forme de mots (squence de symboles) appeles formules (bien formes). Cest laspect structurel et grammatical du langage. On associe au langage une smantique qui permet de lui donner un sens (linterprter). C'est--dire attacher aux formules ainsi qu'aux symboles une signification (paragraphe II). Pour dfinir un langage, on doit commencer par dfinir son alphabet.
ENSI Logique formelle 4
Calcul des propositions
Syntaxe
Des variables propositionnelles (atomes) R 0 = { p, q, } vent. indices { p1, q1, p2, q2, } Des symboles logiques (connecteurs) ngation ( non ) disjonction ( ou ) conjonction ( et ) implication ( implique ) quivalence ( si et seulement si ) Des constantes V (vrai) F (faux) ( ) ,
Logique formelle 5
unaire binaire
Des symboles auxiliaires
ENSI
Calcul des propositions
Syntaxe
Une formule propositionnelle est un mot construit sur lalphabet
A0 = R 0 U { , , , , } U { F,V } U { ( , ) , , }
Comment ?
Selon quelles rgles ?
ENSI
Logique formelle
Calcul des propositions Dfinition Formules propositionnelles
Syntaxe
Lensemble des formules propositionnelles (not L0 ) est le plus petit ensemble de mots construits sur lalphabet A0 et qui vrifie les proprits suivantes : il contient R 0 U { V, F } chaque fois quil contient le mot A, il contient le mot ( A ) chaque fois quil contient les mots A et B, il contient les mots : ( A B ) , ( A B ) , ( A B ) , ( A B )
ENSI Logique formelle 7
Calcul des propositions
Autrement dit
Syntaxe
Lensemble L0 des propositions btis sur lalphabet A0 est le plus petit ensemble qui contient R 0 U { V, F } et qui est clos (stable) pour les oprations suivantes : A L0 ( A ) L0
A , B L0 ( A B ) L0
( A B ) L0
( A B ) L0
( A B ) L0
ENSI Logique formelle 8
Calcul des propositions
Autrement dit
Syntaxe
Soit L0 lensemble des formules propositionnelles, alors : 1. un atome est une formule (R 0 L0 ) 2. V et F sont des formules ( { V,F } L0 ) 3. si A et B sont des formules alors (AB), (AB),(A B),(AB) sont des formules 4. si A est une formule alors ( A ) est une formule 5. rien dautre nest une formule (toutes les formules propositionnelles sont gnres par application des quatre rgles prcdentes uniquement)
ENSI Logique formelle 9
Calcul des propositions
Syntaxe
Remarque Lensemble L0 des formules propositionnelles est appel le langage dordre 0 ou le langage du (calcul) des propositions (ou des prdicats dordre 0) Exemples Les mots suivants sont des formules (p (( ( q r )) p )) (F V) ( p ) F Les mots suivants ne sont pas des formules ( p q )
ENSI Logique formelle
(pq) ((p q)q) (( p ) ( q )) q (( p ) ( q ))
10
Calcul des propositions Remarque
Syntaxe
On peut enlever le parenthsage en labsence de toute ambigut Il faut fixer une priorit (poids) pour les oprateurs Ordre de priorit :
priorit la plus faible (par convention)
(par coutume)
Logique formelle 11
ENSI
Calcul des propositions La formule sera parenthse : pq rs puv
Syntaxe
( ( ( ( p q ) ( r s ) ) ( p ) ) ( u v ) ) 2 5 3 6 1 7 4 La formule sera parenthse : ( ( ( p ( ( (q r ) s ) ( t p ) ) ) ( (p r )) ) t ) p (q r) s t p (p r) t
ENSI
Logique formelle
12
Calcul des propositions
Syntaxe
2- Arbre de dcomposition dune formule
A : ( ( p ( q p ) ) ( q r) )
A11 A1 A12 A2
(qp)
A11: p
A111
( q
A12 : ( q
A121
r )
A122
A1121 A1122 A112
A2 : ( q
A21
p
A22
On peut reprsenter cette dcomposition sous forme dun arbre
ENSI Logique formelle 13
Calcul des propositions A A1 A11
A111
Syntaxe
A12
A121: A21
A2
A22: A221
A112
A122:
A1121
A1122
A11221
A11211
ENSI
Logique formelle
14
Calcul des propositions p q
ENSI
Syntaxe
q r
Les oprateurs traiter en premier se trouvent au bas de larbre
Logique formelle 15
Calcul des propositions Thorme de lecture unique
Syntaxe
Pour toute formule A L0 , un et un seul des 3 cas suivants se prsente : 1. A R 0 U { V, F } 2. il existe une unique formule B L0 telle que # {,, , } et un unique couple de formules ( B, C ) L02 tels que A = (B # C)
" = " galit syntaxique
ENSI Logique formelle 16
A = ( B)
3. il existe un unique symbole de connecteur binaire
Calcul des propositions
Syntaxe
Corollaire Larbre de dcomposition dune formule est unique
Remarque On dit que le langage des propositions est non ambigu
ENSI
Logique formelle
17
Calcul des propositions
Syntaxe
3- Substitution dans une formule
Dfinition Soient A et B deux formules propositionnelles p une variable propositionnelle de A A [ p B ] est le mot obtenu en substituant la formule B la variable p La substitution sapplique toutes les occurrences de la variable p Autre notation : A (B / p)
ENSI Logique formelle 18
Calcul des propositions Exemple A : p (q p) B: q r
Syntaxe
La variable p a 2 occurrences dans A La variable q a une seule occurrence dans A A [ p B ] = B (q B) = (q r) ( q (q r))
ENSI
Logique formelle
19
Calcul des propositions
Syntaxe
On peut tendre la substitution un ensemble de formules A [ p1 B1 , p2 B2 , , pn Bn ] est le mot obtenu en substituant respectivement les formules B1, B2 , , Bn toutes les occurrences des variables p1, p2, , pn
ENSI
Logique formelle
20
Calcul des propositions
Syntaxe
Thorme Soient A , B1 , B2,, Bn des formules propositionnelles p1, p2, , pn des variables propositionnelles alors le mot A [ p1 B1, p2 B2, , pn Bn ]
est une formule propositionnelle
ENSI
Logique formelle
21
Calcul des propositions
Syntaxe
Exemples A: p q B: q r C: p r
A [ p B, q C] = B C = (q r ) (p r ) A [r C] = A
ENSI
Logique formelle
22
Calcul des propositions Remarque
Syntaxe
La substitution simultane (remplacement en parallle) est diffrente de la substitution squentielle (remplacement en srie) A [ p1 B1, p2 B2] substitution simultane
(A [ p1 B1] ) [ p2 B2 ] substitution squentielle
ENSI
Logique formelle
23
Calcul des propositions Exemples A: p q B : p q
Syntaxe
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 Remarque
Syntaxe
Pour la substitution simultane lordre nest pas important A [ p B , q C] = A [ q C , p B ] Pour la substitution squentielle lordre est important (A [ p B]) [q C]
(A [ q C] ) [ p B ]
ENSI
Logique formelle
25
Calcul des propositions
I Syntaxe II Smantique
1. 2. 3. 4. 5. 6. 7. Interprtation Satisfiabilit - Validit Equivalence et consquence smantiques Systme complet de connecteurs Satisfiabilit dun ensemble de formules Application Formes normales
ENSI Logique formelle 26
Calcul des propositions
Smantique
Smantique : relatif au sens (du grec smantikos : qui signifie) Donner un sens une description textuelle (fournir un modle de certains aspects de ce que reprsente cette description) Syntaxe = dfinition des formules (la forme) Smantique = effets de lvaluation des formules (le sens)
ENSI
Logique formelle
27
Calcul des propositions
Smantique
1- Interprtation
A chaque proposition A, on va lui associer une valeur de vrit dans lensemble { VB , FB } au moyen dune application appele interprtation (note I) Notation [A]I Pour cela nous allons utiliser un morphisme sur lalgbre de Boole
ENSI
Logique formelle
28
Calcul des propositions Dfinition Algbre de Boole Lalgbre de Boole est forme par : un ensemble de valeurs de vrit
Smantique
B = { VB , FB }
un ensemble doprateurs boolens { B , B , B , B , B } dfinis comme suit :
suite
ENSI Logique formelle 29
Calcul des propositions
Smantique
b VB VB FB FB
b VB FB VB FB
B b FB FB VB VB
b B b b B b b B b VB FB FB FB VB VB VB FB VB FB VB VB
b B b VB FB FB VB
ENSI
Logique formelle
30
Calcul des propositions George BOOLE (1815 - 1864)
Mathmaticien et logicien anglais. Autodidacte, crateur de la logique moderne qui porte son nom (logique boolenne, aussi appele algbre de Boole ou algbre boolenne). Il a aussi travaill dans d'autres domaines mathmatiques, des quations diffrentielles aux probabilits en passant par l'analyse.
Smantique
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 dveloppe une nouvelle forme de logique, la fois symbolique et mathmatique. Le but : traduire des ides et des concepts en quations, leur appliquer certaines lois et retraduire le rsultat en termes logiques.
ENSI Logique formelle 31
Calcul des propositions Dfinition Interprtation
Smantique
Une interprtation (ou distribution de valeurs de vrit), note I, est une application de R 0 dans lensemble B
suite
ENSI Logique formelle 32
Calcul des propositions Dfinition (suite)
Smantique
Une interprtation peut tre tendue lensemble de formules
L0 (appele aussi interprtation) par le morphisme suivant :
[ V ]I = VB [ 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
[ F ]I = FB
Calcul des propositions Remarque
Smantique
Lextension de lapplication I de R 0 L0 est unique vu lunicit de larbre de dcomposition
ENSI
Logique formelle
34
Calcul des propositions Exemple Soit A : p (q p) = [ p ]I B ([q ]I B [p ]I) [ A ]I = [ p (q p) ]I = [ p ]I B [(q p) ]I
Smantique
Linterprtation de A par I va dpendre de linterprtation de p et de q par I Si I est dfinie comme suit : [ p ]I = VB , [q ]I = FB alors [ A ]I = VB B ( FB B VB) = VB
ENSI
Logique formelle
35
Calcul des propositions
Smantique
Le rsultat de linterprtation dune formule - selon les diffrentes distributions de valeurs de vrit possibles - peut tre reprsent par une table appele table des valeurs de vrit ou table de vrit
La table aura 2n lignes diffrentes qui correspondent aux diffrentes distributions de valeurs de vrit possibles (avec n le nombre de variables distinctes de la formule)
ENSI
Logique formelle
36
Calcul des propositions Table de vrit de [p]I VB VB FB FB A : p (q p) [q]I VB FB VB FB [q p]I VB VB FB VB [ A ]I VB VB FB FB
Smantique
Dsormais nous confondons les oprateurs et les constantes boolens avec les oprateurs et les constantes logiques
ENSI Logique formelle 37
Calcul des propositions
Smantique
Table de vrit de p , p q , p q , p q , p q p F F V V
p V V F F
q V F V F
pq V F F F
pq V V V F
pq V F V V
p q V F F V
ENSI
Logique formelle
38
Calcul des propositions Exemples
Smantique
Table de vrit de p V V F F q V F V F
B : ( ( (p q) p) p ) pq V F V V (p q) p V F F F B V V V V
suite
ENSI
Logique formelle
39
Calcul des propositions
Smantique
Table de vrit de
C : ( (p q) (p q) )
p V V F F
q V F V F
p q V F V V
p q F V F F
C F F F F
ENSI
Logique formelle
40
Calcul des propositions
Smantique
2- Satisfiabilit - Validit
Dfinition Soient I une interprtation et A une formule Si [ A ]I = V, alors on dit que : A est vraie dans linterprtation I A est satisfaite par I I satisfait A I est modle de A notation I A
ENSI Logique formelle 41
Calcul des propositions Dfinitions
Smantique
Une formule vraie dans toute interprtation est dite valide appele aussi une tautologie Pour tout interprtation I, on a [ A ]I = V notation A Elle est dite invalide dans le cas contraire (au moins fausse pour une interprtation ) Une formule fausse pour toute interprtation est dite insatisfiable ou inconsistante ou contradictoire appele aussi une contradiction (ou une antilogie) Elle est dite satisfiable ou consistante dans le cas contraire (au moins vraie pour une interprtation)
ENSI Logique formelle 42
Calcul des propositions
Smantique
Exemples La formule ((p q) p ) p est une tautologie La formule (p q) ( p q ) est une contradiction La formule p (q p) est satisfiable et invalide
ENSI
Logique formelle
43
Calcul des propositions Remarques
Smantique
Si une formule est valide (tautologie) alors elle est satisfiable. Linverse nest pas vrai Si une formule est insatisfiable (contradiction) alors elle est invalide. Linverse nest pas vrai Une formule peut tre la fois satisfiable et invalide Une formule ne peut jamais tre la fois valide et insatisfiable (en mme temps une tautologie et une contradiction)
ENSI Logique formelle 44
Calcul des propositions Remarque
Smantique
Pour nimporte quelle formule propositionnelle, il est possible de savoir si la formule est insatisfiable valide, invalide, satisfiable ou Il suffit de dresser la table de vrit
Donc le calcul des propositions est dcidable : il existe un algorithme qui, pour toute formule propositionnelle, nous dit si oui ou non la formule est une tautologie (notion tudier ultrieurement) Cest une proprit fondamentale du calcul des propositions
ENSI
Logique formelle
45
Calcul des propositions
Smantique
Propositions A est une tautologie A est une contradiction ssi ssi A est une contradiction A est une tautologie
ENSI
Logique formelle
46
Calcul des propositions
Smantique
Preuve 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 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 Proprits (p p) est une tautologie
Smantique
(p q1 qn p qn+1 qn+m) est une tautologie (p A p B) est une tautologie (p p) est une contradiction (p q1 qn p qn+1 qn+m) est une contradiction (p B p C) est une contradiction
ENSI Logique formelle 48
Calcul des propositions
Preuve 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
Smantique
donc (p p) est une tautologie 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 donc (p p) est une contradiction
ENSI Logique formelle 49
[ p p]I = [ p ]I [ p ]I = F V = F
Calcul des propositions Proposition Soient A , B1, B2, , Bn p1, p2, , pn
Smantique
des formules propositionnelles
des variables propositionnelles alors est galement une tautologie
Si A est une tautologie
A [ p1 B1 , p2 B2 , , pn Bn ]
ENSI
Logique formelle
50
Calcul des propositions
Smantique
3- Equivalence et consquence smantiques
Dfinitions Une formule A est consquence smantique consquence logique) dune formule B ssi tout modle de B est un modle de A c--d pour toute interprtation I , si [B]I = V alors [A]I = V notation formule B ssi B A B est consquence smantique de A et A A B
Logique formelle 51
(ou
Une formule A est quivalente smantiquement une est consquence smantique de B ( B A et A B ) notation
ENSI
Calcul des propositions Proprits 1. B A 2. B A ssi ssi
Smantique
B A est une tautologie ( (B A) ) B A est une tautologie ( (B A) ) alors A
3. Si B A et B Remarque
La proprit 1 est trs importante, elle relie le logique, le mathmatique et la consquence smantique () De mme la proprit 2 pour le logique, le mathmatique et lquivalence smantique ( )
ENSI Logique formelle 52
Calcul des propositions Preuve
1. (seulement si) B A
Smantique
Soit I une interprtation : 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 Proprits 1. Si A B 2. Si A B alors et A B C D alors
Smantique
(A C) (A C)
(B D) (B D)
(A C) (B D) (A C) (B D)
ENSI Logique formelle 54
Calcul des propositions Preuve 1. A B alors donc pour tout I et donc [ A ]I = [ B ]I [ A ]I = [ B ]I
Smantique
pour tout I [A ]I = [B ]I do A B
2.
Exo.
Remarque Si A B alors A et B ont forcment le mme modle
ENSI Logique formelle 55
Calcul des propositions Thorme
Smantique
Le calcul propositionnel est muni dune structure dalgbre de Boole Associativit A (B C) (A B ) C A (B C) (A B ) C Commutativit (A B) (B A) (A B) (B A) Distributivit A ( B C) (A B ) (A C ) A ( B C) (A B ) (A C )
suite
ENSI Logique formelle 56
Calcul des propositions Thorme (suite) Lois de De Morgan
Smantique
(A B ) A B (A B ) A B
Idempotence
(A A) A (A A) A
Absorption
A ( A B) A A ( A B) A
suite
ENSI
Logique formelle
57
Calcul des propositions Thorme (suite) Elments neutres (A V ) A Elments absorbants (A F) F Tiers exclu (A A) F
Smantique
(A F) A
(A V ) V
(A A) V
suite
ENSI
Logique formelle
58
Calcul des propositions Thorme (suite) Inverse
V F
Smantique
F V
Involution
A A
Preuve Par table de vrit (exo)
ENSI
Logique formelle
59
Calcul des propositions Augustus De MORGAN (juin 1806 mars 1871)
Mathmaticien et logicien anglais (n en Inde). Fondateur avec Boole de la logique moderne et auteur des lois de calcul des propositions.
Smantique
De Morgan contribua beaucoup aux mathmatiques : la premire notion d'induction mathmatique, loi de De Morgan sur la convergence d'une suite mathmatique... Il dveloppa un thorme sur les probabilits d'vnements vie utilis par les socits d'assurance aujourd'hui. Notons que l'on doit De Morgan l'usage (en 1845) de la notation a/b (slash) pour dsigner le quotient de a par b qui fut trs rapidement adopte. Il imposa l'usage du point dcimal (utilis par Neper) : 23/10 = 2.3 (soit 2,3 pour les francophones)
ENSI Logique formelle 60
Calcul des propositions
Smantique
4- Systme complet de connecteurs
Dfinition On appelle systme (ou ensemble) complet de connecteurs tout ensemble de connecteurs propositionnels permettant dengendrer tous les autres connecteurs propositionnels Il est dit minimal lorsque aucun de ses sous-ensembles strictes nest un systme complet de connecteurs
ENSI
Logique formelle
61
Calcul des propositions
Smantique
Exemples { , , , } est un systme complet de connecteurs car (p q) ( p q ) ( q p )
{ , , } est un systme complet de connecteurs car (p q) ( p q )
suite
ENSI Logique formelle 62
Calcul des propositions { , } est un systme complet de connecteurs car (p q) ( p q)
Smantique
{ , } est un systme complet connecteurs car (p q) ( p q)
{ } nest pas un systme complet car on a au moins besoin dun connecteur binaire { , } et { , } sont donc des systmes de connecteurs complets et minimaux
ENSI Logique formelle 63
Calcul des propositions
Smantique
5- Satisfiabilit dun ensemble de formules
On peut tendre les rsultats de satisfiabilit un ensemble de formules Soient et deux ensembles de formules (vent. infinie) I une interprtation est satisfait par I (ou I est un modle de ) si I est modle de toute formule de est satisfiable (ou cohrent ou consistant ) sil existe au moins une interprtation I qui est modle de
suite
ENSI Logique formelle 64
Calcul des propositions
Smantique
est finiment satisfiable si tout sous-ensemble fini de est satisfiable est contradictoire (ou insatisfiable ou une contradiction) ssi est non satisfiable Une formule B est consquence logique de ( B ) ssi tout modle de est modle de B et sont quivalents ( ) ssi toute formule de est consquence de et toute formule de est consquence de c--d et ont exactement les mmes modles
ENSI Logique formelle 65
Calcul des propositions Thorme de compacit
Version 1
Smantique
Pour tout ensemble de propositions est satisfiable ssi est finiment satisfiable
( admet un modle ssi toute partie finie de admet un modle)
Version 2
Pour tout ensemble de propositions est contradictoire ssi admet au moins un sous-ensemble fini contradictoire
suite
ENSI Logique formelle 66
Calcul des propositions Thorme de compacit (suite)
Smantique
Version 3
Pour tout ensemble de propositions et pour toute formule B B est consquence de ssi B est consquence dau moins une partie finie de
ENSI
Logique formelle
67
Calcul des propositions Propositions Soient
Smantique
= { A1,, An} et deux ensembles de propositions A et B deux formules propositionnelles 1. A ssi U { A } est contradictoire alors est satisfiable
2. Si est satisfiable et si ,
3. Si est satisfiable alors est finiment satisfiable 4. Si est contradictoire et si alors est contradictoire 5. Si A et si ,
ENSI
alors A
Logique formelle
suite
68
Calcul des propositions Propositions (suite) 6. U {A} B 7. ( A B ) ssi ssi (A B) A et ssi B
Smantique
8. { A1, , An } B
(( A1 . An ) B)
9. A est une tautologie ssi A est consquence logique de lensemble vide 10. A est une tautologie ssi A est consquence de nimporte quel ensemble de formules 11. est contradictoire
ENSI
ssi
(A A)
suite
69
Logique formelle
Calcul des propositions Propositions (suite)
Smantique
12. est contradictoire ssi il existe une contradiction qui soit consquence de 13. { A1, , An } est contradictoire ssi ( A1 . An ) est une tautologie 14. et sont quivalents ssi ils sont satisfaits par les mmes interprtations 15. Lensemble vide est satisfiable 16. Lensemble de toutes les formules propositionnelles est contradictoire 17. Tout ensemble fini de formules est smantiquement quivalent un ensemble constitu par seule formule
ENSI Logique formelle 70
Calcul des propositions Preuve TD 1
Smantique
Remarque Un ensemble de formules peut tre vu comme une conjonction de formules = { A1, , An } est smantiquement quivalent la formule ( A1 An ) Plus prcisment { A1, , An } { (A1 An ) }
(point 17 de la proposition prcdente)
ENSI Logique formelle 71
Calcul des propositions
Smantique
6- Application
Soit lnonc suivant : Si je travaille bien alors je vais russir. Si je suis malade , je ne peux pas bien travailler. Or je suis malade mais je travaille bien. Donc je vais russir 1. Dfinition des variables propositionnelles t : bien travailler m : tre malade r : russir
suite
ENSI Logique formelle 72
Calcul des propositions 2. Modlisation de lnonc : H1 : Si je travaille bien alors je vais russir
Smantique tr
H2 : Si je suis malade , je ne peux pas bien travailler mt H3 : je suis malade mais je travaille bien C : je vais russir r 3. Vrifier que {H1, H2, H3} C, c--d : {tr,mt,mt} r ssi ssi
ENSI
mt
(t r) (m t) (m t) r (((t r) (m t) (m t)) r)
Logique formelle
suite
73
Calcul des propositions Remarque On peut voir lnonc comme suit {H1, H2} (H3 C) c--d H3 fait partie de conclusion
Smantique
Ceci ne change rien au rsultat final car nous avons {H1, H2, H3} C ssi {H1, H2} (H3 C)
(point 6 de la proposition prcdente)
suite
ENSI Logique formelle 74
Calcul des propositions Remarque
Smantique
Lnonc est correct : par table de vrit, nous avons bien {H1, H2, H3} C Au fait nous avons {H1, H2, H3} est contradictoire. Donc nimporte quelle conclusion donne toujours un nonc correct. Par exemple si nous prenons C : je ne vais pas russir Nous avons toujours {H1, H2, H3} C
ENSI
Logique formelle
75
Calcul des propositions Commentaires sur les connecteurs logiques Conjonction A B
Smantique
A et B ; A mais B ; A quoique B ; A tandis que B Disjonction A B A ou B ; A sinon B ; Ou exclusif ou inclusif ( vel en latin) A moins que B
A ou/et B (juridique) ; A sauf si B ;
A ou B et peut tre les deux
A B (A B) ( A B) soit A, soit (exclusivement) B
suite
Logique formelle 76
A ou B mais pas les deux ; ( aut en latin)
ENSI
Calcul des propositions Implication A B
Smantique
si / lorsque A, alors / ncessairement/ cest que B A implique / entrane B A est condition suffisante de / suffit B A seulement si / que si B B si /lorsque A B est condition ncessaire de A
suite
ENSI Logique formelle 77
Calcul des propositions Equivalence A B A (est) quivalent B A si et seulement si B
Smantique
A est condition ncessaire est suffisante (CNS) de B A si B et rciproquement
78
A ssi B : A seulement si B (A B) A cns B : A condition suffisante B
; A si B (A B) B)
(A
B)
A condition ncessaire B (A
ENSI Logique formelle
Calcul des propositions
Smantique
7- Formes normales
Dfinition On appelle littral un atome ou une ngation datome (ex. : p , p , ) Une formule est dite sous forme normale disjonctive (FND) si elle est sous forme de disjonction de conjonctions de littraux ( l11 ... l1i ) ( l21 ... l2j) ( ln1 ... lnk )
suite
ENSI Logique formelle 79
Calcul des propositions
Smantique
Dfinition (suite) Une formule est dite sous forme normale conjonctive (FNC) si elle est sous forme de conjonction de disjonctions de littraux ( l11 ... l1i ) ( l21 ... l2j) ... ( ln1 ... lnk ) Une disjonction de littraux est appele une clause
ENSI
Logique formelle
80
Calcul des propositions
Smantique
Exemples Formule en FND : Formule en FNC : (p q) p (p q) (rs)
Formules la fois en FNC et FND : p p q pq
ENSI
Logique formelle
81
Calcul des propositions
Smantique
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 ngations appliques des sous-formules ( A) A (A B) ( A B) (A B) ( A B)
suite
ENSI Logique formelle 82
Calcul des propositions
Smantique
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 une FND) Ceci ncessite lapplication des lois dassociativit et de commutativit
ENSI
Logique formelle
83
Calcul des propositions Thorme
Smantique
Toute formule admet une FNC et une FND et qui sont smantiquement quivalentes Remarque Les FNC et les FND pour une formule donnes ne sont pas uniques mais elles sont toutes smantiquement quivalentes (syntaxiquement diffrentes mais smantiquement quivalentes )
ENSI
Logique formelle
84
