All about flooble | fun stuff | Get a free chatterbox | Free JavaScript | Avatars    
perplexus dot info

Home > Paradoxes
Logical Limbo (Posted on 2002-08-12) Difficulty: 4 of 5
Prove that either

a) this problem is solvable

or

b) this problem is unsolvable

See The Solution Submitted by Cheradenine    
Rating: 3.2000 (15 votes)

Comments: ( Back to comment list | You must be logged in to post comments.)
Solution No Subject | Comment 16 of 33 |
There're are two ways to interpret the semantics of this problem.

1) "Prove that either a or b" = "Prove: (a OR b) is a tautology."

That case is extremely simple given b = NOT a, since (a OR NOT a) is a tautology.

2) "Prove that either a or b" = "(prove a) or (prove b)", that is, perform one of the two actions. In this case, performing either action is a solution to the problem.

Let's use a little propositional logic. Let the variables be as follows:

p = "a can be proven"
q = "b can be proven"
r = "the problem has a solution"

Given my understanding of the problem we begin with some hypotheses:

  (p OR q) <-> r
If we manage to prove either statement, then we have formed a solution to the problem; likewise, the existence of a solution means one of the the statements was proven.

  q <-> NOT r
If b can be proven (q is true), then the problem has no solution, since that is what b claims; likewise, if we come to know the falsity of statement r, b is proven.

We can then use the rules of inference. I've taken a couple of short cuts, such as:
  ((a OR b) -> c) -> (a -> c)
and
  ((a -> b) AND NOT b) -> NOT a
You can verify these rules for yourself if necessary.

1) (p OR q) <-> r, hypothesis
2) q <-> NOT r, hypothesis
3) (p OR q) -> r, from 1
4) q -> r, from 3
5) q -> NOT r, from 2
6) NOT q, from 4 and 5
7) NOT r -> q, from 2
8) NOT (NOT r), from 6 and 7
9) r, from 8

So we have proven "the problem has a solution" is a true statement, which is equivalent to saying "the problem is solvable".

So (a) is the answer in either case.

This should be solid unless I've either left out an interpretation, or my hypotheses in part 2 (steps 1 and 2 in the inference) were fallacious. Let me know if this is the case.
  Posted by Jacob Fugal on 2002-09-28 11:22:03
Please log in:
Login:
Password:
Remember me:
Sign up! | Forgot password


Search:
Search body:
Forums (0)
Newest Problems
Random Problem
FAQ | About This Site
Site Statistics
New Comments (8)
Unsolved Problems
Top Rated Problems
This month's top
Most Commented On

Chatterbox:
Copyright © 2002 - 2024 by Animus Pactum Consulting. All rights reserved. Privacy Information