1Reasoning Systems2Rule-Based Programming Languages•Both forward and backward chaining with rules form thebasis of programming languages.•Prolog (PROgramming in LOGic) represents programs aslogical Horn clauses and treats execution as answeringqueries with backward chaining.•Production system languages (OPS5, CLIPS) representprograms as rules that add and/or delete elements fromworking memory and treat execution as forward chaininginference.3Prolog•Prolog programs are stated as Horn clauses (facts andrules)member(X, [X | L]).member(X, [Y | L]) :- member(X, L).append([ ], L, L).append([X | L1], L2, [X | L3]) :- append(L1, L2, L3).•Programs are executed by making queries.? member(a [a,b,c]) Yes.? append([a,b], [c,d], X)X = [a,b,c,d].•Queries can generate “output” from “input”? member(X, [a,b,c]) a; b; c; No.4Prolog(cont)•More query examples:? append(X, [c], [a,b,c]) X=[a,b].? append(X, Y, [a,b]) X=[], Y=[a,b]; X=[a], Y=[b]; X=[a,b], Y=[]; No.? member(a, X) [a | Z1]; [Z2, a | Z3]; [Z4, Z5, a | Z6]; ....5Prolog Search•Prolog uses depth-first search, pursuing conjuncts in thebody of a clause in left to right order.•Not guaranteed to terminate:ancestor(X,Y) :- parent(X,Y).ancestor(X,Y) :- ancestor(X,Z), parent(Z,Y).parent(Tom, John).? ancestor(X, John)X=Tom;....................•Programs must be written carefully to guarantee efficiencyand termination, as in any other programming language.6Negation as Failure•Since it uses Horn clause inference, Prolog cannot handletrue negation.•However, it does include negation as failure, not(P),which is assumed to be true unless P can be proven.sibling(X,Y) :- parent(P,X), parent(P,Y), not(X=Y).bachelor(X) :- male(X), adult(X), not(married(X,Y)).married(X,Y) :- husband(X,Y).married(X,Y) :- husband(Y,X).married(X,Y) :- wife(X,Y).married(X,Y) :- wife(Y,X).•Unless all relevant knowledge is in the KB (closed worldassumption, CWA), this type of inference is unsound.Not proving P is not the same as proving ¬P!?sibling(mark-twain,samuel-clemens)Yes.7Production Systems•Forward chaining systems used to construct many expertsystems and as a model of human cognition.•Basis of several rule-based programming languages suchas OPS5 and CLIPS.•Maintains a working memory of positive ground literals(facts)•Maintains a production memory or rule memory of rulesof the form:p1∧ p2.... ∧ pn⇒ act1∧ act2 .... ∧ actmwhere pi are positive literals and actiare actions that canadd or delete elements from working memory (and perhapsperform I/O)8Production System ExecutionUntil no more rules fire doMatch: Find all instantiations (variable bindings) of rules whose conditions match working memoryConflict Resolution: Pick one of these rules to actually fireAct: Execute the instantiated actions for this ruleWMProductionsMatcherConflictResolutionAct9Production System Phases•Match: Repeatedly attempting to match all rules every timeis too inefficient. Better to maintain a list of currently“active” rules and update it each time working memory ischanged.-Rete net is a standard approach.•Conflict Resolution: Pick a rule to fire based on:-No duplication: Don’t fire the same rule instantiationtwice.-Recency: Prefer rules whose conditions rely on recentlycreated elements of working memory.-Specificity: Prefer rules with more specific conditions sneezing ⇒ cold sneezing ∧ itching ⇒ allergies10Semantic Networks•Use graphs to represent concepts and the relations betweenthem.•Simplest networks are ISA heirarchies•Must be careful to make a type/token distinctionBevo isa Cattle Cattle(Bevo)Cattle isa Ungulate ∀x (Cattle(x) ⇒ Ungulate(x))•Restricted shorthand for a logical representation.animalvertebrateinvertebratefishreptilemammalungulate primatehuman apecattle deer11Semantic Nets / Frames•Labelled links can represent arbitrary relations betweenobjects and/or concepts.•Nodes with links can also be viewed as frames with slotsthat point to other objects and/or concepts.(b) Translation into first−order logicSubsetSubsetSubsetSubsetName(Opus,"Opus")Name(Bill,"Bill")Friend(Opus,Bill)Friend(Bill,Opus)AnimalsBirds MammalsPenguins Cats BatsRel(Alive,Animals,T)Rel(Flies,Birds,T)Rel(Legs,Birds,2)Rel(Legs,Mammals,4)Rel(Flies,Penguins,F)Rel(Legs,Bats,2)Rel(Flies,Bats,T)Rel(Flies,Animals,F)MemberMemberMemberOpus PenguinsBill CatsPat BatsName(Pat,"Pat")Flies: FLegs: 2Flies: TLegs: 4Flies: FLegs: 2Flies: TOpus BillFriend: Friend:PatName: PatName: BillName: OpusAlive: TSubset(a) A frame−based knowledge baseBirds AnimalsMammals AnimalsPenguins BirdsCats MammalsBats Mammals12Inheritance•Inheritance is a specific type of inference that allowsproperties of objects to be inferred from properties ofcategories to which the object belongs.Is Bill alive?Yes, since Bill is a cat, cats are mammals, mammals areanimals, and animals are alive.•Such inference can be performed by a simple graphtraversal algorithm and implemented very efficiently.•However, it is basically a form of logical inference∀x (Cat(x) ⇒ Mammal(x))∀x (Mammal(x) ⇒ Animal(x))∀x (Animal(x) ⇒ Alive(x))Cat(Bill)|− Alive(Bill)13Backward or Forward?•Backward reasoning is more goal directed and can therefore bemore efficient at answering specific queries.•However, it can be very inefficient for some inferences likeinheritance.?Alive(Bill)Animal(Bill)? Bird(Bill)? Penguin(Bill)? Robin(Bill)?Grackle(Bill),...Mammal(Bill)?, Ungulate(Bill)?.....•In this case, forward reasoning is more efficient but still notdirected towards a particular goal.Cat(Bill) ⇒ Mammal(Bill) ⇒ Animal(Bill) ⇒ Alive(Bill)•Which is more efficient depends on whether the forward orbackward branching factor is worse.•Inheritance methods allow goal-directed efficient reasoning for aspecific, restricted type of inference.14Semantics of Links•Must be careful to distinguish different types of links.•Links between tokens and tokens are different than linksbetween types and types and links between tokens and types.Link Type Semantics ExampleASubset!B AB CatsMammalsAMember!B A2B Bill2CatsAR!B R(A,B) BillAge!12AR!B8x x2A)R(x,B) BirdsLegs!2AR!B8x9y x2A)y2B^R(x,y) BirdsParent!Birds15Inheritance with Exceptionsand Multiple Inheritance•Information specified for a type gives the default