[QUIZ] Inference Engine (#37)

[Ruby Quiz]

The three rules of Ruby Quiz:

1. Please do not post any solutions or spoiler discussion for this quiz until
48 hours have passed from the time on this message.

2. Support Ruby Quiz by submitting ideas as often as you can:

http://www.rubyquiz.com/

3. Enjoy!

-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=

There was an interesting thread on Ruby Talk recently about Truth Maintenance
Systems (TMS). One reason to use a TMS is to validate inferences, given certain
truths. We'll focus on that application here.

This week's Ruby Quiz is to build an inference engine that is capable of
answering questions based on the provided truths.

Note that our Perl friends have already done this quiz, with their own Perl Quiz
of the Week. It was an interesting problem that generated good solutions and
discussion. Because of that, I'm going to copy the format used there,
originally by Dan Sanderson and Mark Jason Dominus.

You should be able to teach your engine truths with the following inputs:

All PLURAL-NOUN are PLURAL-NOUN.
No PLURAL-NOUN are PLURAL-NOUN.
Some PLURAL-NOUN are PLURAL-NOUN.
Some PLURAL-NOUN are not PLURAL-NOUN.

You should also be able to query your engine with the following questions:

Are all PLURAL-NOUN PLURAL-NOUN?
Are no PLURAL-NOUN PLURAL-NOUN?
Are any PLURAL-NOUN PLURAL-NOUN?
Are any PLURAL-NOUN not PLURAL-NOUN?
Describe PLURAL-NOUN.

Here's a sample run straight out of the Perl Quiz to show how all of this fits
together:

All mammals are hairy animals. OK.
All dogs are mammals. OK.
All beagles are dogs. OK.
Are all beagles hairy animals?

Yes, all beagles are hairy animals.

All cats are mammals. OK.
All cats are hairy animals. I know.
Are all cats dogs? I don't know.
No cats are dogs. OK.
Are all cats dogs? No, not all cats are dogs.
Are no cats dogs? Yes, no cats are dogs.
All mammals are dogs.

Sorry, that contradicts what I already know.

Some mammals are brown animals. OK.
Are any mammals dogs? Yes, some mammals are dogs.
Are any dogs brown animals? I don't know.
Some dogs are brown animals. OK.
All brown animals are brown things. OK.
Are any dogs brown things?

Yes, some dogs are brown things.

Describe dogs.

All dogs are mammals.
All dogs are hairy animals.
No dogs are cats.
Some dogs are beagles.
Some dogs are brown animals.
Some dogs are brown things.

Are all goldfish mammals?

I don't know anything about goldfish.

In the discussion of the Perl Quiz, some very interesting examples were posted.
Here's my favorite, which we'll call extra credit:

All dogs are mammals OK.
No octopuses are mammals OK.
Are any octopuses dogs?

I don't know.

That's not the correct answer. See how your engine answers that question.

 

[Pit Capitain]

This week's Ruby Quiz is to build an inference engine that is capable of
answering questions based on the provided truths.

...

Just out of curiosity, after entering

All Foos are Bars

OK.

what should be the response to

No Foos are Bars

If the answer is "OK." it would mean that the set of "Foos" is empty,
because no Foo can be a Bar and not be a Bar. Questions like

Are all Foos <whatever>?

should then be answered with Yes.

The other alternative would be to assume that when speaking of "Foos"
the set of "Foos" isn't empty and there exists at least one Foo?

Regards,
Pit

 

[James Edward Gray II]

Just out of curiosity, after entering

OK.

what should be the response to

Basically, whatever you are comfortable with.

If the answer is "OK." it would mean that the set of "Foos" is
empty, because no Foo can be a Bar and not be a Bar. Questions like


should then be answered with Yes.

This is the correct logical interpretations, but...

The other alternative would be to assume that when speaking of
"Foos" the set of "Foos" isn't empty and there exists at least one
Foo?

This makes more sense to me, so it's probably what I would choose.
Given that, I would likely just print an error message to the user,
in the example you give.

James Edward Gray II

 

[Joost Diepenmaat]

Just out of curiosity, after entering

OK.

what should be the response to


If the answer is "OK." it would mean that the set of "Foos" is empty,
because no Foo can be a Bar and not be a Bar. Questions like


should then be answered with Yes.

The other alternative would be to assume that when speaking of "Foos"
the set of "Foos" isn't empty and there exists at least one Foo?

I'd go with this last interpretation. I'm assuming the input is not
talking about abstract concepts, but about sets of "real, existing" things.

In the same vein:

All dogs are mammals.
All mammals are dogs.

Could be taken to mean that the set of dogs and the set of mammals are
equivalent (so, basically dogs == mammals) OR it could be taken to be
contradictory, if we assume a maximum amount of information conveyed by
the input (i.e. if all dogs are mammals then mammals is a larger set
than dogs and there are other mammals that are not dogs)

Going for the latter interpretation will probably simplify some inferences.

Joost.