Logic a Prop os iz ionale
– E S E R C IT A Z ION E –
DipartimentodiIngegneriadell’InformazioneUniversit`adegliStudidiBresciaAlessandroSaetti
saetti@ing.unibs.it
MaterialeperilCorsodiIntelligenzaArtificiale(Prof.AlfonsoGerevini)
Eser cizio 1
Sel’unicorno`eunanimalemitico,`eimmortale,masenon`emitico,allora`eunmammiferomortale.Se`eimmortaleounmammifero,allorahauncorno.L’unicorno`emagicosehauncorno.
Scriverelerappresentazionilogichedelleprecedentiformuleedi-mostrareperrefutazioneconlastrategiabasatasuinsiemedisup-portoquantosegue.
•L’unicorno`emitico?
•L’unicorno`emagico?
•L’unicornohauncorno?
Eser cizio 2
Johnlosfregiato,BilllosquartatoreeJackildurovengonointer-rogaticonl’accusadiaverrubatolacassettadelleelemosinadellaparrocchia.Jackdicecheilfurtoe’statocommessodaBill;BillsiprofessainnocenteeJohna↵ermadinonavercompiutoilfurto.Sapendochesolounodeitredicelaverit`a,chi`eilladro.
Scriverelerappresentazionilogichedelleprecedentiformuleinmodotalechesianoutilizzabiliconlarisoluzioneunitaria.ScoprireperrefutazioneetramitelastrategiadirisoluzionebasatasuinsiemedisupportochitraJohn,JackeBillhacommessoilfurto.
Suggerimento:UsareiletteraliFurtoBill,FurtoJack,FurtoJohn,VeritaBill,VeritaJack,VeritaJohn
Applic az ioni D imos trato ri di T eo remi
•Dimostrazione,supervisioneeverificaditeoremi
–TeoremadiincompletezzadiGodel
•Verificasoftware,hardware,protocollidiSicurezza
–Sistemadicontrollodellospace-shuttle
–DivisioneFloating-PointperilprocessoreAMD5k86
–ProtocolloRSA
•Generazionedisoftware
–Programmipercomandaresatelliti
Ot te r
•Otter=OrganizedTechniquesforTheorem-provingandE↵ec-tiveResearch
•`Ebasatosulogicadelprimoordine
•Sistemasemi-automatico
•Funzionaancheinbatchmode:otter<input>output
•IndirizziInternetutili:
HomePagediOtter:http://www.mcs.anl.gov/AR/otter/
Manuale:http://www-unix.mcs.anl.gov/AR/otter/otter3manual.pdf
Sintas si
•Nomiordinari:stringacompostadaalfanumerici,
•Caratterispeciali:
–%:commenti
–.:fineespressione
–,():punteggiaturaesimbolidiraggruppamento
•Nomicheinizianocon$sonoriservati(Es.$AND)
•Lettereminuscoledi↵erentidaletteremaiuscole
Sintas si - Claus ole
OperatoriSimboloPriorit`aNegazione-1Disgiunzione|3
•Formaprefissa:|(-(a),|(-(b),c)).
•Formainfissa:-a|-b|c.
•Spaziaturaobbligatoriaprimadi“–”
•Tutteleclausoleterminanocon“.”
Sintas si - F o rmule
OperazioneSimboloPriorit`aNegazione-1Congiunzione&2Disgiunzione|3Implicazione->4Equivalenza<->4
•Tutteleformuleterminanocon“.”
•Ottertrasformaleformuleinclausole
Lis te di Claus ole/F o rmule
Otterutilizzalastrategiabasatasuinsiemedisupporto
•usable:clausole/formuleusateperl’inferenza
•sos:clausole/formulechepartecipanoallaricerca
•passive:clausole/formuleusatepercontrollareilprocessoindimostrazionidifficili(sussunzioni/unit-conflict)
•demodulators:uguaglianzeutilizzateperlariscritturadiclau-sole/formuleinferite
Comandi e F ile di Input
•Otterriconosceduetipidiopzioni:
–flag:opzionibooleaneassegnateconseteclear
ES:set(binaryres);
–parametri:valoriinteriassegnaticonassign
ES:assign(maxseconds,100).
•Lelisteinizianoconlist(list_name).,formula_list(list_name).
listname`eusable,sos,demodulators,oppurepassive
•Lelisteterminanoconend_of_list.
Comandi e F ile di Input
ComandoDescrizioneinclude(filename)includefilenamenelfilecorrenteop(precedenza,tipo,nome)dichiaraunoperatoremakeevaluable(simb,simbvalutato)dichiaraunaliasdisimbolovalutatoset(flagname)settailflagflagnameclear(flagname)resettailflagflagnameassign(parametername,integer)parametername=integerlist(listname)listadelleclausole
formulalist(listname)listadelleformuleweightlist(weightlistname)listadeipesilex(symbollist)assegnaunordinamentoaisimboli
Mo dalit `a Automatica
•Impostatatramiteilflagauto:set(auto)
•set(auto)DEVEessereilprimocomando
•LaKB`einteramenteinlist(usable)
•Otterdecide:
-regolediinferenza;
-strategiadiricerca;
-listasos.
Esempio
Scriverelerappresentazionilogichedelleseguentiformulesecondolasintassidiotter.
Duetalpevivonoinunabuca.Nessunadelleduevuolecondividerelatanaconl’altra.
set(auto).
list(usable).%Ognitalpaviveinunbuco.
ViveT1B1.
ViveT2B1.
%Nellabucavivealpiu’unatalpa.-ViveT1B1|-ViveT2B1.
end_of_list.
Regole di inf erenza
•Binaryresolution(flagbinaryres)Risoluzionecondueclausole.
infermiera(Roberta),¬infermiera(Roberta)False
•Unitresultingresolution(flagurres)Ilrisultato`eunaclausolaunitaria.
Dataunaclausolaconnterminien1clausoleunitarielerisolveinuncolposolo.
¬P(x,y)_Q(y,z)_¬R(u,v)_S(x,z),P(John,Mary),¬Q(Mary,Cats),R(Birds,Mice)S(John,Cats)
•Hyper-Resolution(flaghyperres)Unaclausolahaalmenounletteralenegativo,mentrelealtrenonnehanno.Ilrisultatononcontieneletteralinegativi.
¬P(x,y)_Q(x)_¬R(y)P(Spock,Data)R(z)_S(z)Q(Spock)_S(Data)
Regole di inf erenza
•ParamodulationUnodegliargomentidelpredicatodiuguaglianzadeveunificareconunsottoterminedell’altraclausola.
difference(twosquared,b)equal(twosquared,four)difference(four,b)
–Paramodulationfromthegivenclause(flagparafrom):lagivenclausecontieneunpredicatodiuguaglianza
–Paramodulationintothegivenclause(flagparainto):ilpredicatodiuguaglianzanon`econtenutonellagivenclause,mailrisultatodell’inferenza`elasostituzionediunparametrodellagivenclause.
Ca ratteristiche
•LaKB`especificatatramiteclausoleoppureformuledelprimoordine
•Forwarddemodulation:semplificaleclausoleinferite
•BackwardDemodulation:semplificaleclausoleesistenti
•ForwardSussumption:cancellaleclausoleinferite
•BackwardSussumption:cancellaleclausoleesistenti
•pesieordinamentolessicale
A lg o rit m o d i Ot te r
while(sosnonvuota&nessunadimostrazionee’statatrovata)
begin
given_clause:=migliore_clausola(sos);
usable:=usableUgiven_clause;sos:=sos-given_clause;
new_clauses:=inferisci(given_clause,clause_usables)
ifretention_test(new_clauses)then
sos:=sosUnew_clauses;endwhile.
Esempio (cont. )
Duetalpevivonoinunabuca.Nessunadelleduevuolecondividerelatanaconl’altra.
UtilizzareOTTERperdimostrarechenon`epossibileunacon-vivenzacivile.
givenclause#1:(wt=3)3[]ViveT2B1.**KEPT(pick-wt=0):4[hyper,3,2,1].
--->EMPTYCLAUSEat0.00sec---->4[hyper,3,2,1]$F.
Inconclusione,ladimostrazione`elaseguente:
1[]ViveT1B1.2[]-ViveT1B1|-ViveT2B1.3[]ViveT2B1.4[hyper,3,2,1]$F.
Eser cizio 1
Johnlosfregiato,BilllosquartatoreeJackildurovengonointer-rogaticonl’accusadiaverrubatolacassettadelleelemosinadellaparrocchia.Jackdicecheilfurtoe’statocommessodaBill;BillsiprofessainnocenteeJohna↵ermadinonavercompiutoilfurto.Sapendochesolounodeitredicelaverit`a,chi`eilladro.
ScriverelerappresentazionilogichedelleseguentiformulesecondolasintassidiOTTERedutilizzareildimostratorediteoremiperscoprirechitraBill,JohneJackhacommessoilfurto.
Eser cizio 2
Estensionedell’esempiodelle2talpea3talpe:
Tretalpevivonoinunavalleconduebuche.Nessunadelletalpevuolecondividerelatanaconun’altratalpa.
Scriverelerappresentazionilogichedelleseguentiformulesecondolasintassidiotteredutilizzareildimostratorediteoremiperdimostrarechenon`epossibileunaconvivenzacivile.
Eser cizio 3
Sapendocheglienigmisonodeimisteriechenoncisonoin-dovinellichenonsonoenigmi,scriverelerappresentazionilogichedelleseguentiformulesecondolasintassidiOTTERedutilizzareildimostratorediteoremiperdeterminarequalitraleseguentia↵er-mazionisonovere:
•Imisterisonoindovinelli.
•Noncisonomisterichenonsonoenigmi.
•Gliindovinellisonomisteri.
•Noncisonoenigmichenonsonoindovinelli.
•Glienigmisonoindovinelli.
