Upload
others
View
2
Download
0
Embed Size (px)
Citation preview
INFO-F-302, Cours d’Informatique Fondamentale
La Logique Propositionnelle
Logique PropositionnelleLogique Propositionnelle Definitions de base : Syntaxe, Semantique et
Exemples
INFO-F-302, Cours d’Informatique Fondamentale
La Logique Propositionnelle
Syntaxe
34 Construction des formules
Le vocabulaire du langage de la logique propositionnelle est compose :
I d’un ensemble, fini ou denombrable, de propositions noteesp, q, r , . . .Dans la suite, nous notons les ensembles de propositions par leslettres P , Q,... ;
I de deux constantes : vrai (notee >) et faux (notee ?), parfois notee1 et 0 ;
I d’un ensemble de connecteurs logiques : et (note ^), ou (note _),non (note ¬), implique (note !), equivalent (note $) ;
I les parentheses : (,).
INFO-F-302, Cours d’Informatique Fondamentale
La Logique Propositionnelle
Syntaxe
35 Construction des formules
Soit P un ensemble de propositions. Les formules de la logiquepropositionnelle respectent la regle de formation BNF suivante :
� ::= > | ? | p | �1 ^ �2 | �1 _ �2 | �1 ! �2 | �1 $ �2 | ¬�1 | (�1)
Ou >, ? sont respectivement les constantes vrai et faux, p 2 P est uneproposition et �1, �2 sont des formules propositionnelles bien formees.
INFO-F-302, Cours d’Informatique Fondamentale
La Logique Propositionnelle
Syntaxe
36 Quelques exemples de formules
Voici quelques exemples de formules et leur lecture intuitive :
I la formule propositionnelle ”p ! (q ^ r)”, peut etre lue de la faconsuivante ”p implique q et r”, ou peut etre egalement lue comme ”sip est vrai alors q et r doivent etre vrais” ;
I la formule propositionnelle ”¬(p ^ q)”, peut-etre lue de la faconsuivante ”il est faux que p et q soient vrais (en meme temps)”.
INFO-F-302, Cours d’Informatique Fondamentale
La Logique Propositionnelle
Syntaxe
37 AmbiguıtesL’utilisation de la notation infixe s’accompagne de problemes de lecture :
Comment lire p ^ q _ r ? p ! q ! r ?
Pour lever les ambiguıtes, on utilise les parentheses ou des regles depriorite entre operateurs :
I si op1 a une plus grande precedence (priorite) que op2 alors
e1op1e2op2e3 est equivalent a ((e1op1e2)op2e3)I
Par ex :2⇥ 3 + 5 = (2⇥ 3) + 5 = 11 6= 2⇥ (3 + 5) = 16.
I si op2 a une plus grande precedence (priorite) que op1 alors
e1op1e2op2e3 est equivalent a (e1op1(e2op2e3))I
Par ex :2 + 3⇥ 5 = 2 + (3⇥ 5) = 17.
I si op est associatif a gauche alors
e1ope2ope3 est equivalent a ((e1ope2)ope3)I
Par ex : 10/2/5 = (10/2)/5 = 1 6= 10/(2/5) = 25.
Il faut donc fixer des regles de priorite entre operateurs afin d’avoir unelecture unique de la formule.
INFO-F-302, Cours d’Informatique Fondamentale
La Logique Propositionnelle
Syntaxe
38 Regles de precedence en logique propositionnelle
Ordre de precedence � sur les operateurs :
$ � ! � _ � ^ � ¬
et associativite a gauche pour $,_,^ et a droite pour !.
Exemplesp _ q ^ r se lit p _ (q ^ r)p ! q ! p se lit p ! (q ! p)p _ q ! r se lit (p _ q) ! r¬p ^ q se lit (¬p) ^ qp ! q ^ r ! s se lit p ! ((q ^ r) ! s)
Remarque
Les parentheses permettent de contrecarrer ces regles, si elles neconviennent pas. Elles permettent aussi de rendre une formule plus lisible,ou de ne pas devoir retenir les regles de precedence.
INFO-F-302, Cours d’Informatique Fondamentale
La Logique Propositionnelle
Syntaxe
39 Arbre correspondant a une formuleLa formule p ! q ^ r ! s est donc equivalente a
p ! ((q ^ r) ! s)
et donc son arbre de lecture est :
!
p !
^
q r
s
INFO-F-302, Cours d’Informatique Fondamentale
La Logique Propositionnelle
Semantique
40 La semantique
I jusqu’ici, on a vu la syntaxe des formules, qui ne sont rien d’autreque des suites de caracteres sans signification.
I la semantique donne du sens aux formules, elle permet de lesinterpreter et de leur attribuer une valeur de verite vrai ou faux.
I l’interpretation des symboles de proposition est cependant libre etc’est a nous de la fixer. On se donnera donc une une fonctiond’interpretation V pour l’ensemble P de propositions considerees :
V : P ! {0, 1}
Cette fonction assigne a chaque proposition de P la valeur vrai ou lavaleur faux.
I Dans la suite, nous utiliserons parfois le terme valuation , souventutilise dans la litterature, au lieu de fonction d’interpretation.
I A partir d’une fonction d’interpretation V des symboles deproposition, nous allons voir comment interpreter les formules.
INFO-F-302, Cours d’Informatique Fondamentale
La Logique Propositionnelle
Semantique
41 La semantique
Definition
I La valeur de verite d’une formule propositionnelle � formee a partirdes propositions d’un ensemble P , evaluee avec la fonctiond’interpretation V , est notee [[�]]
V
. En particulier, on a[[�]]
V
2 {0, 1}.I La fonction [[�]]
V
est definie par induction sur la syntaxe de � de lafacon suivante :
I � = >, dans ce cas, [[�]]V
= 1 ;
I � = ?, dans ce cas, [[�]]V
= 0 ;
I � = p, dans ce cas, [[�]]V
= V (p).
I � = ¬�1, [[�]]V
=
⇢0 si [[�1]]
V
= 1
1 si [[�1]]V
= 0
I � = �1 _ �2, [[�]]V
= 1 ssi [[�1]]V
= 1 ou [[�2]]V
= 1
I � = �1 ^ �2, [[�]]V
= 1 ssi [[�1]]V
= 1 et [[�2]]V
= 1
INFO-F-302, Cours d’Informatique Fondamentale
La Logique Propositionnelle
Semantique
42 La semantique
I � = �1 ! �2,
[[�]]V
= 1 ssi [[�1]]V = 0ou [[�2]]V = 1
I � = �1 $ �2,
[[�]]V
= 1 ssi[[�1]]V = 0 et [[�2]]V = 0ou[[�1]]V = 1 et [[�2]]V = 1
I � = (�1), [[�]]V = [[�1]]V .
Nous notons V |=� si et seulement si [[�]]V
= 1, qui se dit “V satisfait �”.
INFO-F-302, Cours d’Informatique Fondamentale
La Logique Propositionnelle
Semantique
43 La semantique sous forme de tables de verites
L’information contenue dans la definition precedente est souventpresentee sous forme de tables, appelees tables de verite :
> ?1 0
� ¬� (�)1 0 10 1 0
INFO-F-302, Cours d’Informatique Fondamentale
La Logique Propositionnelle
Semantique
44 La semantique sous forme de tables de verites
�1 �2 �1 ^ �2 �1 _ �2 �1 ! �2 �1 $ �21 1 1 1 1 11 0 0 1 0 00 1 0 1 1 00 0 0 0 1 1
INFO-F-302, Cours d’Informatique Fondamentale
La Logique Propositionnelle
Exemples
45 Exemples
I Prenons l’interpretation V1(p) = 0, alors on a :
[[p]]V1 = 0 [[¬p]]
V1 = 1 [[p ^ p]]V1 = 0 [[p ^ ¬p]]
V1 = 0[[p ! p]]
V1 = 1 [[p $ p]]V1 = 1 [[¬p ! p]]
V1 = 0
I Prenons la formule � = (p _ q) ^ (¬q _ r) et l’interpretationV2(p) = V2(r) = 1 et V2(q) = 0. Pour calculer la valeur de verite de�, on calcule d’abord les valeurs de verite des sous-formules et onapplique les tables de verite.
(p _ q) ^ (¬q _ r)(1 _ 0) ^ (¬0 _ 1)(1 _ 0) ^ (1 _ 1)
1 ^ (1 _ 1)1 ^ 11
Donc [[�]]V2 = 1.
INFO-F-302, Cours d’Informatique Fondamentale
La Logique Propositionnelle
Exemples
46 Exemples
I Prenons la meme formule � = (p _ q) ^ (¬q _ r) et l’interpretationV3(r) = 1 et V3(p) = V3(q) = 0.
(p _ q) ^ (¬q _ r)(0 _ 0) ^ (¬0 _ 1)(0 _ 0) ^ (1 _ 1)
0 ^ (1 _ 1)0 ^ 10
Donc [[�]]V3 = 0.
INFO-F-302, Cours d’Informatique Fondamentale
La Logique Propositionnelle
Exemples
47 Exemples
On peut utiliser le principe de decomposition en sous-formule etl’application des tables de verite pour obtenir la valeur de verite de �pour toutes les interpretations possibles des variables
p q r (p _ q) ¬q (¬q _ r) (p _ q) ^ (¬q _ r)1 1 1 1 0 1 11 1 0 1 0 1 11 0 1 1 1 1 11 0 0 1 1 1 10 1 1 1 0 1 10 1 0 1 0 0 00 0 1 0 1 1 00 0 0 0 1 1 0
INFO-F-302, Cours d’Informatique Fondamentale
La Logique Propositionnelle
Exemples
48 Exemples
I ¬p _ q (qui se lit (¬p) _ q)
p q ¬p ¬p _ q1 1 0 11 0 0 00 1 1 10 0 1 1
I Remarque : c’est la meme table de verite que pour l’implication :
p q p ! q1 1 11 0 00 1 10 0 1
I On dira que les deux formules ¬p _ q et p ! q sont equivalentes.
INFO-F-302, Cours d’Informatique Fondamentale
La Logique Propositionnelle
Exemples
49 Remarques sur l’implication
I l’implication �1 ! �2 modelise le raisonnement si-alors :
Si �1 est vraie, ALORS �2 est vraie aussi.
I le cas ou �1 est faux ne nous interesse pas dans l’implication.
I par consequent, si �1 est faux, alors peu importe la valeur de veritede �2, l’implication �1 ! �2 reste vraie.
I Autrement dit le faux implique le vrai, et le faux, mais le vrai doittoujours impliquer le vrai.
INFO-F-302, Cours d’Informatique Fondamentale
La Logique Propositionnelle
Exemples
50 Un dernier exemple : � = ¬(p ^ q) $ (¬p _ ¬q)
I Calculons la table de verite :
p q p ^ q ¬(p ^ q) ¬p ¬q ¬p _ ¬q �1 1 1 0 0 0 0 11 0 0 1 0 1 1 10 1 0 1 1 0 1 10 0 0 1 1 1 1 1
I pour toute les interpretations possibles des propositions, � est vraie.On dira dans ce cas que � est valide.
I En fait, on a montre ici que les deux formule ¬(p ^ q) et ¬p _ ¬qsont equivalentes. C’est une des lois de Morgan.
INFO-F-302, Cours d’Informatique Fondamentale
La Logique Propositionnelle
Exemples
51 Exercices
Dire pour les interpretations V et les formules � suivantes si V |= � :
1. V (p) = 1, V (q) = 0 et � = (p ! q) ^ (p ! ¬q)2. V (p) = V (q) = 0 et � = ((¬p ! q) ! (¬q ! p)) ^ (p _ q)
3. V (p) = 0 et V (q) = 1 et � = ((¬p _ q) ! (q ^ (p $ q))
4. V (p) = V (r) = 1 et V (q) = 0 et� = ((¬r ! ¬p ^ ¬q) _ s) $ (p _ q ! r _ s)
5. V (p) = V (q) = 0 et V (r) = 1 et� = (p ^ (q ! r)) $ ((¬p _ q) ! (p ^ r)).
Construire les tables de verite pour les formules suivantes :
1. (p ! q) _ (q ! p)
2. p ^ (p ! ¬q) ^ q
3. (p ! (q ^ r)) $ (p ! q) ^ (p ! r)
4. (p ! (q ! r)) ! ((p ^ q) ! r)
INFO-F-302, Cours d’Informatique Fondamentale
La Logique Propositionnelle
Satisfaisabilite et Validite
52 Validite et Satisfaisabilite
Voici deux definitions importantes :
Definition (Satisfaisabilite)
Une formule propositionnelle � est satisfaisable si et seulement si il existeune fonction d’interpretation V pour les propositions de �, telle queV |=�.
Definition (Validite)
Une formule propositionnelle � est valide si et seulement si pour toutefonction d’interpretation V pour les propositions de �, on a V |=�.
INFO-F-302, Cours d’Informatique Fondamentale
La Logique Propositionnelle
Satisfaisabilite et Validite
53 Exemples
formule satisfaisable valide> oui ouip oui non
V (p) = 1 V (p) = 0¬p oui non
V (p) = 0 V (p) = 1(p _ q) ^ (¬q _ r) oui non
voir table precedente voir table precedentep ^ ¬p non non
p ^ ¬q ^ (¬q ! ¬p) non nonp _ ¬p oui oui
(p ! q) _ (q ! p) oui oui
INFO-F-302, Cours d’Informatique Fondamentale
La Logique Propositionnelle
Satisfaisabilite et Validite
54 Notion de consequence logique
DefinitionSoit �1, . . . ,�n,� des formules. On dira que � est une consequencelogique de �1, . . . ,�n, note �1, . . . ,�n |= �, si (�1 ^ · · · ^ �
n
) ! � estvalide.
Par exemple, p,¬p |= ?, et �1,�1 ! �2 |= �2.
INFO-F-302, Cours d’Informatique Fondamentale
La Logique Propositionnelle
Satisfaisabilite et Validite
55 Application importante de la notion de validite
DefinitionDeux formules � et sont dites equivalentes si la formule �$ estvalide. On notera � ⌘ pour signifier que � et sont equivalentes.
I dans une formule, on peut substituer une sous-formule par une autreequivalente sans changer la semantique de la formule de depart
I par exemple, dans la formule
� = (p _ q) ^ ¬(p ^ r)
on peut remplacer la sous-formule ¬(p ^ r) par (¬p _ ¬r) et onobtient la formule suivante, qui est equivalente a � :
�0 = (p _ q) ^ (¬p _ ¬r)
I l’application d’equivalences simples va nous permettre de simplifierdes formules, et de les mettre sous des formes particulieres
INFO-F-302, Cours d’Informatique Fondamentale
La Logique Propositionnelle
Satisfaisabilite et Validite
56 Quelques equivalences
Pour toutes formules �1,�2,�3, on a :
I ¬¬�1 ⌘ �1 (double negation)
I ¬(�1 ^ �2) ⌘ (¬�1 _ ¬�2) (loi de De Morgan pour le ’et’)
I ¬(�1 _ �2) ⌘ (¬�1 ^ ¬�2) (loi de De Morgan pour le ’ou’)
I �1 ^ (�2 _ �3) ⌘ (�1 ^ �2) _ (�1 ^ �3) (distributivite du ’et’)
I �1 _ (�2 ^ �3) ⌘ (�1 _ �2) ^ (�1 _ �3 (distributivite du ’ou’)
I �1 ! �2 ⌘ ¬�2 ! ¬�1 (contraposition)
INFO-F-302, Cours d’Informatique Fondamentale
La Logique Propositionnelle
Satisfaisabilite et Validite
57 Lien entre satisfaisibilite et validite
TheoremeUne formule propositionnelle � est valide ssi sa negation ¬� n’est passatisfaisable.
Par consequent, si on dispose d’un algorithme qui decide si une formuleest satisfaisable ou non, on obtient un algorithme qui decide si la formuleest valide, il su�t de tester la (non-)satisfaisabilite de sa negation.
INFO-F-302, Cours d’Informatique Fondamentale
La Logique Propositionnelle
Satisfaisabilite et Validite
58 Diagramme
INFO-F-302, Cours d’Informatique Fondamentale
La Logique Propositionnelle
Satisfaisabilite et Validite
59 Comment tester la satisfaisabilite d’une formule ?
I on a vu la methode des tables de verite : tester toutes lesinterpretations de propositions jusqu’a ce qu’on en trouve une quisatisfait la formule
I probleme : quelle est la complexite d’un tel algorithme ? combiend’interpretations faut-il tester si la formule contient n propositions ?
I il faut essayer, dans le pire des cas (c’est a dire le cas ou la formulen’est pas satisfaisable), 2n interpretations : cet algorithme a doncune complexite exponentielle dans le nombre de propositions
I ce n’est pas raisonnable pour les applications que nous allonsaborder, car nous allons generer des formules contenant plusieurscentaines de propositions.
I nous allons maintenant etudier un algorithme “plus intelligent” : lamethode des tableaux semantiques.
INFO-F-302, Cours d’Informatique Fondamentale
La Logique Propositionnelle
Satisfaisabilite et Validite
60 Remarques sur la complexite du probleme SAT
I le probleme de satisfaisabilite d’une formule propositionnelle, appeleprobleme SAT, est dans la classe NP (voir courscalculabilite/complexite)
I actuellement, on ne sait toujours pas s’il existe un algorithme pource probleme dont la complexite en temps est polynomiale.
I la plupart des scientifiques pensent que ce n’est pas le cas, maispersonne n’a ete capable de le montrer.
I ce defit scientifique est plus connu sous la question P 6= NP : est-cequ’il existe un probleme resoluble en temps non-deterministepolynomial qui n’est pas resoluble en temps polynomial ?
I le premier qui aura la reponse (et la preuve de son a�rmation)gagnera 1.000.000$ 1
1. Millenium Prize Problems du Clay Mathematics Institute http://www.claymath.org/millennium/
INFO-F-302, Cours d’Informatique Fondamentale
La Logique Propositionnelle
Satisfaisabilite et Validite
61 Pourquoi SAT est-il si interessant ?
I beaucoup de problemes pratiques interessants se trouvent dans laclasse NP, voir http://www.nada.kth.se/
~
viggo/problemlist/.
I par exemple le probleme du voyageur de commerce : etant donneune distance d et n villes, est-il possible de construire un cycle delongueur au plus d qui passe par les les n villes exactement une fois(sauf la ville de depart). Application : optimiser la trajectoire d’unefraiseuse, d’un bus scolaire, d’un camion de livraison, etc ...
I autre exemple, le bin-packing : etant donne k boıtes de contenancedi↵erentes, n objets de volumes di↵erents, et d � 0 un entier, est-ilpossible de ranger les n objets en utilisant au plus d boıtes.Application : rangement de fichiers sur un support informatique,remplissage de camions ou containers ...
INFO-F-302, Cours d’Informatique Fondamentale
La Logique Propositionnelle
Satisfaisabilite et Validite
62 Pourquoi SAT est-il si interessant ?
I tous les problemes de la classe NP se reduisent au probleme SAT entemps polynomial. En d’autre terme, pour resoudre une instance I duprobleme du voyageur de commerce ou du bin-packing, il est possiblede construire, en temps polynomial, une formule de la logiquepropositionnelle �
I
telle que �I
est satisfaisable ssi I a une solution
I il est donc important d’avoir de “bons” algorithmes pour SAT
INFO-F-302, Cours d’Informatique Fondamentale
La Logique Propositionnelle
Tableaux semantiques
63 Tableaux semantiques
C’est un algorithme pour etablir la satisfaisabilite de formules de lalogique propositionnelle.On a besoin d’une nouvelle definition :
DefinitionUn litteral est une proposition p ou la negation d’une proposition ¬p.
INFO-F-302, Cours d’Informatique Fondamentale
La Logique Propositionnelle
Tableaux semantiques
64 Tableaux semantiques : exemple
Considerons la formule � = p ^ (¬q _ ¬p)Essayons de construire systematiquement une fonction d’interpretation Vtelle que
[[�]]V
= 1
Par definition on a
[[�]]V
= 1ssi
[[p]]V
= 1 et [[¬q _ ¬p]]V
= 1
INFO-F-302, Cours d’Informatique Fondamentale
La Logique Propositionnelle
Tableaux semantiques
et
[[¬q _ ¬p]]V
= 1ssi
[[¬q]]V
= 1 ou [[¬p]]V
= 1
et donc,
[[�]]V
= 1ssi
[[p]]V
= 1 et [[¬q]]V
= 1ou [[p]]
V
= 1 et [[¬p]]V
= 1
Pour �, on construit la fonction d’interpretation V de la facon suivante :
I V (p) = 1 ;
I V (q) = 0.
et on a bien que V |=�.
INFO-F-302, Cours d’Informatique Fondamentale
La Logique Propositionnelle
Tableaux semantiques
66 Tableaux semantiques
I Un ensemble S de litteraux est satisfaisable ssi il ne contient pas unepaire de litteraux complementaires . Par exemple, {p,¬q} estsatisfaisable alors que {p,¬p} ne l’est pas.
I Nous avons reduit le probleme de satisfaction de � a un probleme desatisfaction d’ensembles de litteraux : � est satisfaisable ssi {p,¬q}est satisfaisable ou {p,¬p} est satisfaisable.
INFO-F-302, Cours d’Informatique Fondamentale
La Logique Propositionnelle
Tableaux semantiques
67 Tableaux semantiquesUn autre exemple : � = (p _ q) ^ (¬p ^ ¬q).Par definition, on a
[[�]]V
= 1ssi
[[p _ q]]V
= 1 et [[¬p ^ ¬q]]V
= 1
et donc,
[[�]]V
= 1ssi
[[p _ q]]V
= 1 et [[¬p]]V
= 1 et [[¬q]]V
= 1
et donc,
[[�]]V
= 1ssi
soit [[p]]V
= 1 et [[¬p]]V
= 1 et [[¬q]]V
= 1ou [[q]]
V
= 1 et [[¬p]]V
= 1 et [[¬q]]V
= 1
INFO-F-302, Cours d’Informatique Fondamentale
La Logique Propositionnelle
Tableaux semantiques
68 Tableaux semantiques
et donc,
� est satisfaisablessi
{p,¬p,¬q} est satisfaisableou{q,¬p,¬q} est satisfaisable.
Vu que les deux ensembles de litteraux contiennent chacun uneproposition et sa negation, la formule � n’est pas satisfaisable.
INFO-F-302, Cours d’Informatique Fondamentale
La Logique Propositionnelle
Tableaux semantiques
69 Tableaux semantiques
L’information presente dans les developpements precedents est plusfacilement representee sous forme d’un arbre.Exemple : � = (p _ q) ^ (¬p ^ ¬q) (tableau donne au cours)
INFO-F-302, Cours d’Informatique Fondamentale
La Logique Propositionnelle
Tableaux semantiques
70 Tableaux semantiques – Remarques
I quand on applique le ”pas de simplification” a un noeud ou onselectionne une conjonction, alors on obtient un seul fils ; on appelleces regles, des ^-regles ;
I quand on applique le ”pas de simplification” a un noeud ou onselectionnne une disjonction, alors on obtient deux fils ; on appelleces regles, des _-regles.
INFO-F-302, Cours d’Informatique Fondamentale
La Logique Propositionnelle
Tableaux semantiques
71 Regles de simplification : ^-regles
Etant donne un ensemble S contenant une formule ↵, on cree unensemble fils egal S\{↵} auquel on ajoute ↵1 et ↵2.
↵ ↵1 ↵2
¬¬� ��1 ^ �2 �1 �2
¬(�1 _ �2) ¬�1 ¬�2¬(�1 ! �2) �1 ¬�2�1 $ �2 �1 ! �2 �2 ! �1
^-regles .
Remarque : toutes les formules ↵ peuvent etre considerees commeequivalentes a des conjonctions. Par exemple :
¬(�1 _ �2) est equivalent a ¬�1 ^ ¬�2
INFO-F-302, Cours d’Informatique Fondamentale
La Logique Propositionnelle
Tableaux semantiques
72 Regles de simplification : _-regles
Etant donne un ensemble S contenant une formule �, on cree deuxensembles fils, l’un etant (S [ {�1})\�, et l’autre (S [ {�2})\�.
� �1 �2�1 _ �2 �1 �2
¬(�1 ^ �2) ¬�1 ¬�2�1 ! �2 ¬�1 �2
¬(�1 $ �2) ¬(�1 ! �2) ¬(�2 ! �1)_-regles .
Remarque : toutes les formules � peuvent etre considerees commeequivalentes a des disjonctions. Par exemple :
¬(�1 ^ �2) est equivalent a ¬�1 _ ¬�2
INFO-F-302, Cours d’Informatique Fondamentale
La Logique Propositionnelle
Tableaux semantiques
73 Algorithme
L’algorithme construit a partir d’une formule � un arbre note T� dont lesnoeuds sont des ensembles de formules.
I Initialisation : au depart, l’arbre ne contient qu’un seul noeud :l’ensemble {�} ;
I Tant qu’il existe une feuille de l’arbre F qui contient une formule qui est simplifiable
I si � est simplifiable par une ^-regle, alors on cree un fils F 0a F ou
F 0est obtenu supprimant � de F et en ajoutant la formule (dans le
cas d’une double negation) ou les deux formules (pour les autres cas)
obtenues par la simplification, a l’ensemble F 0
I si � est simplifiable par une _-regle, alors on cree deux fils F1 et F2,
chacun etant obtenu en supprimant � de F et en ajoutant
respectivement les formules obtenues par la simplification.
I si toutes les feuilles de l’arbre contiennent une paire de litterauxcomplementaires, alors retourner non-satisfaisable, sinonretourner satisfaisable.
INFO-F-302, Cours d’Informatique Fondamentale
La Logique Propositionnelle
Tableaux semantiques
74 Exemples
Toutes les feuilles (ici une seule) contiennent une paire de litterauxcomplementaires (a et ¬a), donc la formule n’est pas satisfaisable.
INFO-F-302, Cours d’Informatique Fondamentale
La Logique Propositionnelle
Tableaux semantiques
75 Exemples
Il existe plusieurs feuilles ne contenant pas de paire de litterauxcomplementaires, la formule est donc satisfaisable.
INFO-F-302, Cours d’Informatique Fondamentale
La Logique Propositionnelle
Tableaux semantiques
76 Questions
Soit � une formule et T� un arbre construit avec l’algorithme precedent.
1. Si toutes les feuilles de T� sont satisfaisables, est-ce que cela signifieque � est valide ? Non : prendre par exemple � = p.
2. quelle est la taille maximale de T� (nombre de noeuds) en fonctiondu nombre de symboles de � ? T� peut avoir un nombre exponentielde noeuds. Par exemple, prenons n � 0 et� = (p1 _ q1) ^ (p2 _ q2) · · · ^ (p
n
_ qn
), alors T� a au moins2n+1 + n � 2 noeuds, et exactement 2n feuilles. L’algorithme a doncune complexite exponentielle en temps dans le pire cas.
INFO-F-302, Cours d’Informatique Fondamentale
La Logique Propositionnelle
Tableaux semantiques
77 Tableaux Semantiques : Resume
I la methode des tableaux semantiques est un algorithme pour tester lasatisfaisabilite d’une formule.
I elle est basee sur la construction d’un arbre par applications successives de reglesde simplifications de formules (tableaux)
I les formules equivalentes a une disjonction (disjonction, implication, negationd’une conjonction, negation d’une equivalence) sont satisfaites si un des deuxmembres de la disjonction est satisfait : les deux choix sont representes par dubranchement (deux fils) dans l’arbre.
I les formules equivalentes a une conjonction (conjonction, equivalence, negationd’une implication et d’une disjonction) sont satisfaites si les deux membres de laconjonction sont satisfaits : un seul fils est creer dans l’arbre.
I les feuilles de l’arbres sont des ensembles de litteraux (donc non simplifiables),pour lesquels la satisfaisabilite est facile a tester (absence de litterauxcomplementaires).
I dans le pire cas, l’arbre cree est exponentiellement plus grand que la formule
I pour tester la validite d’une formule, on peut tester la non satisfaisabilite de senegation par la methode des tableaux semantiques.
INFO-F-302, Cours d’Informatique Fondamentale
La Logique Propositionnelle
La deduction naturelle
La Deduction Naturelle
INFO-F-302, Cours d’Informatique Fondamentale
La Logique Propositionnelle
La deduction naturelle
79 Introduction
I L’algorithme des tableaux semantique ne convient pas pour faire desraisonnements “a la main” sur des formules propositionnelles.
I Quand on fait des preuves en mathematique, on utilise des regles quinous permettent, pas par pas, de deduire des conclusions a partir depremisses.
I La deduction naturelle est une formalisation de ce type deraisonnement.
INFO-F-302, Cours d’Informatique Fondamentale
La Logique Propositionnelle
La deduction naturelle
80 Introduction
I Supposons donnee un ensemble de formules �1, . . . ,�n que nousappelons premisses et une formule que nous appelons conclusion .
I Supposons que l’on desire montrer que peut etre derivee de�1, . . . ,�n ; on notera cette intention �1, . . . ,�n ` , cette derniereexpression est appelee un sequent .
I La notion de derivation syntaxique est formalisee avec des regles dededuction.
I Les regles de deduction permettent de faire le lien entre la syntaxeet la semantique, en e↵et, on aura :
�1, . . . ,�n ` ssi �1, . . . ,�n |=
INFO-F-302, Cours d’Informatique Fondamentale
La Logique Propositionnelle
La deduction naturelle
81 La conjonction
Regles pour la conjonction :
I Regle d’introduction :
� �^ ^i
I Regle d’elimination :
�^ � ^e1
�^ ^e2
Par exemple, la regle d’introduction se lit : si j’ai une preuve de � et unepreuve de , alors j’ai une preuve de � ^ .
INFO-F-302, Cours d’Informatique Fondamentale
La Logique Propositionnelle
La deduction naturelle
82 La conjonction
Exemples d’utilisation de ces regles pour la conjonction :
I p ^ q, r `? q ^ r .
1 p ^ q premisse2 r premisse3 q ^
e2 , 14 q ^ r ^
i
, 3, 2
I (p ^ q) ^ r , s ^ t ` q ^ s ;
I p ^ q ` q ^ p ;
I (p ^ q) ^ r ` p ^ (q ^ r) ;
INFO-F-302, Cours d’Informatique Fondamentale
La Logique Propositionnelle
La deduction naturelle
83 Double negation
Regles pour la (double) negation :
I Introduction :
�¬¬�¬¬i
I Elimination :
¬¬�� ¬¬e
Exemple : p,¬¬(q ^ r) ` ¬¬p ^ r
INFO-F-302, Cours d’Informatique Fondamentale
La Logique Propositionnelle
La deduction naturelle
84 Elimination de l’implication : Modus Ponens
Regle pour l’elimination de l’implication (Modus Ponens ) :
� �! !e
Illustration
1. il pleut ;
2. si il pleut alors la route est mouillee.
alors on peut deduire que la route est mouillee.
INFO-F-302, Cours d’Informatique Fondamentale
La Logique Propositionnelle
La deduction naturelle
85 Elimination de l’implication : Modus Ponens
Analogie avec les types de fonctions dans les langages deprogrammation
I Soient f une fonction d’elements de type t1 vers des elements detype t2, et e une valeur de type t1, alors f (e) est une valeur de typet2. On note ceci f : t1 ! t2, e : t1 et f (e) : t2.
I Une fonction f : t1 ! (t2 ! t3) est une fonction qui prend enargument un element de type t1 et retourne une fontion de typet2 ! t3. Etant donnes deux elements e1 : t1 et e2 : t2, on af (e1) : t2 ! t3 et f (e1)(e2) : t3.
I Une application du Modus Ponens correspond a appliquer unefonction a son argument.
INFO-F-302, Cours d’Informatique Fondamentale
La Logique Propositionnelle
La deduction naturelle
86 Elimination de l’implication : Modus Ponens
Etant donnees les premisses
1. p ;
2. p ! q ;
3. p ! (q ! r)
Peut-on deduire r ?
1 p premisse2 p ! q premisse3 p ! (q ! r) premisse4 q !
e
, 1, 25 q ! r !
e
, 1, 36 r !
e
, 4, 5
INFO-F-302, Cours d’Informatique Fondamentale
La Logique Propositionnelle
La deduction naturelle
87 Contraposition ou Modus Tollens
Supposons que p ! q et ¬q soient vraies, si p est vrai alors par la regledu modus ponens on peut deriver q ce qui est en contradiction avec lefait que ¬q est vrai, donc on en deduit que ¬p est vrai. Ce raisonnementest resume dans la regle suivante, appelee regle de Modus Tollens :
�! ¬ ¬� MT
INFO-F-302, Cours d’Informatique Fondamentale
La Logique Propositionnelle
La deduction naturelle
88 Contraposition ou Modus Tollens
Prouvons le sequent suivant :
p ! (q ! r), p,¬r ` ¬q
1 p ! (q ! r) premisse2 p premisse3 ¬r premisse4 q ! r !
e
1et25 ¬q MT4, 3
INFO-F-302, Cours d’Informatique Fondamentale
La Logique Propositionnelle
La deduction naturelle
89 Contraposition ou Modus Tollens
MT nous a permis de montrer :
p ! q,¬q ` ¬p
et le sequent
p ! q ` ¬q ! ¬p
semble d’une certaine facon dire la meme chose. Mais jusqu’a present,nous n’avons pas de regles pour introduire le connecteur “implication”.
INFO-F-302, Cours d’Informatique Fondamentale
La Logique Propositionnelle
La deduction naturelle
90 Introduction de l’implication
Le raisonnement a partir d’hypotheses :On sait que p ! q est vrai. Si on suppose (on fait l’hypothese) que ¬qest vrai alors on peut deduire grace a la regle MT que p est faux. Doncen supposant ¬q on peut deduire ¬p donc “¬q implique ¬p”, exprime demaniere symbolique ¬q ! ¬p est deduit.L’argument pour p ! q ` ¬q ! ¬p peut etre resume de la faconsuivante :
1 p ! q premisse2 ¬q hyp.3 ¬p MT1, 2, fin hyp.24 ¬q ! ¬p !
i
, 2� 3
INFO-F-302, Cours d’Informatique Fondamentale
La Logique Propositionnelle
La deduction naturelle
91 Introduction de l’implication
Regle pour l’introduction de l’implication :
� hyp.··· fin hyp.
�! !i
INFO-F-302, Cours d’Informatique Fondamentale
La Logique Propositionnelle
La deduction naturelle
92 Introduction de l’implication
Prouvons le sequent ¬q ! ¬p ` p ! ¬¬q :
1 ¬q ! ¬p premisse2 p hyp.3 ¬¬p ¬¬
i
, 24 ¬¬q MT , 1, 3, fin hyp.25 p ! ¬¬q !
i
, 2� 4
INFO-F-302, Cours d’Informatique Fondamentale
La Logique Propositionnelle
La deduction naturelle
93 Introduction de l’implication
Preuves de formules vraies sans premisse :
1 p hyp.2 ¬¬p ¬¬
i
, 1, fin hyp.13 p ! ¬¬p !
i
, 1� 2
Donc on a etabli ` p ! ¬¬pNote : les formules � telles que ` � sont appelees theoremes. Comme onle verra dans la suite du cours, ` � ssi |= � et donc pour le systeme dededuction naturelle en logique propositionnelle, les theoremes coincidentavec les formules valides.
INFO-F-302, Cours d’Informatique Fondamentale
La Logique Propositionnelle
La deduction naturelle
94 Introduction de l’implication
Toute preuve de �1, . . . ,�n ` est facilement transformable en unpreuve de ` �1 ! �2 ! . . .�
n
! , on obtient donc le lemme suivant :
LemmePour toutes formules �1, . . . ,�n, ,
�1, . . . ,�n ` ssi ` �1 ! �2 ! . . .�n
!
INFO-F-302, Cours d’Informatique Fondamentale
La Logique Propositionnelle
La deduction naturelle
95 Introduction de l’implicationProuvons le sequent suivant :
`? (q ! r) ! ((¬q ! ¬p) ! (p ! r))
1 q ! r hyp.2 ¬q ! ¬p hyp.3 p hyp.4 ¬¬p ¬¬
i
, 35 ¬¬q MT2, 46 q ¬¬
e
57 r !
e
1, 6, fin hyp.38 p ! r !
i
3� 7, fin hyp.29 (¬q ! ¬p) ! (p ! r) !
i
2, 8, fin hyp.110 (q ! r)
! ((¬q ! ¬p) ! (p ! r)) !i
1, 9
INFO-F-302, Cours d’Informatique Fondamentale
La Logique Propositionnelle
La deduction naturelle
96 Introduction de la disjonction
Regle pour introduire la disjonction :
��_ _i1
�_ _i2
INFO-F-302, Cours d’Informatique Fondamentale
La Logique Propositionnelle
La deduction naturelle
97 Comment eliminer la disjonction ?
Imaginons que l’on puisse :
1. etablir une formule � sous hypothese que 1 est vrai,
2. et que l’on puisse egalement etablir � sous hypothese que 2 estvrai,
3. et qu’il existe une preuve pour 1 _ 2
alors on devrait pouvoir deduire �.
Exemple
Supposons que les faits suivant soient vrais :
1. si ma note d’examen est excellente, j’irai boire un verre
2. si ma note d’examen est bonne, j’irai boire un verre
3. ma note sera bonne ou excellente
Je peux donc en deduire que j’irai boire un verre.
INFO-F-302, Cours d’Informatique Fondamentale
La Logique Propositionnelle
La deduction naturelle
Cette strategie de preuve est formalisee dans la regle suivante :
1hyp. 2hyp.· ·· ·· ·
1 _ 2 �fin hyp. �fin hyp.� _e
Attention : dans chacun des deux cas, on ne peut pas utiliser l’hypothesetemporaire faite pour l’autre cas, sauf si cette hypothese a ete etablieavant.
INFO-F-302, Cours d’Informatique Fondamentale
La Logique Propositionnelle
La deduction naturelle
99 Elimination de la disjonction
Prouvons le sequent
p _ q ` q _ p
1 p _ q premisse2 p hyp.3 q _ p _
i2 , fin hyp.24 q hyp.5 q _ p _
i1 , fin hyp.46 q _ p _
e
1, 4� 5, 2� 3
INFO-F-302, Cours d’Informatique Fondamentale
La Logique Propositionnelle
La deduction naturelle
100 Deduction naturelle
Regle de copie pour conclure un raisonnement sous-hypothese.
��copie
Considerons le sequent :
` p ! (q ! p)
Et la preuve suivante :
1 p hyp.2 q hyp.3 p copie1, fin hyp.24 q ! p !
i
2, 3, fin hyp.15 p ! (q ! p) !
i
1� 4
INFO-F-302, Cours d’Informatique Fondamentale
La Logique Propositionnelle
La deduction naturelle
101 Regles pour la negation.
Les contradictions sont des formules de la forme :
¬� ^ � ou � ^ ¬�
I Notons qu’aucune valuation ne satisfait une contradiction. Donc ona ¬� ^ � |= pour n’importe quel . Donc si la methode dededuction est complete, on devrait avoir : ¬� ^ � ` pourn’importe quel .
I intuition : si le faux est vrai, alors tout est vrai.
I Toutes les contradictions sont logiquement equivalentes a la formule?.
INFO-F-302, Cours d’Informatique Fondamentale
La Logique Propositionnelle
La deduction naturelle
Regles pour la negation.
Le fait que l’on peut tout deduire a partir d’une contradiction estformalise par la regle suivante :
?�?e
Le fait que ? represente une contradiction est formalise par la reglesuivante :
� ¬�? ¬e
Comment introduire une negation ?
INFO-F-302, Cours d’Informatique Fondamentale
La Logique Propositionnelle
La deduction naturelle
Supposons que l’on fasse une hypothese et que l’on arrive a deduire unecontradiction, dans ce cas l’hypothese est fausse. Ceci est formalise par laregle de preuve suivante :
� hyp.···? fin hyp.
¬� ¬i
INFO-F-302, Cours d’Informatique Fondamentale
La Logique Propositionnelle
La deduction naturelle
104 Exemple avec la negation
On est maintenant en mesure de prouver le sequent de l’exempleintroductif (taxi-train-invite) :
p ^ ¬q ! r ,¬r , p ` q
1 p ^ ¬q ! r premisse2 ¬r premisse3 p premisse4 ¬q hyp.5 p ^ ¬q ^
i
3, 46 r !
e
1, 57 ? ¬
e
6, 2, fin hyp.48 ¬¬q ¬
i
4� 79 q ¬¬
e
8
INFO-F-302, Cours d’Informatique Fondamentale
La Logique Propositionnelle
La deduction naturelle
105 Regles pour l’equivalence
�1 ! �2 �2 ! �1�1 $ �2
($i)
�1 $ �2�1 ! �2
($e1)
�1 $ �2
�2 ! �1($e1)
INFO-F-302, Cours d’Informatique Fondamentale
La Logique Propositionnelle
La deduction naturelle
106 Regles derivees
Notons que MT
�! ¬ ¬� MT
est une regle derivee. En e↵et :
1 �! premisse2 ¬ premisse3 � hyp.4 !
e
1, 35 ? ¬
e
4, 2, fin hyp.36 ¬� ¬
i
3� 5
INFO-F-302, Cours d’Informatique Fondamentale
La Logique Propositionnelle
La deduction naturelle
107 Regles DeriveesAutres regles derivees :
¬� hyp.···? fin hyp.
� RAA
RAA :reductio ad absurdum. Cela s’appelle encore un raisonnement parl’absurde ou par contradiction.
�¬¬�¬¬i
�_¬�LEM
LEM : Law of the excluded middle. La loi du tiers exclu.
INFO-F-302, Cours d’Informatique Fondamentale
La Logique Propositionnelle
La deduction naturelle
108 Theoremes
Theoreme (Adequation)
Pour tout �1, . . . ,�n,�, si �1, . . . ,�n ` �, alors �1, . . . ,�n |= �.
Theoreme (Completude)
Pour tout �1, . . . ,�n,�, si �1, . . . ,�n |= �, alors �1, . . . ,�n ` �.
INFO-F-302, Cours d’Informatique Fondamentale
La Logique Propositionnelle
La deduction naturelle
109 Exercices
Demontrer les sequents suivants en deduction naturelle :
1. ` p ! p
2. ` ¬(p ^ ¬p)3. ` p ! (q ! p)
4. ` p ! ((p ! q) ! q)
5. p ^ q ` p _ r
6. p ^ q ` r ! p
7. p ! q ! r ` (p ^ q) ! r
8. p ! q ! r ` q ! p ! r
9. p !` ¬(p ^ ¬q)10. p ! (q _ r) ` ¬r ! (¬q ! ¬p)11. p _ q, p ! r ,¬s ! ¬p ` r _ s
12. ` p _ ¬p (sans utiliser la regle LEM !)
INFO-F-302, Cours d’Informatique Fondamentale
La Logique Propositionnelle
La deduction naturelle
110 ` p _ ¬p
1. ¬(p _ ¬p) H1
2. p H2
3. p _ ¬p _i1 (2)
4. ? ¬e
(1, 3), FIN H2,5. ¬p ¬
i
(2� 4)6. p _ ¬p _
i2 (5)7. ? ¬
e
(1, 6) FIN H1
8. p _ ¬p RAA (1� 7)
INFO-F-302, Cours d’Informatique Fondamentale
La Logique Propositionnelle
La deduction naturelle
Formes Normales
INFO-F-302, Cours d’Informatique Fondamentale
La Logique Propositionnelle
Formes normales
112 Les formes normales
Une formule est en forme normale conjonctive (FNC) ssi c’est uneconjonction de disjonctions de litteraux, c’est-a-dire une formule de laforme :
Vi
(W
j
(¬)pi,j)
Une formule est en forme normale disjonctive (FND) ssi c’est unedisjonction de conjonctions de litteraux, c’est-a-dire une formule de laforme :
Wi
(V
j
(¬)pi,j)
INFO-F-302, Cours d’Informatique Fondamentale
La Logique Propositionnelle
Formes normales
113 Les formes normales
Exemples :
p ^ (q _ ¬r) ^ (¬p _ r)
est une formule en forme normale conjonctive. Tandis que
p _ (q ^ ¬r) _ (¬p ^ r)
est une formule en forme normale disjonctive.
Exercice : donner une forme normale disjonctive pour la premiereformule et une forme normale conjonctive pour la seconde.
INFO-F-302, Cours d’Informatique Fondamentale
La Logique Propositionnelle
Formes normales
114 Les formes normales
Notons Prop(�) l’ensemble des propositions qui apparaıssent dans laformule �.Fonction associee a une formule :
F� : Valuation ! {0, 1}ou encore
F� : {0, 1}Prop(�) ! {0, 1}
F� assigne a chaque valuation possible pour les propositions de � lavaleur 0 ou 1. On definit F� de la facon suivante :
F�(V ) = [[�]]V
INFO-F-302, Cours d’Informatique Fondamentale
La Logique Propositionnelle
Formes normales
115 Les formes normales
Proposition
Deux formules � et sont equivalentes ssi elles definissent la memefonction, c’est-a-dire pour toute fonction d’interpretation V despropositions de �, F�(V ) = F (V ).
(Preuve laissee comme exercice)
CorollaireIl existe au plus 22
n
formules, deux a deux non equivalentes, du calculpropositionnel construit sur n propositions.
Preuve : Soient A et B deux ensembles finis. Le nombre de fonctions(totales) de A vers B est |B ||A|. Dans notre cas, B = {0, 1} et A estl’ensemble des valuations de n propositions, i.e. des fonctions totales de{p1, . . . , pn} vers {0, 1}, il y en a 2n. Donc |A| = 2n et |B | = 2.L’ensemble des fonctions F� pour toute formule � construite sur npropositions contient donc 22
n
fonctions di↵erentes.
INFO-F-302, Cours d’Informatique Fondamentale
La Logique Propositionnelle
Formes normales
116 Les formes normales
TheoremeToute formule de la logique propositionnelle est equivalente a une formenormale disjonctive et a une forme normale conjonctive.
On utilise les transformations successives suivantes pour obtenir lesformes normales :
1. elimination des connecteurs ! et $ grace aux equivalencessuivantes :
(�! ) ⌘ (¬� _ )(�$ ) ⌘ (¬� _ ) ^ (� _ ¬ )
2. entrer les negations le plus a l’interieur possible :
¬(� ^ ) ⌘ (¬� _ ¬ ) ¬¬� ⌘ �¬(� _ ) ⌘ (¬� ^ ¬ )
3. utilisation des distributivite de ^ et _ l’un par rapport a l’autre :
(� ^ ( _ �)) ⌘ (� ^ ) _ (� ^ �) (pour mise sous FND)(� _ ( ^ �)) ⌘ (� _ ) ^ (� _ �) (pour mise sous FNC)
INFO-F-302, Cours d’Informatique Fondamentale
La Logique Propositionnelle
Formes normales
117 Exercice
Appliquer ces transformations a :
¬(p $ (q ! r))
INFO-F-302, Cours d’Informatique Fondamentale
La Logique Propositionnelle
Formes normales
Solution pour la mise en FNC de ¬(p $ (q ! r))1. on retire les equivalences et implications :
¬((¬p _ ¬q _ r) ^ (¬(¬q _ r) _ p))
2. on pousse les negations a l’interieur :
(p ^ q ^ ¬r) _ ((¬q _ r) ^ ¬p)
3. on distribue :
((p ^ q ^ ¬r) _ (¬q _ r)) ^ ((p ^ q ^ ¬r) _ ¬p)
4. et encore :
(p_¬q_r)^(q_¬q_r)^(¬r_¬q_r)^(p_¬p)^(q_¬p)^(¬r_¬p)
5. on retire les formules equivalentes a > :
(p _ ¬q _ r) ^ (q _ ¬p) ^ (¬r _ ¬p)
INFO-F-302, Cours d’Informatique Fondamentale
La Logique Propositionnelle
La Resolution
La Resolution
INFO-F-302, Cours d’Informatique Fondamentale
La Logique Propositionnelle
La Resolution
120 Introduction
I La resolution est une methode pour tester la satisfaisabilite d’uneformule.
I La resolution est a la base de la programmation logique et estutilisee par les solveurs SAT.
I Basee sur une seule operation simple : la coupure.
I Les formules doivent etres sous FNC, en sous forme d’ensemble declauses.
I La resolution permet d’etablir des preuves par refutation : a partird’un ensemble de clauses, on essaie de deriver ? en appliquantiterativement la regle de coupure. Si on peut deriver ?, alorsl’ensemble de clauses de depart est insatisfaisable.
I On verra que cette methode est complete et adequate : si unensemble de clauses est insatisfaisable, alors il existe une suited’application de la coupure qui mene a ?. Reciproquement, si onarrive a ?, alors l’ensemble de clauses de depart est insatisfaisable.
INFO-F-302, Cours d’Informatique Fondamentale
La Logique Propositionnelle
La Resolution
121 Litteraux et Clauses
Rappels
I Une formule propositionnelle � est un litteral si et seulement si � estune proposition ou la negation d’une proposition.
I Une valuation V satisfait un ensemble de formulesA = {�1, . . . ,�n}, que l’on note V |= A, si et seulement siV |= �1 ^ · · · ^ �
n
. Si A = ?, alors toute valuation V satisfait A.
Donc, p et ¬p sont des litteraux.
DefinitionUne formule propositionnelle � est une clause si � = ? (la clause vide) ou� = `1 _ `2 _ · · · _ `
n
ou n � 1 et chaque `i
, 1 i n, est un litteral .
Par exemple, p _ ¬q _ r est une clause, mais pas p ^ q.
INFO-F-302, Cours d’Informatique Fondamentale
La Logique Propositionnelle
La Resolution
122 Remarque
Une clause
¬a1 _ ¬a2 _ · · · _ ¬am
_ b1 _ b2 _ · · · _ bn
ou a1, a2, . . . , am, b1, b2, . . . , bn sont des propositions peut etre ecritecomme l’implication :
a1 ^ a2 ^ · · · ^ am
! b1 _ b2 _ · · · _ bn
On dit que les proposition ai
apparaissent positivement, et lespropositions b
i
negativement.
INFO-F-302, Cours d’Informatique Fondamentale
La Logique Propositionnelle
La Resolution
123 Exemples de clauses
I une clause negativeExemple : ¬p _ ¬q
I une clause positiveExemple : p _ r
I la clause vide ?I une clause tautologique (une proposition apparaıt positivement et
negativement)Exemple : p _ r _ ¬p
INFO-F-302, Cours d’Informatique Fondamentale
La Logique Propositionnelle
La Resolution
124 Satisfaction de clauses
1. Puisque les clauses sont des formules, la notion de satisfaction declauses est la meme que la satisfaction de formules
2. La clause vide n’est satisfaite par aucune fonction d’interpretation.
3. La clause vide est la seule clause non satisfaisable.
4. Une clause tautologique est satisfaite par toutes les fonctionsd’interpretation.
INFO-F-302, Cours d’Informatique Fondamentale
La Logique Propositionnelle
La Resolution
125 Interpretation des ensembles de clauses
Nous etendons maintenant les notions de satisfaction, satisfaisabilite,validite et consequence logique aux ensembles de clauses :
Definition
1. Un ensemble de clauses S est satisfait par la fonction d’interpretationV si et seulement si on a que V |=C pour toute clause C 2 S .
2. Un ensemble de clauses S est satisfaisable si et seulement si il existeune fonction d’interpretation qui satisfait S .
3. Un ensemble de clauses S est valide si et seulement si toute fonctiond’interpretation V satisfait S .
4. Une clause C est une consequence logique d’un ensemble de clausesS , ce que l’on note S |= C si et seulement si pour toute valuation Vqui satisfait S , V satisfait C .
INFO-F-302, Cours d’Informatique Fondamentale
La Logique Propositionnelle
La Resolution
126 Interpretation des ensembles de clauses
Et donc,
I L’ensemble vide de clause est valide et donc satisfaisable.
I Soit S un ensemble de clauses et C une clause tautologique,S [ {C} est satisfaisable (respectivement valide) si et seulement si Sest satisfaisable (respectivement valide).
I Ce dernier corollaire nous indique que, lorsque l’on veut verifier lasatisfaisabilite ou la validite d’un ensemble de clauses, on peuttoujours supprimer les clauses tautologiques.
INFO-F-302, Cours d’Informatique Fondamentale
La Logique Propositionnelle
La Resolution
127 Exemples
I S1 = {p _ q, r _ ¬p} est satisfaisable par V avec V (p) = V (r) = 1et V (q) = 0
I l’ensemble n’est pas valide car V (p) = V (q) = 0 ne satisfait pas S1.
I la clause p _ r est une consequence logique de S2 = {p _ ¬q, q _ r}.
INFO-F-302, Cours d’Informatique Fondamentale
La Logique Propositionnelle
La Resolution
Equivalence entre ensembles de clauses et formules
Proposition
Toute formule � est equivalente a un ensemble fini de clauses.
Preuve : utiliser la mise sous FNC.Exercice : calculer un ensemble de clauses equivalent a ¬(p $ (q ! r)).
INFO-F-302, Cours d’Informatique Fondamentale
La Logique Propositionnelle
La Resolution
129 Regle de coupure
Exemples de coupure
I |= (¬� _ ) ^ �! (Modus Ponens).
I |= (¬� _ ) ^ (� _ 0) ! _ 0.
DefinitionEtant donnees deux clauses de la forme
C1 = p1 _ · · · _ pi�1 _ p _ p
i+1 _ . . . pn
_ ¬q1 _ · · · _ ¬qm
C2 = ¬s1 _ · · · _ ¬sj�1 _ ¬p _ ¬s
j+1 _ . . .¬sk
_ r1 _ · · · _ r`
i.e. deux clauses qui ont une proposition commune p positive dans C1 etnegative dans C2. La regle de coupure permet de deduire la clause :
C3 = p1 _ · · · _ pi�1 _ p
i+1 _ · · · _ pn
_ r1 _ · · · _ r`_¬q1 _ · · · _ ¬q
m
_ ¬s1 _ · · · _ ¬sj�1 _ ¬s
j+1 _ _¬sk
Si n = k = 1 et m = ` = 0, alors C3 = ?. On note par C1,C2`c
p
C3 le faitque C3 est deductible de C1,C2 par coupure sur la proposition p.
INFO-F-302, Cours d’Informatique Fondamentale
La Logique Propositionnelle
La Resolution
130 Coupures : exemples
I ¬e _ b _ p,¬p _ a _ b `c
p
¬e _ a _ b
I p _ r _ s,¬t _ ¬s _ u `c
s
p _ r _ ¬t _ u
I p _ r _ s,¬t _ ¬s _ ¬p `c
p
r _ s _ ¬t _ ¬s = >I ¬p, p _ q `c
p
q
I ¬p, p `c
p
? (clause vide)
INFO-F-302, Cours d’Informatique Fondamentale
La Logique Propositionnelle
La Resolution
131 Validite de la regle de coupure
TheoremeSi C1,C2`c
p
C3, alors C3 est une consequence logique de C1 ^ C2.
Idee de la preuve
C1 = p1 _ · · · _ pi�1 _ p _ p
i+1 _ . . . pn
_ ¬q1 _ · · · _ ¬qm
C2 = ¬s1 _ · · · _ ¬sj�1 _ ¬p _ ¬s
j+1 _ . . .¬sk
_ r1 _ · · · _ r`C3 = p1 _ · · · _ p
i�1 _ pi+1 _ · · · _ p
n
_ r1 _ · · · _ r`_¬q1 _ · · · _ ¬q
m
_ ¬s1 _ · · · _ ¬sj�1 _ ¬s
j+1 _ _¬sk
Soit V telle que V |= C1 ^ C2, alors
I si V (p) = 0, alorsV |= p1 _ · · ·_ p
i�1 _ pi+1 _ . . . p
n
_¬q1 _ · · ·_¬qm
, donc V |= C3.
I si V (p) = 1, alorsV |= ¬s1 _ · · ·_¬s
j�1 _¬sj+1 _ . . .¬s
k
_ r1 _ · · ·_ r`, donc V |= C3.
INFO-F-302, Cours d’Informatique Fondamentale
La Logique Propositionnelle
La Resolution
132 Elimination de litteraux redondants
Prenons C1 = a _ a _ ¬b _ c et C2 = ¬a _ d . Alors :
1 a _ a _ ¬b _ c premisse2 ¬a _ d premisse3 a _ ¬b _ c _ d a, 1, 2
a est toujours present, et nous ne pourrons jamais deduire la clause¬b _ c _ d . En fait, le systeme n’est pas complet et on doit ajouter unenouvelle regle notee `
r
permettant de retirer la redondance :
`1 _ . . . `i
_ ` _ `i+1 _ . . . `
j�1 _ ` _ `j+1 _ . . . `n
`r
`1 _ · · · _ `i
_ ` _ `i+1 _ · · · _ `
j�1 _ `j+1 _ · · · _ `n
ou les `k
et ` sont des litteraux.
INFO-F-302, Cours d’Informatique Fondamentale
La Logique Propositionnelle
La Resolution
133 Preuve par coupure
DefinitionSoit S un ensemble de clauses et C une clause. Une preuve de C parcoupure a partir de S est une suite finie de clauses C1,C2, . . . ,Cn
ouCn
= C et pour tout i , 1 i n, on a que :
I soit Ci
2 S ;
I ou il existe k , l , 1 k < l < i et p tels que Ck
,Cl
`c
p
Ci
.
I ou il existe 1 k < i tel que Ck
`r
Ci
.
On note par S`cC le fait que C est deductible de S par coupure.
Par exemple : de S = {¬q _ p,¬r _ q, r _ s}`cs _ p avec la preuve parcoupure suivante :
1 ¬q _ p premisse2 ¬r _ q premisse3 r _ s premisse4 p _ ¬r q, 1, 25 s _ p r , 3, 4
INFO-F-302, Cours d’Informatique Fondamentale
La Logique Propositionnelle
La Resolution
134 Preuve par coupure, autres exemplesS = {a _ b _ ¬c , a _ b _ c , a _ ¬b,¬a}`c? En e↵et :
1 a _ b _ ¬c premisse2 a _ b _ c premisse3 a _ ¬b premisse4 ¬a premisse5 ¬b a, 2, 36 a _ c b, 2, 57 c a, 4, 68 a _ b c , 1, 79 b a, 4, 810 ? b, 5, 9
c’est ce qu’on appelle une preuve par refutation. On a derive la clausevide de S , donc S n’est pas satisfaisable. En e↵et, si S etait satisfait parune valuation V , alors par validite de la regle de coupure, on aurait aussique toutes les clauses derivees sont satisfaites par V , et donc aussi ?, cequi est impossible.
INFO-F-302, Cours d’Informatique Fondamentale
La Logique Propositionnelle
La Resolution
135 Adequation des preuves par coupure
TheoremePour tout ensemble de clauses S et pour toute clause C , si S`cC alorsS |= C .
Preuve. La preuve est laissee en exercice. Indices : utiliser la validite de laregle de coupure et raisonner par induction sur la longueur de la preuve.
INFO-F-302, Cours d’Informatique Fondamentale
La Logique Propositionnelle
La Resolution
136 Refutation
DefinitionUne refutation d’un ensemble S de clauses par coupure est une derivationde la clause vide a partir de S .
TheoremeSi il existe un refutation de S par coupure alors l’ensemble de clauses Sest non satisfaisable.
Par exemple, {p,¬p _ q,¬q _ r ,¬r} est non satisfaisable :
1 p premisse2 ¬p _ q premisse3 ¬q _ r premisse4 ¬r premisse5 q p, 1, 26 r q, 2, 57 ? r , 4, 6
INFO-F-302, Cours d’Informatique Fondamentale
La Logique Propositionnelle
La Resolution
137 Exercices
Demontrer que les ensembles de clauses suivants ne sont passatisfaisables en donnant une refutation par coupure.
I S1 = {a _ ¬b _ c , b _ c ,¬a _ c , b _ ¬c ,¬b}I S2 = {a _ ¬b, a _ c ,¬b _ c ,¬a _ b, b _ ¬c ,¬a _ ¬c}
INFO-F-302, Cours d’Informatique Fondamentale
La Logique Propositionnelle
La Resolution
Preuve du theoreme
Si S`c ?, alors S |=?. Supposons que V satisfait S , alors V satisfait ?,c’est qui est impossible. Donc S n’est pas satisfaisable.
INFO-F-302, Cours d’Informatique Fondamentale
La Logique Propositionnelle
La Resolution
139 Preuve par refutation et preuve de consequence logique
QuestionComment peut-on se servir de la notion de refutation pour verifier qu’uneformule � est une consequence logique d’un ensemble fini de formules 1, 2, . . . , n
?
Il su�t de proceder de la facon suivante :
1. transformer la conjonction
1 ^ 2 ^ · · · ^ n
en un ensemble fini S de clauses (cette transformation est toujourspossible) ;
2. de la meme facon, transformer ¬� en un ensemble S 0 de clauses ;
3. construire l’ensemble de toutes les clauses D deductibles par coupurede S [ S 0.
INFO-F-302, Cours d’Informatique Fondamentale
La Logique Propositionnelle
La Resolution
140 Preuve par refutation et preuve de consequence logique
Si la clause vide appartient a l’ensemble D alors l’ensemble D n’est passatisfaisable et donc l’ensemble S [S 0 ne l’est pas non plus, ce qui revienta dire que la formule 1 ^ 2 ^ · · · ^
n
^ ¬� n’est pas satisfaisable etdonc � est une consequence logique de l’ensemble { 1, 2, . . . , n
}.
Remarque : lors du calcul de D, on peut s’arreter des qu’on trouve laclause vide, car on sait qu’alors l’ensemble S [ S 0 n’est pas satisfaisable.
INFO-F-302, Cours d’Informatique Fondamentale
La Logique Propositionnelle
La Resolution
141 Completude de la methode par refutation
La methode par refutation est dite complete :
TheoremeSi un ensemble S de clauses est non satisfaisable, alors on peut deduire laclause vide a partir de S avec un nombre fini de pas de resolution.
INFO-F-302, Cours d’Informatique Fondamentale
La Logique Propositionnelle
La Resolution
Remarques
I on a vu que la reciproque est vraie.
I pour decider si une formule est satisfaisable avec la methode deresolution, il faut appliquer les regles `c
p
et `r
de maniere exhaustivejusqu’a ce qu’on ne genere plus de nouvelles clauses (il y a unnombre fini de clauses pouvant etre deduites), et tester que la clausevide n’a pas ete generee.