L o g ic a d e l P rim o Or d in e
– E S E R C IT A Z ION E –
DipartimentodiIngegneriadell’InformazioneUniversit`adegliStudidiBresciaAlessandroSaetti
MaterialeperilCorsodiIntelligenzaArtificiale(Prof.AlfonsoGerevini)
Eser cizi
Rappresentareleseguentiformuleinlogicadelprimoordine,usandounvocabolariocorretto(dadefinire)
1.Alcunistudentistudianofrancesenellaprimaveradel2001
2.Tuttiglistudentichestudianofrancesepassanol’esame
3.Duestudentistuadianogreconellaprimaveradel2001
4.Solounostudentestudiagreconellaprimaveradel2001
Eser cizi (cont. )
5.Ipoliziottiarrestanoiladri
6.Tuttiipoliziottiarrestanounladro
7.Tuttiiladrisonoarrestatidaunpoliziotto
8.Esiteunladroche`earrestatodatuttiipoliziotti
9.Esisteunpoliziottochearrestatuttiiladri
Eser cizi (cont. )
10.Ognipersonacheacquistaunapolizzaassicurativa`eprevidente(Predicatiutili:Persona(.),Compra(.,.),Previdente(.))
11.Nessunapersonaacquistaunapolizzacostosa(Predicatiutili:Persona(.),Compra(.,.),Polizza(.),Costosa(.))
12.Esisteunagentechevendepolizzeapersonenonassicurate(Predicatiutili:Agente(.),Vende(.,.,.),Polizza(.),Persona(.),Assicurato(.))
Eser cizi (cont. )
13.Esisteunagentechevendetuttelepolizzeatuttelepersonenonassicurate(Predicatiutili:Agente(.),Vende(.,.,.),Polizza(.),Persona(.),Assicurato(.))
14.Esisteunagentechevendetuttelepolizzeallepersoneseesoloseessenonsonoassicurate(Predicatiutili:Agente(.),Vende(.,.,.),Polizza(.),Persona(.),Assicurato(.))
15.Esisteunbarbierecheradetuttigliuominichenonsiradonodasoli(Predicatiutili:Barbiere(.),Rade(.,.),Uomo(.))
Eser cizi (cont. )
16.Ipoliticipossonoingannarequalchepersonapertuttoiltempo,tuttelepersoneperqualchetempo,manonpossonoingannaretuttelepersonepertuttoiltempo(Predicatiutili:Politici(.),Persona(.),Inganna(.,.,.))
17.Tuttiitedeschiparlanolestesselingue(Predicatiutili:Tedesco(.),Parla(.,.))
18.Tuttiitedeschiparlanoalmenounastessalingua(Predicatiutili:Tedesco(.),Parla(.,.))
Eser cizi (cont. )
Tradurrelaseguenterappresentazionegraficadiuncircuitodigitaleinuninsiemediformuledellalogicadelprimoordine.
C1
O1
A1
Eser cizi (cont. )
19.Sedueterminalisonoconnessi,allorahannolostessosegnale
20.Ilsegnaleadogniterminale`e1oppure0(16=0)
21.IlterminaleA`econnessoalterminaleBsseilterminaleB`econnessoalterminaleA
22.IlsegnalediuscitadiunaportaOR`e1ssealmenounodeiduesegnalidiingresso`e1
23.IlsegnalediuscitadiunaportaAND`e1sseentrambiiduesegnalidiingressosono1
24.+codificadellospecificocircuito
Eser cizio (Infer enza )
Tradurreleseguentia↵ermazioniusandolalogicadelprimoordine.
•Ognipersonalavoraocomeinfermiereoppurecomeinsegnante
•Tuttigliinfermierisonomaschi
•Tuttelepersonesonoomaschiofemmine
•Steve`eunmaschioeRoberta`eunafemmina
•Robertanon`eunainsegnante
DimostareperrefutazioneetramitelastrategiabasatasuinsiemedisupportocheRobertainsegna.
S in ta ss i Ot te r
•Costanti,variabili,simbolidifunzioneepredicati:stringacom-postadaalfanumerici,
•Predicati/funzioni:simbolo(argomentiseparatida,)NOspaziaturatrasimbolodipredicato/funzionee(
•Nelcontestodiclausole:
–Levariabiliinizianoconu,v,w,x,y,z.
–Seilflagprologstylevariables´eON:levariabiliinizianoconoppureconunaletteramaiuscola
•Nelcontestodiformule:
–Ilsimbolo´eunavariabileseesolose`equantificato.
S in ta ss i Ot te r ( c o n t. )
OperazioneSimboloPriorit`aQuantificatoreesistenzialeexists-Quantificatoreuniversaleall-
•Quantificazionerichiestainformule,daevitareinclausole
•Formaprefissa:$Quantified(all,x,y,exists,z,|(P(x,y),-(Q(z)))).
•Formainfissa:allxallyexistsz(P(x,y)|-Q(z)).Formasemplificata:allxyexistsz(P(x,y)|-Q(z)).
•Obbligatoriaparentesidopouno(opi`u)quantificatori
•Spaziaturaobbligatoriaprima/dopo“all”e“exists”eprima“–”
•=,eq,Eq,EQsonopredicatidiuguaglianza
•!=`eilpredicatodidisuguaglianza
Esempio
Scriverelerappresentazionilogichedelleseguentiformulesecondolasintassidiotter.
Duetalpevivonoinunabuca.Nessunadelleduevuolecondividerelatanaconl’altra.
set(auto).
formula_list(usable).%Inciascunabucavivealpiu’unatalpaallxyz(talpa(x)&talpa(y)&buca(z)&abita(x,z)&-eq(x,y)->-abita(y,z)).
%Ognitalpaviveinunabuca.allx(talpa(x)->(existsz(buca(z)&abita(x,z)))).
%Esistono2talpeexistsxy(talpa(x)&talpa(y)&x!=y).allx(x=x).
%Esiste1eunasolabuca.existsx(buca(x)&(ally(y!=x->-buca(y)))).end_of_list.
Esempio (cont. )
1[]-talpa(x)|-talpa(y)|-buca(z)|-abita(x,z)|eq(x,y)|-abita(y,z).2[]-talpa(x)|buca($f1(x)).3[]-talpa(x)|abita(x,$f1(x)).4[]$c2!=$c1.5[]x=$c3|-buca(x).6[]talpa($c2).7[]talpa($c1).8[]x=x.9[]buca($c3).10[hyper,6,3]abita($c2,$f1($c2)).11[hyper,6,2]buca($f1($c2)).13[hyper,7,3]abita($c1,$f1($c1)).14[hyper,7,2]buca($f1($c1)).18,17[hyper,11,5]$f1($c2)=$c3.19[back_demod,10,demod,18]abita($c2,$c3).22,21[hyper,14,5]$f1($c1)=$c3.23[back_demod,13,demod,22]abita($c1,$c3).30,29[hyper,23,1,6,7,9,19]eq($c2,$c1).35[back_demod,4,demod,30]$c1!=$c1.36[binary,35.1,8.1]$F.
Eser cizio 1
Tradurreleseguentia↵ermazioniinformuledellalogicadelprimoordineutilizzandolasintassidiOtter.
•Ognipersonalavoraocomeinfermiereoppurecomeinsegnante
•Tuttigliinfermierisonomaschi
•Tuttelepersonesonoomaschiofemmine
•Steve`eunmaschioeRoberta`eunafemmina
•Robertanon`eunainsegnante
UtilizzareOTTERpermostrarecheRobertainsegna.
Eser cizio 2
Tradurreleseguentia↵ermazioniinformuledellalogicadelprimoordineutilizzandolasintassidiOtter.
C1
O1
A1
UtilizzareOTTERperdimostrarecheafrontedell’ingressoh1,0,1il’uscita`e1.
Eser cizio 3
Un’indaginefattasuungruppodilavoratorisiderurgicihafornitoleseguentiinformazioni:
•Almenounodeilavoratoriintervistatinone’stranieroealmenounmaschioe’straniero
•Seunlavoratoree’dicoloree’straniero
•None’verochealmenounmachioe’biondo
UtilizzareOTTERpermostarequalia↵ermazionisonovere.
A.Tuttiglistranierisonodicolore
B.Almenounmaschiostranieronone’biondo
C.Nessunmaschiobrunoe’straniero
D.Almenounmaschionone’straniero
E.Almenounafemminae’straniera
Eser cizio 4
Tradurreleseguentia↵ermazioniinformuledellalogicadelprimoordineutilizzandolasintassidiOtter.
Gianni,MarioeDiegosonogestore,cuocoecamerierediunris-torante,nonnell’ordineconsiderato.Gianni,amicodelfratellodiMario,`epi`ugiovanediMarioehagliocchineri.Ilcamerierehagliocchiazzurri,mentreilgestore`efigliounicoed`eilpi`uanzianodeitre.
UtilizzareOTTERpermostarequale`eillavorodiciascuno.
Eser cizio 5
ScriverelarappresentazionelogicadelseguentedispositivoC1sec-ondolasintassidiOTTER.
X1
X2A2
O1
A1 C1
UtilizzareOTTERperdimostrarecheafrontedell’ingressoh1,0,1il’uscita`eh0,1i.
Eser cizio 6 (20/01/2011)
1.Formalizzareutilizzandolalogicadelprimoordineleseguentia↵ermazioni:
•Glistudenticheviaggianosuunqualsiasitaxinonpossiedonounauto,
•Itassistipossiedonounauto,
•Itassistiviaggianosualmenountaxi,
•Esisteuntassistastudente.
2.Trasformareleprecedentiformuledellalogicadelprimoordineinformatoclausolare.
3.Dimostrarechenonpossonoesistereastenuti.
Eser cizio 7 (07/07/2011)
1.Formalizzareutilizzandolalogicadelprimoordineleseguentia↵ermazioni:
•Unladro`earrestatodaalpi`uunpoliziotto(ovveroseunladro`earrestatodaunpoliziottoallorailladrononpu`oesserearrestatodaunsecondodi↵erentepoliziotto).
•Due(di↵erenti)poliziottiarrestanounostessoladro.
2.Trasformareleprecedentiformuledellalogicadelprimoordineinformatoclausolare.
3.Dimostrarechenonpossonoesistereastenuti.
Eser cizio 8 (01/09/2011)
1.Formalizzareutilizzandolalogicadelprimoordineleseguentia↵ermazioni:
•Tuttigliitalianivotanoperalmenounpartito,
•Gliastenutinonvotanoperipartiti,
•Gliastenutisonoitaliani
2.Trasformareleprecedentiformuledellalogicadelprimoordineinformatoclausolare.
3.Dimostrarechenonpossonoesistereastenuti.
