wu :: forums (http://www.ocf.berkeley.edu/~wwu/cgi-bin/yabb/YaBB.cgi)
riddles >> hard >> Where Smullyan went wrong
(Message started by: Jonathan the Red on Aug 3rd, 2002, 9:20pm)

Title: Where Smullyan went wrong
Post by Jonathan the Red on Aug 3rd, 2002, 9:20pm
I first encountered the work of Raymond Smullyan when I was in sixth grade (which was more years ago than I like to remember) when I picked up, on a whim, a copy of What is the Name of This Book? in my local library. I was instantly hooked, and I've been a big fan of logic puzzles ever since.

In WitNoTB?, Smullyan introduces his Knights, Knaves, and Normals. Knights always tell the truth, Knaves always lie, and Normals can do either. He poses many puzzles that are set on islands populated by Knights, Knaves, and Normals, from the easy to the difficult to the sublime.

In the subchapter titled "How to Marry a King's Daughter", Smullyan tells the story of a king who wants his daughter to marry a nice normal Normal, not one of those goody-goody Knights or devious scoundrel Knaves. Smullyan asks:


  • How can you make a true statement that will convince the King you are a Normal?
  • How can you make a false statement that will convince the King you are a Normal?
  • How can you make a statement that will convince the King you are a Normal, but he won't know whether it's true or false?


These problems are not terribly difficult, and the solution is left as an exercise.

Then Smullyan tells the story of a different King, one who is not so kindly disposed towards Normals. In fact, he sees them as wishy-washy girly-men, unreliable and untrustworthy. A Knight will always be true, and a Knave is wholly reliable as long as you remember to believe the exact opposite of what he says, while a Normal will deceive you when you least expect it. He wants his daughter to marry anyone but a Normal. Smullyan asks: how many statements must you make to convince the King?

Smullyan's answer was: no statements you make can ever convince the King you are no Normal. Since a Normal can say anything, any statement you make could be made by a Normal. There is no way to prove your abnormality to the King.

Smullyan was wrong! There is a subtle flaw in his argument, and in fact it is quite possible for a non-Normal to prove it. So the puzzle for you is:


  • How can you, in one statement, convince the King you are a Knight?
  • How can you, in one statement, convince the King you are a Knave?
  • How can you, in one statement, convince the King you are not a Normal, but leave him unable to deduce whether you are a Knight or a Knave?

Title: Re: NEW PROBLEM: Where Smullyan went wrong
Post by Eric Yeh on Aug 3rd, 2002, 9:59pm
Jon,

Smullyan is a great guy, is he not??  My favorite of his was "This Book Needs No Title", which I have since been sad to discover is no longer in print.  Ah well, at least I have my original copy somewhere.

Hmm, I also seem to recall finding some errors in his books at some points, but I no longer remember where -- perhaps it was the same as the one you found.  In any case, I haven't had a chance to read your example very carefully yet, but will definitely do so tomorrow.

Goodnight for now!
Eric

Title: Re: NEW PROBLEM: Where Smullyan went wrong
Post by tim on Aug 4th, 2002, 12:06am
My first guess would be a variant on Epimenides' Paradox. After constructing suitable assertions, I find that it works. I won't spoil the fun too much by actually posting examples ;)

The flaw in Smullyan's reasoning is that by his conditions, Normals are not free to say anything they like. Their statements must be either true or false. That makes them unlike real people, and hence not really normal at all. ;)

Title: Re: NEW PROBLEM: Where Smullyan went wrong
Post by Eric Yeh on Aug 5th, 2002, 8:07pm
Yep, it took me a little while to dig up my copy of WitNoTB, but finding it (and the problem -- god, it's such a hidden chapter!!!) confirmed what I suspected before:  Smullyan really set himself up to be proven wrong on this one!!  If he just presented the "pf" in a section, we might have quickly read it and idly accepted it as the truth.  But instead he presents it as a problem, for which you have to flip several pages for the supposed solution.  Furthermore, it's the first in the section, which really makes one try hard to answer it!  So this is one reason why multiple people find the same error.

As far as the soln, I won't be as generous as Tim, partially bc Ollie is breathing down my neck to post more solns.  But I guess I will at least make it black "to prevent spoilage", as the author would say.  ;)

I don't know who Epimedides is and am too lazy to look it up, but I'll guess it's the same thing I want to use:  any contradiction such as C = "This statement is false."  If N = "I am a normal" then for a normal N=>C is a contradiction, so it cannot be said.  (I'm slightly abusing my notation and letting C control the entire statement.)  Since the statement is true otherwise (since the premise is false), only a Knight can make the statement.  That answers part 1.

Of course, an inversion should give you the opposite effect; the only caveat is that you actually then need to flip the inside to maintain the contradiction.  ~(N=>~C) (equivalently N*C) works for part 2.

