Upload
others
View
0
Download
0
Embed Size (px)
Citation preview
/120
Logiquesetraisonnement
AntoineCORNUÉJOLS
IODAA2016-2017
/120
L’IAnécessitel’u7lisa7ondegrandesquan7tésdeconnaissances
➥ Commentreprésenter:• desdéfini&ons:«UnéléphantestunmammifèregrisàquatrepaLes
etunetrompe»• descatégories:«LesinformaNciens»• desasser&ons:«LedernierroidedeFrances’appelaitLouis-Philippe»• desexcep&ons:«Ilexistedesélèvesquinevontpasencours»• desdéfauts(plausibilité):«laplupartdesinformaNcienssontdeshommes»• letemps:«Tantqu’ilyauradelaneige,jeneretournepasàGrignon»
«Surcesentrefaites,ilarriva»• lesquan&ficateurs∀et∃:«lanuittousleschatssontgris»• lespossibilités• lescer&tudes,lescroyances• …?
Undéfi
2IODAA–Logiquesetraisonnement
/120
➥ Comment:– retrouveruneconnaissance
– serendrecomptedesco-référencesetlestraiter(lesreprésenterparuneseuleenNtéouparplusieurs?): «LedernierroideFrance»&«Louis-Philippe»
– déduiredesconnaissances
– ajouterdesconnaissances(entenantcomptedelanon-monotonie,dumainNendelacohérence,…)
• Commentlecomportementd’unebasedeconnaissancesvarieaveclaquanNtéetletypedeconnaissancesdisponibles?
• Existe-t-ildeslimites?
DesquesNons
3IODAA–Logiquesetraisonnement /120
• JacquesestmariésoitàFrançoise,soitàNicole
Nicolen’estmariéeàpersonne
⇒ JacquesestmariéàFrançoise
• JeanobserveIsabelleetIsabelleobserveGeorges
JeanestmariéetGeorgesnel’estpas
⇒ Unepersonnemariéeobserveunepersonnenonmariée
• Quelstypesd’informa&onspeuventêtreextraitesdequellesformesd’asserNonsd’unemanièreefficaceetfiable?
Quellesinférences?
4IODAA–Logiquesetraisonnement
/120
• Jeanestmortel• Leshommessontmortels=>Jeanestunhomme (Correct/Pascorrect?)• Jeanestimmortel• Jeanestunhomme=>Ilexistedeshommesimmortels (Correct/Pascorrect?)• Touthommeestdouéderaison• Jeann’estpasunhomme=>Jeann’estpasdouéderaison (Correct/Pascorrect?)• Iln’estpasvraiquePierren’aimenilesgâteauxnilestartes=>Pierreaimelestartesetlesgâteaux (Correct/Pascorrect?)
Quellesinférences?
5IODAA–Logiquesetraisonnement /120
• Plusilyadegruyère,plusilyadetrous• Plusilyadetrous,moinsilyadegruyère=>Plusilyadegruyère,moinsilyadegruyère (Correct/Pascorrect?)• Sileloupestlà,ilnousmangera• Iln’estpaslà=>Ilnenousmangerapas (Correct/Pascorrect?)• Unchevalbonmarché,c’estrare• Toutcequiestrareestcjer=>Unchevalbonmarché,c’estcher (Correct/Pascorrect?)• Iln’yaquelesimbécilesquinechangentpasd’avis• Pierrechanged’avis=>Pierren’estpasunimbécile (Correct/Pascorrect?)• Iln’yaquelesimbécilesquinechangentpasd’avis• Pierren’estpasunimbécile=>Pierrechanged’avis (Correct/Pascorrect?)
Quellesinférences?
6IODAA–Logiquesetraisonnement
/120
Leçons
• Lalogiqueconcernelareprésenta&ondechosescertaines(vraiesoufausses)
• Lalogiqueaaussipourbutdefournirdescritèrespourdécidersiunraisonnementestcorrectounon
• S’appuiesurunlangage
• Maispasdelangageuniversel,ilfautdoncunlangagepar&culier
• IlfautconstruireunlangageabstraitpermeLantd’exprimersansambiguïtélesasserNonsdésirées
7IODAA–Logiquesetraisonnement /120
Unlangagerestreint
• Desproposi&onsélémentaires
– AsserNonsquiontunevaleurdevérité(VRAIouFAUX)• PierreaimeMarie• IlapluàParisle13février1807à19h43• L’addi7onbaignesonincident• Ce`ephraseestunmensonge
• Desconnecteurs
– NégaNon :¬A
– DisjoncNon:A ∨B
– ConjoncNon:A ∧B
– ImplicaNon:A =>B
• Desrègles
8IODAA–Logiquesetraisonnement
/120
Unlangagedelapensée?
ReprésentaNonsdeconnaissancesetraisonnements
/120
• HypothèsedessciencescogniNvesorthodoxes:
– Lacogni&on
• peutêtreconsidéréecommeuncalculréalisantlacréa&on,latransforma&on
etlapropaga&ondereprésenta7onsàtraversdesmoyensdereprésenta7on.
– Larésolu&ondeproblèmes
• signifieniplusnimoinstrouver,pardestransforma&ons,unereprésenta&on
quienrendelasolu7ontransparente.
Unlangagedelapensée?
10IODAA–Logiquesetraisonnement
/120
ReprésentaNonetraisonnement
Représentation
Monde
010011110010111 010011110010111010011110010111 010011110010111010011110010111 010011110010111010011110010111 010011110010111010011110010111 010011110010111010011110010111 010011110010111
010011110010111 010011110010111010011110010111 010011110010111010011110010111 010011110010111
BasedeConnaissances
ReprésentaNon(t)
010011110010111 010011110010111010011110010111 010011110010111010011110010111 010011110010111010011110010111 010011110010111010011110010111 010011110010111010011110010111 010011110010111
010011110010111 010011110010111010011110010111 010011110010111010011110010111 010011110010111
ReprésentaNon(t+1)
Monde
PrédictionRaisonnement
11IODAA–Logiquesetraisonnement /120
ReprésentaNonanalogiqueetraisonnement
• ExempledesformesdeShepardhttp://www.ulb.ac.be/psycho/fr/docs/museum/Experiments/Shepard/Shepard.html
12IODAA–Logiquesetraisonnement
/120
ReprésentaNonanalogiqueetraisonnement
13IODAA–Logiquesetraisonnement /120
[Hutchins(1995):"CogniNoninthewild".MITPress,1995]
• Etantdonnésunpointdedépartetunedes&na&on:– commenttrouvercommentyaller(quelledirecNonprendreàchaque
instant)?
– Quelledistanceminimaleentrecespoints?
➥ Lesmoyensdecalcul(etlesreprésenta&ons)sonttrèsvariéset
trèsdépendantsdelaculture
Exemple:lanavigaNon
14IODAA–Logiquesetraisonnement
/120
• Supposonsqu'ilsepasse3mnentredeuxmesuresetqu'ellesdonnentunedistanceparcouruede1500yards.
Quelleestlavitessedubateau?(enmilles)
Soient4contextes(ressourcesdereprésentaNonetdecalcul):
1- Papieretcrayon,connaissancedel'algèbre,connaissancedel'arithméNque,connaissancequ'ilya2000yardsdansunmillenauNqueet60mndansuneheure,connaissancedelarelaNondistance=vitesse×durée
2- MêmeressourcessaufcalculeFeaulieudepapieretcrayon
3- Règleàcalculnau&que(cf.transparentsuivant)+laconnaissancerequisepour
l'uNliser
4- Pasdematérielmaisconnaissancedelarègledes3mn15IODAA–Logiquesetraisonnement
Exemple:lanavigaNon
/120
• Contexte1
(connaissancesenalgèbre)
– d=1500yards=1500/2000mille(connaissancesnécessairessur «yards»et«mille»etarithméNque)
– t=3mn=3/60heure
➥ v=0.75/0.05=15milles/h
Rqs:• lesopéra7onspeuventêtreeffectuéesdansdesordresdifférents• lesopéra7onsdoiventêtreplanifiées
d = v × t ⇒ v = dt
16IODAA–Logiquesetraisonnement
Exemple:lanavigaNon
/120
• Contexte2
– OpéraNonssimilaires,aveccalculeLe,maissansl'aidedepapierpour
mémoriserlesrésultatsintermédiaires
– Ladifficultérésidedanslechoixdel'ordredesopéraNonspoursimplifier
lescalculsetlamémorisaNon.
– L'uNlisaNond'unecalculeLenefacilitepascechoix.
17IODAA–Logiquesetraisonnement
Exemple:lanavigaNon
/12018IODAA–Logiquesetraisonnement
Exemple:lanavigaNon
/120
• Contexte3– MeLreunemarquesurlarèglegraduéeentemps(mn)
– MeLreunemarquesurlarèglegraduéeendistance(yards)
– Tireruntraitentrelesdeux
➥ Lirelerésultatsurlarèglegraduéeenvitesse(nœuds)
– Rqs:• Pasdeproblèmedeconversiond'unités• LesopéraNons(divisions,…)sont"inscrites"danslareprésentaNon(logarithmique)
• Aucuneconnaissancedel'algèbrenécessaire• LesrelaNonsincorrectes(ouerreurs)sont"éliminées"automaNquement(onnepeutlesréaliser)
Exemple:lanavigaNon
19IODAA–Logiquesetraisonnement /120
• Contexte4– 3mn=1/20heure
– 100yards=1/20mille
➥ "Règledes3mn":
Ilsuffitd'enleverles2dernierschiffresdeladistancelue(1500yards)
pouravoirlavitesse:15nœuds
– Rqs:• Laréponseest"évidente"• Uncalculcomplexe(dupointdevueconceptuel)estréaliséparuneopéraNonélémentaire(maisquidemandequ'onfasselepointtoutesles3mn)
Exemple:lanavigaNon
20IODAA–Logiquesetraisonnement
/120
• Niveau"computaNonnel"– Spécifiecequefaitlesystèmeetpourquoiillefait
• E.g.Contrainteentredistanceparcourue,duréeetvitesse
• Niveaudes"représentaNons"– SpécifielechoixdereprésentaNondesentréesetdessorNesetdes
algorithmesdetransformaNonentrelesdeux
• Niveaudel'implémentaNon– Concerneledétaildel'implémentaNonphysiquedesalgorithmesetdes
représentaNons
distance vitesse
durée
LesniveauxdereprésentaNondeMarr(1982)
21IODAA–Logiquesetraisonnement /120
Lesquatrecontextesdecalculcorrespondentaumêmeniveaucomputa&onnelmaisàdeschoixdeniveauxdereprésenta&ondifférents.
➥ Unereprésenta&ondonnelemoyendetrouverlasoluNon
• QuesNonsessenNelles:
– QuellessontlespropriétésquevérifientlestransformaNons• Conserventlavaleurdevérité…?
• Calculables(entempsetespacemémoireraisonnables)?
Morale
22IODAA–Logiquesetraisonnement
/120
?
Raisonnement…?Etpreuve…?
23IODAA–Logiquesetraisonnement /120
?
Raisonnement…?Etpreuve…?
24IODAA–Logiquesetraisonnement
/120
?
Raisonnement…?Etpreuve…?
25IODAA–Logiquesetraisonnement /120
?
Raisonnement…?Etpreuve…?
26IODAA–Logiquesetraisonnement
/120
ReprésentaNonsetraisonnements
Monde
010011110010011110010011110010011110010011110010011110
BasedeConnaissances
Représenta&onspossibles(t)
010011110010111 010011110010111010011110010111 010011110010111010011110010111 010011110010111010011110010111 010011110010111010011110010111 010011110010111010011110010111 010011110010111
010011110010111 010011110010111010011110010111 010011110010111010011110010111 010011110010111
ReprésentaNon(t+1)
Monde
ReprésentationPrédictionRaisonnement
= coordinationefficace & féconde
010011110010011110010011110010011110010011110010011110
010011110010011110010011110010011110010011110010011110
010011110010011110010011110010011110010011110010011110
Mul&plesmanifesta&onspoten&elles
010011110010011110010011110010011110010011110010011110
27IODAA–Logiquesetraisonnement /120
1.Olivierabu3verresdegin
Charlesabu4verresdegin
2. OlivieretCharlesontbuensemble7verresdegin
Charlesabuunverredeplusqu’Olivier
Expression complète + immédiate (vivid)
⇒ calculs simples et rapides
Expressiondesconnaissancesetraisonnement
28IODAA–Logiquesetraisonnement
/120
SelonBrachman&Levesque(inthe80s)
• Lesstructuresd’unereprésentaNondesconnaissancesdoiventavoirundoublestatut
1. IldoitêtrepossibledelesinterprétercommedesproposiNonssurlemonde.Ilfautdoncquelareprésenta7onsupporteunethéoriedelavérité.
2. Ellesdoiventavoirunrôlecausaldansleraisonnementetdoncdanslecomportementdusystème
• Unsystèmeàbasedeconnaissanceapourresponsabilitéde:– sélec7onnerunereprésenta&ondesconnaissancesadaptéepourle
domaineétudié
– sélec7onnerdesmécanismesderaisonnementappropriésàlafoispourchercherdesréponsesetpourassimilerdenouvellesinformaNons
Expressiondesconnaissancesetraisonnement
29IODAA–Logiquesetraisonnement /120
• FavorisantlanoNondecalculdelavéritéetlagénéralitédesinférences
– Leslogiques• ordre0 :proposiNonnelle• ordre1 :desprédicats• ordresupérieur :quanNficaNonportantsurlesprédicats
– Systèmesàbasederègles
– Approchesprobabilistes
• Favorisantl’expressiondesconnaissances(ontologie)– Leslangagesdeschémasetdeframes
• Systèmeshybrides:cherchantunboncompromisentrepuissanceetefficacité
DessoluNons
30IODAA–Logiquesetraisonnement
/120
…consisteen:
1.UnsystèmeformelpermeLantdedécrirelesétatsdumonde– Lasyntaxedulangage(décrivantcommentconstruiredesexpressions)
– Laséman7quedulangage(décrivantcommentlesexpressionsréfèrentauxétatsdumonde)
2.Unethéorieousystèmedepreuve(Ensemblederèglesdedéduc7onc.a.d.calculantdesimplicaNons)
Unelogique...
31IODAA–Logiquesetraisonnement /120
1. Lalogiquedesproposi&ons
1. Langage
2. Séman&que
3. Preuves
4. Leprincipederésolu&on
2. Lelogiquedesprédicats
1. Langage
2. Unifica&on
3. ClausesdeHorn
4. Preuveparrésolu&on
3. PROLOG
4. Leraisonnementbayésien
5. Leraisonnementincertainetlalogiquefloue
32
Plan
IODAA–Logiquesetraisonnement
/120
Lalogique
IntroducNoninformelle
/120
IntroducNoninformelle
«Ilfaitbeauetjesuisenvacances»
– VraiseulementsilaproposiNon«ilfaitbeau»estvraieetlaproposiNon
«jesuisenvacances»estvraieaussi
– SilaproposiNon«ilfaitbeau»estvraie,alorslaproposiNon«ilnefaitpasbeau»estfausse
• Valeurdevérité
• ConnecteurET
• Principedecomposi&onalitépourcalculerlesvaleursdevérité
34IODAA–Logiquesetraisonnement
/120
DescripNond’unmonde
• Tabledevérité(formenonstandard)
35IODAA–Logiquesetraisonnement /120
AsserNonsetcontraintessurlemonde
• Soitunensembled’asserNons:
– AbbydoesnotlikeDana.
– AbbylikeseveryonethatBesslikes.
– BesslikesCodyorDana.
– Codylikeseveryonewholikesher.
– DanalikesCody.
– DanadoesnotlikeAbby.
36IODAA–Logiquesetraisonnement
Contraintessurlesmondespossibles
Unmondepossible
/120
AsserNonsetcontraintessurlemonde
AbbydoesnotlikeDana.
AbbylikeseveryonethatBesslikes.
BesslikesCody.
Codylikeseveryonewholikesher.
DanadoesnotlikeAbby.
DanalikesCody.
37IODAA–Logiquesetraisonnement
Contraintessurlesmondespossibles
Quesepasse-t-ilsila4èmeAsserNonestremplacéepar:BesslikesCodyandDana.?
/120
QuesNons
• C’estquoiunepreuve?
• Quepeut-ondémontrerici?
• Comment?
38IODAA–Logiquesetraisonnement
/120
Conclusionlogique
• Certainesproposi&onspeuventêtrevraiesdanstouslesmondesquisaNsfontunensembledeproposiNons(prémisses)
Conclusionslogiques
39IODAA–Logiquesetraisonnement
• BesslikesCody
• BessdoesnotlikeDana
• Everybodylikessomebody
• Everybodyislikedbysomeone
/120
Conséquenceslogiquesetpreuves
• Difficulté:examinertouteslesconclusionslogiquesparexamendetablesdevérité.
RecoursàlanoNondedémonstra&onetdepreuve(raisonnement)
40IODAA–Logiquesetraisonnement
– NoussavonsqueAbbyaimetouteslespersonnesqueBessaime
– Abbyn’aimepasDana
– Conclusion?
/120
NoNondeconséquenceslogiques
• Commentfairepourlesobtenir?
Nousyreviendronsaveclathéoriedelapreuve
41IODAA–Logiquesetraisonnement /120
---Exercice---
• OnconsidèrelesasserNonssuivantes:
– SiAliceetJulieviennentàParis,Zoéviendraaussi
– SiJulievientàParis,Aliceaussi
– JulieouZoé,l’unedesdeuxaumoins,viendraàParis
1-ExprimezcestroisasserNonsenlogiquedesproposiNons
2-Endéduire:
Aliceviendra-telleàParis?EtJulie?EtZoé?
42IODAA–Logiquesetraisonnement
/120
LalogiquedesproposiNons
/120
Lelangage:lasyntaxe
• Élémentsdulangage:lasyntaxe
– Atomes
• Constanteslogiques:TetF(vraietfaux)• SymbolesdeproposiNon
– ToutechaînedecaractèrescommençantparuneleLreminuscule
– p,q,p1,p2,on_A_B,…
– Lesconnecteurslogiques• V(OU),�(ET),=>(implique),¬(NON)• Unatome(précédéounonde¬)estappeléunli`éral
– Formulesbienformées(wffs)
44IODAA–Logiquesetraisonnement
/120
Lelangage
• Élémentsdulangage:lasyntaxe
– Formulesbienformées(wffs)• Toutatomeestunewff• Siω1etω2sontdeswff,alors:
– ω1Vω2 (disjonc7on)– ω1∧ω2 (conjonc7on)– ω1=>ω2 (implica7on)– ¬ω1 (néga7on)….sontdeswff
• Exemples:– (p∧q)=>¬p– p=>¬p– pVp=>p– (p=>q)=>(¬q=>¬p)
45IODAA–Logiquesetraisonnement /120
LacomposiNondesproposiNons
• v(¬p)=T ssi v(p)=F
• v(p∧q)=T ssi v(p)=v(q)=T
• v(pvq)=F ssi v(p)=v(q)=F
• v(p=>q)=F ssi v(p)=Tetv(q)=F
• v(p<=>q)=T ssi v(p)=v(q)
46IODAA–Logiquesetraisonnement
/120
Tabledevérité
• Lavaleurdevéritéd’unewffestcalculéerécursivementenuNlisantlatabledevéritéci-dessus
• E.g.pestFaux,qestFauxetrestVrai
– Quelleestlavaleurde((p=>q)=>r)=>p?
• Rq:Unewffpeuravoirdifférentesvaleursdevéritédansdifférentesinterpréta7ons
(différenteslignesdelatabledevérité)(onparleausside«mondespossibles»)
47IODAA–Logiquesetraisonnement
ω1 ω2 ω1∧ω2 ω1Vω2 ¬ω1 ω1=>ω2
Vrai Vrai Vrai Vrai Faux Vrai
Vrai Faux Faux Vrai Faux Faux
Faux Vrai Faux Vrai Vrai Vrai
Faux Faux Faux Faux Vrai Vrai
/120
Ré-écritures/équivalences
• Contradic&onA ∧¬A ≡F
• TautologieA ∨¬A ≡T
• Absorp&onA ∧(A∨B) ≡A
• Absorp&onA ∨(A∧B) ≡A
• Distribu&vitéde∧sur∨w1 ∧(w2∨w3) ≡(w1∧ w2)∨ (w1∧ w3)
• Distribu&vitéde∨sur∧w1 ∨(w2∧w3) ≡(w1∨ w2)∧ (w1∨ w3)
48IODAA–Logiquesetraisonnement
• Implica&on
A =>B ≡¬A∨B
• RèglesdeMorgan
¬(A ∨B) ≡¬A∧¬B
¬(A ∧B) ≡¬A∨¬B
/120
ProposiNonséquivalentes
• ProposiNonséquivalentes– DeuxproposiNons(wff)peuventavoirdesformesdifférentesetavoirla
mêmesignifica&on
– DeuxproposiNonssontéquivalentesiellesontmêmetabledevérité
– OnuNliselesymbole≡
• Tautologies– wffrestantvraiequelquessoientlesvaleursdevéritédesatomesla
composant
• Contradic&ons– wffrestantfaussequelquessoientlesvaleursdevéritédesatomesla
composant
49IODAA–Logiquesetraisonnement /120
---Exercice---
• Montrezquelaformulesuivanteestunetautologie
50IODAA–Logiquesetraisonnement
/120
---Exercice---
• Danslabandedessinée«OnamarchésurlaLune»,lesDupondtsefâchentsommentlecapitaineHadockdereNrerlaphrasesuivante,jugéeinsultantepoureux:
– «LecirqueHipparqueabesoindedeuxclowns,vousferezparfaitementl’affaire»
• LecapitaineHadockreconnaîtqu’ilsontraisonetproposeenguised’excuse:
– «LecirqueHipparquen’apasbesoindedeuxclowns,vousnepouvezdoncpasfairel’affaire»
QuellephraseauraitdudirelecapitaineHadockpourniersapremièreaffirmaNon?
51IODAA–Logiquesetraisonnement /120
---Exercice---
• SimplificaNondeformules
52IODAA–Logiquesetraisonnement
F = ¬((p _ q) ) p) ^ q
G = (a _ (b ) c)) ) (a _ b _ c)
/120
Aretenir
• Rôlesdelalogique– Représenterdesconnaissances(certaines)surlemonde
– Fournirdescritèrespourassurerlacorrec&ond’unraisonnement
– Fournirdesmoyens(automaNques)depreuve(raisonnement)
• AsserNonsetmondespossibles
• ProposiNons;formulesbienformées
• Formuleséquivalentes;tautologies;contradicNons
• Règlesderé-écriture
53IODAA–Logiquesetraisonnement /120
2èmecours
NoNondeconséquencelogique
/120
Langage:lasémanNque
• LasémanNquedéterminelesfaitsdumondeauxquelslesformulesréférent.
OncherchequellessontlesproposiNonsvraiesounécessairesdanslemonde
– SignificaNonaLachéeauxatomesetwffs
• E.g.l’atomebat_OKestassociéeàlaproposi&on«baLeriechargée»
– Interpréta&on.FoncNonπ:atomes,wffs→ {Vrai,Faux}
– SiunatomeαestassociéàlaproposiNonp,αapourvaleurVraisipestvraiedanslemonde.
– OnsupposequelesproposiNonssontforcémentvraiesoufausses
• Maisc’estunprésupposétrèsfort.E.g.«tasdesable»?• Voirlogiquefloue
55IODAA–Logiquesetraisonnement
(laproposiNonassociéeàl’atomeestVouFdanslemonde)
/120
ReprésentaNonetraisonnement
Sémantique
Monde
010011110010111 010011110010111010011110010111 010011110010111010011110010111 010011110010111010011110010111 010011110010111010011110010111 010011110010111010011110010111 010011110010111
010011110010111 010011110010111010011110010111 010011110010111010011110010111 010011110010111
BasedeConnaissances
ReprésentaNon(t)
010011110010111 010011110010111010011110010111 010011110010111010011110010111 010011110010111010011110010111 010011110010111010011110010111 010011110010111010011110010111 010011110010111
010011110010111 010011110010111010011110010111 010011110010111010011110010111 010011110010111
ReprésentaNon(t+1)
Monde
Sémantique
Raisonnement
56IODAA–Logiquesetraisonnement
/120
Tabledevérité
• Lavaleurdevéritéd’unewffestcalculéerécursivementenuNlisantlatabledevéritéci-dessus
• E.g.pestFaux,qestFauxetrestVrai
– Quelleestlavaleurde((p=>q)=>r)=>p?
• Rq:Unewffpeuravoirdifférentesvaleursdevéritédansdifférentesinterpréta7ons
(différenteslignesdelatabledevérité)(onparleausside«mondespossibles»)
57IODAA–Logiquesetraisonnement
ω1 ω2 ω1∧ω2 ω1Vω2 ¬ω1 ω1=>ω2
Vrai Vrai Vrai Vrai Faux Vrai
Vrai Faux Faux Vrai Faux Faux
Faux Vrai Faux Vrai Vrai Vrai
Faux Faux Faux Faux Vrai Vrai
/120
InterprétaNonspossiblesetsaNsfiabilité
• SiunagentpeutconsidérernproposiNonscorrespondantànatomes:
– Ilexiste2nmondespossibles(interpréta&ons)(lignesdelatabledevérité)
• ÉtantdonnéeuneinterprétaNon,l’agentpeutcalculerlavaleurdevéritéden’importequellewff.
• Inversement?
– Étantdonnéunensembledewffavecleurvaleurdevérité
– Peut-ontrouverlesvaleursdevéritédesatomescorrespondantes?
Problèmedesa&sfiabilité
58IODAA–Logiquesetraisonnement
/120
SaNsfiabilité
• UneinterprétaNonIsa&sfaitunewffAsilawffestVraisousceLeinterprétaNon(Aestsa7sfiableparI)
• Modèle:uneinterprétaNonIquisaNsfaitunewffouunensembledonnédewffsA(IestunmodèledeA)
• NotaNon:A|=B(danstouteslesinterprétaNonsdeA,Bestvraie)
• E.g.
– Soitlaformulep∧q=>r• pvraietqvraietrfaux :n’estpasunmodèle• pfauxetqfauxetrvrai :estunmodèle(ouinterprétaNonoumondepossible)
• Siiln’existeaucunmodèlepourunensembledewffs,celui-ciestditinconsistentouinsa&sfiable
• p∧¬p• {pvq,pv¬q,¬pvq,¬pv¬q}
59IODAA–Logiquesetraisonnement /120
---Exercice---
• Pourchacundestroisensemblesdeformulessuivants,indiquezs’ilestinconsistant.Danslecascontraire,donnez-enunmodèle.
60IODAA–Logiquesetraisonnement
Si on suppose qu’aucun des flacons ne contient un poison (ligne 1 de la table), les deux inscriptions IR et IBsont fausses alors que IJ est vraie.
Si les trois inscriptions sont vraies, est-ce qu’un ou plusieurs flacons contiennent un poison ?
Les trois inscriptions sont vraies si et seulement si on se trouve dans la situation de la ligne 3, c’est-à-dire queseul le flacon jaune contient du poison.
Si seuls les flacons ne contenant pas un poison ont une inscription vraie, est-ce qu’un ou plusieurs flacons ne
contiennent pas un poison ?
Par hypothèse : (¬R … IR) · (¬J … IJ) · (¬B … IB) est vrai. Or :
• (¬R … IR) est vrai aux liens 3, 5, 6 et 8• (¬J … IJ) est vrai aux lignes 1, 2, 6 et 7• (¬B … IB) est vrai aux lignes 2, 3, 4, 5, 6, 7 et 8
Donc (¬R … IR) · (¬J … IJ) · (¬B … IB) est vrai uniquement à la ligne 6. C’est-à-dire quand le flaconjaune ne contient pas de poison.
7. Pour chacun des trois ensembles de formules suivants, indiquez s’il est inconsistant. Dans le cas contraire,donnez-en un modèle.
(a) {p ‚ q, p æ q, ¬q }(b) {p æ q, q æ r, r æ ¬ p}(c) {p æ q, q æ r, r æ ¬ p, p ‚ ¬s, s }
Corrigé
(a) {p ‚ q, p æ q, ¬q } © {p ‚ q, ¬p ‚ q, ¬q } est insastifiable(b) {p æ q, q æ r, r æ ¬ p} © { ¬p ‚ q, ¬q ‚ r, ¬r ‚ ¬p } {¬p,q, r } est un modèle(c) {p æ q, q æ r, r æ ¬ p, p ‚ ¬s, s } © { ¬p ‚ q, ¬q ‚ r, ¬r ‚ ¬p, p ‚ ¬s, s}
est insastifiable car s est vrai, donc p aussi, donc q aussi, donc r aussi, mais on doit avoir ¬r ‚ ¬p, cequi est impossible.
1.4 Premières preuves syntaxiques
8. Soient les formules :F = ((p ∆ q) ‚ s) · ((s ∆ p) ‚ ¬p)G = (¬q · ¬p) ‚ (q · ¬p) ‚ (p · q) ‚ r
(a) Écrire leurs tables de vérité.(b) SANS écrire la table de vérité de F ∆ G, montrer que „ F ∆ G.
5
/120
Validité
• UnewffestvalidesielleestvraiesoustouteinterprétaNondesatomeslaconsNtuant
– Unetellewffneditriensurlemonde.C’estunetautologie.
• p=>p• T• ¬(p∧¬p)• qvT• ((p=>q)=>p)=>p• p=>(q=>p)
• QuesNon:Quelleestlacomplexitécalculatoiredelavérifica7ondelavaliditéd’unewff?
61IODAA–Logiquesetraisonnement
sontdes
tautologies
/120
Conséquencelogique
• Basedeconnaissances(knowledgebase)– EnsembledeproposiNons(wffs)supposéesvraies
– Chaqueélémentestunaxiome
• Rappel:Unmodèled’unensembledeproposiNonsestuneinterprétaNonpourlaquelletouteslesproposiNonssontvraies.
• SiBCestunebasedeconnaissancesetωestuneproposiNon,alorsω estconséquencelogiquedeBCsiωestvraiepourtouteinterprétaNondeBC.(notaNon:BC|=ω)
– i.e.Iln’existepasd’interpréta&ondeBCpourlaquelleωestfausse.
62IODAA–Logiquesetraisonnement
/120
Conséquencelogique
• Exemples
– {p}|=p
– {p,p=>q}|=q
– F|=ω(pourtoutω)
– p∧q|=p
• Lecalculnécessitel’examendetouteslesinterprétaNonspossiblesdelaBC(2nsiilyanatomes)
63IODAA–Logiquesetraisonnement /120
LasémanNquevueduconcepteur
1. Choixd’undomaine– E.g.lefoncNonnementd’AgroParisTech,d’unecommunauté
villageoiseauMali,…
– etdesproposi&onsd’intérêt(e.g.lesmembresduCEsontélus)
2. Sélec&ondesatomesquireprésenterontlesaspectsdumondejugésperNnents.
3. Écritureenmachinedesproposi&onsvraiesdansl’interprétaNond’intérêtpourleconcepteur.Lesaxiomesdudomaine.
4. Requêtesausystèmepourdéterminerdesconséquenceslogiquesdesaxiomes.
64IODAA–Logiquesetraisonnement
Danslatête
Àlamachine
/120
---Exercice---
65IODAA–Logiquesetraisonnement
= (p · ¬p · q) ‚ (q · ¬p · q)= ¬p ‚ q
G = (a ‚ (b ∆ c)) ∆ (a ‚ b ‚ c)= (a ‚ (¬b ‚ c)) ∆ (a ‚ b ‚ c)= ¬(a ‚ (¬b ‚ c)) ‚ (a ‚ b ‚ c)= ¬a · ¬(¬b ‚ c)) ‚ (a ‚ b ‚ c)= (¬a · b · ¬c) ‚ (a ‚ b ‚ c)= (¬a · b · ¬c) ‚ b ‚ a ‚ c) (règle d’absorption)= b ‚ a ‚ c
1.3 Interprétations et modèles
5. Dans le Marchand de Venise, de Shakespeare, Portia a trois co�rets, un d’or, un d’argent et un de plomb et,dans l’un d’eux, elle a caché son portrait. Quand un des soupirants se présente, elle lui fait choisir l’un desco�rets, et c’est celui qui aura la chance (ou l’astuce) de trouver le co�ret contenant son portrait qui pourral’épouser. Mais le couvercle de chaque co�ret porte deux inscriptions pour guider le choix du soupirant, carPortia ne veut pas choisir un époux pour sa vertu mais pour son intelligence.Elle traça un jour les inscriptions suivantes :
Coffret en Or Coffret en Argent Coffret en Plomb
Le portrait n’est pas dans
ce co�ret
Le portrait n’est pas dans
le co�ret en or
Le portrait n’est pas dans
ce co�ret
Le portrait est dans le
co�ret en argent
Le portrait est dans le
co�ret en plomb
Le portrait est dans le
co�ret en or
Elle expliqua à son soupirant que sur l’un des co�rets deux a�rmations étaient vraies, sur un autre elles étaientfausses toutes les deux, et sur le troisième l’une était vraie et l’autre était fausse. Quel co�ret le candidat aumariage devrait-il choisir pour épouser Portia ?
Corrigé
Il faut faire une table de vérité avec les 3 atomes Or (le portrait est dans le co�ret en or), Ar et Pb, et les 12lignes correspondant aux 12 possibilités (premier co�ret : les deux assertions sont vraies ; 2ème co�ret : lesdeux assertions sont fausses , 3ème co�ret : une assertion est vraie et l’autre fausse), etc.On trouve finalement que le portrait est dans le co�ret en Plomb.
6. Lors de ses aventures au pays des merveilles rapportées par Lewis Carroll, Alice est souvent accompagnée par lechat de Cheshire. Ce félin énigmatique s’exprime sous la forme d’a�rmations logiques qui sont toujours vraies.Alice se trouve dans un corridor dont toutes les portes à sa taille sont fermées. La seule porte ouverte estnettement trop petite pour qu’elle puisse l’emprunter. Une étagère est fixée au-dessus de cette porte. Le chatdit alors à Alice : « L’un des flacons posés sur cette étagère contient un liquide qui te permettra de prendre
3
/120
Àretenir
• Interpréta&on– AtomesouvariablesproposiNonnelles:p
– LiFéral:atomeounégaNond’unatome
– Interpréta&on:Ensemble(s)devaleursdevéritédesatomesdelaformule
• Modèle:interprétaNonrendantvraielaformule
• Sa&sfiabilitéd’uneformule:trouverlesmodèlesdelaformule
• Formulesvalides:saNsfaitesdanstouteslesinterprétaNons
• Conséquencelogique– BvraiepourtouslesmodèlesdeA
66IODAA–Logiquesetraisonnement
A |= B
/120
Preuveetraisonnement
/120
DémonstraNon
• Organisa&ond’unensembled’étapesélémentaires(inférences)
68IODAA–Logiquesetraisonnement
Raisonnement
/120
LasémanNquevuedelamachine
• Lamachinen’apasaccèsàlasémanNque
• SeulementauxproposiNonsdelaBC
Commentpeut-ellecalculerlesconséquenceslogiques?
69IODAA–Logiquesetraisonnement /120
Raisonnement…
• …parmanipula&onsyntaxiquedesformules
• Lamachinen’examinepaslesvaleursdevéritédesformules
– Commeenalgèbre
70IODAA–Logiquesetraisonnement
/120
Inférencesetraisonnement
• Déduc&on
• Touslesxsonty• Touslesysontz
• Touslesxsontz
• Induc&on
• Onaobservé1000corbeauxnoirs• Onn’ajamaisobservéuncorbeaunonnoir
• Touslescorbeauxsontnoirs
71IODAA–Logiquesetraisonnement
x–3y=0x+y=12
-4y=-12
Algèbre
/120
Calculdeconséquences:preuvesetdéducNons
• Ladéduc&onestuneformederaisonnement
– Ellecalculedesconséquenceslogiquesd’uneBC
– EnuNlisantuneprocédurededémonstraNonmécanisable:unepreuve
• UnthéorèmeestuneproposiNondémontrableàparNrdesaxiomes(grâceàdesrèglesd’inférence)
• NotaNon:BC|-ωsignifiequeωpeutêtredémontréàparNrdeBC
– Uneprocéduredepreuveestcorrecte(`sound’)parrapportàunesémanNquesitoutcequ’ellepermetdedémontreràparNrdeBCestuneconséquencelogiquedeBC
• SiBC|-ω,alorsBC|=ω
– UneprocéduredepreuveestcomplètesitoutcequiestconséquencelogiquedeBCpeutêtredémontré.
• SiBC|=ω,alorsBC|-ω
72IODAA–Logiquesetraisonnement
/120
Règlesd’inférence
• Enplusdesrèglesderé-écriture
• Onabesoinderèglesd’inférence
– Unensemblede«condi&ons»
– UneparNe«conclusion»(vraiesilescondiNonssontvérifiées)
73IODAA–Logiquesetraisonnement /120
Règlesd’inférence
=desschémaspourdesétapesélémentairesdedémonstraNon
74IODAA–Logiquesetraisonnement
• Modusponens
• ET-élimina7on
• ET-introduc7on
• OU-introduc7on
• Elimina7ondoublenéga7on
• Résolu7onunitaire
• Résolu7on
α => β, αβ
α1 ∧ α2 ∧ … ∧ αnαι
α1, α2, … ,αnα1 ∧ α2 ∧ … ∧ αn
αι α1 v α2 v … v αn
¬¬αα
α v β, ¬βα
α v β, ¬β v γα v γ
/120
Méthodesdepreuve
• Déduc&on
– UneformuleAsedéduitd’unensembledeformules{B1,B2,…,Bi,…,Bn}etl’onnote:B1,B2,…,Bn|-As’ilexisteunesuitefinie(A1,A2,…,Ai,…A)oùchaqueAiest
• Soitunaxiome
• Soitl’undesBi• Soitobtenuparl’applicaNond’unerègled’inférencesurdeuxélémentsAj,Akdelasuitedéjàobtenue(j,
k<i).Onaalorsunthéorème.
Contrôledel’explora7ondel’espacedespreuvespossibles
– E.g.Stratégie«ascendante»
• ParNrdesélémentsdelaBCpourenchercherlesconséquences,dontcelle(s)quinousintéresse(nt).
• E.g.est-cequeq∧restconséquencede{p,p=>q,r}?
– E.g.Stratégie«guidéeparlesbuts»
• ParNrdesconséquencesrecherchéesetvoirquellesrèglesd’inférencepourraientpermeLredelesdémontrer(démarcherécursive)
75IODAA–Logiquesetraisonnement /120
Méthodesdepreuve
• E.g.Stratégie«ascendante»– ParNrdesélémentsdelaBCpourenchercherlesconséquences,dont
celle(s)quinousintéresse(nt).
– E.g.est-cequeq∧restconséquencede{p,p=>q,r}?
76IODAA–Logiquesetraisonnement
! !"#$"% &
%
modus ponens
%"!"&
ET introduction! !"#$"% &
%
modus ponens
! !"#$"% &(1)
(2)
(3)
/120
Méthodesdepreuve
• E.g.Stratégie«descendante»– Enpartantdesbuts
– E.g.est-cequeq∧restconséquencede{p,p=>q,r}?• Démontrerd’abordq• Démontrerensuiter
77IODAA–Logiquesetraisonnement
! !"#$"% &
%
modus ponens
%"!"&
ET introduction
/120
Unepreuve
• Soientlesaxiomes:
1. (p∧q)=>r
2. (s∧t)=>q
3. s
4. t
5. p
• Prouverr
78IODAA–Logiquesetraisonnement
• Unepreuve:1. s (axiome3)
2. t (axiome4)
3. s∧t (conj.)
4. (s∧t)=>q (axiome2)
5. q (mod.po.)
6. p (axiome5)
7. p∧q (conj.)
8. (p∧q)=>r (axiome1)
9. r (mod.po)
/120
---Exercice---
79IODAA–Logiquesetraisonnement
Corrigé
F = ((p ∆ q) ‚ s) · ((s ∆ q) ‚ ¬p)= ((¬p ‚ q) ‚ s) · ((¬s · q) · ¬p)= (¬p ‚ q ‚ s) · (¬s ‚ q ‚ ¬p)= ¬p ‚ {(q ‚ s) · (¬s ‚ q)}¬p ‚ q
G = (¬q · ¬p) ‚ (q · ¬p) ‚ (p · q) ‚ r= r ‚ (¬q · ¬p) ‚ (q ‚ (q · p)) · ((¬p) ‚ (q · p))= r ‚ (¬q · ¬p) ‚ ((q ‚ q) · (q ‚ p)) · ((¬p ‚ q) · (¬p ‚ p))= r ‚ (¬q · ¬p) ‚ (q · (q ‚ p) · (¬p ‚ q)= r ‚ (¬q · ¬p) ‚ (q ‚ (p · ¬p)= r ‚ (¬q · ¬p) ‚ q= r ‚ (¬q ‚ q) · ¬p ‚ q= r ‚ ¬p ‚ q
Donc F „ G par la règle de ‚-introduction.
9. Soit la base de connaissances BC comprenant les clauses suivantes :
(a) b · c ∆ a(b) d ∆ b(c) e ∆ b(d) c(e) h ∆ d(f) e(g) b · g ∆ f(h) c · k ∆ g(i) a · b ∆ j
• Calculer toutes les conséquences logiques de BC par une méthode de preuve ascendante.• f n’est pas une conséquence logique de BC. Donnez un modèle de BC dans lequel f est fausse.• a est une conséquence logique de BC. Donnez-en une preuve guidée par le but.
(tiré de [Poole & Macworth, p.210])
Corrigé
• {e, e ∆ b} donne b{b, c} donne b · c{b · c, b · c ∆ a} donne a{a, b} donne a · b{a · b, a · b ∆ j donne j
Et on ne peut plus appliquer de règles d’inférence. On a « saturé » la base de connaissances. On saitque : {a, b, c, e, j}.
6
/120
Preuves
• Variétédepreuvespossibles
• Commentobteniruneprocéduredepreuve
– saine :toutcequiestdémontrableestvrai(cq.Logique)
– complète:toutcequiestvrai(cq.Logique)estdémontrable
– efficace
80IODAA–Logiquesetraisonnement
?
/120
3èmecours
Preuvespar«résolu&on»
/120
Démarche
1. Normaliserlareprésenta&on
– Lesformesnormales:clauses
2. IntroducNond’unerègled’inférenceunique– larésolu&on
3. Maisceseranoncomplet
– IntroducNonduprincipederéfuta&on
– LienavecleproblèmedesaNsfiabilité
82IODAA–Logiquesetraisonnement
/120
StandardisaNondelareprésenta&on
• Ilexisteplusieursmanièresd’exprimerlesmêmesproposiNons
– p=>q,¬pvq,¬(p�¬q)– UNlitéd’avoiruneformestandardiséeoucanonique
• LesCNF(Conjunc7veNormalForms)
– ConjoncNonsdeclauses
– clause=liLéraloudisjoncNondeliLéraux• (¬rvp)∧(qvsv¬p)
• TransformaNondewffsenCNF(toujourspossible)
83IODAA–Logiquesetraisonnement
((p=>q)=>r) ≡(pvr)∧(¬qvr) ≡{(pvr),(¬qvr)}
(r=>(pvq) ≡¬RvPvQ ≡{(¬rvpvq)}
(r=>(p∧q)) ≡ ((¬rvp)∧(¬rvq)) ≡{(¬rvp),(¬rvq)}
/120
TraducNonwff->CNF
• Jusqu’à5étapesnécessaires
1. Éliminerleséquivalencesó• AóB≡ (A=>B)∧(B=>A)
2. ÉliminerlesimplicaNons=>• A=>B≡¬AVB
3. FairemigrerlesnégaNons• ¬(AVB)≡¬A∧¬B• ¬(A∧B)≡¬AV¬B
4. ÉliminerlesdoublesnégaNons• ¬¬A≡A
5. Distribuerles∧surlesv• AV(B∧C)≡(AVB)∧(AVC)
84IODAA–Logiquesetraisonnement
(¬p∧(¬q=>r))=>s
¬(¬p∧(¬q=>r))vs (2)
¬(¬p∧(qvr))vs (2)
(¬¬pv(¬q∧¬r))vs (3)
(pv(¬q∧¬r))vs (4)
(pv¬q)∧(pv¬r))vs (5)
((pv¬q)vs)∧((pv¬r)vs) (5)
(pv¬qVs)∧ (pv¬rvs)
/120
---Exercice---
85IODAA–Logiquesetraisonnement
• Un modèle de BC dans lequel f est faux : {a, b, c, e, j} avec les atomes d, g, h et k qui peuventêtre vrais ou faux.
• a vrai si {b, c} par la règle (a).b vrai si {e} est vrai, par la règle (c)Or e est vrai (par l’axiome (f))Et c est vrai par l’axiome (d).
1.5 Mise sous forme normale
10. Soit la formule F = ((p ∆ q) · (r ‚ p)) … (r ∆ ¬q)
(a) Donner la table de vérité de : F © ((¬p ‚ q) · (r ‚ p)) … (¬r ‚ ¬q)(b) Mettez F sous forme DNF (forme normale disjonctive)(c) Mettez F sous forme CNF (forme normale conjonctive)
11. Soit la formule F = ((p · q) ‚ (¬p ‚ r)) ∆ (q ∆ r)
(a) Mettez F sous forme DNF (forme normale disjonctive)(b) Mettez F sous forme CNF (forme normale conjonctive)
12. Soit la formule F = ((¬p ‚ q) · r) … (p xor r)
(a) Mettez F sous forme DNF (forme normale disjonctive)(b) Mettez F sous forme CNF (forme normale conjonctive)
7
/120
Inférenceparrésolu&on
• Idée
– Soitlesclauses(pvq)et(¬qvr)• Siqestvraialorsrestvrai• Siqestfauxalorspestvrai
– Donconpeutconclurepvr
• Règled’inférenceparrésolu&on
– SoituneclausecontenantleliLéralgetuneautreclausecontenantleliLéral¬g,onpeuteninférerlaclausecontenanttouslesliLérauxdesdeuxclausessaufget¬g.
{f1,f2,…,g,…,fm}{h1,h2,…,¬g,…,hn}-----------------------------------{f1,f2,…,fm,h1,h2,…hn}
86IODAA–Logiquesetraisonnement
! !"#$"%
%
modus ponens
&"!"'"%
LemodusponensestuncasparNculierdelarésoluNon
[Robinson,1965]
/120
RaisonnementavecleprincipederésoluNon
• Commeaveclesautresrèglesd’inférence:
– ParNrdesprémisses
– AppliquerlarésoluNonauxprémissesetauxrésultatsobtenujusqu’à
• Obtenirlaconclusiondésirée• OunepluspouvoirappliquerderésoluNons
• LarésoluNonn’estpascomplète!– E.g.Étantdonnés{p}et{q}onnepeutconcluresur{p,q}(cad.p∧q)
– MAIS…
87IODAA–Logiquesetraisonnement /120
ComplétudeduprincipederésoluNon!!
• ThéorèmederéfutaNon
– UnensembledeproposiNonsBCentraînelogiquementuneproposiNonφssiBC∪{¬φ}estinconsistant.
• Ilsuffitdoncd’ajouterlanéga&ondelaconclusiondésiréeàl’ensemblede
clausestraduisantlabasedeconnaissancespoursavoirsilaconclusions’en
déduit(obtenNondelaclausevideparrésoluNon)
LarésoluNonestcomplèteparréfuta&on!!
88IODAA–Logiquesetraisonnement
/120
ComplétudeduprincipederésoluNon?
• Principederéfuta&on:SiunensembleΔdeclausesestinsaNsfiable,alorsonpeutgaranNrquel’onpeutobtenirlaclausevide{}(False)parrésoluNon.
– Soient:BC={(pvq),(pv¬q),(¬pvq)}etp∧qlaconclusionrecherchéedontlanégaNonest:(¬pv¬q)
• Iln’existepasd’interprétaNondecetensemble• ParrésoluNon:
1. (pvq) prémisse2. (pv¬q) prémisse3. (¬pvq) prémisse4. (¬pv¬q) négaNonconclusion5. p résoluNon1,26. ¬p résoluNon3,47. {} résoluNon5,6
89IODAA–Logiquesetraisonnement /120
PreuveparrésoluNon
1. Silavoituredémarrealorssilavoituren’apasétépousséealorslaba`eriefonc7onne
2. Silaba`eriefonc7onnealorsleslampess’allument
3. Silavoituredémarreetlavoituren’apasétépousséealorsleslampess’allument
90IODAA–Logiquesetraisonnement
OnuNliselessymboles:
1. d:lavoituredémarre
2. b:labaLerieestmorte
3. p:lavoitureaétépoussée
4. l:leslampess’allument
1. d=>(¬p=>¬b)
2. ¬b=>l
3. (d∧¬p)=>l
1. (¬dvpv¬b)
2. (bvl)
3. (¬dvpvl)
¬3.{d,¬p,l}
¬dvpv¬bdpv¬b¬pb¬dvpv¬b¬dvpdp¬p{}
/120
PreuvesparrésoluNon
• Soitàprouver:{p=>r,q=>r}|=(pvq)=>r– NégaNondelaconséquenceettransformaNonenCNF
{¬pvr,¬qvr,pvq,¬r}
91IODAA–Logiquesetraisonnement
!"#$#%
!"
!%
&
"#$#& !&#$#% !%
!"
!"#$#% "#$#&
%#$#&
!%
!%
& !&#$#%
%
/120
---Exercice---
92IODAA–Logiquesetraisonnement
15. Utiliser la méthode de résolution pour prouver ou infirmer les a�rmations suivantes :
(a) |= p ∆ p(b) |= ((p ∆ q) · (q ∆ r)) ∆ (p ∆ r)(c) |= ((s ∆ r) · p · ¬r) ∆ ¬r · ¬s · p(d) |= [(p · q) ‚ (r · q)] ∆ (p ‚ r)(e) {q ∆ (¬q ‚ r), q ∆ (p · ¬r)} |= q ∆ r(f) {q ∆ (¬q · r), q ∆ (p · ¬r)} |= q · r(g) {p ∆ q, q ∆ r, p ‚ ¬r} |= p · q · r(h) {p ∆ q, q ∆ r, p ‚ ¬r} |= (p · q · r) ‚ (¬p · ¬q · ¬r)
Corrigé
(a) |= p ∆ pSoit la formule „ = p ∆ p. La forme clausale de „ est {p, ¬p}
Par résolution : p ¬p
‹Donc „ „ et, par correction, |= „.
(b) |= ((p ∆ q) · (q ∆ r)) ∆ (p ∆ r)
Soit la formule „ = ((p ∆ q) · (q ∆ r)) ∆ (p ∆ r)On a
¬„ = ((p ∆ q) · (q ∆ r)) · ¬(¬ p ‚ r)= ((¬p ‚ q) · (¬q ‚ r)) · ¬(¬p ‚ r)= (¬p ‚ q) · (¬q ‚ r) · p · ¬r
La forme clausale de ¬„ est donc : {¬p ‚ q, ¬q ‚ r, p, ¬r}.Par résolution, on obtient :
p ¬p ‚ qq ¬q ‚ r
r ¬r‹
Donc „ „ et, par correction, |= „.
(c) |= ((s ∆ r) · p · ¬r) ∆ ¬r · ¬s · p
Soit la formule :
„ = ((s ∆ r) · p · ¬r) ∆ ¬r · ¬s · p= ¬((¬s ‚ r) · p · ¬r) ‚ ¬r · ¬s · p
On a donc :
¬„ = ((¬s ‚ r) · p · ¬r) · (r ‚ s ‚ ¬p)
D’où la forme clausale de ¬„ = {(¬s ‚ r, p, ¬r, r ‚ s ‚ ¬p}Par résolution, on obtient :
10
/120
StratégiedecontrôledelarésoluNon
• CommentchoisirquellerésoluNonappliqueràchaquepas?
– Contrôledel’ordre• Enlargeurd’abord• Enprofondeurd’abord
– ContrôledutypederésoluNon• Stratégiedel’ensembledesupport• Entréeslinéaires• Filtragedesancêtres
– ClausesdeHorn• Unedisjonc7onavecunseulli`éralposi7fauplus(règleavecunseulconséquent)
• Algorithmesdedéduc7onentempslinéaire
93IODAA–Logiquesetraisonnement /120
4èmecours
Systèmesàbasederègles
/120
Sicondi7onsalorsconséquence
Exemples:
Silatempératureduréacteurdépasse800°Calorsdescendrelesbarresdecontrôle
Sichampignonsàlamesséparablesetsporéerosealorschampignondugenreleucopaxillus
SiXestunchienalors Xestunmammifère
RèglesdeproducNon
95IODAA–Logiquesetraisonnement /120
Historique:DENDRAL
• Le système DENDRAL – Pour la NASA : 1965 - …
– Y a-t-il de la vie sur Mars ?
– Spectrographie de masse
Formuledéveloppéeducomposéchimique?
masse
intensité
/120
Historique:DENDRAL
• D’abordenFortran
• ÉvoluNonrapidedesconnaissancesimpossibleàsuivre
➠ SéparaNon:
– desméthodesd’inférence:assezstables
– delaconnaissance:enévoluNon
/120
Historique:DENDRAL
• Exemples de connaissances – Règle :
Si le spectre de la molécule présente deux pics x1 et x2 tels que : 1. x1 - x2 = M + 28 2. x1 - 28 est un pic élevé 3. x2 - 28 est un pic élevé 4. au moins l’un des pics x1 et x2 est élevé Alors la molécule contient un groupe cétone
C C
R1
R2
O C
R1 (x1)
R2
O C
R1
R2 (x2)
Sedécomposeen:
ouen:
/120
Historique:MYCIN
• Système de diagnostic de maladie bactérienne du sang
• Shortliffe à Stanford (1972-1985)
• Premier vrai système expert
/120
p
p→q
q?
Chaînage avant :
utilisé quand on cherche les conséquences de l'ajout de nouveaux faits
q ?
p → q
q
Chaînage arrière :
utilisé quand on cherche à prouverun but
Chaînageavantetchaînagearrière
100IODAA–Logiquesetraisonnement
/120
R1 :Si A alors ER2 :Si B alors D
R3 :Si H alors A
R4 :Si E et G alors C
R5 :Si E et K alors B
R6 :Si D et E et K alors C
R7 :Si G et K et F alors A
Chaînageavant: H,K --R3--> H,K,A
--R1--> H,K,A,E --R5--> H,K,A,E,B
--R2--> H,K,A,E,B,D --R6--> H,K,A,E,B,D,C
(succès)
Chaînageavant
OncherchesiCestvrai
101IODAA–Logiquesetraisonnement /120
C
GE D E K
A
R7
R1
R4 R6
B
R2
H
R3
X(échec)
E K
R5
R1 :Si A alors E
R2 :Si B alors D
R3 :Si H alors A
R4 :Si E et G alors C
R5 :Si E et K alors B
R6 :Si D et E et K alors C
R7 :Si G et K et F alors A
Chaînage arrière :
Chaînagearrière
102IODAA–Logiquesetraisonnement
/120
Structuredessystèmesexperts
Mémoiredetravail
Moteurd’inférence
Basedeconnaissances
U&lisateur
Moduled’interface
Moduled’explicaNon
Moduled’acquisiNon
desconnaissances
Expert
/120
Leraisonnement:lecycledebase
DETECTIONDétermine les règles et les faitspertinents au moyen d'unifications
"pattern matching"
CHOIXDécide parmi les règles applicablescelle qu'il convient de déclencher
effectivement
EXECUTION
Exécute la partie action de la règleen tenant compte des substitutions
trouvées à l'étape 1. Met à jour la Base de Données ou
Mémoire de Travail.
Ensemble de conflit
Règle sélectionnée
/120
Contrôleduraisonnement:LaphasedesélecNon
• SélecNonneunerègleparmil’ensembledeconflit
• Méthodes:– Lapremièrerègleapplicable(e.g.Prolog)
– Larèglelaplusspécifique
– LarèglerèglelaplusuNle(selonunevaleurd’uNlitéàcalculer)
– …
MaisviolentleprincipedetransparencedesSE
➠ Lesmétarègles – DesrèglescontrôlantlasélecNondesrèglesàappliquer
/120
Contrôleduraisonnement:Exemplesdemetarègles
• Metarègle 1 : Si (1) le patient est un hôte à risque et (2) il existe des règles qui mentionnent des pseudomonias dans une
prémisse et (3) il existe des règles qui mentionnent des klesiellas dans une prémisse alors il est probable (0,4) qu’il faille utiliser les premières avant les secondes
• Metarègle 2 : Si l’on cherche une thérapie alors, dans cet ordre, considérer les règles qui permettent de : 1. acquérir des informations cliniques sur le patient 2. trouver quels organismes, s’il en existe sont cause de l’infection 3. identifier les organismes les plus vraisemblables 4. trouver tous les médicaments potentiellement utiles 5. choisir les plus adatés en plus petit nombre
/120
MYCIN-exemplededialogue
Mes recommandations thérapeutiques seront basées sur les infections probables et les organismes infectieux potentiels suivant :
L’organisme peut être : 1° pseudomonia aeruginosa, 2° klebsiellia pneumoniae, 3° escherichia coli, 4° bacteroides fragilis, 5° enterobactoriaceae, 6° proteus non mirabilis
Voulez-vous me donner la gravité de la maladie de M. Fred Smith sur une échelle de 0 à 4 ?
3
M. Fred Smith présente-t-il des réactions allergiques à un quelconque agent microbien ?
Non
Quel est son poids en kilos ?
70
MYCIN:
MYCIN:
MYCIN:
Médecin:
Médecin:
Médecin:
/120
MYCIN-exemplededialogue
Ma recommandation thérapeutique sera en premier choix : pour couvrir les points <1 2 3 5 6>, prescrire de la Gentamicine, dose 119 mg 98 h IV, pendant 10 jours;
Pour couvrir le point 4, prescrire de la Clindamycine, dose 595 mg 96 h IV, pendant 14 jours.
Désirez-vous éventuellement éliminer certains médicaments ?
Oui, la Clindamycine.
Pour couvrir les points <2 3 4 5 6> donner du Chloramphénicol, dose 1 g 96 h IV, pendant 14 jours;
** Surveiller le taux de globules blancs du patient.
Pour couvrir le point 1, donner de la gentamicine, dose 119 mg 98 h IV, pendant 10 jours.
** Modifier la dose en cas de faiblesse rhénale.
MYCIN:
MYCIN:
Médecin:
/120
MYCIN-exempled’explicaNon
L’infection du malade a t-elle été contractée à l’hôpital ?
Pourquoi ?
[Pourquoi est-ce important de savoir cela ?]
Cela aidera à déterminer la catégorie à laquelle appartient l’organisme responsable de l’infection :
- il a déjà été établi que 1° l’organisme est à Gram négatif, 2° c’est un bâtonnet, 3° il se développe à l’air ou sans air.
- Donc si l’infection par cet organisme n’a pas été contractée lors du séjour à l’hôpital
Alors il est presque certain (0,8) que l’organisme est de la catégorie des enterobactoriaceae; de plus, il se peut (0,1 ; règle 37) que ce soit de la pseudomonia aeruginosa.
Pourquoi n’avez-vous pas envisagé la possibilité que l’organisme soit un streptocoque ?
La règle 33 aurait du être utilisée pour identifier l’organisme comme un streptocoque, mais la seconde clause « la morphologie est de type coque » était déjà connue comme fausse et la règle 33 n’a jamais été essayée.
MYCIN:
TEIRESIAS:
Médecin:
TEIRESIAS:
Médecin:
/120
QuesNons
• Sur le contenu de la base de connaissances
– Prescrivez-vousparfoisdelacarbenicillinepourlesinfecNonsparpseudomonas?
• Règlesconcernées:règle024,règle068,règle138
• Lesquellesdésirez-vousexaminer?
/120
QuesNons
• De type « comment ? »
– Commentsaviez-vousquelepaNentn’avaitpaseudestéroïdes?
• Larègle395aétéuNliséepourconclurequeJohnSmithn’avaitpaseudecorNcostéroïdes:
– SiJohnSmithn’estpasaffaiblisurleplanimmunitaireAlorsilsûrqueJohnSmithn’apasreçudecorNcostéroïdes
– Commentsaviez-vousquelepaNentn’étaitpasaffaiblisurleplanimmunitaire?
• Larègle350aétéuNlisée…
/120
QuesNons
• De type « pourquoi ? »
• JohnSmithest-ilunhôteàrisque?
– Pourquoi?(pourquoiest-ilimportantdedéterminersiJohnSmithestunhôteàrisque?)
• CelaaideraàdéterminersiJohnSmithestaffaiblisurleplanimmunitaire
– SiJohnSmithn’estpasunhôteàrisqueAlorsilestsûr(1.0)queJohnSmithn’estpasaffaiblisurleplanimmunitaire[règle343]
– Pourquoi?
• PourdéterminersiJohnSmithareçudescortocostéroïdes
– SiJohnSmithn’estpasaffaiblisurleplanimmunitaireAlorsilestsûr(1.0queJohnSmithn’apasreçudecorNcostéroïdes[Règle395]
/120
QuesNons
• De type « pourquoi ? » (suite)
– Pourquoi?
• Pourdéterminerlesorganismescausesdel’infecNon
– Iladéjàétéétablique
» L’infecNonquirequiertunethérapieestuneméningite
» L’idenNtédel’organismen’estpasconnueaveccerNtude
» Laméningiteestdetypebactérien
– Sideplus
» JohnSmithareçudescorNcostéroïdes
– Alors
» ilestpossiblequel’organismecausedel’infecNonsoit:E.Coli(0.4)ouklebsiella-pneumoniae(0.2)[Règle543]
/120
Raisonnementnonexact
• Incertain– Neigera-t-ilàNoël?
– Lefourgonpostalpasserasansdouteparce`eroute
• Vague– Unfourgonpostalavecpasmaldelingotspasseraauxenvironsde10h15
• HypothéNque– Sixestétudiant,alors,jusqu’àpreuveducontraire,onpeutsupposerque
xestjeune
/120
Leraisonnementincertain:sourcesduproblème
• Théoriedudomaine
– Conceptsimprécis
– EmploiderèglesheurisNques
• Lesdonnées– Senseursinsuffisammentprécis
– Donnéesmanquantes(parprincipe,outropdifficilesàobtenir)
/120
Leraisonnementincertain:approches (1/2)
• LeraisonnementdesSE:– Guidéparlasyntaxe
– Propaga&onlocaledesvaleursdevérité
– PriseencompteincrémentaledesinformaNons
➥ Onvoudraitlesmêmesfacilitéspourleraisonnementincertain
MAIS...c’estimpossible!
/120
R.Incertain:Approchesextensionnelles
• GénéralisaNondesvaleursdevérité➥ Dépendantseulementdesvaleursdevéritédessous-formules
Exemple:CF(A&B)=Min[CF(A),CF(B)]
A->B SiAestobservéalorsonpeutmodifierlacroyancedeBd’unmontantdépendantdelaforcemdelarègle
m
/120
Leraisonnementincertain:approches
• Approchesextensionnelles– IncerNtude≈valeurdevéritégénéralisée
– Calcullocaletincrémental
➥ àlaMYCIN/certaineslogiques
• Approchesintensionnelles– Baséessurlesmodèles
– L’incerNtudedépenddelaBasedeConnaissancesenNère
➥ CalculBayésien/Réseauxprobabilistes
/120
Approchesextensionnelles:MYCIN
• LescoefficientsdecerNtude(certaintyfactor:CF)
– Desfaitsouhypothèses
0-.2 +.2-1 +1
Plutôtfaux Plutôtvrai
– DesrèglesExprimantlacerNtudeenlaconclusion,lesprémissesétantsupposéesvraies
Maisquellevraiesignifica&on?
CF(h, e) =
p(h|e) − p(h)1− p(h)
si p(h|e) ≥ p(h)
p(h|e) − p(h)p(h)
si p(h|e) ≤ p(h)
⎧
⎨ ⎪
⎩ ⎪
/120
Approchesextensionnelles:MYCIN
• PropagaNondescoefficientsdecerNtude
Ri:a1&a2&...&an=>conséquents(CF(R))
❶ CF(a1&a2&...&an)=min(CF(a1),CF(a2),...,CF(an))
❷ CF(conséquents)=CF(a1&a2&...&an).CF(Ri)
CF(H) = x + y− x.y si x& y > 0 x +y+ x.y si x& y < 0
x+ y1−min(|x|, | y|)
sinon
⎧
⎨ ⎪
⎩ ⎪ CF(H)=?
x y
/120
Approchesextensionnelles:MYCIN
• Lecontrôle
– Nepasappliquerunerègleplusd’unefois
– RechercheexhausNve,
– ...sauf...
• Sifaitcertainementvraioucertainementfaux
• SiCF(fait)<.2
/120
Approchesextensionnelles:MYCIN
• Lesdéfauts– Traitementdesinférencesbidirec&onnelles
• (InférencesdéducNvesetabducNves:“iln’yapasdefuméesansfeu”)
– “Explainingaway”• “SiAalorsC”&“SiBalorsC”
– Limitesdelamodularité• “Silesolesthumidealors(.9)ilaplu”• MT: “Lesystèmed’arrosageafoncNonnétoutelanuit”(excepNonou
suppresseur)• Demême: “Silesolesthumidealorsilaplu”
“Silesystèmed’arrosageafoncNonnéalorslesolest humide”
– ProblèmedesrèglesdifférentesuNlisantdessourcesiden&ques
– LesexpertsconfondentCFetprobabilitéscondiNonnelles
/120
Expressivitédesrègles
• Ordre 0 : logique des propositions – Si Ferrari et Michael alors rapide
• Ordres 0+ : logique des propositions typée (attribut-valeur) – Si voiture = ferrari et pilote=michael alors vitesse=rapide
• Ordre 1 : logique des prédicats – ∀ X,Y : Si voiture(X) et X=ferrari et pilote(X,Y) et Y=michael
alors rapide(X)
• Ordre 2 : logique d’ordre 2 – ∀ R, X,Y : Si type(R)=symétrique et R(X,Y)
alors R(Y,X)
/120
5èmecours
Lalogiquedesprédicats
/120
LimitesdelalogiqueproposiNonnelle
• NoNondesimilitudeentreproposi&onsinexistante• Pierreestunhomme• Jacquesestunhomme
– ConsidéréescommedesproposiNonsindépendantessanslien,alorsqueliéepar:«quelqu’unestunhomme»,uneproposiNongénérale.E.g.
• Manquedequan&fica&onuniverselle– DisNncNonentrel’universeletleparNculier
– Commentexprimerquetouslesobjetsontunpoids?• Énumérertouslesobjets:pesant(A1) ∧pesant(A2)∧ …∧ pesant(B23)?
– Oubien: • Socrateestunhomme• Tousleshommessontmortels• …etalors?
125IODAA–Logiquesetraisonnement /120
MoNvaNon
• LimitesdelalogiqueproposiNonnelle
– E.g.ON-B-C&bouger BLOC-B:commentfairelelienentrelesdeuxB(mêmebloc)?
➥ Iln'estpaspossibled'exprimerdesrela&onsentresymboles
(carlesatomessontdeschaînesdecaractèressansstructureinterne.Commesi,pourleraisonnement,onavaitR-23&Q-204)
126IODAA–Logiquesetraisonnement
/120
Connaissancesincomplètes
Žtudiant(jean)
parent(lucie,pierre)∨parent(lucie,charles)
∃Xcousin(corinne,X)∧masculin(X)
∀Xami(georges,X)⇒ ∃Yenfant(X,Y)
• Lapuissancedelalogiquedupremierordrevient
decequ’onpeutlaisserimplicite!!!
MoNvaNon
127IODAA–Logiquesetraisonnement /120
---Exercice---
• Soient– h(X)leprédicatunaire«Xestunhomme»
– c(X)leprédicatunaire«Xestunchien»
– p(X,Y)leprédicatbinaire«XapeurdeY»
– Soitauneconstantepour«Jacques»
1. ExprimerlaproposiNon«jacquesapeurdeschiens»
2. ExprimerlaproposiNon«tousleshommesontpeurdeschiens»
128IODAA–Logiquesetraisonnement
/120
1-Marcusétaitunhomme
2-MarcusétaitunPompéien
3-Touslespompéiensétaientromains
4-Césarétaitunhommed'état
5-TouslesromainsétaientsoitloyauxàCésaroulehaïssaient
6-Toutlemondeestloyalàquelqu'un
7-Lesgensn'assassinentqueleshommesd'étatqu'ilshaïssent
8-Marcustentad'assassinerCésar
Exemple
129IODAA–Logiquesetraisonnement /120
1-homme(marcus)
2-pompéien(marcus)
3-∀Xpompéien(X)→romain(X)
4-homme-d-état(césar)
5-∀Xromain(X)→loyal(X,césar)∨hait(X,césar)
ou:∀Xromain(X)→(loyal(X,césar)∨hait(X,césar))∧¬(loyal(X,césar)∧hait(X,césar))
6-∀X∃Yloyal(X,Y)
7-∀X∀Ypersonne(X)∧homme-d-état(Y)∧tente-assassiner(X,Y)→¬loyal(X,Y)
8-tente-assassiner(marcus,césar)
¬loyal(marcus,césar)?
ReprésentaNonenlogiquedesprédicats
130IODAA–Logiquesetraisonnement
/120
Jeanestunhomme Médorestunchien JeandonneunsucreàMédor
humain(jean)chien(médor)
donner(jean, médor, sucre)
ou sorte-de(humain, jean)
sorte-de(chien, médor)
donner(jean, médor, sucre)ou égal(nature(jean), humain)
égal(nature(médor), chien)
transfert(propriété_de, jean, médor, sucre)
ProblèmeduchoixdelabonnereprésentaNon
131IODAA–Logiquesetraisonnement /120
Syntaxe
1. Termes– Constantes:chaînesdecaractèrescommençantparuneminusculeouunnombre
• E.g.aA,125,13B,jean,tour_Eiffel
– Symbolesdefonc&ons (f(t1,…tn)oùlestisontdestermes)• E.g.pereDe(X),distance_entre(X,Y),…
– Prédicats(ouatomes) (p(t1,…tn)oùlestisontdestermes)• E.g.sur(X,Y),sur(Z,table),…
2. Ensembledevariables– Chaînesdecaractèrescommençantparunemajuscule
• E.g.X1,B23,Taille,…
3. Connecteurs– ∧,∨,¬,=>,ó
4. Quan&ficateurs– ∃ (existenNel), ∀ (universel)
132IODAA–Logiquesetraisonnement
/120
Syntaxe
• Terme
– Toutevariableestunterme (quel’ondénoteraparunemajuscule)
– Touteconstanteestunterme (quel’ondénoteraparuneminuscule)
– Sit1,…,tnsontdestermesetfestunsymboledefonc&on,alorsf(t1,…,tn)estunterme
• E.g.plus_grand(5,2),f(a,b,c,d),…
• Untermeestcloss’ilneconNentpasdevariable(«groundterm»)
• Formules
– Unatome:affirmeunfait (e.g.frère(richard,jean))
– SiFestuneformule,alors¬Festuneformule
– SiFetGsontdesformules,alorsF∧G,FvG,F=>Gsontdesformules
– Laformulevide,{}(ouuncarré),définieparx∧ ¬x
133IODAA–Logiquesetraisonnement /120
• Variableliée:variablesetrouvantdanslaportéed’unquan&ficateur
– ∀ Xb(X): Xestliée
– (∀Xb(X,Y))=>a(X):laportéde∀estb(X,Y)etXestliéedansb(X,Y),maislibredansa(X)
• Variablelibre:unevariablequiestnonliée
– ∀X(b(X,Y)=>∃Y,c(Y)):Xestliée,la1èreoccurrencedeYestlibre,maisla2èmeestliée
• LanoNondeportéeetdevariablelibreestimportantequandonveut
remplacerdesvariablespard’autresvariablesoupardestermes.
– Seuleslesvariableslibrespeuventêtreremplacées
Variableslibres,variablesliées
134IODAA–Logiquesetraisonnement
/120
---Exercice---
• Soient– h(X)leprédicatunaire«Xestunhomme»
– c(X)leprédicatunaire«Xestunchien»
– p(X,Y)leprédicatbinaire«XapeurdeY»
– Soitauneconstantepour«Jacques»
1. ExprimerlaproposiNon«jacquesapeurdeschiens»
2. ExprimerlaproposiNon«tousleshommesontpeurdeschiens»
135IODAA–Logiquesetraisonnement /120
---Exercice---
• Danslescassuivants,déterminezquellesoccurrencesdesvariablessontliéesetquellesoccurrencessontlibres.Ditesaussisilaformuleestclose(sansvariablelibre).
1. ∃X(p(X,Y)∧q(X))
2. (∃Xp(X,Y)∧q(X))
3. (∀X∀Yp(X,Y)=>r(X,Y))
4. ∀X(∀Yp(X,Y)=>r(X,Y))
5. ∀X∀Y(p(X,Y)=>r(X,Y))
6. (∃Ys(X)∧∀X(q(Y)=>∃Yr(X,Y))
7. ∃Y(s(X)∧(∀Xq(Y)=>∃Yr(X,Y))
136IODAA–Logiquesetraisonnement
/120
PropriétésdesquanNficateurs
• ∀X�∀Y estéquivalentà ∀Y∀X
• ∃X�∃Y estéquivalentà ∃Y∃X
• ∃X�∀Y n’estpaséquivalentà ∀Y∃X:
– ∃X�∀Yaime(X,Y):«Ilexisteunepersonnequiaimetoutlemonde»
– ∀Y∃Xaime(X,Y):«Toutlemondeestaiméparquelqu’un»(pourtoutepersonne,ilexistequelqu’unquil’aime).
• SoientG,FetHdesformules.SoitQ�{�,�}
QXF[X] ∨ G≡QX(F[X] ∨ G) et QXF[X] ∧ G≡QX(F[X] ∧ G).
¬(�XF[X])≡�X(¬F[X]) et ¬(�XF[X])≡�X(¬F[X]).
�XF[X] ∧ �XH[X]≡�X(F[X] ∧ H[X])et �XF[X] ∨ �XH[X]≡�X(F[X] ∨ H[X]).
137IODAA–Logiquesetraisonnement /120
FormeNormalePrenexd’uneformule
• UneformuleFestenformenormaleprenexssiFestdanslaforme
Q1X1Q2X2...QnXn(M)
oùchaqueQiXiestsoit�Xisoit�XietMestuneformuleenformenormale
prenexnecontenantpasdequanNficateurs.
• Exemple:�X�Y(�Z(p(X,Z) ∧ p(Y,Z))→�U(q(X,Y,U)))
≡�X�Y(¬(�Z(p(X,Z) ∧ p(Y,Z))) ∨�U(q(X,Y,U)))
≡�X�Y(�Z(¬(p(X,Z) ∧ p(Y,Z))) ∨�U(q(X,Y,U)))
≡�X�Y(�Z(¬p(X,Z) ∨ ¬p(Y,Z)) ∨�U(q(X,Y,U)))
≡�X�Y�Z�U((¬p(X,Z) ∨ ¬p(Y,Z) ∨ q(X,Y,U)))
138IODAA–Logiquesetraisonnement
/120
Misesousformeprenex
• Onappliqueautantdefoisquenécessaireleséquivalences:
1. ¬(�Xw) ≡�X¬w
2. ¬(�Xw) ≡�X¬w
3. (�Xw1)∧ w2 ≡(�Xw1∧ w2) (siXn’apparaîtpasdansw2)
4. (�Xw1)v w2 ≡(�Xw1v w2) (siXn’apparaîtpasdansw2)
139IODAA–Logiquesetraisonnement /120
ÉliminaNondes�:skolemisaNon
• SoitF=Q1X1Q2X2...QnXn(M)uneformuleenFNP.
• ConstrucNondelaformestandarddeF:SupposonsqueQr=�,avec1≤r≤n.
– SiavantQriln’yapasde�alorsonremplacetouteslesoccurrencesdelavariablexrdansMparunenouvelleconstantecrn’apparaissantpasavantdansMetonélimineQrxr.
– SiavantQrilyades�,disonsQj1,Qj2,...,Qjt,avec1≤j1<j2<...<jt<ralorsonremplacetouteslesoccurrencesdexrdansMparunenouvellefonc&ont-airefr(xj1,xj2,...,xjt)dansMetonélimineQrxr.
– Exemple:
• Soit F=�X�Y�Z�U�V�W(p(X,Y,Z,U,V,W)).
Fskolemisée: F=�Y�Z�V(p(a,Y,Z,f(Y,Z),V,g(Y,Z,V))).
140IODAA–Logiquesetraisonnement
/120
• ReprésentaNon"plate"etsansquanNficateurs
∀X{[romain(X)∧ connaît(X,marcus)]→ �
[hait(X,césar) ∨ (∀Y(∃Zhait(Y,Z))→pense-fou(X,Y))]}
TouslesromainsquiconnaissentMarcus,soithaïssentCésaroubienpensentquequiconquehaitquelqu'unestfou.
¬romain(X)∨¬connaît(X,marcus)∨hait(X,césar)∨¬hait(Y,Z)∨pense-fou(X,Y)
TraducNonwffs->formeclausale
141IODAA–Logiquesetraisonnement /120
SubsNtuNon
• UnesubsNtuNonestunensemble{X1/t1,...,Xn/tn}oùchaqueXiestunevariable,chaquetiestunterme≠deXi,etpourtouti≠j,Xi≠Xj.
– Exemples:{X/f(z),Z/Y},{X/a,Y/g(Y),Z/f(g(b))}.
• Soientθ={X1/t1,...,Xn/tn}unesubsNtuNonetEuneexpression.AlorsEθestuneexpressionobtenueàparNrdeEenremplaçantdemanièresimultanéechaqueoccurrencedelavariableXidansEparletermeti,1≤i≤n.EθestappeléeuneinstancedeE.
– Exemple:Soientθ={X/a,Y/f(b),Z/c}unesubsNtuNonetE=p(X,Y,Z)uneexpression.Alors,Eθ=p(a,f(b),c).
142IODAA–Logiquesetraisonnement
/120
ComposiNondesubsNtuNons
• Soientθ={X1/t1,...,Xn/tn}etλ={Y1/u1,...,Ym/um}2subsNtuNons.
Lacomposi&onθ◦λestunesubsNtuNondéfinieparl’ensemble
{X1/t1λ,...,Xn/tnλ,Y1/u1,...,Ym/um},oùoneffacetousleséléments
Xj/tjλtelsquetjλ=XjetoneffacetouslesélémentsYi/uitelsqueYi
�{X1,...,Xn}.
– Exemple:
Soientθ={X/f(Y),Y/Z}etλ={X/a,Y/b,Z/Y}.
Alors,θ◦λ={X/f(b),Y/Y,X/a,Y/b,Z/Y}={X/f(b),Z/Y}.
143IODAA–Logiquesetraisonnement /120
UnificaNon
• UnesubsNtuNonθestappeléeununificateurpourunensemble{E1,E2,...,Ek}ssiE1θ=E2θ=...=Ekθ.
• L’ensemble{E1,E2,...,Ek}estditunifiables’ilexisteununificateurpourlui.
• Ununificateurσpourunensembled’expressions{E1,...,Ek}estl’unificateurplusgénéralssipourchaqueunificateurθpourl’ensemble,ilyaunesubsNtuNonλtellequeθ=σ◦λ.
– Exemple:
L’ensemble{p(a,X,f(g(Y))),p(Z,f(Z),f(W))}estunifiableetapouru.p.g.la
subsNtuNonθ={Z/a,X/f(a),W/g(Y)}.
144IODAA–Logiquesetraisonnement
/120
Algorithmed’unificaNon
145IODAA–Logiquesetraisonnement /120
t
X g
Y 3
t
f g
5 Z 3 2
σ = {X/ f (3 2), Y/5, Z/3}
t
f g
5 3 3 2 t(f(3,2),g(5,3))
t(X,g(Y,3)) t(f(3,2),g(5,Z))
L'unificaNondetermes
146IODAA–Logiquesetraisonnement
/120
• SubsNtuNon/InstanNaNon:homme(X)s'instancieenhomme(socrate)parlasubsNtuNonσ ={X/socrate}
• UnificaNon:homme(socrate)ethomme(X)s'unifientenhomme(socrate)
• RésoluNon(Robinson,1965){homme(socrate)}∪ {¬homme(X),mortel(X)}|=mortel(socrate)
Le problème de la déduction: {C1,...,Cn} ı= C ?
{¬ homme(X), mortel(X)} ∪ {homme(socrate)} ı= mortel(socrate) ?
σ = { X/socrate}
LarésoluNon
147IODAA–Logiquesetraisonnement /120
PreuveparrésoluNon
• LarésoluNonestplusdifficilequ’enlogiqueproposiNonnelle
– Traitementdesvariables
– TraitementdesquanNfieurs
148IODAA–Logiquesetraisonnement
Étapes
1. Éliminerlesimplica&onsetéquivalences
2. Réduirelaportéedesnéga&ons(commeenordre0)
3. Renommerlesvariables:chaquequanNficateurneportequesurunevariable
4. ÉliminerlesquanNfieursexisten&els(skolemisaNon)
5. ÉliminerlesquanNfieursuniversels
6. Conver&renconjuncNvenormalforms(CNF)
7. TransformerlesconjoncNonsenensembledeclausesetrenommerlesvariablespourquedeuxclausesnepartagentpaslesmêmesvariables
/120
RésoluNonenlogiquedesprédicats
• SoientdeuxclausesAetBsansvariablescommunes(sinon,onrenommelesvariablescommunesdansl’unedesclauses)tellesqueA=C1∨ L1etB=C2∨ ¬L2.
• S’ilexisteununificateurplusgénéralθpourL1etL2(c-a-d,L1θ=L2θ)alors,larésolu&onentreAetBpeuts’exprimerpar:
C1∨ L1,C2∨ ¬L2donne(C1∨ C2)θ
– Exemple:
SoientA=p(X) ∨ q(X)etB=¬p(a)∨ r(X).Enrenommantd’abordXparY
dansB,lerésolvantdeAetBestq(a)∨ r(Y)souslasubsNtuNonθ={X/a}.
149IODAA–Logiquesetraisonnement /120
AlgorithmederésoluNon
150IODAA–Logiquesetraisonnement
/120
Stratégiedecontrôleduraisonnement
• Commentsélec&onnerlesclausesàrésoudreàchaqueétape?
– IlfautdeuxclausesquipossèdentdesliLérauxdesignesopposés
– Siilyaplusd’unchoix?
• Préférerlesclausesprovenantdelaconclusioncherchée
(stratégieorientéeparlebut(«goal-oriented»))
• Préférerlesclausescourtes(plusprochesdelaclausevide)
151IODAA–Logiquesetraisonnement /120
RésoluNon:exemple
• SoitlaformuleF1∧ F2∧ F3→Coù:– F1=�X((e(X)∧ ¬v(X))→�Y(s(X,Y)∧ c(Y))),
– F2=�X(p(X)∧ e(X)��Y(s(X,Y)→p(Y))),
– F3=�X(p(X)→¬v(X)),
– C=�X(p(X)∧ c(X)).
• Laformestandard(c-à-d,laFNP+SkolemizaNon)est:– S1=(¬e(X) ∨ v(X)∨ s(X,f(X)))∧ (¬e(X)∨ v(X)∨ c(f(X))),
– S2=p(a)∧ e(a)∧ (¬s(a,Y)∨ p(Y)),
– S3=(¬p(X)∨ ¬v(X))
– ¬C=(¬p(X)∨ ¬c(X)).
152IODAA–Logiquesetraisonnement
/120
RésoluNon:exemple
1. ¬e(X)vv(X)vs(X,f(X))
2. ¬e(X)vv(X)vc(f(X))
3. p(a)
4. e(a)
5. ¬s(a,Y)vp(Y)
6. ¬p(X)v¬v(X)
7. ¬p(X)v¬c(X)
153IODAA–Logiquesetraisonnement
8.¬v(a) (3et6par{X/a})
9.v(a)vc(f(a)) (2et4par{X/a})
10.c(f(a)) (8et9)
11.v(a)vs(a,f(a))(1et4par{X/a})
12.s(a,f(a)) (8et11)
13.p(f(a)) (12et5par{Y/f(a)})
14.¬c(f(a)) (13et7par{X/f(a)})
15.{} (10et14).
/120
1.homme(marcus)
2.pompéien(marcus)
3.né(marcus,40)
4.¬ homme(X1)∨mortel(X1)
5.¬pompéien(X2)∨mort(X2,79)
6.érupNon(vésuve,79)
7.¬mortel(X3)∨¬né(X3,t1)∨¬gt(T2-T1,150)∨mort(X3,t2)
8.présent=2013
9a.¬vivant(X4,T3)∨¬mort(X4,T3)
9b.Mort(X5,T4)∨vivant(X5,T4)
10.¬mort(X6,T5)∧¬gt(T6,T5)∨mort(X6,T6)
Vivant(marcus,présent) ¬ vivant(X4,T3)∨ ¬ mort(X4,T3)
¬mort(marcus,présent) ¬ mort(X6,T5)∧ ¬ gt(T6,T5)∨mort(X6,T6)
¬ mort(marcus,T5)∧ ¬gt(présent,T5)¬pompéien(X2) ∨mort(X2,79)
¬ pompéien(marcus) ∨ ¬gt(présent,T5)présent=2002
¬ pompéien(marcus)∨ ¬gt(2013,79)
¬ pompéien(marcus) Pompéien(marcus)
marcus/X4,présent/T3
marcus/X6,présent/T6
Marcus/X2,79/T5
substituer =
réduire
PreuveparrésoluNon:exemple
154IODAA–Logiquesetraisonnement
/120
• Lesprocéduresdepreuveenlogiquedesprédicatsnepeuvent
êtrequesemi-décidables:
❏ ellesterminentenuntempsfinisiunepreuveexisteàlarequête
❏ ellespeuventnepasterminersilarequêten'estpasprouvable
Semi-décidabilité
155IODAA–Logiquesetraisonnement /120
?
-1 +1
parent(X,claude) := fille(claude,X) fille(claude,jacques)
parent(jacques,claude)
fille(claude,jacques)
parent(jacques,claude)
Unexempled'induc&on:inversiondelarésoluNon
156IODAA–Logiquesetraisonnement
/120
Bilan
• Lesinférencess’appuientsurdesinforma&onslocales+ Efficace
+ Modularitédelabasedeconnaissance
+ Fortementparallélisable
– Maisnepermetpasderéaliserpleinementcertainstypesderaisonnement(e.g.leraisonnementincertain)
• Lemécanismederaisonnement(moteurd’inférence)peutêtreséparédelabasedeconnaissances:lessystèmesexperts
• Propriétésdemonotonicité
– SionajoutedesconnaissancesàlaBC,ilnepeutenrésulterquedavantagedeconséquenceslogiques
• Mais– Twi�eestunoiseau ->ilvole– Twi�eestunmanchot ->L
157IODAA–Logiquesetraisonnement /120
PROLOG
/120
SLD-resoluNon
• LaprogrammaNonlogiqueuNliseunestratégiespécifiquede
résoluNon:laSélecNonLinéaireDéfinie(SLD).
– Àchaqueétape,uneclausedel’ensemblededépartestuNlisée
• Laméthoden’estpascomplèteengénéral,
saufsielleestappliquéeàuneclasseparNculièredeclauses:les
clausesdéfiniesouclausesdeHorn
159IODAA–Logiquesetraisonnement /120
ClausesdeHornetSLD-resoluNon
• LaSLD-resolu&on(SélecNonnéLinéaireDéfini)estuneprocédureservantà
prouveruneformuledelogiqueàparNrd’unensembledeclausesdeHorn.
• Clausedéfinie:clausedeHorncontenantexactementunliLéralposiNf
¬av¬bvc(a∧b)=>cc:-a,b
– cestlaconclusionetaetbsontlesprémissesouantécédents
160IODAA–Logiquesetraisonnement
Troismanièresdel’exprimer
/120
ClausesdeHorn
• UneclausedeHornestuneclausecontenantauplusunli`éralposi7f• p• ¬p• ¬pv¬qvr≡(q∧r=>p)
• TroistypesdeclausesdeHorn
– «Faits»:unatome(e.g.P) (enProlog:p.)
– «Règles»:• antécédent=conjoncNondeliLérauxposiNfs• conclusion=unliLéralposiNf
– (e.g.(q∧r=>p)≡pV¬qV¬r) (enProlog:p:-q,r.)
– «Buts»:ensembledeliLérauxnégaNfs (enProlog::-q.)
161IODAA–Logiquesetraisonnement /120
Mécanismedepreuve
• Programme =ensembledeclausesdeHorn
• Requête =conjoncNondeliLérauxposiNfs
1. ConstrucNondelanéga&ondelarequête=clausedeHornnégaNve(listedebuts)
2. UnificaNondu1erélémentdelanéga&onavecuneclauseduprogramme
– 1èreclauseduprogrammedontlatête(conclusion)estlacontreparNeposiNvedel’élémentconsidéré
• SicontradicNon=>succèsetpassageàl’élémentsuivant• Sifiniparéchouer,oncherchelaclausesuivanteéligible
162IODAA–Logiquesetraisonnement
/120
SLD-resoluNon:exemple(1)
• Soitleprogramme:
qv¬p
p
• Etlarequête:{q}
• Listedebuts=négaNondelarequête:{¬q}1. ¬qpeuts’unifieravec{qv¬p}donnant:¬p
2. quipeuts’unifieravecla2èmeclause:{p},donnantcontradicNon
3. Donclarequêteestprouvée
163IODAA–Logiquesetraisonnement /120
SLD-resoluNon:exemple(1)
• Soitleprogramme:
qv¬r
qv¬p
p
• Etlarequête:{q}
• Listedebuts=négaNondelarequête:{¬q}1. ¬qpeuts’unifieravec{qv¬r}donnant:¬p
2. Puiséchecàprouver¬r
3. Doncpassageàlaclausesuivanteqv¬p…
164IODAA–Logiquesetraisonnement
/120
LaSLD-ResoluNonavecdesclausesdeHorn
• …estcomplète
– SiBC|=F,alorsBCU¬FpossèdeuneréfutaNonlinéaire.
165IODAA–Logiquesetraisonnement /120
PROLOGavecdesclausesdeHorn
• StratégieparNculière:
– UNlisaNondesfaitsetrèglesdansl’ordreoùilssontécrits
– Respectdel’ordredesli`érauxdanslesantécédents
– Stratégieenprofondeurd’abord
• Stratégieengénéralefficace
• MAISincomplète
166IODAA–Logiquesetraisonnement
/120
Exemple
1. p(X,X):-q(X,Y),r(X,Z).
2. p(X,X):-s(X).
3. q(b,a).
4. q(a,a).
5. q(X,Y):-r(a,Y).
6. r(b,Z).
7. s(X):-q(X,a).
8. :-p(X,X).
167IODAA–Logiquesetraisonnement /120
Conclusion
/120
• Lesagents intelligentsontbesoindeconnaissancessurlemondepouragirefficacement
• LaconnaissanceestexpriméegrâceàunlangagedereprésentaNonsousformedeformulesdansunebasedeconnaissances(BC)
• Unagentbasésurlaconnaissanceestcomposéd'uneBCetd'unmécanisme d'inférence
• Unlangage de représentationestdéfiniparsasyntaxeetsaséman&que
• Lemécanisme d'inférencepermetdecalculerdenouvellesexpressionsàparNrd'expressionsexistantes
• IlestditcorrectsiildérivedesexpressionsvraiesàparNrdeprémissesvraies• Ilestditcompletsiildérivetouteslesexpressionsvraiesdécoulantd'unens.deprémisses
• Lalogiquedesproposi&onsdécritdesfaitssimplessurlemonde.ElleaunesyntaxeetunesémanNquesimples
• Lalogiquedesprédicatspermetd’exprimerdesrela&onsetderaisonneràleurpropos
Àretenir
169IODAA–Logiquesetraisonnement /120
• Latempératureduréacteurestélevée
➥ Logiquefloue
• Lesblondesontsouventlesyeuxbleus
➥ Raisonnementincertain(e.g.Raisonnementbayésien)
• Enl'absencederaisondecroirelecontraire,onpeutsupposerquechaqueadultequel'onrencontresaitlire
➥ Logiquedesdéfauts
• Ilestmieuxd'avoirplusdepiècesquel'adversaireauxéchecs
➥ ConnaissanceheurisNque
• JesaisqueJohnpensequelesAustraliensvontgagner,maisjecroisquec'estleXVdeFrancequil'emportera
➥ Maintenancedecroyances
Besoind'autres"logiques"
170IODAA–Logiquesetraisonnement
/120
Références
• CallanR.(2003)«ArtificialIntelligence».PalgraveMacMillan.
• FreundM.(2011)«Logiqueetraisonnement».Ellipses.
• GeneserethM.(2012)«IntroductiontoLogic».Morgan&Claypool.
• NilssonN.(1998)«ArtificialIntelligence.Anewsynthesis».MorganKaufmann.
• PooleD.&MackworthA.(2010)«ArtificialIntelligence.Foundationsofcomputational
agents».CambridgeUniversityPress.
• RusselS.&NorvigP.(2009)«ArtificialIntelligence.Amodernapproach».
PrenticeHall(3rded.).
(trad.françaisedela2nded.:«IntelligenceArtificielle»,Pearson,2010)
171IODAA–Logiquesetraisonnement