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