PLOG_ppt5

Procdure de preuve par rfutation

Copyr

ight :

Jean-P

hilipp

e Pra

ux


Exemple dutilisation.

Non-dterminisme ce stade de la procdure.

Stratgies de preuve. Procdures dterministesCo

pyrigh

t : Jea

n-Phili

ppe P

raux

Exemple : Supposons vraies les assertions suivantes : Tout dclar coupable aura la tte

tranche. Certains criminels sont en libert. On ne peut pas la fois avoir la tte

tranche et tre en libert.On voudrait prouver que : Certains criminels nont pas t dclars

coupables.

Copyr

ight :

Jean-P

hilipp

e Pra

ux

On choisit un langage pour traduire ces noncs. Ils deviennent :

On veut prouver que :

On forme sa ngation :

1- , ( ) ( )x coupable x guillotine x 2- ( ( ) ( ))x, criminel x libert x

3- , ( ( ) ( ))x guillotine x libert x

C- ( ( ) ( ))x, criminel x coupable x

C- ( ( ) ( ))x, criminel x coupable x Copyr

ight :

Jean-P

hilipp

e Pra

ux

On met sous forme clausale :

1- , ( ) ( )x coupable x guillotine x

2- ( ( ) ( ))x, criminel x libert x


C- ( ( ) ( ))x, criminel x coupable x Co

pyrigh

t : Jea

n-Phili

ppe P

raux






( ) ( )coupable x guillotine x

Copyr

ight :

Jean-P

hilipp

e Pra

ux







criminel( k ) libert( k )

Copyr

ight :

Jean-P

hilipp

e Pra

ux








guillotine( y ) libert( y )

Copyr

ight :

Jean-P

hilipp

e Pra

ux








guillotine( y ) libert( y )

criminel( z ) coupable( z ) Copyr

ight :

Jean-P

hilipp

e Pra

ux

On obtient la forme clausale :

{ coupable( x ) guillotine( x );criminel( k );libert( k );guillotine( y ) libert( y );criminel( z ) coupable( z )}

Copyr

ight :

Jean-P

hilipp

e Pra

ux

criminel( k ) criminel( z ) coupable( z )

( z / k )

coupable( k )

Copyr

ight :

Jean-P

hilipp

e Pra

ux


( z / k )

coupable( k ) coupable( x ) guillotine( x )

( x / k )

guillotine( k )

Copyr

ight :

Jean-P

hilipp

e Pra

ux


( z / k )


( x / k )

guillotine( k ) guillotine( y ) libert( y )

( y / k )

libert( k )

Copyr

ight :

Jean-P

hilipp

e Pra

ux


( z / k )


( x / k )

guillotine( k ) guillotine( y ) libert( y )

( y / k )

libert( k ) libert( k )( )+

CQFDCopyr

ight :

Jean-P

hilipp

e Pra

ux


Pour prouver que est consquence logique de Former la forme clausale C de

utiliser pour cela lalgorithme de la partie 2. Tant que la clause vide nest pas dans C.

Faire :Choisir deux clauses de C. Leur appliquer si cest possible le principe de rsolution (pour cela utiliser lalgorithme dunification de littraux).Adjoindre la clause rsolvante obtenue C.

1 2 n{ , ,..., }

1 n...

Copyr

ight :

Jean-P

hilipp

e Pra

ux

Procdure de preuve par rfutationSi lon produit la clause vide on a bien prouv la conclusion recherche.Si la conclusion est vraie il existe une faon de mener la procdure qui aboutit la clause vide.Si la conclusion nest pas vraie : Parfois on peut sen rendre compte (ex: que des

littraux positifs) En gnral la procdure tournera indfiniment sans

ne jamais aboutir la clause vide . Indcision (on retrouve ici lindcidabilit)

Ca ne marche que lorsque la conclusion est vraie !Co

pyrigh

t : Jea

n-Phili

ppe P

raux

Non dterminisme

Si la conclusion est vraie il existe une faon de mener la procdure qui aboutit la clause vide.Seulement en ltat, la procdure ncessite un choix de lutilisateur, dans le choix des clauses.En ltat, mme lorsque la conclusion est vraie on nest pas assur de produire la clause videCo

pyrigh

t : Jea

n-Phili

ppe P

raux

Stratgie de rsolution

Une stratgie est une faon deffectuer les choix inhrents la procdure.

Il sagit en gnral dun ordonnancement ou dune restriction dans la production des clause.Une stratgie fournit une approche dterministe lapplication de la procdure. Co

pyrigh

t : Jea

n-Phili

ppe P

raux

Stratgies compltes, effectivement compltes

Une stratgie est complte si pour tout ensemble inconsistant de clauses, elle est mme de produire la clause vide.

Une stratgie est effectivement compltelorsque pour tout ensemble inconsistant de clauses, elle est sre de produire la clause vide.Co

pyrigh

t : Jea

n-Phili

ppe P

raux

Graphe de drivation, de rfutation

Un graphe de drivation contient toutes les clauses rsolvantes. Il est en gnral infini.

Exemple. Considrons les hypothses :

On veut prouver la conclusion :

, ,( ( ) ( )),( ( ) ( , ))x y P x Q yz P b R a z

( , ) , ( )R a b u Q u Cop

yright

: Jean

-Philip

pe Pr

aux

On obtient la forme clausale :

{ ( ) ( ( ));( ) ( , );( , );( )}

P x Q f xP b R a yR a bQ z

Copyr

ight :

Jean-P

hilipp

e Pra

ux

Graphe de drivation

( ) ( ( ))P x Q f x ( ) ( , )P b R a y ( , )R a b ( )Q z

( ( )) ( , )Q f b R a y ( )P x ( )P b

( ( ))Q f b ( ( ))Q f b ( , )R a y ( , )R a y+

+ + + +Co

pyrigh

t : Jea

n-Phili

ppe P

raux

Graphe de rfutation


( ( )) ( , )Q f b R a y ( )P x ( )P b

( ( ))Q f b ( ( ))Q f b ( , )R a y ( , )R a y+

+ + + +

Cest un sous-graphe qui aboutit la clause videCop

yright

: Jean

-Philip

pe Pr

aux

Graphe de rfutation


( ( )) ( , )Q f b R a y

( ( ))Q f b

+

Cest un sous-graphe qui aboutit la clause videCop

yright

: Jean

-Philip

pe Pr

aux

Stratgie en largeur

On note lensemble de clauses initiales

On note lensemble des clauses rsolvantes dont les parents sont dans

Pour , on note lensemble des rsolvantes dont un parent est dans et lautre parent est dans un pour .

On produit successivement , , etc jusqu aboutir la clause vide.

0C

1C0C

1n nC1nC

iC i n

Documents

PLOG_ppt5