Finally, you can throw in an extra clause to allow the randomness, e.g. (N=>C)*~Kv where Kv = "I am a knave".  This last term has the profile TTF for N/Kt/Kv, which is precisely what we need to multiply by.

Happy now Ollie?  ;)

Best,
Eric

Title: Re: NEW PROBLEM: Where Smullyan went wrong
Post by zarathustra on Sep 9th, 2002, 8:58am
Woh, where does it say that normals can't speak contradictions?  "Knights always tell the truth, Knaves always lie, and Normals can do either."  Word choice is important here as with any riddle and it says that Normals can tell the truth or lie, but not that they can only tell the truth or lie.  Also, If you think of a normal as a (somewhat) normal person like you or me, we would certainly be able to speak contradictions.  I agree with Smullyan on this one, clearly it is strongly implied that normals can make any statment, and therefore there is no possible answer.

Title: Re: NEW PROBLEM: Where Smullyan went wrong
Post by Eric Yeh on Sep 9th, 2002, 1:03pm
Zari,

To me, the statement "Knights always tell the truth, Knaves always lie, and Normals can do either" does contain the strong implication that "either" is all the Normals can do, i.e. that we have been given a complete specification.  If not, it is an unclear specification of how a Normal behaves, and that would be a problem.  For example, if he is allowed to do anything he wants (as a true "normal" person, per your writing), he could just remain silent when I ask him a question, or other strange things.  Supposing you are correct about his intention, I would claim it was poorly expressed in this case.

Eric

Title: Re: NEW PROBLEM: Where Smullyan went wrong
Post by Brett Danaher on Oct 4th, 2002, 8:45am
I'm sorry, I don't understand your notation c=>n, so I don't know what statement you mean.  Is it "I am a normal is a false statement"?

Because I do not see why a normal could not say that.  He would be lying, but he's allowed.  What does he say that causes a contradiction?

Title: Re: NEW PROBLEM: Where Smullyan went wrong
Post by James Fingas on Oct 4th, 2002, 10:03am
The notation A => B is short form for "A implies B", or "if A, then B". So Eric is saying:

A Normal would be making a contradiction if he were to say "If I am a Normal, then this statement is false".

Title: Re: NEW PROBLEM: Where Smullyan went wrong
Post by Eric Yeh on Oct 11th, 2002, 3:27pm
Oops, just saw this msg -- sorry Brett.  Yes, James' comment if correct.  P=>Q is F iff P is T and Q is F.  Hence can also be written as "~P or Q".

Best,
Eric

Title: Re: NEW PROBLEM: Where Smullyan went wrong
Post by Jonathan_the_Red on Oct 11th, 2002, 4:43pm
For what it's worth, my solutions to these were:


Knight: If I am normal, this sentence is false.
Knave: I am normal and this sentence is false.
Either: I am normal if and only if this sentence is false.


...which have a symmetry I quite like.

Title: Re: NEW PROBLEM: Where Smullyan went wrong
Post by Eric Yeh on Oct 11th, 2002, 6:23pm
Indeed, that's a nice symmetry  :)

Title: Re: NEW PROBLEM: Where Smullyan went wrong
Post by Jim Harvey on Apr 25th, 2005, 6:11am
Just because you put two statements in one sentence does not make it one statement. A normal, since he can lie, and he can tell the truth could say. I am normal. I am not a normal. Two statements, a contradiction, this does not prove that the one telling me is not a normal, only that he tells the truth, and then doesn't.

While it's true a knights COULD say that, it doesn't restrict the normal from making the statement. If you are normal, then the if statement is made true, so it would mean that "I am normal and this statement is false", these are just two separate statements and I don't see how a normal could not say this. I don't think this is a proper answer and I don't think that this puzzle should be posted on the site.

Title: Re: NEW PROBLEM: Where Smullyan went wrong
Post by rmsgrey on Apr 25th, 2005, 9:12am

on 04/25/05 at 06:11:09, Jim Harvey wrote:
Just because you put two statements in one sentence does not make it one statement. A normal, since he can lie, and he can tell the truth could say. I am normal. I am not a normal. Two statements, a contradiction, this does not prove that the one telling me is not a normal, only that he tells the truth, and then doesn't.

While it's true a knights COULD say that, it doesn't restrict the normal from making the statement. If you are normal, then the if statement is made true, so it would mean that "I am normal and this statement is false", these are just two separate statements and I don't see how a normal could not say this. I don't think this is a proper answer and I don't think that this puzzle should be posted on the site.

In Logic, it's generally accepted that you can form compound propositions out of simple propositions by using various logical connectives (And, Or, Iff, Implies, Not, Xor, etc...). If you don't allow the construction of compound propositions, instead insisting that all propositions must be simple, then things generally become rather confusing.

