Math Is Fun Forum

shaoen01

Member

Registered: 2008-01-26

Posts: 18

Proof by using multiple theorems

Hi all,

I have the solution to this question, but i don't understand how it was derived. And i hope someone could further explain it to me. A lot of theorems have been used such as modus tollen, proof by contradiction, etc.

Qns:
Knights always tell the truth, knaves always lie.
Can we tell what A and B are, from what they say below?

A: B is a knight
B: A and I are of opposite type.

Let a = "A is a knight"
Let b = "B is a knight"

Solution:

   1. a
   2. therefore b -- A tells the truth
   3. therefore (a^~b) v (~a^b) -- B tells the truth (**)
   4. therefore a^~b -- elimination
   5. therefore ~b -- specialization
   6. therefore c (contradiction)
   7. therefore ~a -- by contradiction
   8. ~b -- A lies

The above argument tells us that if there is a solution, it must be that both A and B are knaves.

My question:
From (**) onwards, i start to not understand the solution. Firstly, how do we know which we should eliminate at 3? When specializing at 5, why can't we select "a" instead of "~b". Do i just select anyone? And how does it lead to "c" from "~b" at 5 to 6?

Thanks for your help in advance!

mathsyperson

Moderator

Registered: 2005-06-22

Posts: 4,900

Re: Proof by using multiple theorems

At 3, you have to eliminate (~a^b), because at 1 you already said a, and so ~a can't be true.

When you specialise at 5, there's nothing illegal about selecting a instead of ~b, but it won't help the argument at all, so you don't. This way, you get ~b here, which combines with the b you found at 2 to form a contradiction.

That shows that the assumption made at 1 must be false, and so you have ~a (and therefore ~b).

For some reason the solution stops there. It hasn't actually proven that they're both knaves (although it turns out they are), it's only proven that either they're both knaves or it's a paradoxical question.

---

Why did the vector cross the road?
It wanted to be normal.

shaoen01

Member

Registered: 2008-01-26

Posts: 18

Re: Proof by using multiple theorems

Wow, thanks your explanation has really helped me. So basically, when we are doing this kind of question i should find ways of contradicting the answer in some sense right? So that i can make further assumptions like the part on specialisation. At step 1, it is also possible for me to start with b instead a right?

JaneFairfax

Member

Registered: 2007-02-23

Posts: 6,868

Re: Proof by using multiple theorems

You can already get a contradiction at 4. That’s because if a and b are true, both (a^~b) and (~a^b) are both false; hence (a^~b)v(~a^b) is false. Therefore

   1. a – assumption
   2. therefore b – A tells the truth
   3. therefore (a^~b) v (~a^b) – B tells the truth
   4. therefore c
   5. therefore ~a – by contradiction
   6. therefore ~b – A lies

Last edited by JaneFairfax (2008-01-26 02:37:09)

shaoen01

Member

Registered: 2008-01-26

Posts: 18

Re: Proof by using multiple theorems

JaneFairfax: Thanks for showing me how to look at it from a different perspective.

JaneFairfax

Member

Registered: 2007-02-23

Posts: 6,868

Re: Proof by using multiple theorems

It’s not a different perspective. It’s still looking at the problem from tbe same point of view, only the list of deductions is not so long and wordy. Anyway, you’re welcome.

shaoen01

Member

Registered: 2008-01-26

Posts: 18

Re: Proof by using multiple theorems

JaneFairfax: I have one more question, i do understand step 1-4, but what i want to find out is why at step 5 do you put "~a" and not just put "~b"?

The definition of a contradiction rule: If you can show that the supposition that statement p is false leads logically to a contradiction, then you can conclude that p is true.

How do i apply the contradiction rule to derive the answer at step 5? I feel a little bit confused by the definition and unsure of how to apply it properly. Hopefully you can give me some insight, thanks.

Last edited by shaoen01 (2008-01-26 17:41:19)

phamthephong100

Member

Registered: 2007-10-13

Posts: 8

Re: Proof by using multiple theorems

I think the answer is quite simple
*If A lies => A is a knave =>b is a knight
*If A tells the truth =>A is a knight =>B is a knave
  a knave always lies ,B:"A and I are of opposite type." is a lie=> B is a knight ( impossible )
Conclusion: A is a knave and B is a knight

Do you think this is correct ? I can not tell you all the things that i'm thinking -- my English is not good

shaoen01

Member

Registered: 2008-01-26

Posts: 18

Re: Proof by using multiple theorems

I think the conclusion should be both are knaves because at step 6, there is a contradiction as shown below which proves that A is lying. So if A lies, then B is definitely not a knight.

   1. a
   2. therefore b -- A tells the truth
   3. therefore (a^~b) v (~a^b) -- B tells the truth (**)
   4. therefore a^~b -- elimination
   5. therefore ~b -- specialization
   6. therefore c (contradiction)
   7. therefore ~a -- by contradiction
   8. ~b -- A lies