[techtalk] This talk of N-ary trees and other things...

[Mary Gardiner]

On Fri, Mar 23, 2001 at 04:55:09PM -0800, Nancy Corbett wrote:
> One time someone told me to study Logic...but not just any logic, some
> specific type of logic.  I can no longer remember what it's called.  Maybe
> you know. I can see how it would help me to cover all my bases when
> writing programs.  It involves mapping out truth tables for problems like:
> 
> ---
> Knights and Knaves problem. 
> 
> Suppose you visit a strange island with three types of people. Knights,
> who always tell the truth, Knaves, who always lie and Normals who
> sometimes lie and sometimes tell the truth. It is also the custom that
> normals marry only normals, and knights marry only knaves. 
> You meet two couples, Mr. and Mrs. Smith and Mr. and Mrs. Brown. They tell
> you the following: 
> 
> Mr. Brown: Mr. Smith is a knight. 
> Mrs. Brown: My husband is right, Mr. Smith is  a knight. 
> Mrs. Smith: That?s true, my husband is indeed a knight. 
> 
> Can you determine which type each person must be? Explain.

OK here's my solution, which is a bit more logically explicit than
others, even though I didn't complete the process of deducing all the
conclusions from the premises (of which we have rather a lot) because it
always takes a long time and I've forgotten the names of the rules.

You can map out propositions from the question:
First, set up the propositions:
married(X,Y) means X is married to Y
knave(X) means X is a knave
knight(X) means X is a knight
normal(X) means X is a normal
says(X, stY) means that X says statement Y is true
stY means statement Y is true
!stY means statement Y is false

There are then implications ( => means implies):
married(X, Y) => married(Y, X) (not obvious, child(X, Y) doesn't imply
child(Y, X)!)
married(X, Y) and knight(X) => knave(Y)
married(X, Y) and knave(X) => knight(Y) (although David Merril doesn't
agree with this interpretation)
married(X, Y) and normal(X) => normal(Y)
says(X, stY) and knight(X) => stY
says(X, stY) and knave(X) => !stY

We then have facts:
married(Mr Brown, Mrs Brown)
married(Mr Smith, Mrs Smith)
says(Mr Brown, knight(Mr Smith))

I'm actually having trouble with the last two statements.
If Mrs Brown is lying when she says that "My husband is right, Mr. Smith
is  a knight" what is actually true - "My husband is wrong, Mr Smith is
knight", "My husband is wrong, Mr Smith is a knave"...

I'll make the simplest assumption, and everyone can laugh at me if I've
negated the sentence wrong or it's a trick question...

says(Mrs Brown, knight(Mr Smith))
says(Mrs Smith, knight(Mr Smith))

We need to keep in mind that the implication doesn't work backwards, ie
stY => says(X, stY) and knight(X) doesn't follow from says(X, stY) and
knight(X) => stY

However, if p => q, !q => !p

I won't derive everything properly because it's such a pain to write out
all the rules.

Now, there are three possibilities, knight(Mr Smith), normal(Mr Smith),
and knave(Mr Smith).

If knight(Mr Smith):
	knave(Mrs Smith)
	BUT Mrs Smith wouldn't then say truthfully Mr Smith is a knight,
	so Mr Smith can't be a knight

If normal(Mr Smith):
	Mrs Smith is a normal, which is consistant with her lying.
	
So normal(Mr Smith) (I sould have put in a rule about X having to be
something!)

normal(Mr Smith):
	normal(Mrs Smith)
	Now Mr Brown *and* Mrs Brown are lying too.

So everyone's a normal.

Is this actually right?

-- 
Mary Gardiner
<mary at puzzling.org>
GPG Key ID: 77625870