For example, "this statement is false" is usually treated as a compound proposition, made of "this statement", "is", and "false". If you require it to be treated as a simple proposition rather than a compound proposition, then it could be true or it could be false, depending on how you choose to assign truth to it. For it to be paradoxical, you need its truth value to be based on the meaning of its component parts.

The statements: "I am normal" and "I am not normal" stated by the same person in either order establish him as normal. The statement "I am normal and I am not normal" only establishes that the speaker is not a knight - the presence of an "and" in the statement merges the two statements into one compound statement whose overall truth is dependent on both the truth of the component statements, and the rules for joining statements with an "and".


The statement "If I am normal then this statement is false" is equivalent (accoridng to the normal rules for "if ... then ...") to "I am not normal or this statement is false". When spoken by a normal, this is equivalent to "{false} or this statement is false" which is equivalent to "this statement is false".

The question then is whether a "normal" can ever make the statement "this statement is false" - a statement which is neither true nor false. If every statement a "normal" makes has to be either true or false, then the puzzle in his thread is solvable. If a "normal" can say anything he likes regardless of whether it's true, false or paradoxical, then the puzzle is insoluble.

Title: Re: Where Smullyan went wrong
Post by Grimbal on Apr 27th, 2005, 8:05am
To prove he is a knight:
[hide]
"If I'm not lying, I am a Knight".
If he were lying, the premisce would not be met and the sentence would be true.  So, he is not lying, and therefore he is a Knight.

A nicer formulation is: "If I'm not mistaken, I am a Knight."
It only works if you understand "being mistaken" as applying to the "if ... then ... " sentence and not to "I am a knight".
[/hide]



Title: Re: Where Smullyan went wrong
Post by rmsgrey on Apr 28th, 2005, 10:05am
If I'm not lying, I'm a knave.

Title: Re: Where Smullyan went wrong
Post by Jim_Harvey on Apr 28th, 2005, 2:26pm
Actually, in logic, if an if statement is not satisfied, then it is true, so a knave could never state an if statement that wasn't true.

Title: Re: Where Smullyan went wrong
Post by rmsgrey on Apr 29th, 2005, 4:57am

on 04/28/05 at 14:26:14, Jim_Harvey wrote:
Actually, in logic, if an if statement is not satisfied, then it is true, so a knave could never state an if statement that wasn't true.

I was trying to provide a counter-argument to Grimbal's post without actually (re-)posting the argument.

If there is some entity that can say "If I'm not lying, I'm a knave", then Grimbal's post doesn't provide a proof.

Title: Re: Where Smullyan went wrong
Post by Three Hands on Apr 29th, 2005, 5:23am
There is some question as to whether the normal analysis for "if...then" statement (that it is only false when the antecedent is true and the consequent false) actually translates to "if...then" statements in a linguistic sense. Granted, it's the best version of a potential truth-table analysis we can have, but given that the defence of such an analysis is based in linguistic conventions, I would tend towards not really accepting that kind of analysis.

From the normal analysis of "if...then" statements, since the "If I'm not lying" part of the statement requires that the antecedent be true (as if it were false then the statement would be true, making the antecedent true), this forces the consequent to be true, and so a statement "If I'm not lying, then I'm a knave" could never logically be stated, since it creates a paradox. From an analysis which makes the truth value of "if...then" statements undetermined when the antecedent is false, then rmsgrey's statement  could be used, and Grimbal's would not prove that the person talking is a Knight. I suspect, however, that the normal analysis is what is intended for this puzzle, and so Grimbal's statement would prove that the individual is a Knight.

Title: Re: Where Smullyan went wrong
Post by Grimbal on Apr 29th, 2005, 6:15am
If you prefer, "If I'm not lying, I am a Knight" can be restated as  "I am lying or I am a Knight".  The analysis is simpler.  For anybody not a Knight, it is like saying "I am lying".

But of course, rmsgrey could also say "I am lying".  So it is no proof unless you accept there is some magic in that kingdom that makes it so that every sentence is either true or false, and that every Knight tells the truth however deep the consequences.  That magic doesn't apply to the forum, obviously.

Title: Re: Where Smullyan went wrong
Post by Deedlit on Apr 29th, 2005, 6:32am
Somehow I'm not following the latest objections.  Of course if someone is allowed to make contradictory statements, then all bets are off, but for someone who has to say something true or false, Grimbal's statement could only be made by a knight.  :-/

Title: Re: Where Smullyan went wrong
Post by Jim_Harvey on Apr 29th, 2005, 12:17pm
The only phrase in question is the phrase "I am lying", who could possibly say they are lying? It is an incomplete sentence, what are you lying about? If you said, I am hoping, is that a paradox? Just because you don't know what you're hoping for?

Arg1: Lish Mish Dish
Arg2: Arg1 is a lie

Arg3: Arg3 is a lie

