=========================preview======================
(COMP221)midterm97S_sol.pdf
Back to COMP221 Login to download
======================================================
ASolutionSketchForSampleMidterm
1.(a)Sequenceofnodesthatareexpanded:ACFBEJ.Solutionpath: ABEJ.Pathcost.34.(b)Sequenceofnodesthatareexpanded:ACF BGN.Solutionpath:ACGN.Pathcost.31.(c)Let'sdenotebyh.(n) thepathcostoftheoptimalsolutionfromnodentoagoalnode.Forhto beadmissible,youneedtoshowthath(n).h.(n)foreverynodeinthe tree.Thiscanbedonebyjustenumeratethemall:h(A).25,h.(A).31, h(B).26,h.(B).31,...
2.TheMAXplaywillchoosetheleftmoveif:
min(max(x0)10)min(2max(3y)).
thatis,ifx2.
3.(a)\thereissomeonewhorespectseveryone".(b)\everyoneisrespected bysomeone".(c)theyarenotequivalent.Toexplainwhyformally,youneed toconstructaninterpretationthatsatis.esonebutnottheother.Sincewe didnottalkmuchaboutformalsemantics,youcanjustgiveanyinformal reasons.
4.(a)Thereareseveralwaystodothis.Recallthatwhenwetransform asentencetoitsconjunctivenormalform,wesaidthatallstepspreserve logicalequivalenceexceptthestepofSkolemization.Soonepossibleway toshowthatthesetwosentencesareequivalentistoseewhetherwecan transformthemintotheirCNFwithoutusingSkolemization.Thisisnot alwayspossible,butforthisproblemitisok:
The.rstsentence:
8x[9yLoves(yx)])Happy(x)7!(eliminateimplication) 8x:[9yLoves(yx)]_Happy(x)7!(movenegationinside) 8x[8y:Loves(yx)]_Happy(x)7!(movequanti.erstothefront) 8xy:Loves(yx)_Happy(x)7!(dropquanti.ers) :Loves(yx)_Happy(x)(1)
Thesecondsentence:
8xyLoves(yx))Happy(x)7! 8xy:Loves(yx)_Happy(x)7! :Loves(yx)_Happy(x)(2)
Since(1)and(2)arethesame(ingeneral,it'sokiftheycanbemadethe samebyrenamingsomevariables),sotheyareequivalent.
1
Amoregeneralwayofprovingequivalenceistouseresolution:toshowthat thesetwosentencesareequivalent,youneedtoshowthat
[8x[9yLoves(yx)])Happy(x)],[8xyLoves(yx))Happy(x)]
isvalid,thatis,followsfromtheemptyKB.Byrefutationusingresolution,
.rsttransformthenegationoftheaboveequivalenceintoCNF,andthen useresolutiontoderivetheemptyclause.
6.(a)Asearchstrategyiscompleteifitisguaranteedtoreturnasolution ifoneexists.(Seepage73inthetextbook)(b)Aninferenceprocedureis completeifitcanderiveallconclusionsentailedbytheKB.(Seepage286 ofthetextbook.)
2