MathGroup Archive 1995

[Date Index] [Thread Index] [Author Index]

Search the Archive

Re: Logic Problems

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

In article <47pnbh$fhc at>,
   TTCJ34A at (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., 
->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

  • Prev by Date: Re: Request for MMA benchmarks & platform comparisons
  • Next by Date: Re: Positive[a] = True ???
  • Previous by thread: Re: Logic Problems
  • Next by thread: Re: Logic Problems