Arg4: Arg5 is a lie
Arg5: _________

See, the only problem with Arg3 is that there is no argument whatsoever. To make the statement, "this statement is a lie," well, there is no statement made to make it a lie, it is the lack of an argument that makes it not a lie, and not a truth. Lish Mish Dish, is also not a lie, and it is not the truth, wouldn't you agree? Could a normal say Lish Mish Dish? It is neither true, nor false. So could you make a statement, "if I've lied before, lish mish dish" to prove that I'm a knight?

There is nothing saying that a Normal can say only truths and lies, it just states that he can say either, not only, so I think it is within the power of the Normal to say a senseless statement, even ones without an actual argument such as "this statement is a lie." This statement is really no different than Arg4, it is no paradox, only a senseless statement, and there is nothing saying a normal can't say senseless statements.

Title: Re: Where Smullyan went wrong
Post by Grimbal on May 5th, 2005, 8:08am
The original post asked to prove you are a Knight, a Liar (a Knave) or a Normal.  Here is the answer.  I put it in gif form because of the diagrams.

Title: Re: Where Smullyan went wrong
Post by FredFnord on May 29th, 2005, 11:23pm
There is another answer to the riddle as stated, even if you assume that normals can utter any sentence (sentence fragment, word, contradiction, truth, falsehood, meaningless sound, whatever) in existence.

At least, it answers the first and second questions.  I must admit, I'm at a loss for the third.

Anybody?

-fred

Title: Re: Where Smullyan went wrong
Post by Deedlit on May 30th, 2005, 1:13am
The same methods that convice the king you are not a knight and/or not a knave under the stricter definition of normal, will also convince him under the more inclusive definition.  The difference is the latter will allow a few more possibilies that a normal could say.

However, under the more inclusive definition of normal, it is impossible to ever convice the king that you are not a normal;  whatever set of responses you give, a normal could give the same set of responses.

Title: Re: Where Smullyan went wrong
Post by Ajax on May 30th, 2005, 2:15am
I don't think there is an answer for the second problem. A normal guy can say whatever he wants without wondering if he's lying, telling the truth or being paradoxical. It's not a case of black or white; it can be grey. A normal guy cannot be restricted from saying whatever a knight or a knave may say. After all, we wants to marry the princess and get the dowry; Why would he let anyone else get it?

Title: Re: Where Smullyan went wrong
Post by asterex on May 30th, 2005, 7:45am
What we really need is a new two-bit self-referential logic system. Not being a mathematician I don't know if anybody has invented such a creature, but it would have 4 values:
0=indeterminate
1=true
2=false
3=paradox
And it would have a consistent method for every situation where a part of the statement references the whole statement.  It would also have new rules and new logic gates to handle its increased flexibility, such as
If paradox then ... (how would that be evaluated? Always indeterminate? Always opposite the second value?)
or, in addition to a Not gate that converts true to false how about an "Opposite" gate that converts Paradox to Indeterminate or "Logical" and "Illogical" gates that convert Paradox to False and True and Indeterminate to True and False respectively.
Is there such a system? And to what extent could it be applied to linguistics or used to clearly express a Knight/Knave/Normal type of question?

Title: Re: Where Smullyan went wrong
Post by Three Hands on May 30th, 2005, 8:20am
There are some logicians who consider there to be truth value gaps - which sounds similar to the suggestion of "indeterminate/paradox", just as one category - which apply to statements which cannot be evaluated as either true or false, and simply denies that they have a truth value. This is also one of the proposed methods of getting around the statement "This sentence is not true." but possibly runs into the same kind of trouble as suggesting the sentence is "paradoxical" (often suggested as a third truth value in a trivalent system)

