tag:blogger.com,1999:blog-67927106717334455932026-03-04T05:59:26.559-06:00Summer of GödelDavid Furcyhttp://www.blogger.com/profile/12284114397975852146noreply@blogger.comBlogger62125tag:blogger.com,1999:blog-6792710671733445593.post-14625559216567242222019-05-31T18:34:00.000-05:002019-05-31T18:34:40.061-05:00[Part 11] Raymond Smullyan's Certified Knights and Knaves puzzles A new puzzle
Here is a completely new puzzle that (as far as I know) isn't in any of Smullyan's or anybody else's books:
Every day on the island, I kept meeting natives and over time started to invent my own labels for them. For example, when two natives had a different type, i.e., knight versus knave, and a different certification status, i.e., certified versus uncertified (in any order), I thought ofDavid Furcyhttp://www.blogger.com/profile/12284114397975852146noreply@blogger.com0tag:blogger.com,1999:blog-6792710671733445593.post-28758511406740701962019-05-30T16:30:00.001-05:002019-05-30T16:30:42.974-05:00[Part 10] Raymond Smullyan's Certified Knights and Knaves puzzles Puzzle #6 - A new variant
Now that we have a JavaScript program to solve the following puzzle (see the last four posts):
On another particularly interesting occasion I came across two natives A and B each of whom made a statement such that I could infer that at least one of them must be an uncertified knight, but there was no way to tell which one it was. From neither statement alone could one have deduced this.
David Furcyhttp://www.blogger.com/profile/12284114397975852146noreply@blogger.com0tag:blogger.com,1999:blog-6792710671733445593.post-71892626209874025762019-05-29T17:15:00.001-05:002019-05-30T14:49:01.719-05:00[Part 9] Raymond Smullyan's Certified Knights and Knaves puzzles Puzzle #6 - (At least) nine distinct solutions
Recall our sixth puzzle:
On another particularly interesting occasion I came across two natives A and B each of whom made a statement such that I could infer that at least one of them must be an uncertified knight, but there was no way to tell which one it was. From neither statement alone could one have deduced this.
What two statements would work? [This problem is not easy!]
and the David Furcyhttp://www.blogger.com/profile/12284114397975852146noreply@blogger.com0tag:blogger.com,1999:blog-6792710671733445593.post-51599856557554114492019-05-28T22:32:00.002-05:002019-05-30T14:48:39.518-05:00[Part 8] Raymond Smullyan's Certified Knights and Knaves puzzles Puzzle #6 - Finding solutions using JavaScript
In the previous post, we discussed how to represent an entire column of a truth table as a single integer and how to perform Boolean operations on entire columns in JavaScript.
Here is the code that we wrote last time:
var A = parseInt("0000000011111111",2);
var Ac = parseInt("0000111100001111",2);
var B = parseInt("0011001100110011",2);
var Bc = parseInt("0101010101010101",David Furcyhttp://www.blogger.com/profile/12284114397975852146noreply@blogger.com0tag:blogger.com,1999:blog-6792710671733445593.post-43679077153265716862019-05-27T16:54:00.000-05:002019-05-30T14:48:09.199-05:00[Part 7] Raymond Smullyan's Certified Knights and Knaves puzzles Building truth tables in JavaScript
In the previous post, I promised to write a JavaScript program to find formulas that satisfy a given truth table.
Before we can write such a program, we need to understand how to build truth tables in JavaScript.
This post is thus devoted to a discussion of the tools that JavaScript (and similar programming languages) provides to manipulate truth tables and perform Boolean logic David Furcyhttp://www.blogger.com/profile/12284114397975852146noreply@blogger.com0tag:blogger.com,1999:blog-6792710671733445593.post-38814675198271477602019-05-26T17:11:00.000-05:002019-05-26T17:12:42.463-05:00[Part 6] Raymond Smullyan's Certified Knights and Knaves puzzles Puzzle #6 - Analysis
For our sixth puzzle, we will solve Problem 6 on page 42 of the 2013 Dover edition [ISBN: 978-0486497051] of Raymond Smullyan's 2013 book entitled "The Gödelian Puzzle Book - Puzzles, Paradoxes & Proofs", which reads:
On another particularly interesting occasion I came across two natives A and B each of whom made a statement such that I could infer that atDavid Furcyhttp://www.blogger.com/profile/12284114397975852146noreply@blogger.com0tag:blogger.com,1999:blog-6792710671733445593.post-40127963450250192402019-05-25T15:54:00.001-05:002019-05-25T15:54:40.164-05:00[Part 5] Raymond Smullyan's Certified Knights and Knaves puzzles Puzzle #5 - With two natives and a two-step solution
For our fifth puzzle, we will solve Problem 7 on page 42 of the 2013 Dover edition [ISBN: 978-0486497051] of Raymond Smullyan's 2013 book entitled "The Gödelian Puzzle Book - Puzzles, Paradoxes & Proofs".
[Note that we skipped Problem 5 in the book because it is very similar to the two previous problems in this series. We also skipped Problem 6 David Furcyhttp://www.blogger.com/profile/12284114397975852146noreply@blogger.com0tag:blogger.com,1999:blog-6792710671733445593.post-74930512240234456892019-05-23T13:10:00.000-05:002019-05-23T13:10:00.272-05:00[Part 4] Raymond Smullyan's Certified Knights and Knaves puzzles Puzzle #4 - Going backwards again
For our fourth puzzle, we will solve Problem 4 on pages 41-42 of the 2013 Dover edition [ISBN: 978-0486497051] of Raymond Smullyan's 2013 book entitled "The Gödelian Puzzle Book - Puzzles, Paradoxes & Proofs".
This puzzle reads:
I once came across a native who made a statement such that I could deduce that he must be certified (either a David Furcyhttp://www.blogger.com/profile/12284114397975852146noreply@blogger.com0tag:blogger.com,1999:blog-6792710671733445593.post-42940921125455921972019-05-22T21:20:00.001-05:002019-05-22T21:20:22.500-05:00[Part 3] Raymond Smullyan's Certified Knights and Knaves puzzles Puzzle #3 - Going backwards
For our third puzzle, we will solve Problem 3 on page 41 of the 2013 Dover edition [ISBN: 978-0486497051] of Raymond Smullyan's 2013 book entitled "The Gödelian Puzzle Book - Puzzles, Paradoxes & Proofs".
This puzzle reads:
I once came across a native who made a statement from which I could deduce that he must be a[n] uncertified knave. What David Furcyhttp://www.blogger.com/profile/12284114397975852146noreply@blogger.com0tag:blogger.com,1999:blog-6792710671733445593.post-74334993178408640512019-05-19T19:45:00.001-05:002019-05-19T22:49:35.296-05:00Summer of Gödel - Season 2 - What do you think?The first post on this blog was entitled "I just want to understand the proof of Gödel's incompleteness theorems". Sadly, this is a goal that I have yet to reach.
Six years ago, after many years of trying to understand the proofs of these two theorems, I found Peter Smith's book and decided to try to blog about it over one summer. Somehow, after covering the first 9 chapters (which make up less David Furcyhttp://www.blogger.com/profile/12284114397975852146noreply@blogger.com0tag:blogger.com,1999:blog-6792710671733445593.post-74903229319687235372019-05-14T20:29:00.000-05:002019-05-14T20:29:10.067-05:00[Part 2] Raymond Smullyan's Certified Knights and Knaves puzzles Puzzle #2
For our second puzzle, we will solve Problem 2 on page 41 of the 2013 Dover edition [ISBN: 978-0486497051] of Raymond Smullyan's 2013 book entitled "The Gödelian Puzzle Book - Puzzles, Paradoxes & Proofs".
This puzzle reads:
On another occasion I came across a native who said, "I am an uncertified knight." Is this the same situation as the lastDavid Furcyhttp://www.blogger.com/profile/12284114397975852146noreply@blogger.com0tag:blogger.com,1999:blog-6792710671733445593.post-83559348751629013502019-05-11T22:03:00.000-05:002019-05-11T22:03:03.477-05:00[Part 1] Raymond Smullyan's Certified Knights and Knaves puzzles Puzzle #1
In two earlier series, we had some fun with basic knights and knaves puzzles and then with knights, knaves, and normals puzzles.
In this series, we will solve puzzles from Chapter V of Raymond Smullyan's 2013 book entitled "The Gödelian Puzzle Book - Puzzles, Paradoxes & Proofs".
These puzzles take place on another island with only knights and knaves who have the David Furcyhttp://www.blogger.com/profile/12284114397975852146noreply@blogger.com0tag:blogger.com,1999:blog-6792710671733445593.post-7015874147643618622019-05-11T22:02:00.001-05:002019-06-02T22:21:28.510-05:00Table of contents for the series on Certified Knights and Knaves puzzles
Puzzle #1
In which we solve our first puzzle using three different formal approaches all based on propositional logic
Puzzle #2
In which we solve our second puzzle with a careful translation of negation in the puzzle statement
Puzzle #3 - Going backwards
In which we solve our third puzzle in the reverse direction
Puzzle #4 - Going backwards again
In which we solve our fourth puzzle David Furcyhttp://www.blogger.com/profile/12284114397975852146noreply@blogger.com0tag:blogger.com,1999:blog-6792710671733445593.post-91072524925505346402019-05-10T22:39:00.000-05:002019-05-10T22:39:22.993-05:00[Part 8] Raymond Smullyan's Knights, Knaves, and Normals puzzles Fourth puzzle, on the island of Bahava
For our fourth puzzle, we will use the \(46^{th}\) (and last) puzzle in Chapter 3 of Raymond Smullyan's 1978 book entitled "What Is the Name of This Book?: The Riddle of Dracula and Other Logical Puzzles". This puzzle takes place again on the island of Bahava, on which marriage is highly regulated. As stated on pages 25-26 of the 2011, paperback Dover Recreational David Furcyhttp://www.blogger.com/profile/12284114397975852146noreply@blogger.com0tag:blogger.com,1999:blog-6792710671733445593.post-44421359784081414852019-05-09T21:33:00.000-05:002019-05-09T21:33:30.769-05:00[Part 7] Raymond Smullyan's Knights, Knaves, and Normals puzzles Third puzzle, on the island of Bahava
For our third puzzle, we will use the \(44^{th}\) puzzle in Chapter 3 of Raymond Smullyan's 1978 book entitled "What Is the Name of This Book?: The Riddle of Dracula and Other Logical Puzzles". This puzzle takes place on the island of Bahava, on which marriage is highly regulated. As stated on pages 25-26 of the 2011, paperback Dover Recreational Math edition [ISBNDavid Furcyhttp://www.blogger.com/profile/12284114397975852146noreply@blogger.com0tag:blogger.com,1999:blog-6792710671733445593.post-49745510077134287642019-05-07T20:31:00.002-05:002019-05-07T20:31:25.411-05:00[Part 6] Raymond Smullyan's Knights, Knaves, and Normals puzzles Second puzzle, solved with Prover9
For our second example, we will use the \(40^{th}\) puzzle in Chapter 3 of Raymond Smullyan's 1978 book entitled "What Is the Name of This Book?: The Riddle of Dracula and Other Logical Puzzles". As stated on page 24 of the 2011, paperback Dover Recreational Math edition [ISBN: 9780486481982], the puzzle reads:
Here is an unusual one: Two people, A and B, David Furcyhttp://www.blogger.com/profile/12284114397975852146noreply@blogger.com0tag:blogger.com,1999:blog-6792710671733445593.post-46115210050026033132019-05-04T23:28:00.001-05:002019-05-04T23:32:57.451-05:00[Part 5] Raymond Smullyan's Knights, Knaves, and Normals puzzles First puzzle, solved with Prover9
In the previous post, we used Mace4 to solve the following puzzle:
We are given three people, A, B, C, one of whom is a knight, one a knave, and one normal (but not necessarily in that order). They make the following statements:
A: I am normal.
B: That is true.
C: I am not normal.
What are A, B, and C?
In this post, we use Prover9 to build a proof by contradiction of thisDavid Furcyhttp://www.blogger.com/profile/12284114397975852146noreply@blogger.com0tag:blogger.com,1999:blog-6792710671733445593.post-83631803685454225312019-05-01T21:59:00.000-05:002019-05-04T23:33:18.382-05:00[Part 4] Raymond Smullyan's Knights, Knaves, and Normals puzzles First puzzle, solved with Mace4
Being comfortable with predicate logic and our new representation principle, we are now ready to automate the solution of our first puzzle.
For our first example, we will use the \(39^{th}\) puzzle in Chapter 3 of Raymond Smullyan's 1978 book entitled "What Is the Name of This Book?: The Riddle of Dracula and Other Logical Puzzles". As stated on pages David Furcyhttp://www.blogger.com/profile/12284114397975852146noreply@blogger.com0tag:blogger.com,1999:blog-6792710671733445593.post-74319886159050183672019-04-30T19:13:00.003-05:002019-05-02T08:03:27.781-05:00[Part 3] Raymond Smullyan's Knights, Knaves, and Normals puzzles Representing statements made by islanders
Now that we understand the advantages of using predicates and quantifiers, we can represent the fact that each and every inhabitant of this island must have exactly one type using the following axioms:
\(∀x\ (Kni(x)\ |\ Kna(x)\ |\ Nor(x))\)
\(∀x\ (Kni(x) \rightarrow (-Kna(x)\ \&\ {-Nor(x)}))\)
\(∀x\ (Kna(x) \rightarrow (-Kni(x)\ \&\ {-Nor(x)}))\)
\(∀x\ (Nor(x) \rightarrow (David Furcyhttp://www.blogger.com/profile/12284114397975852146noreply@blogger.com0tag:blogger.com,1999:blog-6792710671733445593.post-68095877542223748592019-04-29T23:14:00.003-05:002019-04-29T23:14:39.080-05:00[Part 2] Raymond Smullyan's Knights, Knaves, and Normals puzzles Predicates and quantifiers to the rescue
In the previous post, we identified some limitations of propositional logic as a formal language for representing knights, knaves, and normals puzzles.
The main issue was that too many propositions were needed. For example, in the scheme we described, we used the propositions \(AKni\) and \(BNor\) to represent the facts that A is a knight and B is normal, respectively.
More David Furcyhttp://www.blogger.com/profile/12284114397975852146noreply@blogger.com0tag:blogger.com,1999:blog-6792710671733445593.post-90758536368272445972019-04-28T10:20:00.000-05:002019-05-28T17:34:59.771-05:00Table of contents for the series on Knights, Knaves, and Normals puzzles
Limitations of propositional logic
In which we discuss why propositional logic is far from ideal when it comes to represent these puzzles formally
Predicates and quantifiers to the rescue
In which we discuss how to use first-order predicate calculus to represent succinctly the type constraints on all inhabitants
Representing statements made by islanders
In which we discuss how to use David Furcyhttp://www.blogger.com/profile/12284114397975852146noreply@blogger.com0tag:blogger.com,1999:blog-6792710671733445593.post-84026425694753983932019-04-27T23:57:00.002-05:002019-04-28T10:20:31.345-05:00[Part 1] Raymond Smullyan's Knights, Knaves, and Normals puzzles Limitations of propositional logic
Raymond Smullyan introduced the Knights and Knaves puzzles in chapter 3 of his 1978 book entitled "What Is the Name of This Book?: The Riddle of Dracula and Other Logical Puzzles".
We discussed these puzzles at length in an earlier series.
In this series, we discuss the second kind of puzzle that Smullyan introduced later in that same chapter, called the "Knights, Knaves, and David Furcyhttp://www.blogger.com/profile/12284114397975852146noreply@blogger.com0tag:blogger.com,1999:blog-6792710671733445593.post-26366849088116649452019-04-23T00:02:00.000-05:002019-05-28T17:35:20.831-05:00Table of contents for the series of posts on Knights and Knaves puzzles
Review of propositional logic
In which we discuss propositional variables, logical connectives, and a couple of logical equivalences
Representation principle for Knights and Knaves puzzles
In which we discuss a general principle for representing, in propositional logic, statements made by the island's inhabitants
First example - Informal solution
In which we discuss a typical puzzle David Furcyhttp://www.blogger.com/profile/12284114397975852146noreply@blogger.com0tag:blogger.com,1999:blog-6792710671733445593.post-88313921543254581222019-04-22T00:30:00.002-05:002019-04-23T00:10:02.043-05:00[Part 16] A Propositional Logic approach to Raymond Smullyan's Knights and Knaves puzzles Creating our own puzzles
So far in this series, we have discussed how to solve Knights and Knaves puzzles both informally and (mostly) formally. We have illustrated a few types of formal proofs, such as direct proofs, proofs by contradiction, and proofs based on truth tables.
When using truth tables, we followed this process:
Represent the puzzle statement using a formula \(\varphi\) that is a conjunction David Furcyhttp://www.blogger.com/profile/12284114397975852146noreply@blogger.com0tag:blogger.com,1999:blog-6792710671733445593.post-3359142513119521312019-04-21T18:11:00.000-05:002019-04-23T00:09:52.847-05:00[Part 15] A Propositional Logic approach to Raymond Smullyan's Knights and Knaves puzzles Seventh example
In this post, we will solve our last example in this series. In this seventh Knights and Knaves puzzle, we must determine if the answers to two questions posed to two inhabitants are the same.
For our seventh example, we will use the twelfth puzzle in Chapter 3 (or the \(37^{th}\) puzzle overall) of Raymond Smullyan's 1978 book entitled "What Is the Name of This Book?: David Furcyhttp://www.blogger.com/profile/12284114397975852146noreply@blogger.com0