Re: Logic Problems

*To*: mathgroup at smc.vnet.net*Subject*: [mg2512] Re: Logic Problems*From*: rubin at msu.edu (Paul A. Rubin)*Date*: Wed, 15 Nov 1995 02:01:11 -0500*Organization*: Michigan State University

In article <47pnbh$fhc at ralph.vnet.net>, TTCJ34A at prodigy.com (DR JOHN C ERB) wrote: ->Can Mathematica be used to solve logic problems? As a ->simplistic example: Mary is older than Tom; Tom is older ->than Sue; is Mary older than Sue? I would like to be able ->to do this type of problem without specifying values (i.e., ->ageMary=35). ->Thank you. ->John C. Erb The short answer is "yes," but the only way I know of to do it involves some rather tricky (or at least finicky) programming. A solution to your problem follows: people = {mary, tom, sue}; (* define the population *) (* define the predicate "Older" as a function *) Clear[ Older ]; Older[ x_, x_ ] := False /; MemberQ[ people, x ] (* antireflexive *) Older[ x_, y_ ] := False /; OrderedQ[ {x, y} ] && (* anticommutative *) Older[ y, x ] Older[ x_, y_ ] := (* transitive *) Select[ Complement[ people, {x, y} ], (Older[ x, # ] && Older[ #, y ])& ] != {} /; MemberQ[ people, x ] && MemberQ[ people, y ] (* known values of the predicate follow *) Older[mary, tom] = True; Older[tom, sue] = True; (* form all pairs of people *) pairs = Flatten[ Outer[ List, people, people ], 1 ] {{mary, mary}, {mary, tom}, {mary, sue}, {tom, mary}, {tom, tom}, {tom, sue}, {sue, mary}, {sue, tom}, {sue, sue}} (* see which pairs satisfy the relation *) Select[ pairs, Older[ Sequence@@# ]& ] {{mary, tom}, {mary, sue}, {tom, sue}} As you can see, the solution involves defining an "alphabet" of atoms (in this case the list of people), and then defining a predicate which returns True or False accordingly as the relation holds/does not hold. Known instances of the predicate (Mary older than Tom, Tom older than Sue) are established using explicit Set (=) commands. Properties of the relation useful for logical solution (antireflexive, anticommutative, transitive) are established as substitution rules using SetDelayed (:=). Here's why I called it finicky. It's difficult to predict, let alone control, the order in which Mma will apply substitution rules, so you have to be extremely careful to rule out any chance of an infinite recursion. For instance, without the OrderedQ[] qualifier on the anticommutativity (is that a word?) statement, Mma will attempt to evaluate Older[ mary, sue ] by checking Older[ sue, mary ], which it then attempts to evaluate by checking Older[ mary, sue ] ... Similarly, you either have to be careful to place antireflexivity ahead of anticommutativity, or add the qualifier x =!= y to the list of conditions in the anticommutativity statement, or else Mma goes into a recursion fit trying to decide if Older[ mary, mary ] holds (since OrderedQ[{mary, mary}] is true). Still, if you don't mind extensive debugging to resolve recursion hassles, and if you can recognize which properties of the underlying question you need, this would seem to work. Paul Rubin ************************************************************************** * Paul A. Rubin Phone: (517) 432-3509 * * Department of Management Fax: (517) 432-1111 * * Eli Broad Graduate School of Management Net: RUBIN at MSU.EDU * * Michigan State University * * East Lansing, MI 48824-1122 (USA) * ************************************************************************** Mathematicians are like Frenchmen: whenever you say something to them, they translate it into their own language, and at once it is something entirely different. J. W. v. GOETHE