One of the main difficulties would be justifying why a sentence lacks a truth value, as this suggests some definition of truth and falsehood, which is notoriously difficult to do (there are, in fact, various logicians who do not believe that truth can be properly defined beyond Tarski's Semantic Theory, which requires at least 2 more limited languages than everyday language in order to work).

Still, I think systems similar to the one you propose exist, asterex, although bivalent systems tend to be more popular, since we've worked out more what the consequences of such a system are, and it helps enormously to say that if something is not false, it is true, and if something is not true, then it is false. That, and it seems to fit our everyday conception of truth much better.

Title: Re: Where Smullyan went wrong
Post by Icarus on May 30th, 2005, 8:29am
Logicians have studied a number of different logic systems, including ones fitting your description. The most successful alternative logic is Fuzzy Logic. In it, statements are assigned real numbers from 0 to 1 as truth values, with 0 being definitely false, and 1 being definitively true. Values between are considered partially true. Numerically, the logical operators are defined by:

NOT x = 1 - x
x AND y = min{x, y}
x OR y = max{x, y}

Fuzzy logic mostly gets its partial truth values by rules set up for a particular application, but when used to study self-referential statements, values can often be deduced. For instance, the liar's paradox "This statement is false" has a truth value of 1/2.

Title: Re: Where Smullyan went wrong
Post by FredFnord on May 30th, 2005, 10:44am
I don't think there is an answer for the second problem. A normal guy can say whatever he wants without wondering if he's lying, telling the truth or being paradoxical. It's not a case of black or white; it can be grey. A normal guy cannot be restricted from saying whatever a knight or a knave may say.

Absolutely true.

Note that I am answering this based on a strict semantic reading of the puzzle in at least two places.  It is highly likely that, after I give my answer, the puzzle will be changed to exclude it.  And it may well not be a solution in the original; I'm assuming that the wording there could be subtly different in any one of a number of ways to exclude this answer.

Hint: [hide]We know the answer can't be in what they can say.  Perhaps it has to do with what they are likely to say.[/hide]

In the following solution, I take knights as my example... everything of course also works for knaves, since the two are equivalent.

Solution:
Proposition 1:
[hide]The puzzle says 'Knights always tell the truth.'  It does not say 'Knights always tell what they believe to be the truth.'  If we open the door to false beliefs, then none of the solutions you guys have proposed can be acceptable, because if a normal mistakenly believes he is a knight, he will answer as a knight will answer.  (This doesn't make him a knight: beliefs can clearly change over time, so a week after his wedding he might change his mind.)  Nor does it say 'Knights will only say what they know to be true.'  This might work better, but it would leave knights practically speechless: he couldn't say 'I met the queen yesterday,' because there is a small but finite chance that the person he met was just pretending to be the queen (and the guards were complicit, etc.)  In fact, knights could ONLY speak in syllogisms, which is a pretty rough fate to sentence your daughter to, day in and day out.  ("IF I am not mistaken, THEN it is a lovely day out today.")[/hide]

[hide]So, everything a knight says is, ipso facto, truth, or they cannot utter it.  This gives the knight (and knave, and -- only if you believe the true/false dichotomy for normals -- even the normal, a very interesting property: they can determine the truth of a statement simply by uttering it. (Or, in the normal's case, by uttering it so that it is a contradiction if false.)[/hide]

[hide]Incidentally, I assume for the sake of simplicity and sanity that neither knaves nor knights can make certain statements regarding the future.  If we assume that the future is not predestined, then no statement about the future can be allowed that does not boil down to one of three things: probabilistic (there is a greater than 50% chance the sun will rise tomorrow morning), identity (if it rains tomorrow, it will rain tomorrow), or vacuously true (if one equals zero, tomorrow the princess will be carried off by a dragon).[/hide]

Proposition 2:
[hide]It does not say in the problem, 'How do you demonstrate with absolute certainty that there is no way you could be a normal.'  The problem states, 'How can you, in one statement, convince the King you are a Knight?'  Thus I judge that, if you make a statement that makes the likelihood of your being a normal sufficiently remote, the king is convinced.[/hide]

Solution:
[hide]Have the king put you in a private room, with no contact with anyone else possible.  Beforehand, give the king a bag of n dice.  The king retreats to another private room, and rolls the dice as many times as he likes, summing the numbers.  The king returns to your room, and you make your statement.[/hide]

[hide]While the king was gone, you were standing there trying to say 'The king is finished'.  When you were capable of saying it, you then started in with the 'The sum of the dice was greater than eight.  The sum of the dice was greater than sixteen.'  Etc.  With any luck, you know the number before the king returns to your room.  (Come to think of it, it would be prudent to also try saying to yourself 'The king correctly summed the dice', or use a slightly different wording than 'the sum of the dice') You say to the king, 'The number you are thinking of is 5,138.'  (Or whatever.)[/hide]

[hide]If I were the king, I'd be convinced.[/hide]

[hide]The same argument holds for the knave, inserting 'nots' where appropriate, but the normal, ASSUMING that he is in fact able to say anything he wants, has no such prophetic power.  He is highly unlikely to simply guess right.[/hide]

[hide]Incidentally, your private room is so that a normal can't just ask his knight/knave friend what the answer was, or have him signal it in some way.  The dice are to add an essential element of randomness: if the king were to simply pick a number, the normal could ask his knight friend beforehand, 'If the king were to pick a number right now, what number would he pick?' (thus avoiding asking future questions) or 'What number is the king most likely to pick?' (using a probabilistic approach to future questions) and certainly get an answer that is more likely than random guessing.[/hide]

[hide]Another solution: if the king is a knight (or has already identified a knight) it is even easier.  The petitioner approaches the king (alone in a room), the king snaps his fingers, and then asks, 'What was the exact time of day, down to hundredths of a second, that I just snapped my fingers?'  Then, the king (or his reference knight) repeats the answer; if he can, the petitioner is a knight.[/hide]

Wow, hidden text is ugly.

-fred

Title: Re: Where Smullyan went wrong
Post by asterex on May 30th, 2005, 11:18am
Obviously, I haven't thought this ought fully.  Fuzzy logic doesn't seem very helpful to our knights and knaves. If "This statement is false." =1/2, does that mean it's a half-truth, a paradox, or vague?
In its simplest form, I was just thinking of defining our characters more fully. (For example a Knight can speak only truth or vaguely/indeterminate. A Knave can speak only lies or paradoxes. How a normal speaks is the real key to a solution).
We would need to determine how to evaluate statements like, "This statement is vague." Let's say we consider T and F as constants, I (indeterminate) as a variable with more than one solution, and P (paradox) as a variable with no solutions.  Use S temporarily to refer to the statement. Then "This statement is a paradox," becomes S=P and you evaluate it by seeing if (S=P)=S. That's false because (F=P)=F (i.e., a false statement is not a paradox). But "This statement is vague." becomes (S=I)=S. Since I can be either T or F, (T=I) may be T or F and (F=I) may be F or P. So the statement is True. T and F would always take priority over I and P, in cases where a statement may be assigned a definite answer.
I or T=T.  I and T=I. I or F=I. I or I=I.  (In statements with more than one I you would have to distinguish whether they are the same I, so "I IFF (Not I)" would be F unless you have two different Indefinite conditions).
P and T=F.  P or T=T. P or P=F. P or I=I. P and I=F.
Not P=I.  (That says an answer is Not impossible, but it's unknown whether it's T or F).
Not I=P.  (That's because not indetermined means there is a definite answer, but since that answer could be either T or F, it's not determined. And Not I=I would be a paradox).
My question is, could this be expanded to evaluate all the other logical statements in a consistent way? What is the simplest example you can come up with where this system would break down?

Title: Re: Where Smullyan went wrong
Post by Deedlit on May 30th, 2005, 2:27pm
Another logic that I've seen has three possible values - true, false, and undetermined.  Basically you can think about it as having incomplete knowledge - in reality, everything will have a true or false value, but you don't know what they all are, so you put a question mark by some of them.  Fuzzy logic extends this concept, allowing for differing shades of true versus false.  Neither one is quite what you are looking for - there isn't two separate categories for indeterminate and contradictory.

Title: Re: Where Smullyan went wrong
Post by Icarus on May 31st, 2005, 3:34pm
The problem with trying to define such a 4-valued logic system is that you cannot always separate indeterminate and paradoxical statements. For example, consider the pair of statements:

The following statement is true.
The preceding statement is false.

Each statement is, by itself, indeterminate. It is only when they are considered together that they become a paradox. Which value do you assign them?

If we try to ignore such matters (for instance, consider each statement only as a separate entity), then we can define truth tables by:

(U = indeterminate; C = Contradictory):

 A   NOT A
---  -----
T     F
F     T
U     U
C     C

A    B   A OR B
---  ---  ------
T    T     T
T    F     T
T    U     T
T    C     C
F    F     F
F    U     U
F    C     C
U    U     U
U    C     C
C    C     C


But problems still arise when you try to combine statements. If I let A and B be the two statements above, considering them individually to be indeterminant, I find that A AND B is also indeterminant by the logic tables. But the actual meaning is contradictory.

And you cannot declare any statement that appears as an essential part of a contradictory group to be contradictory by itself, as every statement can be placed in a contradictory group, with other statements added that contradict it.

So essentially, you cannot have a single "contradictory" logic value.

Title: Re: Where Smullyan went wrong
Post by Deedlit on May 31st, 2005, 5:27pm
Just to quibble, we could consider T or C to just be T, since we don't need to worry about the second half when the first half is true.  In that case, it would be unclear what U or C should be.

Title: Re: Where Smullyan went wrong
Post by asterex on May 31st, 2005, 5:58pm
You're probably right (in fact, I'm pretty sure you are), but I'm not trying to devise an absolutely robust system here, just something that could help us with our knights, knaves and normals. And having some recognition of and a handle on contradictions and indeterminate statements is better than having the knight/knave universe crash and burn as soon as someone says "This statement is false."

In a 4-value system, we'd have to tweak the definition of the gates. I'd define OR as "Pick the preferred term, where T is better than U (possibly true) is better than F is better than C." Other definitions are possible.
By my definition, I'd change a few of the elements of your truth table.
NOT U is C
(NOT U means the answer is specified but it leaves the answer unspecified)
NOT C is U
(means there is an answer possible, but doesn't specify what it is)
T OR C = T
F OR C = F
U OR C = U

In evaluating
"The following statement is true. "
"The preceding statement is false. "
I'd encode them as
S2=T
S1=F
Find the truth by looking for a consistent answer to:
(S2=T)=S1
(S1=F)=S2
Solve by substition: either
((S1=F)=T)=S1
or
((S2=T)=F)=S2
Either equation lead to S = NOT S, a contradiction. Linguistically, it's the same as turning them into one sentence to evaluate. "The claim that this statement is true is false."
Either statement by itself is indeterminate. Together they are a contradiction. I don't see any more of a problem with that than saying
x>y
which does not have one specific answer, and
y>x
which is also unspecific. But put them together and you have an unsolvable equation, where when one is true the other is false, and vice versa.

"And you cannot declare any statement that appears as an essential part of a contradictory group to be contradictory by itself, as every statement can be placed in a contradictory group, with other statements added that contradict it. "

I would only focus on establishing a workable truth value for the statement as a whole. The parts, by themselves, don't need a specific value except as the merge into the overall truth. For example, "I am human or Martians are green." Since I really am human (trust me), I don't need to know anything at all about Martians to say that sentence is true.  The same would be true if the second term was vague or contradictory or changes as it's surroundings change. So parts don't need a definite and immutable value all by themselves to
achieve our goal of a single overall truth value.

Title: Re: Where Smullyan went wrong
Post by Icarus on May 31st, 2005, 6:50pm
I posted the tables as an example of an approach - not as a demand that this is how it has to be. However, if you deviate too far from the values I gave, then you are in fact deviating from the meanings we normally ascribe to these words. In particular:


on 05/31/05 at 17:58:45, asterex wrote:
By my definition, I'd change a few of the elements of your truth table.
NOT U is C
(NOT U means the answer is specified but it leaves the answer unspecified)
NOT C is U
(means there is an answer possible, but doesn't specify what it is)


You are confusing the concept of "NOT" here. NOT is an operator on statements that take statements to their opposite truth value. A truth value of U means that one lacks sufficient information to determine if the statement is true or false. If you cannot tell whether a statement is true or false, then you also cannot tell if its negation is true or false. So NOT U definitely has to be U, not C. A truth value of C means that you can show that for the statement to be true, it also must be false, and vice versa. If this is the case for some statement. Negating just flips this definition with its "vice versa" clause - which is the same thing. So the negation of a contradictory statement is also contradictory: NOT C = C.

As for robustness: any system has to be robust or else it is without value. As soon as you try to apply your non-robust system to the problem, I promise you the whole thing will collapse from its inconsistencies.

Title: Re: Where Smullyan went wrong
Post by asterex on May 31st, 2005, 7:07pm
I guess I see your point a little better than I did when I just wrote all that.  U is a variable which can represent either T, F, or C. As such, it has no single answer in the truth tables. A statement like
U AND U, seen in isolation would be U. But in practice, as in your example of "The following statement is true. The preceding statement is false," the merger of the two gives enough further data to make U AND U = C. In other cases, U AND U may be T or F. So in the truth tables, you have to treat U as if it's just shorthand for (T or F or C) , but in the sense of three equally likely possibilities, not in the mathematical sense where T or anything = T. Evaluate U, in any particular case, not as a truth value that can be looked up in the appropriate truth table to find the answer, but as a variable that must be reexamined whenever another equation tells you more about it's identity. But that negates the value of the simple truth table approach to logic. It might not be completely worthless, though.

Title: Re: Where Smullyan went wrong
Post by Icarus on May 31st, 2005, 8:30pm
Not quite - U can be treated as a simple truth value. A statement has truth value T if it can be proved from the axioms. A statement has truth value F if its negation can be proved from the axioms. A statement has truth value U if neither of the above hold. If you can prove by some means that a statement has truth value U and then later prove that it has truth value T, then your theory is inconsistent.

When deciding how U behaves in truth tables, I keep in mind its interpretation. But this is because I want the truth table to reflect the meaning I desire for U. It is the truth table that actually establishes what U means. But if I do not make it consistent with the meaning I intend, then I don't end up with an "undecidable" truth value, but something else. For example, if I define the truth tables:

     A |  T  |  F  |  U  |  C
NOT A |  F  |  T  |  C  |  U

 A    |  T  |  T  |  T  |  T  |  F  |  F  |  F  |  U  |  U  |  C
 B    |  T  |  F  |  U  |  C  |  F  |  U  |  C  |  U  |  C  |  C
A OR B |  T  |  T  |  T  |  T  |  F  |  U  |  F  |  U  |  U  |  C


Then, while I might have intended "undecidable" and "contradictory" for U and C, all I have really defined is U = "also true" and C = "also false", with the only difference being that T has priority over U and F has priority over C.

Title: Re: Where Smullyan went wrong
Post by asterex on Jun 1st, 2005, 12:22am
I should probably just drop this. It was just a crazy idea. And Inever studied logic, so I have no idea what I'm talking about. But one more try.   (I'll concede your point about NOT U is U and NOT C is C)


"If you can prove by some means that a statement has truth value U and then later prove that it has truth value T, then your theory is inconsistent. "
It's not inconsistent to say there's currently not enough information to decide, but later there might be.  The statement "The following statement is false." Is not inconsistent by itself, just incomplete. A normal truth table has no idea what to do with it. But it might when the following statement shows up.

Let's establish a consistent way to deal with U.
Imagine superimposed parallel universes. Wherever U comes up, imagine it's a T in one universe and an F in the other. If both resolve to the same definite answer, then that answer shows up, otherwise you get the U of overlapping differences. It makes U look like "also true" with the OR gate. But it makes U look like "also false" with the AND gate.
T AND U is U
F AND U is F
U AND U is U.

If T then U is U.
If F then U is T.
If U then T is T.
If U then F is U.

C is more difficult. While U requires superimposed universes. C requires superimposed time. It's only defined in self-referential (or indirectly self-referential) statements. Imagine every statement as a loop where the output is repeatedly fed back as input. If the output keeps switching between T and F, it's C. In your original truth table, a C anywhere always makes the whole statement C. But sometimes an internal C shouldn't cause any wavering of the whole statement's output.
T OR (S=F)= S
Try feeding in a T
T OR (T=F) = T.
No wavering
Try feeding in a F
T OR  (F=F) = ~F
Looks like a C but you then feed T back in and all the wavering stops. No C.
If you tried F OR C similarly you'd get
F OR (T=F) = F so you feed F back in to get
F OR (F=F) = T.
Okay, genuine contradiction. F OR C is C.

Now combining U's and C's.
U OR C:
In one universe it evaluates to T. In the other it evaluates to C. On second thought, I suppose I'd declare that a C.

U AND C
Let's try
T AND (S=F) = S
T AND (T=F) = F
T AND (F=F) = T
That's a contradiction.
F AND (T=F)=F
F AND (F=F)=F
That's a simple F evaluation.
I'd say U AND C evaluates the same as U OR C, a contradiction in one universe is a contradiction overall.

This whole thing may not follow all the same principles, rules, and procedures as a standard truth table, but I think it could be made consistent. And it's better than just throwing up your hands when faced with a contradiction or incomplete knowledge.

Title: Re: Where Smullyan went wrong
Post by towr on Jun 1st, 2005, 2:28am

on 06/01/05 at 00:22:00, asterex wrote:
"If you can prove by some means that a statement has truth value U and then later prove that it has truth value T, then your theory is inconsistent. "
It's not inconsistent to say there's currently not enough information to decide, but later there might be.
The problem here is that it means you're not really talking about the same statement. You have to take time in account
So you have statement(1, t1) and statement(1, t2), which aren't the same, even though for example  they are both "it's raining".
If you want to use knowledge updates you need to extend your language, for example use a temporal logic, or dynamic logic (or even a combination).


Quote:
The statement "The following statement is false." Is not inconsistent by itself, just incomplete.
Yes, there might not even be a following statement, which means it refers to something that doesn't exist.
I really have to wonder why we're trying to capture such sentences in a sort of extended propositional logic. I'd say you need at least first order (predicate) logic, and maybe even higher order logic.

Or lambda calculus.

"this sentence is false":
(\lambda X.not((X) (X))) (\lambda X.not(X X))
It doesn't reduce in itself, but you can use it without any problem in compound statements.

I suppose it doesn't immediatley help, but does give a proper formalism to at least describe what we're dealing with.

Title: Re: Where Smullyan went wrong
Post by asterex on Jun 1st, 2005, 5:53am
Okay, never mind.
I was just wondering if such a system might exist, and if it would bring any clarity to a Knights/Knaves world where anything is possible. Suppose Knights are allowed to be indeterminate and Knaves are allowed to be self-contradictory. Suppose I wanted to craft a riddle with another group of individuals, called Noodles, wishy-washy people who never say anything than can be nailed down, and a religious sect called the Nix who contradict everything, including themselves. It would be tough to ask them a yes or no question, but there might be a riddle in there somewhere about interpreting what they say. Only to do that, you'd need a consistent way of analyzing statements with multiple and interrelated contradictions and uncertainties, to see if any certainty and truth can be extracted.

Title: Re: Where Smullyan went wrong
Post by Icarus on Jun 1st, 2005, 3:51pm
Interesting possibilities there. Just because the concept of "contradictory" can't be clearly separated from "Indeterminate" as a logic value does not mean that your idea is not workable.

One possibility is to allow Nixes to give any individual answers, provided that the whole of their conversation is contradictory. (Should you attempt to leave before completion of the contradictory set, they will shout out the final statement before you go).



Powered by YaBB 1 Gold - SP 1.4!
Forum software copyright © 2000-2004 Yet another Bulletin Board