% ================================================================= % == == % == An Introduction to ARTIFICIAL INTELLIGENCE == % == Janet Finlay and Alan Dix == % == UCL Press, 1996 == % == == % ================================================================= % == == % == chapter 2, page 35: non-monotonic reasoning == % == TMS - truth maintenace system == % == == % == Prolog example, Alan Dix, August 1996 == % == == % ================================================================= % Items and their dependencies are coded using the two % predicate 'item'. % Each item is either of the form: % item( item number, description, sl([positive support],[negative]) ). % which says that the given item is dependent on the positive list % being true and the negative list all false, % or: % item( item number, description, unknown ). % which says that the item has not been given a support list and its % truth is unknown. This is different from the empty support list % 'sl([],[])', which says that the item does not depend on anything % - it is a fact. % % In the book the items in the support list are given a + or - sign % to say whether the item depends on their truth or falsity. % However, in this Prolog representation, this is assumed from which % list they are in. item( 1, 'it is winter', sl([],[]) ). item( 2, 'it is cold', sl([1],[3]) ). item( 3, 'it is warm', unknown ). % Before starting the truth maintenance procedure an easier % to use dependency representation is constructed. % For each pair X, Y where X depends on Y, a Prolog term % is asserted tms_dep(X,Y,true) if it is a positive dependency % and tms_dep(X,Y,false) if it is a negative dependency. % This would be a very verbose representation to write, but % is easier to use in Prolog than the list based representation. % tms_clear_dep - removes and existing dependency information % tms_build_dep - actually builds the new representation % tms_build_dep_2 - runs through a list of items adding a dependency % for each tms_clear_dep :- retractall(tms_dep(X,Y,PorN)), assert(tms_dep(-1,-2,null)). % null entry so that % tms_dep always exists tms_build_dep :- item(Item,Desc,sl(Pos,Neg)), tms_build_dep_2(Item,Pos,true), tms_build_dep_2(Item,Neg,false), fail. tms_build_dep. tms_build_dep_2(Item,[],PorN). tms_build_dep_2(Item,[First|Rest],TorF) :- assert(tms_dep(Item,First,TorF)), tms_build_dep_2(Item,Rest,TorF). % tms_update completely rebuilds the truth values % by setting everything to false and then setting % the given facts to true using tms_do_set. % (N.B. given facts = empty support list - 'sl([],[])') % The setting of facts to true uses 'tms_do_set' % which chases dependencies setting other items to % true or false appropriately. % At the end the whole system will be at a consistent truth state. tms_update :- retractall(is_true(X,Y)), !, tms_set_all_false, tms_set_facts_true. tms_set_all_false:- item(Item,Desc,SL), assert(is_true(Item,false)), fail. tms_set_all_false. tms_set_facts_true:- item(Item,Desc,sl([],[])), tms_do_set(Item,true), fail. tms_set_facts_true. % tms_do_set sets the relevant item to be either true or false % dependent on the second argument. % If there is no change, then tms_do_set simply succeeds and does % nothing. % If there is a change, then this may have altered the truth of % other items. In this case tms_do_dep is called to check and, % if necessary, to update any dependent items tms_do_set(Item,TorF) :- is_true(Item,TorF),!. % do nothing if no change tms_do_set(Item,TorF) :- is_true(Item,NotTorF), retract(is_true(Item,NotTorF)), fail. % remove old fact if set tms_do_set(Item,TorF) :- assert(is_true(Item,TorF)), !, % end of sequential part tms_do_dep(Item,TorF). % tms_do_dep is called when an item changes its truth. % It checks to see if any dependents of the item should change % their truth. This can happen for two reasons. % (i) If an item now agrees with a dependency then the dependent % item MAY become true, but all other dependents must also be % checked by calling tms_recheck % (ii) If the item now disagrees witha dependency, the dependent % item MUST become false. No other checking is necessary. tms_do_dep(Item,TorF) :- tms_dep(X,Item,DepTorF), % item now agrees with dependency tms_do_dep2(X,TorF,DepTorF), fail. tms_do_dep(Item,TorF). tms_do_dep2(X,TorF,TorF) :- % item now agrees with dependency tms_recheck(X). % X may now be true, check it tms_do_dep2(X,TorF,NotTorF) :- not TorF = NotTorF, % item now disagrees with dependency tms_do_set(X,false). % X must therefore be false % An item must be false if any of its dependent items disagree. % That is if the item is dependent on another item X and % either X is false and is a positive dependent % or X is true and is a negative dependent tms_is_false(Item) :- tms_dep(Item,X,TorF), is_true(X,NotTorF), not TorF = NotTorF. % tms_recheck looks at dependencies to see if an Item % which used to be false has now become true tms_recheck(Item) :- is_true(Item,true). % if it is true already do nothing tms_recheck(Item) :- is_true(Item,false), not tms_is_false(Item), % are any dependencies wrong? tms_do_set(Item,true). % if not it must be true! % tms_init and tms_set are the predicates that you use to interact % with the truth maintenance system. % tms_init should be called when you start and subsequently % if you want to reset the system. % tms_set can only be used to set the truth of falsehood of any item % which has an 'unknown' value. Other values are calculated using % the dependencies in the support lists. tms_init :- tms_clear_dep, fail. tms_init :- tms_build_dep, fail. tms_init :- tms_update. tms_set(Desc,TorF) :- item(Item,Desc,unknown),!, tms_do_set(Item,TorF). tms_set(Desc,TorF) :- item(Item,Desc,sl(Pos,Neg)), write('Item '), write(Item), write(': '), write(Desc), write(' has support list, cannot be set true or false'), nl, fail. % tms_list prints the truth/falsity of all items tms_list:- item(Item,Desc,SL), is_true(Item,TorF), write(Item), write(': '), write(Desc), write(' - '), write(TorF), nl, fail. tms_list. % RUNNING THIS CODE % % The example given is a bit small (3 items!), so there is not % much you can do. However, even with three items you can check % things function as expected. here is an example script: % % tms_init. % necessary as first action % tms_dep(X,Y,T). % examine the constructed dependencies % is_true(X,T). % see what has been deemed to be true % tms_set('it is winter',false). % see the error message % tms_set('it is warm',true). % really set an item % tms_list. . % see how it has affected the other items % % After doing this you can try an build a more extensive set of % items and support lists by making your own 'item' definitions %